Sign in to follow this  
dmatter

spatial partitioning, BVHs & collision detection

Recommended Posts

Just recently I've started looking into spatial partitioning in my latest engine and I was thinking about the best way to properly emplement it into an extensible and fast engine. I think that potentially it should be possible to choose different partitioning schemes to suite different game specifics (in-doors, out-door terrain or mountains, space, etc) The only space partitioning I have actual experience with is quad-trees (for a terrain engien) but I have seen BSP implemented in other code. The purpose, as I understand it, is to reduce the amount of polygons renderered and considered for collsion detection by reducing the number of objects processed. I have been looking into lots of different related conepts: BSP, quad-trees, oc-trees, kd-trees, bounding volume hierarchies (BVHs) and portals Now I have some questions about some of these. Am I right in thinking that BVHs are used in conjunction with a spatial partitioning system for culling parts of complex objects down to some level (eg polygonal level) for collision detection and rendering? My current scene-graph system does include nodes with bounding volumes which encompass all child nodes, does that make my scene-graph a BVH aswell? Even though it is not suitable for trimming out actual polygons from geometry nodes? Is a kd_tree simply a general term for ANY tree, meaning quad/oc-trees and scene-graphs are just specialisations of a kd-tree? Why then is it talked about like a separate (but related) concept? Can they be used for speeding up collision detection and for object culling? Are portals basically spatial partitioning with arbitrary chosen polygons separating the different portals, are they similar to a bsp tree and best suited for in-door environments? Finally - are any of these suitable for spliting up geometry into smaller geometry at run-time for collision detection (etc)? - I've heard that doing this with bsps is achievable but not efficient. [Edited by - dmatter on July 4, 2005 4:18:07 PM]

Share this post


Link to post
Share on other sites
Quote:

Am I right in thinking that BVHs are used in conjunction with a spatial partitioning system for culling parts of complex objects down to some level (eg polygonal level) for collision detection and rendering?


BVH is already a form of spatial partitioning that let you cull parts of a given set of data down to an arbitrary precision (eg: you could use a sphere tree that goes down to the polygon level in your meshes, but that would be overkill). Note that you can cull for rendering as well as culling for collisions... But collisions usually require more precise culling than display so you usually do not use the same structure for both tasks.

Quote:

My current scene-graph system does include nodes with bounding volumes which encompass all child nodes, does that make my scene-graph a BVH aswell? Even though it is not suitable for trimming out actual polygons from geometry nodes?


Yes, it is suitable for culling against frustrums for example (eg: culling a whole hierarchy from its bounding volume instead of culling each node individually is already a big win since it may mean that for, let's say, an NPC, you can cull it's display/animation update and maybe AI all together).

Quote:

Is a kd_tree simply a general term for ANY tree, meaning quad/oc-trees and scene-graphs are just specialisations of a kd-tree? Why then is it talked about like a separate (but related) concept? Can they be used for speeding up collision detection and for object culling?


No, a kd-tree is a special tree and both kd-trees and scene graphs are trees (but a tree is a 'limited' graph) that differ in the way they organize datas. You could make a scene graph using a kd-tree but it would be very unpractical (most certainly useless) to perform common scene tasks like hierarchy matrice calculations. While related (because both are trees) both concepts are used to describe different things.

Quote:

Are portals basically spatial partitioning with arbitrary chosen polygons separating the different portals, are they similar to a bsp tree and best suited for in-door environments?


Portals are not trees. You could see them as dynamic frustrums that should accurately represent what can be seen from a given location, in a given direction. Given a camera frustrum clipped against one or, potentially, many portals you will still have to cull (and maybe clip) items in your scene.

Quote:

Finally - are any of these suitable for spliting up geometry into smaller geometry at run-time for collision detection (etc)? - I've heard that doing this with bsps is achievable but not efficient.


You are not clear about what is not efficient. The generated tree or the time required to build it? Depending on your input datas and the heuristic that you use to build/balance your tree the answer will vary greatly. While you can split geometry against a kd-tree I'm not sure it will be more suited to accelerating display than an octree, this is things that you need to test for yourself by using the datas you need to display.

On a modern PC, building collision structure on moderate geometry (~1000 polygons) is doable in a few ms with a fairly good tree as a result.

[Edited by - b34r on July 4, 2005 10:54:15 AM]

Share this post


Link to post
Share on other sites
edit: doh to late :P, also made some clarifications regarding kd-tree

I'll have a go at the questions you have:

Quote:

Am I right in thinking that BVHs are used in conjunction with a spatial partitioning system for culling parts of complex objects down to some level (eg polygonal level) for collision detection and rendering?

This is often the case yes. For example considering an outdoors rts. The terrain could be handled by a quad-tree and in this tree we could have BVHs containing troops etc. The quad-tree could be used for culling of terrain, high level culling of nodes and/or collisions between nodes and projectiles.

Note though that you often need separate representations/configurations for culling and collisions/physics depening on the fact that what is efficient from a rendering point of view is not efficient from a physics point of view.

