In Computer Graphics, there are two important data structures, The BSP Tree and the Octree.I want to use them to fast detect collisions.I mainly use it to get visible objects in a limited space from the whole scene,or to simulate physical motion,or to implement Ray-Traced renderer...Some people told me BSP is faster,and the other said Octree is faster.Who should I believe?
Thanks
Of course it depends, but we can list some key differences:
BSP is slow to build which limits it to static geometry. Octree can be rebuilt / updated per frame for dynamic scenes.
BSP needs to cut static geometry along its partitioning planes into pieces and you need to add dynamic objects to multiple nodes. Octree can can be used in a way to ensure each objects links to only one node (see 'loose' octree).
BSP can do exact front to back rendering for static geometry. Octree can do it only coarsely (except you cut geometry along grid planes or use voxels itself for geometry).
In short: Octree is very flexible. BSP is very limited. Chances that BSP is better for you are very small.
Note that i often prefer BVH over Octree because it is even more flexible and simple. You can view Octree as a special case of BVH.
6 hours ago, Royma said:Thank very much.What kind of BVH do you use?Is it good for me too?
This thread turned into discussion of relevant pros/cons:
For your list of use cases i would recommend BVH in general, yes. Personally i never used one tree for multiple systems e.g. graphics and physics, but it's surely possible i would pick BVH for this without much doupts.
Here are some important points mostly ignored in tutorials / introductions:
The concept of loose octree is very important but works for others like BVH or regular grids, so i give you an example of a regular 2D grid:
We have a grid size of 1 and an object of size 2. So we need to add this object to multiple grid cells, so each grid cell needs to maintain a list with unknown memory requirements. Solution: We add a second coarser grid with cell size of 2. We add each object to the single cell where it's center is and the object also has a pointer to the next object in the same cell. A cell only needs one pointer to the first object but no dynamic list. Now the object may intersect neighbouring cells (3 at max if we think of it, not all 8) and we need to account for this during traversal, but usually performance is much better than having a large object in many small cells. We end up having grids of size 1,2,4,8 etc. Small grid cells must check few nearby large cells for collisions, but large cells do not need to check any smaller cells although they cover lots of them.
For trees this means to store objects in internal nodes and not just in the leaves (like most simple tutorials suggest). This is a bit harder to implement and often not necessary to do, but important to know.
Also, tutorials often use a binary tree. For BSP that's a must but for BVH you can use any branching factor you want. Larger branching factor (more children per node) often means better cache utilization (or better thread utilization on GPU). Personally i often use 8 children because the tree is easy to build. (Take the center of current node bounding box and split to 8 smaller boxes and sort objects in, similar to octree. The difference to octree is that children bounds may intersect and are not tied to a grid in global space.) The second choice you make is to use axis aligned / oriented bounding boxes or spheres as bounding volumes.
To make this a real win, you usually store only one child pointer per node and a child count. All children are stored sequentially in memory so you can iterate cache friendly. This also works for mixed static / dynamic trees (e.g. keep the subtree for each ragdoll but rebuild tree top levels over all 1000 ragdolls each frame.)
In contrast, using 8 child pointers instead is no good idea, but maybe easier to implement or learn and you can optimize later.
And finally, regular grid with multiple levels is easy to implement and fast. Trees only beat this by smaller memory requirements and abilities to mix partial rebuild / refit (update bounds only but keep structure, that's where BVH shines).
So i'd start with regular grid (multi level grid, nested grid, cascades - all those are good search terms i guess).
