Jump to content
  • Advertisement
Amir_r_KB

Updating Bounding Volume Hierarchy Leaves

Recommended Posts

I've been thinking of implementing a bounding volume hierarchy(BVH) system to speed up my tests against high poly collision meshes and soups. So far i think an implementation like what physX does (An AABB Tree) would suffice.

But now i wonder, what are the efficient ways to handle a mesh instance that has been rotated, making the AABB bounds invalid. 

One obvious way i can think of, is to only recalculate the AABBs that we're actually testing against (Every frame, Without saving the result). What are the better ways people have figured out?

Share this post


Link to post
Share on other sites
Advertisement

I am not at the point of implementing that myself, but I recently read some chapters of  "real time collision detection" of Christer Ericson. From what I can remember you basically recalculate the AABBs. An alternative option would be, to use bounding spheres. They don't care about rotations.

 

Greetings

Share this post


Link to post
Share on other sites
1 hour ago, Dirk Gregorius said:

Erin Catto gave an exhaustive presentation on this topic this year at GDC:

http://box2d.org/files/GDC2019/ErinCatto_DynamicBVH_Full.pdf

Great read thanks for sharing. though it doesn't cover my question. His presentation is mainly about broad-phase, but my question is about what to do for a "Mesh BVH (Enclosing primitives)" when the actor orientation has been changed, should i recompute every AABB that i'm testing against to match the new orientation or is there a better way?

Share this post


Link to post
Share on other sites
4 hours ago, Amir_r_KB said:

Great read thanks for sharing. though it doesn't cover my question. His presentation is mainly about broad-phase, but my question is about what to do for a "Mesh BVH (Enclosing primitives)" when the actor orientation has been changed, should i recompute every AABB that i'm testing against to match the new orientation or is there a better way?

Usually this is handled by a 2-level BVH, where each lower level BVH have transformations associated. One BVH for the objects in the scene that is dynamic, and a second static one for each mesh that is nested within the scene BVH. When traversing the scene, you only transform what is necessary. For the case of ray casting, you would just transform the ray into the mesh's local BVH space, and then undo the transform for hit information (normals) when the information is returned. For mesh vs. mesh collision, it might not be so easy. In that case you would probably have to transform the node AABBs of one BVH on the fly during traversal into the other BVH's local space.

Share this post


Link to post
Share on other sites

Solution will always be something quite simple, for example, don’t rotate meshes. Or, look at velocity and inflate the AABB with a prediction.

Share this post


Link to post
Share on other sites
4 hours ago, Aressera said:

One BVH for the objects in the scene that is dynamic, and a second static one for each mesh that is nested within the scene BVH

I'm not very familiar with terminologies in this field unfortunately, If i understand you correctly, This means two completely separate hierarchies; One for potentially movable/rotatable objects called dynamic and another for objects that definitely won't move called static (Assuming the game needs this distinction). but does the static hierarchy divide down to sub mesh granularity in your model? if so that means a complete set of new AABB tree for each instance of that mesh in different orientations, which requires a lot of memory i suppose! i most likely misunderstood it.

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!