Quote:

My current scene-graph system does include nodes with bounding volumes which encompass all child nodes, does that make my scene-graph a BVH aswell? Even though it is not suitable for trimming out actual polygons from geometry nodes?

I would say that this is pretty much a text book case of a BVH :) Trimming out actual polygons is not done that often on models anymore since todays harware can handle massive amount of polys and removing polygons is time consuming, hard and messes up batching/indexing when rendering.

Quote:

Is a kd_tree simply a general term for ANY tree, meaning quad/oc-trees and scene-graphs are just specialisations of a kd-tree? Why then is it talked about like a separate (but related) concept? Can they be used for speeding up collision detection and for object culling?

As I understand it bsp-, quad- and oc-trees are forms of kd-trees. The k refers to the number of dimensions being divided. a quad tree should then be a 2d-tree (k=2), octree and bsp should be 3d-tree (k=3). It is used as the most genereal term of a spatial subdivision i guess.

A scene-graph is however a graph not a tree.

Quote:

Are portals basically spatial partitioning with arbitrary chosen polygons separating the different portals, are they similar to a bsp tree and best suited for in-door environments?

Hmmm not sure I understand what you mean. In a portal sollution the world is divided into cells/rooms that have portals between them. BSP-trees are acutually not used that much for culling (more for collision detection) anymore. Portals seem to be the way to go. However, using the bsp you can compute the PVS.

Quote:

Finally - are any of these suitable for spliting up geometry into smaller geometry at run-time for collision detection (etc)? - I've heard that doing this with bsps is achievable but not efficient.

Not really sure I understand what you mean by "splitting up geometry". BSPs typically split geometry and impose an order. Quad-Octrees typically partition geometry into different nodes.

Hope this helps some :)

Regards,
hObbE

Share this post


Link to post
Share on other sites
Thanks for the fast responses so far, they've been great.

Let me clarify what I mean by 'splitting up geometry' I mean that when it comes to collision detection between to objects you can split an object into two parts and check which of those two is going to have the collision, then split that one up.... recursively reducing the amount of polygons that need to be tested until you split it up to an acceptable degree of accuracy (per polygon is the most accurate and just testing the whole objects bounding volume is the least accurate).

To sum that up I could have a single mesh of a person which a bounding box and when I want to test a collision between the person and a bullet I can split him up into a smaller hierarchy of bounding volumes (either on the fly or using some pre-processed tree) to increase the precision of the accuracy (aka more accurate than just his bounding box) but at the same time prevent testing each and every polygon of the person (so reducing the number of polygons).

In the same way I need to select objects of the world to render and test for collision I also need to be able to select the polygons of those objects that are candidates for collision (I don't do this for rendering becuse it messess up batches etc as already pointed out)

I hope that was clear enough (its difficult to be any clearer)

Thanks so far [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
[...]
To sum that up I could have a single mesh of a person which a bounding box and when I want to test a collision between the person and a bullet I can split him up into a smaller hierarchy of bounding volumes (either on the fly or using some pre-processed tree) to increase the precision of the accuracy (aka more accurate than just his bounding box) but at the same time prevent testing each and every polygon of the person (so reducing the number of polygons).


You can do collision detection against the mesh polygons or against (one, many or in a hierarchy) bounding volumes. You want to reduce the number of primitive tests, eg. ray/polygon or ray/sphere. You can use any method or combination of method to achieve that goal, as you suggest it a coarse BVH then a kd/bsp/aabb tree for the finer levels works very well.

While splitting meshes is required to perform culling on modern GPUs, collision detection does not require that. It is not clear wether you are talking about physically splitting the mesh or not.

In any case, accuracy should not be affected by the methods you use to speedup your collision tests. If you work at polygon level brute force testing every single polygon in a mesh should give you (tangent cases set aside) the same result as any correctly accelerated method. The same goes if you collide with the BVH primitives. The only difference should be in the amount of tests required and as a direct effect: speed [smile].

Quote:

In the same way I need to select objects of the world to render and test for collision I also need to be able to select the polygons of those objects that are candidates for collision (I don't do this for rendering becuse it messess up batches etc as already pointed out)


While you can use the same structure to accelerate both collision and display (eg. by using quadtrees or octrees) it is generally not a good idea. Cards like large batches of polygons wich would require a large amount of ray/polygon tests per node for the character/level collision.

Almost every game model character collisions as BVH.

Share this post


Link to post
Share on other sites
Right, I've been looking at kd-trees but I can't find much detailed info on the net. I have found that they seem to be better than quad and oc trees because they are generally balanced (where-as a quad-tree for example can have empty spaces)

Now I already have a BVH and I intend (at some point) to implement portals but I think that kd-trees are the way to go for the main spatial-partitioning scheme.

I was wondering if anyone could point to/give any more detailed information about kd-trees. I don't have too much money so unless its really worth reading then books are mainly no-nos.

The responses so far have been really useful
thanx

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

Sign in to follow this