Real-Time Physics Simulation Forum

Posted: **Fri Oct 28, 2011 2:45 pm**

Hi all,

I am trying to make sense of the frustum culling feature of btDbvt (the collideOCL and collideKDOP functions). I am looking at the single implementation I can find using it in the BulletSAPCompleteBoxPruningTest.cpp file (found in the Extras/CDTestFramework) as reference but as I read elsewhere here on the forum it's not written to be a properly documented example.

I nearly got it working now, but I'm struggling with the back-to-front sorting which fails (reverses) depending on the rotation of my frustum and I think I probably defined something wrong somewhere.

Both the code in the example and in btDbvt itself is completely written without any usable comments or documentation, which is a real shame. I've successfully used this tree in a couple of interesting ways now and it is extremely useful, I just wish it was better documented. I spend a lot of time trying to figure it out based on the usage elsewhere in Bullet.

If anyone can share some more information on this topic it would be great!

- How exactly is the definition of the normal and offset arrays in the collideOCL/collideKDOP functions? (ok, normals of the frustum planes, but should the normals point in or out, for example? Offset from what?)

- What does KDOP and OCL stand for?

- Can any number of planes be defined or is just 4 or 5 allowed?

- Is the sort axis algorithm in btDbvt::collideOCL tested properly (widespread use in games etc), or can there still be bugs with the sorting algorithm?

- Also is there any documentation on which functions in btDbvt::ICollide should be implemented or not depending on the usage? In my case I only re-implemented Process(const btDbvtNode*).

- What does btDbvt::collideTU do?

- How often should the optimize-functions be called? Which one of the 3 is recommended, what are the trade-offs? Must the optimize-functions be called to get correct results, or do they just improve the query performance?

Best regards,
Ola

Posted: **Sun Oct 30, 2011 8:30 am**

ola wrote:I am trying to make sense of the frustum culling feature of btDbvt [...]

I would like better documentation about it too (expecially for occlusion culling, actually).
I can be of some help if you just want to add btDbvt frustum culling to, let's say, a Bullet Demo (I remember I made it a few years ago, and I reused it in some of my Bullet-plain OpenGL integrations (I don't know if it's possible to do it with rendering engines that already perform frustum culling for you...)).

In short, I don't know much about docs and I think I can set up a Bullet Demo with btDbvt frustum culling, but I need some time (to look for the code pieces and put them together).

The main point is to extract the frustum correctly in a suitable way, then you can just copy the code in CDTestFramework. Posting generic code snippets wouldn't be too useful here...

I'll see if I can put together something next week about it if you need it.
(and I hope somebody will extend it to support basic occlusion culling).

In the meantime, answers to your specific questions are welcome

Posted: **Sun Oct 30, 2011 5:59 pm**

Flix wrote:I'll see if I can put together something next week about it if you need it.
(and I hope somebody will extend it to support basic occlusion culling).

No need to wait, I've just found it:

DbvtCullingDemo.zip: (18.2 KiB) Downloaded 2069 times

UPDATE:Updated DbvtCullingDemo.zip to support very basic occlusion culling with box shaped occluders only.
Keys:
'c': change culling mode (frustum+occlusion / frustum only / none)
's': show / hide occlusion buffer (visible only when occlusion culling is activated: slow)
'+','-': change the size of the occlusion buffer (currently powers of two with width = height, but it can be any number AFAIK)

Posted: **Mon Oct 31, 2011 3:09 pm**

Thank you very much, Flix

I got the frustum culling to work now, after some time of trial and error. The OCL sorting works just fine.

I also tried to use the occlusion culling code from the test framework. It seems it's assuming a fixed camera with no rotation, as the buffer is not paying any attention to the OpenGL modelview matrix. Have you had any success yourself? I have never actually run this application myself, did anyone compile it on Linux?

If I understand the method correctly then the occlusion buffer is a low-resolution eye-space depth buffer (128x128 pixels). The front-to-back OCL query renders into this buffer per node and stops "descending" when the occlusion buffer says a node boundingbox is completely occluded by a pixel in the buffer.

