Broadphase / Midphase / Narrowphase optimization

[voxel]

I am thinking of writing a custom broadphase as my game has fairly controlled conditions:

A large number of separate static objects spread out over a large area (yes, bad) that will be interacting with a very limited number of high polygon (moving) objects.

So the narrowphase will definitely be expensive, however the broadphase should use a hierarchical structure as the number of kinematic/dynamic to static interactions will be confined to a sub-section of the world.

Is what I am thinking of already implemented in the MultiSAPBroadphase?

[Nathanael]

Bullet already provide a wide range of broad-phases implementations:
- btAxisSweep3 (SAP)
- btMultiSapBroadphase (multiSAP)
- btDbvtBroadphase (dynamic hierarchy)

Perhaps you should try existing implementations, then make sure broad-phase is actually a bottleneck.
btMultiSapBroadphase especially can be configured to support custom number of 'inner' SAPs, that may fit your needs.
Alternatively btDbvtBroadphase provide unbounded world space, and fast insertion/removal.

Hope it help,
Nat.

[voxel]

Thanks for the info.

From first guess, the narrowphase is definitely taking the bulk of the time as it can involve two high resolution collision shapes.

I guess I want to modify the broadphase / midphase to provide "physics LOD" as certain interactions between two objects can be handled using the roughest of approximations:

• Object X interacts with Object Y using the high density convex hull (expensive - want exact point on surface).
• Object X interacts with Object Z using a OBB or AABB (cheap - only want boolean answer - close enough is okay).

i.e Object X has two collision shapes. Y and Z are of different types.

I think this can be handled using custom callbacks (ala setNearCallback())? Will I have to write a custom dispatcher/broadphase/etc. for the above?

[Erwin Coumans]

Usually it is best to avoid moving concave triangle meshes, and use approximated compounds of convex parts instead (using btCompoundShape). If you can't use an approximation, try using btGImpactShape instead.

Will I have to write a custom dispatcher/broadphase/etc. for the above?

One way is to create a new collision shape (btLodCollisionShape), with several child shapes. Then register new collision algorithms, that deal with the interaction between btLodCollisionShape and other shapes.

This requires considerable amount of experience with the inner workings of Bullet, so please let us know if you need more information,
Hope this helps,
Erwin

[voxel]

Will I have to write a custom dispatcher/broadphase/etc. for the above?

One way is to create a new collision shape (btLodCollisionShape), with several child shapes. Then register new collision algorithms, that deal with the interaction between btLodCollisionShape and other shapes.

This requires considerable amount of experience with the inner workings of Bullet, so please let us know if you need more information,
Hope this helps,
Erwin

Thanks.

Before I go try, I'm wondering if custom algorithms will help. Essentially what I am asking for is collision algorithms to return "different granularity of answers" depending on the object type.

i.e two planets can quickly decide if an intersection has occurred via bounding spheres, but a planet vs. meteor may require a finer answer via convex hulls. All three could have been convex hull shapes, but when two planets interact they should fallback on sphere shapes.

Is the triggering of shape-to-shape collision algorithms performed at the nearCallback level (which can be controlled at the game logic level)? I'd hate to push game logic deep into Bullet. The trigger of the algorithms will be done on a case by case basis I suspect.

Right now, I see Bullet perform the same granular level of intersection testing for all objects - returning a list of (persistent) contact points. So yes, one way is to use LOD shapes and the other is get Bullet to use different collision tests, right?

[voxel]

One way is to create a new collision shape (btLodCollisionShape), with several child shapes. Then register new collision algorithms, that deal with the interaction between btLodCollisionShape and other shapes.

This requires considerable amount of experience with the inner workings of Bullet, so please let us know if you need more information

I've roughly examined the execution path of discrete dynamics world and found the area where the new btLodCollisionShape + new collision algorithms would be used.

I should call my new shape "MultiRep" vs. LOD. The new shape will just aggregate existing shapes (I wonder if I could use CompoundShape?) and my new collision algorithm will also just aggregate existing algorithms. I do worry about switching between internal shapes and how that will cause drastic frame-to-frame changes to AABB + contact points, but I am assuming that is okay.

I'll probably need to hack in some game-specific narrowphase filter at the algorithm/shape level (around processCollision) to accomplish what I want.

-----

Code: Select all

predictUnconstraintMotion()
	For all (non-static / non-kinematic) rigid bodies
		- integrateVelocities()
		- applyDamping()
		- predictIntegratedTransform()

-- Broadphase
performDiscreteCollisionDetection()
	updateAabbs();
		- Broadphase: setAabb()
	
	Broadphase: calculateOverlappingPairs (see btAxisSweep3, btMultiSapBroadphase, btDbvtBroadphase, etc.)
		- Callback findPair()
		- Callback addOverlappingPair()
				- Collision group/mash filtering: needsBroadphaseCollision()
		- Callback removeOverlappingPair()
		- Callback removeOverlappingPairsContainingProxy()
	
	Dispatcher: dispatchAllCollisionPairs()
		OverlappingPairCache: processAllOverlappingPairs()
			- Callback btOverlapCallback()
				- processOverlap()
					- near call back (see Narrowphase below)
	
-- Narrowphase
	needsCollision(object0, object1)
		- object0 checkCollideWith/checkCollideWithOverride (object1)
	
	findAlgorithm(object0, object1)
		- CreateCollisionAlgorithm
			- allocateCollisionAlgorithm
			- Create "Obect To Object" collision algorithm
			- BoxBox
			- Compound
			- ConvexConcave
			- ConcaveConvex
			- ConvexPlane
			- Empty
			- SphereBox
			- SphereSphere
			- SphereTriangle
			- etc...

	Algorithm: processCollision(object1, object1) -> contact point generation (see above algorithms)

...
... simulation islands + constraints + etc..