QuadTree: Out of Nodes! error when recreating my physics scene.

[bryanedds]

From a search of the repository, the error seems to be originating from -

uint32 QuadTree::AllocateNode(bool inIsChanged)
{
	uint32 index = mAllocator->ConstructObject(inIsChanged);
	if (index == Allocator::cInvalidObjectIndex)
	{
		Trace("QuadTree: Out of nodes!");
		std::abort();
	}
	return index;
}

I've stumbled upon this while editing a small scene in my editor. I've spent a bit of time trying to reproduce and I think I've figured out how to do so locally. But first, some preliminary necessary explanation about my specific case -

Mine is a functional game engine. So the way it does undo and redo is by restoring old snapshots of the world. To make this approach work with an imperative physics engine, I destroy and recreate the entire physics scene from the restored snapshot when an undo or redo happens. The trace occurs when this rebuilding happens.

I'm wondering if this is an error indicating some improper API usage on my end or if it indicates an internal Jolt physics engine code error. If it's a user error, could you provide some general advice on how to either avoid it or mitigate it in general?

[jrouwe]

A reason for running out of nodes is if you don't batch add bodies to the world (BodyInterface::AddBodiesPrepare/AddBodiesFinalize). It is ok to insert a few bodies through BodyInterface::AddBody but if you add 1000s of bodies (e.g. for the static world), they should really be batched. If not, you will be building a very inefficient broadphase tree and you could run out of nodes.

If you really can't batch add bodies, you could also call PhysicsSystem::OptimizeBroadPhase every X-th body you insert. X should be below 128 * 3. This will not be a very efficient solution.

The number of quad tree nodes scales with the inMaxBodies parameter you provide to PhysicsSystem::Init so a work around could be to increase the max number of bodies in your world.

[bryanedds]

Investigating now, but I can't quite make sense of the behavior in this specific case given your description on the API's intent. When I rebuild the scene, I first destroy all existing bodies in Jolt, the recreate them. The number of bodies I recreate is the same as there were before. I have about 800 bodies total each time when the scene is rebuilt. So I'm not sure how this could hit the limit you're describing. If I understand you correctly, if the user of Jolt were to add one body per frame then remove it the next frame, it seems it would still trigger this node exhaustion eventually, even if there's only ever a couple of bodies in the scene at a time. I tried triggering an OptimizeBroadPhase at each physics engine clear just to experiment, but the std::abort call persists. I'm presuming that I'm not understanding some detail?

Regardless, I'm continuing to experiment with your potential solutions.

[bryanedds]

Okay, I've added the following to the bottom of the body creation function -

        // HACK: optimize broad phase if we've taken in a lot of bodies. INEFFICIENT!
        physicsEngine.BodyCreationCount <- inc physicsEngine.BodyCreationCount
        if physicsEngine.BodyCreationCount = 128 * 3 then
            physicsEngine.PhysicsContext.OptimizeBroadPhase ()
            physicsEngine.BodyCreationCount <- 0

...and that does seem to silence the issue!

Maybe this answers my above question - basically, the issue could still occur since 800 bodies at a time is still greater than 128 * 3...? But I wonder, is the issue about the total number of bodies created and possibly destroyed, or is about the total number of existing bodies?

[jrouwe]

If I understand you correctly, if the user of Jolt were to add one body per frame then remove it the next frame, it seems it would still trigger this node exhaustion eventually

No, a call to PhysicsSystem::Update (even with delta time 0) will do maintenance on the tree so it will recycle unused nodes.

I tried triggering an OptimizeBroadPhase at each physics engine clear just to experiment, but the std::abort call persists. I'm presuming that I'm not understanding some detail?

OptimizeBroadPhase after clear should also recycle all nodes.

But I wonder, is the issue about the total number of bodies created and possibly destroyed, or is about the total number of existing bodies?

It's only about body creation. Every 3 bodies (or batches of bodies) you insert require a new node to be created. How it works is detailed in my GDC talk (link on the main page).

