Bounded volume hierarchie

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 May 30, 2010 at 15:45

Hi there !
I’m new to this forum but not new in reading you :).
So i’m not pure english or american so excuse my language mistakes.

I have one question for my futur 3D engine. I want to handle a scene with a sceneManager based on bounded volume hierarchie. I want to use sphere tree for the simple computation for collision.

I would like to know :

1) How can i build a sphere tree in order to handle the total space scene. I have read a lot of paper that explain the theory but not the algorithm to build the tree. I know that i have to sub divide one node with two or more sphere node taking the average vertex for the center of sphere. Am i right ? Can you guys give me a good algorithm or better a video demonstration?

2) Are Sphere tree, the best choice to handle culling occlusion , collision ? (if it is, can u give me some algorithm to handle mainly occlusion ? because culling and collision i know how i can proceed).

3) how can i dynamically update the tree for dynamic shapes in the scene ?

Thanks for all response. I precise that i have an idea for question 2 and 3 but no idea for the first one.

THANKS again !

33 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 May 30, 2010 at 17:41

Sphere trees aren’t very common; people usually use bounding box trees or BSP trees from what I’ve seen. And loose bounds like BBs and spheres are more useful for visibility testing than collision. For collision you usually don’t want just boxes and spheres as you’ll get physics that feels like everything is a box or a sphere; most people support arbitrary collision meshes, and a BSP is the easiest way to represent those in a way that’s easy to intersect with.

That being said, most of the time when people build BB trees or sphere trees, they just put one BB/sphere around each separately movable or drawable object in the scene. The scene usually already has such objects in it naturally due to the way it’s modeled, i.e. one doesn’t usually need to subdivide an arbitrary polygon soup.

But if you do need to subdivide a polygon soup, you might try the classic kd-tree subdivision algorithm. You can read up on kd-trees on google, but basically you split the poly set along one axis (X, Y, or Z), usually the axis along which it has the longest extent, and find the median split - the point at which you have equally many polys on both sides of the split. Then recurse to the two subsets.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 May 30, 2010 at 21:35

thanks a lot for your answer.
If i understand what ou are saying, i can build a BB tree using Bounding volume aroud each objects in the scene. And to increase performance i can recursively build a “sub tree” for complicated object like a terrain. But this way i don’t have any information about where the object is located …. Even if i keep the worl position matrix to the leaf node i can’t build an effective algorithm like octree where “if a ray don’t intersept a node u do not test the children”. And if i do a partition like octree whith sphere tree i don’t know how ….

i’m still in trouble…

And with bsp i see a lot of engine using it but with dynamic objects that is not optimal. Rearranging node, space etc… very slow i think.

Have you some fast algo ?

i see adaptive bsp tree on internet , but wtf ? they are trying using thresold to determine how can a node grow up before reorganising the tree for dynamic objects… It is a lot of hack i won’t make in my engine ..

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 May 30, 2010 at 22:47

@ftyou

Even if i keep the worl position matrix to the leaf node i can’t build an effective algorithm like octree where “if a ray don’t intersept a node u do not test the children”.

I don’t see what the issue is…yes, of course each leaf node (drawable object) should have a full world matrix and whatnot so you can draw it. And you know each bounding box or sphere encloses all the nodes inside it since you built it that way. :)
@ftyou

And with bsp i see a lot of engine using it but with dynamic objects that is not optimal. Rearranging node, space etc… very slow i think.

Yeah, BSP is not great for dynamic stuff. Better to use BBs or something that is quick to rebuild. You can still use BSP for collision meshes but you needn’t force all the objects to be in one BSP; you can keep a prebuilt BSP for each dynamic object as long as the objects move rigidly (don’t deform) and a BSP for the environment.
@ftyou

they are trying using thresold to determine how can a node grow up before reorganising the tree for dynamic objects… It is a lot of hack i won’t make in my engine ..

In real life people often use all kinds of “dirty” heuristics to get things to work well…not everything can be solved in an elegant theoretical way. ;)

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 May 30, 2010 at 22:54

@Reedbeta

most people support arbitrary collision meshes, and a BSP is the easiest way to represent those in a way that’s easy to intersect with.

Really? I doubt it. How would you handle the intersection of 2 bsp trees? A plane-plane intersection doesn’t reveal much useful information. I recon most physics engines use bounding volume hierarchies, with the actual mesh (or mathematically defined objects) encoded in the leaf nodes. A BSP tree in physics is only useful if you’re using solid-leaf trees and are only testing against simple volumes. Not against other trees.