Best regards,
Ola

Posted: **Tue Nov 01, 2011 7:59 am**

ola wrote:I got the frustum culling to work now, after some time of trial and error. The OCL sorting works just fine.

Glad you made it

. I think the main difficulty is the correct extraction of the frustum planes.

ola wrote:I also tried to use the occlusion culling code from the test framework. It seems it's assuming a fixed camera with no rotation, as the buffer is not paying any attention to the OpenGL modelview matrix. Have you had any success yourself? I have never actually run this application myself, did anyone compile it on Linux?

Interesting stuff. Actually I was thinking about it myself yesterday (the fact that the modelview was not taken into account). The truth is that I didn't bother too much about trying to understand how occlusion culling works and there are still some pieces I need to know better (for example how the software rasterizer works, where in my ICollide struct I must add/query occluders, which "bounding box" I must use for them, how I can be sure that a body is completely behind them if I use an aabb for occluders and things like them). And no, I didn't compile it on Linux, but I can run the CDTestFramework on windows and I think that displaying the occlusion buffer can be very useful to understand how things are going (so I think I'll add that code as soon as possible, before experimenting with occlusion culling myself).Another thing is that the CDTestFramework uses an "oriented bounding box class", and it's not clear to me if this is something just related to it, or something I have to add myself... As you can see, I suppose it's going to take a LOT of time for me to (hopefully) master the "occlusion API".

ola wrote:If I understand the method correctly then the occlusion buffer is a low-resolution eye-space depth buffer (128x128 pixels). The front-to-back OCL query renders into this buffer per node and stops "descending" when the occlusion buffer says a node boundingbox is completely occluded by a pixel in the buffer.

This makes sense (this theory looks similiar in some aspects to the shadow mapping technique), but this time all must be done in sofware, and the point is that, to fill a pixel, I would like to understand what I'm supposed to use (I mean, occluders should use their whole collision shape that will be "software rendered" to a pixel in the occlusion map? The code seems to use just "btDbvt node bounding boxes as occluders": are they oriented or not?).

...the more I dig into it, the more I understand how difficult this subject is...

Posted: **Tue Nov 01, 2011 4:48 pm**

I've made a small progress (basically just by passing the modelview * projection matrix (already calculated) instead of the simple projection matrix in the occlusion buffer, and by setting code to display it):

: btDbvtOcclusionCulling.JPG (16.52 KiB) Viewed 29225 times

Basically now the problem is that one of my two box shaped occluders (the ground body) works correctly, but for the other its whole aabb is taken into consideration as the occluding shape (instead of the "oriented" bounding box). In short it's too big. The CDTestFramework had all its boxes aabb aligned, so I think it wasn't affected by this problem...

Posted: **Tue Nov 01, 2011 5:02 pm**

I create a new issue to show how the btDbvt occlusion culling works:
https://github.com/erwincoumans/experiments/issues/9

Note that there are several implementations, not just CDTestFramework.
It is also used in Blender Game Engine and in Gamekit so you might want to check out their source code and some docs in their wiki.

Posted: **Wed Nov 02, 2011 12:36 pm**

Erwin Coumans wrote:I create a new issue to show how the btDbvt occlusion culling works:
https://github.com/erwincoumans/experiments/issues/9

Thanks

Anyway I managed to make it work by adding the following code:

Code: Select all

void	OcclusionBuffer::appendOccluder( const btVector3& occluderInnerBoxCollisionShapeHalfExtent,
							const btTransform& collisionObjectWorldTransform
							)	{
	const btVector3 c(collisionObjectWorldTransform.getOrigin());
	const btVector3& e = occluderInnerBoxCollisionShapeHalfExtent;
	const btMatrix3x3& basis = collisionObjectWorldTransform.getBasis();
	const btVector4	x[]={	transform(c+basis*btVector3(-e[0],-e[1],-e[2])),
							transform(c+basis*btVector3(+e[0],-e[1],-e[2])),
							transform(c+basis*btVector3(+e[0],+e[1],-e[2])),
							transform(c+basis*btVector3(-e[0],+e[1],-e[2])),
							transform(c+basis*btVector3(-e[0],-e[1],+e[2])),
							transform(c+basis*btVector3(+e[0],-e[1],+e[2])),
							transform(c+basis*btVector3(+e[0],+e[1],+e[2])),
							transform(c+basis*btVector3(-e[0],+e[1],+e[2]))};								
	static const int	d[]={	1,0,3,2,
								4,5,6,7,
								4,7,3,0,
								6,5,1,2,
								7,6,2,3,
								5,4,0,1};
	for(int i=0;i<(sizeof(d)/sizeof(d[0]));)
		{
		const btVector4	p[]={	x[d[i++]],
								x[d[i++]],
								x[d[i++]],
								x[d[i++]]};
		clipDraw<4,WriteOCL>(p,ocarea);
		}	
	}

And by using it this way:

Code: Select all

void	DbvtBroadphaseFrustumCulling::Process(const btDbvtNode* leaf)	{	
				btBroadphaseProxy*	proxy=static_cast < btBroadphaseProxy*> (leaf->data);
				if ((proxy->m_collisionFilterGroup & m_collisionFilterMask) != 0)	{
					btCollisionObject* co = static_cast < btCollisionObject* > (proxy->m_clientObject);
					if (co == m_additionalCollisionObjectToExclude) return;
					m_pCollisionObjectArray->push_back( co );	
					
					
					if (m_ocb && IsOccluder(co) && co->getCollisionShape()) {
						static btVector3 aabbMin;
						static btVector3 aabbMax;
						co->getCollisionShape()->getAabb(btTransform::getIdentity(),aabbMin,aabbMax);	// Actually here I should get the MINIMAL aabb that can be nested INSIDE the shape (ie. only btBoxShapes work)
						m_ocb->appendOccluder((aabbMax-aabbMin)*btScalar(0.5f),co->getWorldTransform());	// Note that only a btVector3 (the inner box shape half extent) seems to be needed...
					}
				}	
			}

Now the big issue I have is to find a way (if it is possible) to handle bodies marked as non-occlubable, since I suspect (but I must check it), that objects are considered "occluded" if the 8 points of their (global) aabb are occluded: I think this approach creates a lot of false positives (i.e. blinking objects). I'll see what I'll manage to do about it.

For now, I can only have (oriented) box shaped occluders, but it's enough for me (I'm even thinking about (software) rendering just 3 quads (passing from the center of the box) instead of all the 6 box quads, if the software rasterizer is the bottleneck (or if the camera is far from the body center for example)).