If you want to add 800 bodies, I would really implement some sort of batching. We activate a mode during loading that queues up any bodies that we want to add to the world, when loading is done we insert all of them as a single batch. This is implemented as a 'start batching' / 'end batching' call to switch in and out of that mode. The rest of the code just uses the regular 'add single body' call on our wrapper and doesn't know if this mode is active or not.

What is your 'max body count' you're passing to the Init function?

[bryanedds]

What is your 'max body count' you're passing to the Init function?

10,240 max bodies. I took the number from what seemed to be Jolt's canonical demo application. You can see other relevant numbers above as well below -

[<RequireQualifiedAccess>]
module Physics =

    let [<Uniform>] GravityDefault = Vector3 (0.0f, -9.80665f, 0.0f)
    let [<Uniform>] mutable AlwaysObserve = match ConfigurationManager.AppSettings.["AlwaysObserve"] with null -> true | observe -> scvalue observe
    let [<Literal>] BreakingPointDefault = 100000.0f
    let [<Literal>] CollisionWildcard = "*"
    let [<Uniform>] mutable Collision3dBodiesMax = match ConfigurationManager.AppSettings.["Collision3dBodiesMax"] with null -> 10240 | value -> scvalue value
    let [<Uniform>] mutable Collision3dBodyPairsMax = match ConfigurationManager.AppSettings.["Collision3dBodyPairsMax"] with null -> 65536 | value -> scvalue value
    let [<Uniform>] mutable Collision3dContactConstraintsMax = match ConfigurationManager.AppSettings.["Collision3dContactConstraintsMax"] with null -> 10240 | value -> scvalue value
    let [<Uniform>] mutable Collision3dSteps = match ConfigurationManager.AppSettings.["Collision3dSteps"] with null -> 1 | value -> scvalue value
    let [<Uniform>] mutable Collision3dThreads = match ConfigurationManager.AppSettings.["Collision3dThreads"] with null -> max 1 (Environment.ProcessorCount - 2) | value -> scvalue value
    let [<Uniform>] mutable Collision3dBarriersMax = match ConfigurationManager.AppSettings.["Collision3dBarriersMax"] with null -> max 1 (Environment.ProcessorCount - 2) | value -> scvalue value
    let [<Uniform>] mutable Collision3dJobsMax = match ConfigurationManager.AppSettings.["Collision3dJobsMax"] with null -> 128 | value -> scvalue value

