Configuring fidelity of contacts

[mihe]

This might be a dumb idea, but I'm curious to hear your take on it.

From what I understand, based on previous conversations and passing mentions, part of the reason for the performance caveat with mCollideKinematicVsNonDynamic is the fact that Jolt collects and maintains all of the contacts of these kinds of collisions in its contact cache, which becomes problematic when overlapping potentially intricate shapes, like MeshShape.

However, the recently added ClosestHitPerBodyCollisionCollector got me thinking. Would it be possible to control the underlying collector used during collision detection for bodies, so that you could then effectively control the fidelity of the contacts stored?

I imagine you'd be able to choose different levels of fidelity, such as:

1. All contacts with all sub-shapes
2. Only one (closest) contact per sub-shape
3. Only one (first) contact per sub-shape
4. Only one (closest) contact per body
5. Only one (first) contact per body

You might think of better levels, but hopefully you get my point.

Now, from what I understand, manifolds exist in the context of a pair, so I imagine there would have to be some kind of "smallest common denominator" when picking the collector. Perhaps this is fundamentally problematic for some reason.

I should also say that my comprehension of sub-shapes is a bit murky right now. So, just to be clear, when I say "one contact per sub-shape" I generally mean JPH::Shape, i.e. sub-shapes in a compound shape, but not individual triangles of a MeshShape. Maybe that's a problematic distinction, I'm not sure.

My reason for asking is that I've been seeing a worrying amount of projects seemingly just blindly enabling the "Areas Detect Static Bodies" project setting (which enables mCollideKinematicVsNonDynamic for sensors) in both the Godot extension and the new Godot module, ever since it was first introduced. I fear that it's become this magic checkbox that gets passed around as "you just need to enable this for things to work", without stopping to ask why they need it in the first place, or what the implications of it are.

There are several other problems at play here as well, of course:

1. People tend to rely on Area3D in Godot quite heavily for stuff that you traditionally could/should use plain shape queries for.
2. People sometimes rely on StaticBody3D for stuff that you could also use a kinematic body for.
3. The notion of kinematic bodies is somewhat poorly exposed in Godot at the moment.
4. This setting being global is pretty bad (and is something I will try to address for Godot 4.5).
5. It wasn't possible to provide in-editor documentation (i.e. have a tooltip) for the project setting in the extension.
6. Some (many?) people presumably don't stop to actually hover the project settings to find out what they're enabling anyway.

So this is arguably a communication problem to a large degree, but even if we were to put a scary popup whenever you enable the project setting you're likely going to have a certain amount of people who click right past it, find that their project still runs fine (in that moment) and then find themselves in trouble later down the line, without understanding the correlation.

Anyway, I figured since Area3D in Godot doesn't actually need all the contacts that make intersections with MeshShape problematic, nor does it care about where a contact is, since it just needs to know that two shapes overlapped at all, maybe we could just pick a simpler collector and negate some (much?) of the performance impact? Perhaps even to such a degree that we could just remove the setting completely and have it always be enabled?

I guess there's also the "last resort" to consider, which we've talked about once before, where we just ditch sensors altogether and re-implement Area3D to be a bunch of narrow phase queries, similar to how it was done for Bullet in Godot 3, but from what I understand we'd end up losing some of the parallelism we get to enjoy by using sensors. Frankly, I couldn't even begin to reason about the effective performance differences between the two methods, without actually trying it first.

[jrouwe]

Would it be possible to control the underlying collector used during collision detection for bodies, so that you could then effectively control the fidelity of the contacts stored?

It is possible to have some quality level, but I think there are some caveats:

• For simulated bodies, I don't think any other setting that the current setting makes sense: You want to collect all contacts in order to handle collisions properly. Otherwise you'd e.g. get a long box resting on a dense mesh alternating between finding contacts on one side and then the next step on the other side.
• For sensors, we could add an early out as soon as a hit/the closest hit is found. The problem here is that the touching/closest sub shapes can be different from frame to frame (SubShapeIDs will vary from frame to frame). This means you'll get an OnContactRemoved for one SubShapeID and an OnContactAdded for another and you would have to suppress sending these to godot if they relate to what you consider the same 'shape'. Maybe this is not a problem, but something to be aware of.

