Using broadphase collision detection only

[thegeneralsolution]

I am trying to make some optimizations of my game's graphics engine. Specifically, I want a fast way to:

1. determine which objects are in my view volume (so I can render only these objects)
2. determine which objects are inside of a light volume (so I can use just these objects for shadow calculations)

My thinking is to use Bullet's broadphase algorithms for this, because in both cases I want it to be fast, and it doesn't ruin it if it accidentally gives me a few extra objects there are technically outside of the volume.

I could create a dynamics world and add spheres or boxes representing my volumes and bounding boxes, but bullet would still perform precise collision checking after the broadphase.

Does bullet expose its broadphase API so I can use just this component or is it hard-wired into the engine's pipeline?

[benelot]

First of all, you should keep graphics totally separate from a physics engine. Broadphase collision only use the aabb collision boxes and returns also collisions between the objects in view O(n^2) algorithm. What your rendering system should do must be much more efficient than broadphase, because it should tell you which faces should be rendered and which not. So you should in fact do pure vector geometry to determine if your face looks towards your view frustrum and if it is in view. That should not be done on the base of whole objects.

You can use the Broadphase API with the following callbacks:
http://www.bulletphysics.org/mediawiki- ... d_Triggers

[drleviathan]

Bullet's broadphase is faster than O(n^2) because it maintains a hierarchy of bounding volumes. There are several different data structures to choose from (see the documentation on btBroadphaseInterface) but I think the btDbvtBroadphase is most commonly used. I remember reading somewhere that there are tradeoffs between using btDbvtBroadphase and btAxisSweep3 but I forget details.

There is an efficient way to make Bullet track broadphase overlaps between its objects and a btPairCachingGhostObject however it only tracks Aabb overlaps -- it can't use a frustum for its overlap shape. This means that you could wrap your frustum in a big Aabb but you would tend to collect a fair number of false positives where the Aabb overshoots the frustum.

I suppose if you're motivated and clever enough you could derive a new class from one of the BroadphaseInterfaces that has special efficient handling for a Aabb-vs-frustum overlap.

[thegeneralsolution]

...What your rendering system should do must be much more efficient than broadphase, because it should tell you which faces should be rendered and which not. So you should in fact do pure vector geometry to determine if your face looks towards your view frustrum and if it is in view. That should not be done on the base of whole objects.

To stray into the topic of graphics engines for a sec...
I am using OpenGL and to my knowledge, meshes are baked into Vertex Buffer Objects which are sent as groups of polygons down the rendering pipeline. OpenGL automatically performs clipping(removes out of view polygons) and back-face culling (removes non-front facing polygons) in the GPU. Even if I could write an efficient algorithm to determine which faces were in view, I would have to re-define or re-sort the vertex buffer object, and re-upload the mesh to the GPU per-frame to render only the desired polys, which defeats the advantage of baked vertex buffer objects. By my understanding, it is much more efficient to run a quick algorithm to determine if an object's bounding box is in view, before sending all of its polygons down the rendering pipeline. So I am surprised that you say this should be done at a per-face, rather than a per-object level. Can you clarify how this is supposed to be faster?

There is an efficient way to make Bullet track broadphase overlaps between its objects and a btPairCachingGhostObject however it only tracks Aabb overlaps -- it can't use a frustum for its overlap shape. This means that you could wrap your frustum in a big Aabb but you would tend to collect a fair number of false positives where the Aabb overshoots the frustum.

Wrapping the frustrum in an AABB is doable! An important distinction for what I need is that I have two classes of objects: AABBs that enclose my volumes, and AABBs that enclose the objects of my scene. I am lucking for mesh to volume collisions only (not mesh-mesh, or volume to volume).

A naive approach would be O(N*M), but I think better should be possible if some sort of spacial partitioning is used....

[DestroyerOfCities]

You're right, you should have a VBO per object and you should only render objects that are within your view frustum. But you don't want to only perform physics on objects in your view frustum; what if an object gets hit just to the right of your camera space, and should be knocked into your field of view? You want to keep your rendering separate, and only render based on your own frustum occlusion culling.

Honestly, what you are asking is completely separate from the physics engine. You want to perform frustum-AABB intersection tests to determine what objects are within a camera's view space. You should do this for each camera you want to render with (view, shadow, etc.). Your physics should be run independently of this visibility checking.

[Flix]

Specifically, I want a fast way to:

1. determine which objects are in my view volume (so I can render only these objects)
2. determine which objects are inside of a light volume (so I can use just these objects for shadow calculations)

My thinking is to use Bullet's broadphase algorithms for this

There is an efficient way to make Bullet track broadphase overlaps between its objects and a btPairCachingGhostObject however it only tracks Aabb overlaps -- it can't use a frustum for its overlap shape.

It's always a bit funny to read recent Bullet posts... I remember that some year ago I've successfully implemented frustum culling using the narrowphase with a frustum-shaped ghost object and frustum culling + occlusion culling using the btDbvtBroadphase directly (using btDbvt::collideOCL, etc...).

The odd thing is that I even posted working demos of both implementations to this forum...

[drleviathan]

The odd thing is that I even posted working demos of both implementations to this forum...

So you did, and here is a link to some of it.

[benelot]

Oh, I thought you were writing your totally own renderer, that is why I thought that you would want to filter per-face. Because trying to drawing an entire object just because it is partly in view is large overhead. Well yeah, for a quick test, you can definitely use broad phase and you definitely already received good answers on that.

[thegeneralsolution]

Thank you all for your responses. I will have to check out that implementation!