For visibility testing, bsp trees aren’t very useful either. Of course, you can push a frustum down the tree to see which nodes intersect, but view frustums are fairly large, so if you don’t actually split the frustum using the bsp planes, as most people don’t as it is costly, you’re going to have a lot of false positive tree nodes.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 May 30, 2010 at 22:58

AHA ! i know that people use a lot of tricks and that make me feel extremly bad :D.

Concerning the BBs i don’t see the difference between octree and BB for example. octree have only space information. But with BBs we have for each node a complete geometry ( no split for an objects ).

In fact, i don’t see why BBs are better than octree for dynamic object. And even more why can you compute a culling or collision detection with BBs, cause they don’t split the space equally ….

thanks for taking your time :D

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 May 30, 2010 at 23:08

@.oisyn

Really? I doubt it. How would you handle the intersection of 2 bsp trees?

Well, what I’ve seen is usually a BSP with a dual representation, where you have the actual polygons stored in the leaves of the tree. Then you can intersect two BSPs by pushing the polys of object A through the tree of object B, and vice versa. It can certainly be handy to combine this with BBs. For instance if you have a complicated physics object colliding against the environment you wouldn’t want to push all its polys through the environment BSP straightaway; you could first push its BB through the environment BSP to find a minimal subtree that potentially has an intersection, then push the polys through just that subtree.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 May 31, 2010 at 00:29

@Reedbeta

Well, what I’ve seen is usually a BSP with a dual representation, where you have the actual polygons stored in the leaves of the tree. Then you can intersect two BSPs by pushing the polys of object A through the tree of object B, and vice versa.

My point was that you can’t efficiently use the BSP tree for B to push down A’s tree. And if you’re already testing each individual polygon from B, there’s no point in doing the reverse as well. You’ll need some sort of bounding volume information for each node to make BSP trees a viable solution. But fair enough, I should’ve chosen my words more carefully, I thought we were talking about the goold old classic BSP tree with mere split planes, and other information only in the leaf nodes.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 May 31, 2010 at 08:44

Sorry guys but i don’t follow you at all …

Can you explain what mean “push the polys down to the bsp tree ?”
And why do i need 2 bsp tree ? How can i build them ? How perform culling, collisions, and occlusion.

I’m really sorry but i’m so sick reading 100 papers about bsp, sphere tree, portal i don’t really know the structure for my scene manager.

indoor + outdoor + culling + occlusion + collision + static and dynamic object.

17ba6d8b7ba3b6d82970a7bbba71a6de
0
vrnunes 102 May 31, 2010 at 09:14

There is no perfect, definitive solution for all of this yet. All this discussion is just mental massage from these guys and they know that — although that’s an excellent discussion, of course.

But there is simply no single best solution for all types of geometry and games yet! This is one of the reasons they are discussing. With the current technologies, the best solution still depends on which type of universe you’re going to build.

Currently, every algorithm out there lies somewhere between a fully Dynamic World and a Precise Spatial Division (and I’m not including here memory consumption).

more                       more
dynamic                   spatially divided
| ------------------- |
          ^

When you invest on fully dynamics, you lose on spatial division and vice-versa. For example, if you don’t use any algorithm at all, you have a fully dynamic world, but then you have a very slow engine, because your culling, collision detection and physics will be very costly. When you have complex spatial division, you have essentially static objects, because if you move them, this operation will slow down your engine. When you have both, memory consumption is too high and won’t fit in memory. =)

The best you can do is learn pros and cons of each method, then decide the best ones to fit into your engine.

If you don’t need too much dynamic objects, some algorithms fit better than when you need a good spatial division.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 May 31, 2010 at 12:37

Thank you for your clear answer !
I’m wondering what structure the expert engine like cry engine and unreal engine are using ? I know that unreal engine don’t use portal (clearly exposed in specifications) So in FPS in general you have more static objects (i think) But you can have hard dynamic objects like a car or a plane.

So it is a good way to build octree for static objects and then sphere tree for dynamic objects ? So the culling occlusion is easy for static and sphere tree update easy for dynamic objects.

But ….

How can you perform collision between static and dynamic object ? brute force algorthm testing bounding volume of dynamic objects vs all the bounding volume of whole scene and then recursively eliminate children node ?