So, just to be clear, when I say "one contact per sub-shape" I generally mean JPH::Shape, i.e. sub-shapes in a compound shape, but not individual triangles of a MeshShape. Maybe that's a problematic distinction, I'm not sure.

Yes, that is another complication. Currently the collector only gets information when starting/finishing a new body (CollisionCollector::OnBody/OnBodyEnd), not when starting on a new sub shape. Adding this is possible, but would add yet another virtual call in the inner(-ish) loop. Not only would we need an OnSubShape, but we would also need an OnSubShapeEnd:

• OnSubShape stores early out fraction (on a stack, because we can have multiple levels)
• AddHit will update the early out fraction so that we immediately abort (in case we want the first hit) or set it to the value of the hit (in case we want the closest hit, in this case we would also need to buffer the hit so that we don't return non-closest hits to the simulation)
• OnSubShapeEnd would restore the early out fraction so that the parent shape will continue searching instead of earlying out.

Technically we have ShapeFilter that notifies us when we're entering a sub shape. This could be abused instead of having a OnSubShape call, but we can't get around the OnSubShapeEnd call as otherwise we'd have no way to restore the early out fraction.

Another thing that I can think of is to have a completely seperate code path for sensors in PhysicsSystem::ProcessBodyPair which would call Shape::CollectTransformedShapes to collect all leaf shapes for both bodies and then collides all permutations with a closest/first hit collector per permutation. This also has some downsides as you'll lose some of the benefits of the tree structure in the compound shape.

I guess there's also the "last resort" to consider, which we've talked about once before, where we just ditch sensors altogether and re-implement Area3D to be a bunch of narrow phase queries

Obviously I'd prefer it when Sensors keep getting used. The 'parallelism' you'd lose is easy to implement: Jolt basically does 'parallel for each sensor do NarrowPhaseQuery::CollideShape'. The advantage that Jolt has internally is that it does it together with all other collision checks so there's a pretty good chance that all threads will be occupied with work. You would need to run it outside of the PhysicsSystem::Update call which would mean another sync point and a chance that not all threads have work to do.

[mihe]

For simulated bodies, I don't think any other setting that the current setting makes sense: You want to collect all contacts in order to handle collisions properly.

Yes, definitely. I'm purely talking from the perspective of sensors, so kinematic and (?) static bodies I guess. We obviously have the "Generate All Kinematic Contacts" project setting in Godot as well, which enables mCollideKinematicVsNonDynamic for any RigidBody3D frozen with FREEZE_MODE_KINEMATIC, but I would be wary about culling contacts for that use-case, so that should probably remain an opt-in setting I guess. Although it definitely needs to be a per-body property instead of a global setting, same as the Area3D setting.

For sensors, we could add an early out as soon as a hit/the closest hit is found. The problem here is that the touching/closest sub shapes can be different from frame to frame (SubShapeIDs will vary from frame to frame). This means you'll get an OnContactRemoved for one SubShapeID and an OnContactAdded for another and you would have to suppress sending these to godot if they relate to what you consider the same 'shape'. Maybe this is not a problem, but something to be aware of.

I think that this is easy to cater to on the Godot side of things without changing much. We would just need to flush the AREA_BODY_ADDED events before the AREA_BODY_REMOVED events, thereby bumping the counter for that particular shape overlap on the scene side of Area3D, preventing the remove (and subsequent add) signal from firing. Currently the flushing happens the other way around, which I'm pretty sure was just an arbitrary (and in hindsight maybe not the most correct) choice on my part.

Another thing that I can think of is to have a completely seperate code path for sensors in PhysicsSystem::ProcessBodyPair which would call Shape::CollectTransformedShapes to collect all leaf shapes for both bodies and then collides all permutations with a closest/first hit collector per permutation. This also has some downsides as you'll lose some of the benefits of the tree structure in the compound shape.

Are you referring to the potential compound shape of the sensor, or of the body it's colliding with?

The advantage that Jolt has internally is that it does it together with all other collision checks so there's a pretty good chance that all threads will be occupied with work. You would need to run it outside of the PhysicsSystem::Update call which would mean another sync point and a chance that not all threads have work to do.

Yes, exactly.

[jrouwe]

Are you referring to the potential compound shape of the sensor, or of the body it's colliding with?

Both could be compounds. So you would end up doing a cartesian product of every shape in the sensor against every shape in the colliding body.

[jrouwe]

I have been thinking about how we'd go about implementing this and I think the extra code path in PhysicsSystem::ProcessBodyPair is the way to go, basically this line (and its sister line in the 'use manifold reduction' case):

JoltPhysics/Jolt/Physics/PhysicsSystem.cpp

Line 1242 in 5220a7f

auto f = enhanced_active_edges? InternalEdgeRemovingCollector::sCollideShapeVsShape : CollisionDispatch::sCollideShapeVsShape;

will have an extra condition to select a 3rd collision function.

I was thinking of the following options:

1. I introduce a new overriable callback on PhysicsSystem which has the signature of CollisionDispatch::sCollideShapeVsShape replacing shape 1 & 2 by body 1 & 2. The body would get a new flag called something like 'custom collision callback' which, when set, would call the callback instead of the line above. This would allow you to implement all of the fidelity levels above and you can inspect the bodies / store some data on the mUserData field of the body to select which one you need. I could provide some helper functions to implement the different fidelity levels.
2. I implement the 5 fidelity levels above, adding a new flag on BodyCreationSettings and Body to select the one you want. I'll call it something like ESensorQuality to make it clear that it's only used for sensors. I don't know if all 5 modes end up getting used. My gut feel is that in most cases you're only interested in if there is an overlap, not where, so option 5 seems like the most common mode. Obviously godot requires mode 3, so that will need to be implemented too.

What do you think? I think I'm leaning towards 1 since it allows people to completely bypass the collision detection system and implement whatever they want. The API is a bit more complex to grasp though.

Note that for sensor vs soft body we're tracking only 1 contact per body so I don't think anything is needed there.
Note also that this only works for the motion type Discrete case, LinearCast calls TransformedShape::CastShape but doesn't work for sensors anyway.

[mihe]

and its sister line in the 'use manifold reduction' case

Perhaps this makes more sense with your first option, but I assume that manifold reduction wouldn't be applicable for anything but the "all contacts with all sub-shapes" fidelity level if you went with the second option anyway?

The body would get a new flag called something like 'custom collision callback' which, when set, would call the callback instead of the line above. This would allow you to implement all of the fidelity levels above and you can inspect the bodies / store some data on the mUserData field of the body to select which one you need. I could provide some helper functions to implement the different fidelity levels.

Would this then technically be applicable to dynamic bodies as well? If so, wouldn't that require that you expose ContactConstraintManager to the public interface?

I implement the 5 fidelity levels above, adding a new flag on BodyCreationSettings and Body to select the one you want. I'll call it something like ESensorQuality to make it clear that it's only used for sensors.

Would ContactSettings::mIsSensor (and I guess ContactSettings::mInv*Scale) throw a wrench into this option in any way? Is there a reasonable use-case for dynamic bodies to want to control their fidelity as well, assuming of course that they have no collision response (by messing with ContactSettings)?

What do you think? I think I'm leaning towards 1 since it allows people to completely bypass the collision detection system and implement whatever they want. The API is a bit more complex to grasp though.

Somewhat selfishly I would of course prefer less complexity on the user side of things, so would prefer the second option from that standpoint, but I can certainly see the appeal of the first option from an API design standpoint.

I guess it depends on how much the helper functions help reduce the complexity, but in the end I would be grateful for the ability to achieve this at all, with either option.

Note that for sensor vs soft body we're tracking only 1 contact per body so I don't think anything is needed there.

Makes sense. That reminds me, I still need to sit down and finish up the stuff you started for the Godot side of this. It sort of fell by the wayside in the rush to get the engine module done.

Note also that this only works for the motion type Discrete case, LinearCast calls TransformedShape::CastShape but doesn't work for sensors anyway.

Makes sense.

[jrouwe]

Perhaps this makes more sense with your first option, but I assume that manifold reduction wouldn't be applicable for anything but the "all contacts with all sub-shapes" fidelity level if you went with the second option anyway?

This is mostly for completeness in case someone wants to completely override the collision results for dynamic objects for some reason.

Would this then technically be applicable to dynamic bodies as well? If so, wouldn't that require that you expose ContactConstraintManager to the public interface?

Yes it would be suitable for dynamic objects. And no I don't need to expose the ContactConstraintManager as all the collide function would do is call AddHit on the collision collector with a valid CollideShapeResult and then Jolt would proceed to create the actual contacts.

[jrouwe]

WIP: https://github.com/jrouwe/JoltPhysics/tree/feature/sim_collide_shape

(still need to provide an example and the collide function)

[mihe]

So I assume that if you wanted to implement something like the "Only one (closest) contact per body" fidelity level, you could make a custom collector very similar to ClosestHitPerBodyCollisionCollector, but instead of adding to mHits you'd defer to some inner collector's AddHit that points to whatever collector was passed into mSimCollideShapeVsShape, and then you'd just call sDefaultSimCollideShapeVsShape with this "wrapper" collector?

(or I guess you can also just reimplement sDefaultSimCollideShapeVsShape instead of deferring to it)

[jrouwe]

Yes, that's more or less the idea. I'm working on the demo, it'll be ready in a couple of days.

[jrouwe]

I have something working in #1489

2025-01-31.17-07-28.mp4

It's a big sensor box. The scene toggles through all 5 modes that you mentioned above. You should mostly ignore the dynamic bodies, they're there to show that they're not affected by this change. Focus on the green triangles + yellow arrows on the floor that indicate collision. Each 'pyramid' is a sub shape of a compound shape.

The collide function itself is quite simple at the moment:

template <class LeafCollector>
static void sCollideBodyVsBodyPerLeaf(const Body &inBody1, const Body &inBody2, Mat44Arg inCenterOfMassTransform1, Mat44Arg inCenterOfMassTransform2, CollideShapeSettings &ioCollideShapeSettings, CollideShapeCollector &ioCollector, const ShapeFilter &inShapeFilter)
{
	if (inBody1.IsSensor() || inBody2.IsSensor())
	{
		// Tracks information we need about a leaf shape
		struct LeafShape
		{
			...

			AABox			mBounds;
			Mat44			mCenterOfMassTransform;
			Vec3			mScale;
			const Shape *		mShape;
			SubShapeIDCreator	mSubShapeIDCreator;
		};

		// A collector that stores the information we need from a leaf shape in an array that is usually on the stack but can fall back to the heap if needed
		class MyCollector : public TransformedShapeCollector
		{
		public:
			void			AddHit(const TransformedShape &inShape) override
			{
				mHits.emplace_back(inShape.GetWorldSpaceBounds(), inShape.GetCenterOfMassTransform().ToMat44(), inShape.GetShapeScale(), inShape.mShape, inShape.mSubShapeIDCreator);
			}

			Array<LeafShape, STLLocalAllocator<LeafShape, 32>> mHits;
		};

		// Get bounds of both shapes
		AABox bounds1 = inBody1.GetShape()->GetWorldSpaceBounds(inCenterOfMassTransform1, Vec3::sOne());
		AABox bounds2 = inBody2.GetShape()->GetWorldSpaceBounds(inCenterOfMassTransform2, Vec3::sOne());

		// Get leaf shapes that overlap with the bounds of the other shape
		SubShapeIDCreator part1, part2;
		MyCollector leaf_shapes1, leaf_shapes2;
		inBody1.GetShape()->CollectTransformedShapes(bounds2, inCenterOfMassTransform1.GetTranslation(), inCenterOfMassTransform1.GetQuaternion(), Vec3::sOne(), part1, leaf_shapes1, inShapeFilter);
		inBody2.GetShape()->CollectTransformedShapes(bounds1, inCenterOfMassTransform2.GetTranslation(), inCenterOfMassTransform2.GetQuaternion(), Vec3::sOne(), part2, leaf_shapes2, inShapeFilter);

		// Now test each leaf shape against each other leaf
		for (const LeafShape &leaf1 : leaf_shapes1.mHits)
			for (const LeafShape &leaf2 : leaf_shapes2.mHits)
				if (leaf1.mBounds.Overlaps(leaf2.mBounds))
				{
					LeafCollector collector;
					CollisionDispatch::sCollideShapeVsShape(leaf1.mShape, leaf2.mShape, leaf1.mScale, leaf2.mScale, leaf1.mCenterOfMassTransform, leaf2.mCenterOfMassTransform, leaf1.mSubShapeIDCreator, leaf2.mSubShapeIDCreator, ioCollideShapeSettings, collector);
					if (collector.HadHit())
						ioCollector.AddHit(collector.mHit);
				}
	}
	else
	{
		// If not a sensor: fall back to the default
		PhysicsSystem::sDefaultSimCollideBodyVsBody(inBody1, inBody2, inCenterOfMassTransform1, inCenterOfMassTransform2, ioCollideShapeSettings, ioCollector, inShapeFilter);
	}
}

It is not the most efficient implementation possible at the moment:
* It is using the AllHitCollisionCollector which does a memory allocation that you really shouldn't be doing during the simulation
* If both bodies are compound shapes it gathers all shapes from body 1 using the bounding box of body 2 and vice versa. This could be made a bit more fine grained as it will potentially test sub shapes whose bounding boxes are not overlapping. It would need some profiling but I suspect that getting the bounds of each sub shape while collecting the shapes and checking these boxes for overlap should improve performance.

Edit: I've updated the code to implement what I suggested earlier.

I'm not sure if it makes sense for me to move this function into Jolt itself as it's not that big and quite custom for what we're trying to achieve here.

[jrouwe]

Edit 2: I've just merged the PR. I might move that function into Jolt later in order to make a unit test out of this.

[mihe]

Great, thank you so much! That does looks pretty clean, all things considered.

The potential memory allocation (even with STLLocalAllocator) is a little bit concerning. I imagine there's probably a few projects out there that stick a few hundred shapes in a StaticBody3D and wrap an Area3D around the entire thing, but perhaps that would have incurred similar overhead with some other approach as well.

It might be a little while before I get around to implementing this, but I'm excited to try and remove that project setting.

[jrouwe]

If the sensors are static, I think it's actually quite ok. You'll get a memory allocation on the first simulation step, but afterwards it will just reuse the contact cache and never call sCollideBodyVsBodyPerLeaf again. If the sensor is moving, then yes, you'll get a malloc every time step. If there are multiple sensors, you'll potentially get concurrent mallocs and those tend to create a lot of contention on the memory mutex. You can remove the mallocs by doing something like:

class MyCollector1 : public TransformedShapeCollector
{
	void AddHit(...)
	{
		MyCollector2 collector2;
		shape2->CollectTransformedShapes(...., collector2)
	}
}

class MyCollector2 : public TransformedShapeCollector
{
	void AddHit(...)
	{
		LeafCollector collector;
		CollisionDispatch::sCollideShapeVsShape(...)
		if (collector.HadHit())
			ioCollector.AddHit(collector.mHit);		
	}
}

MyCollector1 collector1;
shape1->CollectTransformedShapes(..., collector1);

But that does come at a cost of executing CollectTransformedShapes on shape 2 for every leaf shape in shape 1.

[mihe]

If the sensors are static, I think it's actually quite ok. You'll get a memory allocation on the first simulation step, but afterwards it will just reuse the contact cache and never call sCollideBodyVsBodyPerLeaf again.

Oh right. For some reason I got the idea that this new callback circumvented the contact cache, but that doesn't make much sense.

But that does come at a cost of executing CollectTransformedShapes on shape 2 for every leaf shape in shape 1.

I do wonder if maybe this is worthwhile anyway. I honestly can't remember seeing a single use of a compound Area3D in all the projects I've looked at. That is heavily biased towards small repro projects though, but still.

I would imagine that might create a "steeper" performance pitfall than the allocation one, but the use-case seems more niche to me.

[jrouwe]

The collide function can now be found here and I added a unit test.