Would it make sense in principle to, by default, use different constants than what I'm using here? The current number does seem too low to me as we're hoping to support modern mid-sized games. If I were to increase the number to, say, 100K, how much extra overhead will that force Jolt to internally utilize? It's hard to decide what these constants should be without knowing the costs associated with them. If I had to guess, the costs would be relatively marginal from our perspective considering scale of our target game size. But without hard info, it's always going to be a bit of a mystery (assuming we don't just dig into the code and find out for ourselves, ofc).

If you want to add 800 bodies, I would really implement some sort of batching. We activate a mode during loading that queues up any bodies that we want to add to the world, when loading is done we insert all of them as a single batch. This is implemented as a 'start batching' / 'end batching' call to switch in and out of that mode. The rest of the code just uses the regular 'add single body' call on our wrapper and doesn't know if this mode is active or not.

Aye aye. For us, 800 bodies is a small scene. Going to take some time to figure out how to create the cross-system coordination required to support the batched approach. For now, we just pushed the new hack since the engine is live and we definitely don't want the editor crashing on developers during undo / redo operations.

[bryanedds]

Closing this as a resolved.

For fun, here's a screenshot from our Jolt-based game engine that I captured just now -

Physics work great in every scene we've tried so far, including this one!

Cheers!

[jrouwe]

Looks nice!

10,240 max bodies.

10240 max bodies will give you 13654 quad tree nodes which means you should be able to add 40962 bodies before running out of nodes (minus some because it keeps 2 trees, but the 2nd tree will be an optimized one that uses a lot less nodes). So I don't see how you can run out of nodes with just 800 bodies unless you're adding/removing individual bodies every frame without ever calling PhysicsSystem::Update or PhysicsSystem::OptimizeBroadPhase.

If I were to increase the number to, say, 100K, how much extra overhead will that force Jolt to internally utilize?

Increasing the max number of bodies is not a very big deal, I did a very quick test and it seems to cost 3 MB to go from 10 to 100K (this is only the static bookkeeping, if you actually create 100K bodies then it will cost more). Increasing the max number of contacts is what costs a lot of memory as Jolt allocates for the max number of contacts at the beginning of the physics update so that constraints can be added lock free.

[bryanedds]

Thanks!

So if I were to lift the max bodies from 10k to 100k, what might be an appropriate default value for max body pairs and max contact constraints? I'm presuming these wouldn't be increased in direct proportion to the number of max bodies, right? Or would they?

As for creating this many bodies - it's in the nature of integrating an imperative subsystem like jolt with a functional game engine to recreate the entire imperative representation on every undo / redo. We don't currently track the differences and patch up only the needed changes (tho we could perhaps if we had the bandwidth to find and fix any subtle bugs that crawl out of that approach). Instead we currently just wipe the entire jolt physics sim and recreate everything from the functional representation (which has all the data needed to reconstruct it). It's a bit costly with bigger scene, but it's one of the things that enables undo and redo of live gameplay (rather than only working for individual editor operations). The ability to undo and redo gameplay is a great tool for troubleshooting, balancing, and testing new game mechanics. Coupled with the ability to reload game code on the fly, our approach is uniquely powerful, but can seemingly also be demanding enough to stress jolt in unique ways. We think developers should have an option to write games in a functional way with it unique affordances. And in release mode, the engine is configured to run in Imperative mode, which elides the cost of doing engine operations exclusively with more costly functional transformations.

So we're exercising Jolt in some potentially very interesting ways! So far, things have worked out great, too!

[jrouwe]

I'm presuming these wouldn't be increased in direct proportion to the number of max bodies, right?

No, for most games you wouldn't need to increase these values. But if you're making an engine then I would recommend exposing these properties to the user. If someone wants to simulate a gigantic pile of rigid bodies then they can increase the numbers.

we currently just wipe the entire jolt physics sim and recreate everything from the functional representation

I would recommend calling OptimizeBroadPhase after wiping the physics system to clean out the broad phase (possibly even 2x to completely wipe out state because it always tracks a previous and current tree). I think that should be enough to avoid the issue you're currently seeing.

[bryanedds]

Excellent, thank you! Another screen shot from today that you work helps make possible ❤

At first I didn't know if the Jolt character controller would be able to walk properly over the lumps and bump on the ground, but it actually works pretty well!

My highest regards!

• Bryan

[bryanedds]

I took a look at your related commit and do have a comment -

		// Calling PhysicsSystem::Update or PhysicsSystem::OptimizeBroadPhase will perform maintenance
		// on the tree and will make it efficient again. If you're not calling these functions and are adding a lot of bodies
		// you could still be running out of nodes because the tree is not being maintained. If your application is paused,
		// consider still calling PhysicsSystem::Update with a delta time of 0 to keep the tree in good shape.

When we're in the editor, the game is not advancing, and so we don't integrate the Jolt physics system. The biggest reason why is that we can't afford to have physics messages / events coming out of our physics subsystem as that could cause the state of the game to change while paused and editing in the editor. We could follow the advice of integrating jolt with 0 time if and only if it is guaranteed to produce no event-worthy physics information in the process. So while I'd like to follow said advice, I'm not sure if it would lead to no physics events produced while paused in the editor and moving bodes around via edit operations.

Would you be able to provide some clarification in this regard?

[jrouwe]

So while I'd like to follow said advice, I'm not sure if it would lead to know physics events produced while paused in the editor and moving bodes around via edit operations.

An Update with a delta time of 0 should not produce any events. While typing this I quickly checked the code and saw that that code is buggy and was calling contact remove callbacks for all contacts in that case. That is fixed in #1525.