I think i’m pretty in a good way using this.
Can you guys give me some advises ?

17ba6d8b7ba3b6d82970a7bbba71a6de
0
vrnunes 102 May 31, 2010 at 15:31

Common architectures are:

  • BSP for indoors;
  • Quadtreee for outdoors;
  • Some form of bounding volume (sphere, box) for moving objects.

One of the reasons BSPs and Quadtrees were created is exactly to accelerate collision detection, because you have near optimal space partitioning, so searching through space is quite an optimized process.

Suggested search: http://www.google.com/search?hl=en-US&safe=off&client=firefox-a&hs=2BS&rls=org.mozilla%3Aen-US%3Aunofficial&q=bsp+quadtree+%22collision+detection%22&aq=f&aqi=&aql=&oq=&gs_rfai=

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 May 31, 2010 at 18:24

quadtree is using in 2D game i think. The equivalent in 3D game is octree.

My question is how can you perform a collision detection with a dynamic object and a static object stored in octree. Do you have to go with a bruteforce algorithm ?

thanks for your answer :)

17ba6d8b7ba3b6d82970a7bbba71a6de
0
vrnunes 102 Jun 01, 2010 at 01:03

@ftyou

quadtree is using in 2D game i think. The equivalent in 3D game is octree.

Not true. Quadtree is used for 3D as well. Don’t be confused by the term “quadtree is a 2D tree” and “octree is a 3D tree”. Both are applied to 3D worlds.
@ftyou

My question is how can you perform a collision detection with a dynamic object and a static object stored in octree. Do you have to go with a bruteforce algorithm ?

I am not sure I’m understanding your question. All those structures were created exactly to avoid brute force. When you have a spatial structure like an Octree, for example, the Octree will enable you to quickly traverse all nodes that are near the object you’re going to test for collisions, or near the camera you’re going to use to render the scene. So you will test only the nodes that are near to the object, hence no brute force needed. If you have a complex scene with lots of nodes (to simplify, let’s say objects), the Octree will quickly discard all the nodes that are far from the object you want to test for collisions.

An octree traditionally requires a pre-process stage, when you build the octree. At this stage there is a process that will include the scene’s objects into octree nodes, partitioning the scene into separated spaces.

So after building your octree (which you can save to avoid reprocessing every time you run your game), lets say you have your dynamic object flying within the octree. The dynamic object has a bounding box. At each new frame, you get the current 3D position of your dynamic object, and start with the root node of the octree. This root node represents the full volume of the entire static scene, and it has 8 child nodes, each one getting 1/8 of the scene (draw a cube on paper, and divide the cube by eight sub-cubes, you’ll get the figure). Proceeding then, the octree is able to quickly tell you which one of the child nodes your object is inside. Then you jump to that child node, and if it has more child nodes, you get the one which your object is inside again. You repeat this process until you get to a leaf node, that is, an octree node that has no children. There you have the other objects that are close to your object. See how it discarded all far objects? You quickly localized the objects (or polygons) in the world that are near to your object, without looping through all the world objects. That is very smart. OK, now you start testing your object’s bounding box against the bounding boxes of the found objects.

Well… there are some other details but hopefully you’ll understand the overall algorithm.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 01, 2010 at 04:44

You can also put dynamic objects in the octree. You just have to keep track of when they cross node boundaries as they’re moving, and delete them from the old node and place them in the new node.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 07:53

Hey !
Thanks for your answer !
I understand now the overall algorithm yes.
Octree seems to be a very good structure to handle static objects. Moreover it is very easy to test collision with dynamic objects stored in another structure> I think dynamic objects can’t be stored in octree because rebuilding a sub tree on the fly can be slowly ….

Last question for you :).

If you have a terrain (very large object) and you want to put this one in octree to avoid rendering all polys with frustrum culling. The fact is that u need to cut the all polys to fit corretly in octree. So ….

1) how can you know if u need to cut an object to fit octree, or if you simply put the object into 2 nodes.


   
   

Here the rectangle can be stored in the 2 node and you can render the rectangle if your algorithm finish in one of the two node. Here no problem the few polygons draw for nothing are not important.

But in case with terrain u need to cut it into the different nodes. So how can u detect that ?

2) More generally if in your engine u have a class object with vertex normal texture attribute related to this object and your octree need to cut the objects into two node, how can u store the different information into node without creating 2 objects. It is a structure class question so feel free to advice me like you want :)