I'll update the code when I'll clean it up a bit... [This could be used as an easier to understand example on how to use btDbvt frustum and occlusion culling, if needed (and good enough); although most of it it's just a direct copy of the CDTestFramework...].

Posted: **Thu Nov 03, 2011 11:41 am**

Flix wrote:Now the big issue I have is to find a way (if it is possible) to handle bodies marked as non-occlubable [...]

I've discovered that this is not necessary, since there are not "false positives" at all (all the pixels that make up the 6 (global) aabb quads of an object are checked for occlusion).

I've updated the demo in the third post.

It's all I was able to understand based on the CDTestFramework demo, so maybe somebody can make a better demo based on GameKit or Blender code (I'm aware that I'm a newbie about occlusion culling after all).
As usual, feel free to improve/modify/extend/use the code in the demo as you like (well, to be honest it's more than 50% CDTestFramework code, so...).

Real-Time Physics Simulation Forum

btDbvt::collideOCL (and KDOP) documentation

btDbvt::collideOCL (and KDOP) documentation

Re: btDbvt::collideOCL (and KDOP) documentation

Re: btDbvt::collideOCL (and KDOP) documentation

Re: btDbvt::collideOCL (and KDOP) documentation

Re: btDbvt::collideOCL (and KDOP) documentation

Re: btDbvt::collideOCL (and KDOP) documentation

Re: btDbvt::collideOCL (and KDOP) documentation

Re: btDbvt::collideOCL (and KDOP) documentation

Re: btDbvt::collideOCL (and KDOP) documentation