Bullet in Frustum Culling

[Ripiz]

Hello,

I've made (very) simple frustum culling using Bullet, it simply checks for collisions between frustum shape and btBoxShape in world, collision means object is visible.
I thought maybe someone knows any way to optimize my way of culling (or maybe even suggest better algorithm), or got some tips what I've done wrong/etc?

1. I build frustum shape by adding 8 points to ConvexShape:

Code: Select all

	btConvexHullShape ConvexShape;
	ConvexShape.addPoint(btVector3(Left, Top, -NearPlane));
	ConvexShape.addPoint(btVector3(Right, Top, -NearPlane));
	ConvexShape.addPoint(btVector3(Left, Bottom, -NearPlane));
	ConvexShape.addPoint(btVector3(Right, Bottom, -NearPlane));
	ConvexShape.addPoint(btVector3(FarLeft, FarTop, -FarPlane));
	ConvexShape.addPoint(btVector3(FarRight, FarTop, -FarPlane));
	ConvexShape.addPoint(btVector3(FarLeft, FarBottom, -FarPlane));
	ConvexShape.addPoint(btVector3(FarRight, FarBottom, -FarPlane));

2. Then create Ghost Object for it and set transformation (to match camera's transformation)
3. Find collisions using contactTest()

Code: Select all

mCulling.contactTest(&GhostObject, Callback);

Thank you in advance.

[Flix]

A similiar solution can be found here: http://bulletphysics.org/Bullet/phpBB3/ ... it=culling (and I believe that using a btPairCachingGhostObject is better than using contactTest).

A more efficient and fast approach consists in using the btDbvtBroadphase (instead of the narrowphase) and supports (optional) occlusion culling. Basic source code can be found here:http://bulletphysics.org/Bullet/phpBB3/ ... it=culling.

[Ripiz]

I am having some problems with btPairCachingGhostObject implementation.

It seems to detect my objects (heightmap to be precise) as visible even when they're way outside my view (I suspect it uses AABB instead of frustum). Here's my implementation:

Culling Physics World initialization:

Code: Select all

	mCullingConfiguration = new btDefaultCollisionConfiguration();
	mCullingDispatcher = new btCollisionDispatcher(mCullingConfiguration);
	mCullingBroadphase = new btDbvtBroadphase();
	mCullingSolver = new btSequentialImpulseConstraintSolver();
	mCulling = new btDiscreteDynamicsWorld(mCullingDispatcher, mCullingBroadphase, mCullingSolver, mCullingConfiguration);
	mGhostPairCallback = new btGhostPairCallback();
	mCulling->getBroadphase()->getOverlappingPairCache()->setInternalGhostPairCallback(mGhostPairCallback);

Object's shape for culling (using simple box for speed instead of precise shape):

Code: Select all

	if(mCullingObject)
		mCulling->removeCollisionObject(mCullingObject);
	mCullingShape = new btBoxShape(btVector3(mHeightmapSize * 0.5f, (Min + Max) * 0.5f, mHeightmapSize * 0.5f));
	mCullingObject = new btCollisionObject();
	mCullingObject->setCollisionShape(mCullingShape);
	mCullingObject->setUserPointer(this);
	// setup transformation, heightmaps possess no rotation
	mCullingObject->setWorldTransform(btTransform(btMatrix3x3::getIdentity(), btVector3(mTransformation.col0[3], Offset, mTransformation.col2[3])));
	mCulling->addCollisionObject(mCullingObject);

Construction of frustum shape:

Code: Select all

	const btScalar nearPlane = gCamera.mNear;
	const btScalar farPlane = gCamera.mFar;
	const btScalar planesFraction = farPlane / nearPlane;
	const btScalar centralPlane = (farPlane - nearPlane) * 0.5f;
	btScalar left, right, bottom, top, farLeft, farRight, farBottom, farTop; 
	const btScalar aspect = gCamera.mAspect;
	if(aspect >= 1) {
		left = -aspect;
		right = aspect;
		bottom = -1.0;
		top = 1.0;	
	} 
	else {
		left = -1.0;
		right = 1.0;			
		bottom = -aspect;
		top = aspect;
	}	
	farLeft = left * planesFraction;
	farRight = right * planesFraction;
	farBottom = bottom * planesFraction;
	farTop = top * planesFraction;

	btConvexHullShape ConvexShape;
	ConvexShape.addPoint(btVector3(left, top, -nearPlane));
	ConvexShape.addPoint(btVector3(right, top, -nearPlane));
	ConvexShape.addPoint(btVector3(left, bottom, -nearPlane));
	ConvexShape.addPoint(btVector3(right, bottom, -nearPlane));
	ConvexShape.addPoint(btVector3(farLeft, farTop, -farPlane));
	ConvexShape.addPoint(btVector3(farRight, farTop, -farPlane));
	ConvexShape.addPoint(btVector3(farLeft, farBottom, -farPlane));
	ConvexShape.addPoint(btVector3(farRight, farBottom, -farPlane));

	btPairCachingGhostObject GhostObject;
	GhostObject.setCollisionShape(&ConvexShape);
	GhostObject.setCollisionFlags(btCollisionObject::CF_NO_CONTACT_RESPONSE);
	btMatrix3x3 Rotation;
	// angles might seem weird, but according to debug draw frustum's direction does match my camera's direction
	Rotation.setEulerZYX(-gCamera.mRotY, -gCamera.mRotX + MyEngine::PI * 0.5f, 0);
	btTransform Transform(Rotation, btVector3(gCamera.mEye.x, gCamera.mEye.y, gCamera.mEye.z));
	GhostObject.setWorldTransform(Transform);
	mCulling->addCollisionObject(&GhostObject);

Actual culling:

Code: Select all

	mCulling->getDispatcher()->dispatchAllCollisionPairs(GhostObject.getOverlappingPairCache(), mCulling->getDispatchInfo(), mCulling->getDispatcher());
	btBroadphasePairArray &CollisionPairs = GhostObject.getOverlappingPairCache()->getOverlappingPairArray();
	int VisibleCount = 0;
	for(int i = 0; i < CollisionPairs.size(); ++i) {
		const btBroadphasePair &CollisionPair = CollisionPairs[i];
		btManifoldArray ManifoldArray;
		CollisionPair.m_algorithm->getAllContactManifolds(ManifoldArray);
		for(int j = 0; j < ManifoldArray.size(); ++j) {
			btPersistentManifold *Manifold = ManifoldArray[j];
			for(int p = 0; p < Manifold->getNumContacts(); ++p) {
				const btManifoldPoint &Point = Manifold->getContactPoint(p);
				if(Point.getDistance() < 0.0) {
					// it's always Body0; sorry for pointer mess, I just set heightmap's bool to true, so it gets rendered
					((Heightmap*)((btCollisionObject*)(Manifold->getBody0()))->getUserPointer())->mVisible = true;
					++VisibleCount;
				}
			}
		}
	}

Just an image:

According to VisibleCount variable it draws all 61 heightmaps, though only 5 are visible in the image. Other heightmaps are to the left and right, in similar manner as visible ones (single heightmap is 128 units, so last ones are over 3000 units away from center). Cross on the screen is frustum's shape drawn by debug drawer.

Anyone know what I have done wrong?
Thank you in advance.

[Flix]

Anyone know what I have done wrong?

Not easy to tell The strangest thing I can see in your code is that you seem to create the ghost object and its collision shape on the stack (and then you add it to the world with something like: world->addCollisionObject(&myObjectOnTheStack)...).
I'm not sure if this the problem, but I suggest you create everything on the heap, just in case.

I also suggest you stick to the code in the link I posted before (that should work).

P.S. There are two more optimizations to the code I posted:
1)Replace:

Code: Select all

m_dynamicsWorld->getDispatcher()->dispatchAllCollisionPairs(m_pairCachingGhostObject->getOverlappingPairCache(), m_dynamicsWorld->getDispatchInfo(), m_dynamicsWorld->getDispatcher());

with findPair(...); please see the GhostObjectsDemo.zip here: http://bulletphysics.org/Bullet/phpBB3/ ... tsDemo.zip.
2)

Code: Select all

GhostObject->getCollisionShape()->setMargin(0)

But these alone won't solve your problems.

[Ripiz]

1. I created objects on heap and nothing changed

2. Tried findPair(...) and failed to notice any difference in performance. Possibly because rendering took most of the time

3. Added (...)->setMargin(0) line, no idea what it does though XD

4. After some debugging I noticed my frustum's left and right sides are way outside far plane. Since frustum construction was copy/pasted from demo I assumed it's correct and never bothered to test. Managed to figure instead of

Code: Select all

   farLeft = left * planesFraction;
   farRight = right * planesFraction;
   farBottom = bottom * planesFraction;
   farTop = top * planesFraction;

I have to use

Code: Select all

   farLeft = left * farPlane;
   farRight = right * farPlane;
   farBottom = bottom * farPlane;
   farTop = top * farPlane;

After this change frustum shape looked much much better, but it still didn't match my camera perfectly. 6 heightmaps were visible but it detected 15.
Then I remembered raycasting. Maybe not fastest way to make frustum (matrix inverse, 12 dot products, 4 vector normalizations, ...) but it's very accurate, frustum perfectly matches camera:

Code: Select all

	const Matrix &ViewInv = gCamera.GetViewMatrix().Inversed();
	const Vector4 ScreenCorners[] = {
		// SSE structures make it confusing to access individual elements
		Vector4(-1.0f / gCamera.GetProjMatrix().col0.m128_f32[0], 1.0f / gCamera.GetProjMatrix().col1.m128_f32[1], 1, 0),
		Vector4(1.0f / gCamera.GetProjMatrix().col0.m128_f32[0], 1.0f / gCamera.GetProjMatrix().col1.m128_f32[1], 1, 0),
		Vector4(-1.0f / gCamera.GetProjMatrix().col0.m128_f32[0], -1.0f / gCamera.GetProjMatrix().col1.m128_f32[1], 1, 0),
		Vector4(1.0f / gCamera.GetProjMatrix().col0.m128_f32[0], -1.0f / gCamera.GetProjMatrix().col1.m128_f32[1], 1, 0)
	};
	const btVector3 PartialCameraCorners[] = {
		btVector3(ScreenCorners[0].dot(ViewInv.col0), ScreenCorners[0].dot(ViewInv.col1), ScreenCorners[0].dot(ViewInv.col2)).normalized(),
		btVector3(ScreenCorners[1].dot(ViewInv.col0), ScreenCorners[1].dot(ViewInv.col1), ScreenCorners[1].dot(ViewInv.col2)).normalized(),
		btVector3(ScreenCorners[2].dot(ViewInv.col0), ScreenCorners[2].dot(ViewInv.col1), ScreenCorners[2].dot(ViewInv.col2)).normalized(),
		btVector3(ScreenCorners[3].dot(ViewInv.col0), ScreenCorners[3].dot(ViewInv.col1), ScreenCorners[3].dot(ViewInv.col2)).normalized()
	};
	const btVector3 CameraPosition(gCamera.mEye.x, gCamera.mEye.y, gCamera.mEye.z);
	const btVector3 ConvexPoints[8] = {
		PartialCameraCorners[0] * gCamera.mNear + CameraPosition,
		PartialCameraCorners[1] * gCamera.mNear + CameraPosition,
		PartialCameraCorners[2] * gCamera.mNear + CameraPosition,
		PartialCameraCorners[3] * gCamera.mNear + CameraPosition,
		PartialCameraCorners[0] * gCamera.mFar + CameraPosition,
		PartialCameraCorners[1] * gCamera.mFar + CameraPosition,
		PartialCameraCorners[2] * gCamera.mFar + CameraPosition,
		PartialCameraCorners[3] * gCamera.mFar + CameraPosition
	};

Thanks for help, Flix.

[Flix]

2. Tried findPair(...) and failed to notice any difference in performance. Possibly because rendering took most of the time

To be honest I haven't make any performance comparison myself, and I've never fully understood which of the two ways is correct/better...

3. Added (...)->setMargin(0) line, no idea what it does though XD

Otherwise: "Objects that are on the edges of the frustum will get culled out early making them blink in and out." (quote taken from the post I linked above).

1. I created objects on heap and nothing changed [...] 4. After some debugging I noticed my frustum's left and right sides are way outside far plane. [...]

Well, calculating the exact frustum points/planes is always something that it's better to do very carefully (although with a ghost object shaped frustum it should be a little easier, because it can be done only once when the collision shape is created and not every frame). I'm sorry my code was not clear enough, but I made it long ago (and now I prefer using the broadphase approach). I'm glad you eventually made it !