Thanks a lot!

17ba6d8b7ba3b6d82970a7bbba71a6de
0
vrnunes 102 Jun 01, 2010 at 08:28

To detect when to split a triangle, you can store a division plane separating each of the octree nodes. Then, using plane equation, you determine if a triangle is in front, back, or intersecting the octree plane.

When intersecting, some people will insert the triangle into the two nodes where it intersects (just leaving it duplicated), and other people will prefer to split the triangle in two (split at the division plane of the two octree nodes).

On my own old, dirty octree experiment I decided to split the triangles that intersected octree nodes. It worked well for what I needed.

But even then… for open terrains, I actually would stick with a simple Quadtree…

17ba6d8b7ba3b6d82970a7bbba71a6de
0
vrnunes 102 Jun 01, 2010 at 08:32

@Reedbeta

You can also put dynamic objects in the octree. You just have to keep track of when they cross node boundaries as they’re moving, and delete them from the old node and place them in the new node.

Sure, perfectly. But then would you create/delete child nodes by demand or switch to a fixed depth tree with all nodes created beforehand? I would choose the second, probably, considering the performance implications.

EDIT: Or would you just insert the object into the nearest greater node then? That would still work quick I guess.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 08:38

ok i understand the splitting case. But when you split a triangle how hold you the information ? I mean you have mainly an entire object in database wich hold a vertex buffer> Do you need to split the buffer ( reallocate + allocate ) and create @ objects separatly or what ?

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 01, 2010 at 09:42

Splitting is an offline process, that takes place even before the concept of a vertex buffer even exists. After you know what all the chunks of primitives (triangles) will be, then it’s time to store all the data in contiguous databuffers so you can copy that to a vertex buffer at runtime during load.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 09:53

How can you split a triangle of 3 vertexs if a vertex buffer doesn’t exist before ?

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 01, 2010 at 10:05

Well that kind of depends on what your definition of a vertex buffer is. For offline tools, you don’t have to necessarily work with vertex buffers like the GPU does. You could just as well have a triangle struct like:

struct Triangle
{
    Vertex v0, v1, v2;
}

Or, you could have a datastructure such as a doubly connected edge list (DCEL), which is handy if you need adjacency information.

It’s not strictly necessary to maintaining contiguous vertex buffers during the split process. You can just as well (re)construct them after your split operation is complete. The data that usually comes from 3D modeling tools as 3D Studio Max and Maya isn’t in the correct format either - those usually support separate index channels per vertex property so they can share more data. This means 3 indices for the position, 3 for the normal, 3 per texture channel, etc. Of course, you could call a list of vertex positions a “vertex buffer”, but there’s no point in maintaining it as the GPU can’t render such data anyway (as it can only deal with one index per whole vertex, not per vertex property)

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 10:35

Ok I mean, If you have a complicated structure (like a terrain or a big object) stored with a linked list of triangle or a buffer of triangle how can you perform the splitting by a plane. It seems very complicated … And ery slow operation too. I am a little bit confused by all the techniaue for space partitionning and even i understand one thing, one harder things come to me lol :(

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jun 01, 2010 at 11:13

Just walk over all the triangles and test if it has vertices on either side of the plane. If it has, it needs to split, so then you walk along the triangle and split each edge that crosses the plane. Note that this will leave you with a triangle and a quad in most cases (you’ll only get two triangles if one of the vertices is exactly on the plane). You’ll have to divide the quad in two to get two triangles (just take vertex 0, 1 and 2 for the first triangle, and then vertices 2, 3, 0 for the second).

Since you’re only splitting in x-, y- and z-planes, you could sort all geometry in those directions to quickly be able to find the necessary split candidates. However, I’d make sure your split algorithm works before optimizing it.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 11:44

Ok i understand. I have download a lot of engine in section ( 3d engine database) searching an implementation of octree.

i would like somebody provide me a good examplne of implementation with real c/c++ code (not pseudo code) showing how build octree from vertexs list to the end. Can ou give me a good engine where it is clearly implemented ?

thanks a lot

46407cc1bdfbd2db4f6e8876d74f990a
0
Kenneth_Gorking 101 Jun 01, 2010 at 13:40

@ftyou

i would like somebody provide me a good examplne of implementation with real c/c++ code (not pseudo code) showing how build octree from vertexs list to the end. Can ou give me a good engine where it is clearly implemented ? thanks a lot

http://developer.amd.com/gpu/radeon/archives/RadeonSampleCode/TerrainDemoonRadeon/Pages/default.aspx

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 14:53

thank you. i will take a look !

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 21:10

Ok Very helpful :).

I have another question ….

When pre processing octree with static data i want to use VBOs. Si i have a list of triangle with materials. But when the octree algorithm split one or more triangle the list isn’t continue anymore. So i had already upload all the data to the graphic card to optimize the uploading runtime phase.

I do now a frustrum culling and i hold the triangle that need to be displayed. So each frame i can sort the triangle by materials for rendering … BUT all the data is already on GPU and even if i sort the data i can’t reorganize the data on GPU.

How can i perform this type of operation without uploading data on GPU every frame ?

I’m working with OPENGL.

To sum up, i start with a list of triangle. I upload all the data to GPU. I build an octree that split some goemetry. I want to optimize rendering with sorting the data with materials. How can i do that ?

I don’t want to upload data after splitting geometry because i want tue user build static objects with an octree on the fly….

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 01, 2010 at 21:26

You can have a separate vertex buffer for each leaf node of the octree, containing just those triangles that are in that node. Better yet, keep everything in one vertex buffer, but organize it by node, so e.g. it has all the triangles from node 1, then all the triangles from node 2, and so on. Either way, when you determine that an octree node is visible, you can draw just the triangles that are in that node.

For extra credit, organize the vertex buffer so that leaf nodes that are siblings are a contiguous block in the buffer (it’s easy to do this for all levels of the tree). Then when an entire interior node is visible at once, you need only do 1 draw call for the whole thing, rather than descending into the children and doing (up to) 8 draw calls.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 21:40

Wow what a clear answer !

The last idea is very interesting but i want the user build static data on the fly in his program. So the octree can split his data and the vertex buffer in one level stored in GPU need to be updated = deleted + reallocating + uploaded.

I think i don’t have the choice anyway. So the user build all this geometry in the programme and at runtime the octree build the scene splitting some data and build vertex buffer with node data. then the data is uploaded. And all of this operation during a loading screen (relatively fast with a few polygons).

And so the data is already on GPU and i can save the octree in a file for reusing it.

I think i’m right or i missed some good informations ?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 01, 2010 at 22:04

I don’t see what you mean by “build static data on the fly”. The words “static” and “on the fly” are usually exact opposites. ;)

If you mean the user is building the geometry in a modeling program separate from the engine, then compiling it and loading it in the game engine: then the exporter/compiler should do the job of building the octree and making all the vertex buffers.

If the user is changing the geometry in the engine while it’s running: then you have to re-upload the changed data to the GPU anyway, no matter whether you use octrees or not.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 22:34

Yes sorry for static and on the fly i was exactly thinking about a small builder. :). I think i understand the concept.

So if the frustrum culling provide me to render the node 3,7 and 8 i know i have the vertex buffer aligned in GPU memory by node so 3 call to drawArray is required. But if in one node you have different material or shader to apply to polygons (for instance a table, a terrain and a bottle), how can you keep trace about this informations? in a separate buffer stored in client memory ? I have some trouble to think about how to handle this problem. Because firstly i would to sort the triangle bu shader/materials to minimize the call function (because when u change material or chaders for differents objects an other drawArray call is needed) But if i do like you i organise my data per node…. So any idea ?

Thank you again for taking your time and reading my horrible english lol

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 01, 2010 at 23:02

Yes, it’ll need to be organized both per node and per material. You could have a separate vertex buffer for each material, and organize each vertex buffer per node the way I described previously. When you draw, you loop over materials first, then loop over visible nodes on the inside. So you’d draw: node 3 material A, node 7 material A, node 8 material A; then node 3 material B, node 7 material B, node 8 material B; and so on.

9137f0bd6d99129577098d910cfc8294
0
ftyou 101 Jun 01, 2010 at 23:17

Ok thqnks. In fact i want to use shaders to simulate materials normals and other things. So i need to keep a trace in memory of which shaders to apply to each part of vertex buffer in a node. So it will be :

bind(shader1) –> part of node 1
–> part of node 7
–> part of node 8

bind(shader2) –> part of node 1
–> part of node 7
–> part of node 8

Its that a good idea ?

It mean that the data are duplicated in GPU memory and standard memory ….