# K-D Tree + BSP Tree Hybrid?

This topic is 3845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

At the moment I'm building a a K-D Tree class for a small game engine. While building the K-D Tree I have found that by splitting the triangles every time I make two new nodes I actually end up creating much more geometry then I started with. I quickly learned that if I set the leaf size to only accept a small amount of triangles such as 0-80 that it would actually continually split until the app crashed. This outcome makes sense, but I had not expected it. Since then I upped the leaf size as well as adding an exit case which would not split if the cost of the split would be more then just making the current node into a leaf. These changes made the tree very stable. Since then I decided to test the K-D Tree class against some large scenes, and I am quite happy with the results for the visual purposes. Yet, I'm still a little disappointed since I was hoping I would be able to use the K-D Tree for both visual culling as well as collision detection. Then, I had an idea that I wanted to share and get some feedback on. My idea is that I would first split the scene geometry as explained above until I reached a leaf size of around 100-300 triangles. After the K-D Tree was created I would then take it's leaves which had geometry and compile a BSP Tree for each. When I wanted to cull the geometry outside of the frustum I could traverse the K-D Tree only down to it's leaves. Or if I wanted to do collision detection I could just continue past these leaves and move onto the BSP tree below. Do you think that this method would work well? Or, do you think it might be better to make two separate trees all together? Thank you very much. - Kiro

##### Share on other sites
Are you using the same geometry for rendering and collision?

##### Share on other sites
We have some very deep discussions on kd-tree building on ompf.org, which might help you a lot.

Also look out for Havran's notes on Surface Area Heuristics (ompf, too).

You might also be interested in bih-trees (a hybrid of kd-trees and bvh's, see ompf).

greetings,

seb.

##### Share on other sites
Quote:
 Original post by KiroNeemDo you think that this method would work well? Or, do you think it might be better to make two separate trees all together?

You need to be abit more specific here, if you're talking about a large static triangle mesh then i would have separate structures, i suggest not using BSP tree for collision detection i recommend using a bounding volume hierarchy (BVH) one of the advantages of BVHs are you don't have the issues of splitting primitives.

Unless you're only dealing soley with ray intersections spatial partitioning structures like bsp-trees for triangle meshes are unnecessary because you typically don't care for spatial ordering when it comes to collision detection.

I also suggest you make your kd-tree leaf sizes much bigger for rendering (on modern graphics cards), talking about in order of 10^3 to 10^4 triangles per leaf (which is murder for CD). Each leaf can go into a separate VB batches.

[Edited by - snk_kid on June 4, 2007 7:14:09 AM]

##### Share on other sites
Quote:
 Original post by snk_kidspatial partitioning structures like bsp-trees for triangle meshes are unnecessary because you typically don't care for spatial ordering

Really? Why not?
Only thing I can imagine where you don't need spatial ordering is, when your collision responder simply rollbacks a vector to the last position before the last "move", which is really a bad responder.

Searching for intersections using a good spatial ordering scheme (which results in early ray termination) is one of the reasons for the O(log(n)) complexity of ray tracing, and what is a better collision detector than a good ray tracer? If I'd write a game, I'd use my Ray Tracer for exact and damn fast collision detection (for example, I intersect about 2 Million Rays per Second with a 128 million+ triangles terrain).

Only thing plausible, where you don't care for the nearest intersection, is shadow rays (or visibility checking in a game, which is nothing else then a shadow probe).

greetings,

seb

##### Share on other sites
Quote:
 Original post by greenhybridReally? Why not?Only thing I can imagine where you don't need spatial ordering is, when your collision responder simply rollbacks a vector to the last position before the last "move", which is really a bad responder.Searching for intersections using a good spatial ordering scheme (which results in early ray termination) is one of the reasons for the O(log(n)) complexity of ray tracing, and what is a better collision detector than a good ray tracer? If I'd write a game, I'd use my Ray Tracer for exact and damn fast collision detection (for example, I intersect about 2 Million Rays per Second with a 128 million+ triangles terrain).Only thing plausible, where you don't care for the nearest intersection, is shadow rays (or visibility checking in a game, which is nothing else then a shadow probe).

You've seem to totally ignore the first part of that sentance which was "Unless you're only dealing soley with ray intersections" which isn't the case with general collision detection, he/she may want to collide all kinds of objects/entities like two triangle mesh bounding volume hierarchies or a BV and BVH or convex polygon/polyhedral and BVH, etc, etc.

By the way you still gain acceleration of ray intersections with BVHs, it's still a logarithmic time operation but in practice spatial partitioning structures are (slightly) more efficent than BVH exactly because of there strict spatial ordering but you pay for potentially (more like most definitely) having to split primitives or really, really long construction times to reduce the number of split primitives.

Collision detection libraries hardly use spatial partitioning structures except for specific cases like decomposing concave polygons into convex regions.

I don't see KiroNeem mention he's writing a ray tracer or doing purely ray intersections.

##### Share on other sites
And I said "spatial ... schemes are *one* of the reasons".

I don't see a reason why no other kinds of objects (objects in an abstract manner) than rays should benefit from spatial schemes, as they still gain much speed due to depth-first traversal (Jensen's Photon Mapping for example basically relies on sphere/kd-traversal). I don't see, too, which responder would be a good one without having the proper "nearest collision" information.

As for exponential building times: the Bounding Interval Hierarchy (or briefly BIH, Wächter, Keller; also deeply discussed on ompf.org), a bvh/kd-hybrid, builds in near-linear time and is dedicated to animated scenes consisting of tens of thousands of objects, and builds in some milliseconds (each frame), plus it creates a good approximation of Surface Area Heuristics.

##### Share on other sites
Quote:
 Original post by greenhybridAnd I said "spatial ... schemes are *one* of the reasons".I don't see a reason why no other kinds of objects (objects in an abstract manner) than rays should benefit from spatial schemes, as they still gain much speed due to depth-first traversal (Jensen's Photon Mapping for example basically relies on sphere/kd-traversal). I don't see, too, which responder would be a good one without having the proper "nearest collision" information.

Did i say they don't benefit? NO, i'm saying BVH have some advantages over spatial paritioning structures in the context of collision detection not ray tracing and BVHs are generally preferred in this context.

Quote:
 Original post by greenhybrid... As for exponential building times: the Bounding Interval Hierarchy ....

You you keep referring to papers/discussions specifically on the subject of ray tracing, where not talking about accelerating ray intersections, he/she hasn't even mentioned anything about ray intersections yet.

##### Share on other sites
There is a lot of good information here, and I will try and answer all of the questions about my system as I can. I would like to learn all I can, so if anyone replies fell free to go in depth.

Quote:
 Are you using the same geometry for rendering and collision?

In my original plan, everything would initially be based off of the same geometry, although in memory the geometry that is sent to the renderer and the geometry which is used for collision detection would be separate. The figured this would be the best method since the geometry in the K-D Tree leaves are compacted down into a OpenGL vertex array for quick drawing.

Quote:
 You need to be abit more specific here, if you're talking about a large static triangle mesh then i would have separate structures, i suggest not using BSP tree for collision detection i recommend using a bounding volume hierarchy (BVH) one of the advantages of BVHs are you don't have the issues of splitting primitives.Unless you're only dealing soley with ray intersections spatial partitioning structures like bsp-trees for triangle meshes are unnecessary because you typically don't care for spatial ordering when it comes to collision detection.

Yes, the levels would be large static triangle meshes. It's funny that you mention BVH since the system I have at the moment actually is one at heart. Each node in the scene graph has it's own bounding volume (Currently a AABB) and the node's bounding volume is guaranteed to always contain it's children's bounding boxes. The KDTree class is derived from a standard scene node so in essence the BVH is already there.

If I wanted to do collision detection with a BVH, I could just use the information already created by the K-D Tree, then make sure that the collision specific nodes continue to split at the K-D Tree leaves. Or do you think it might be better to still make a new tree completely?

Quote:
 I also suggest you make your kd-tree leaf sizes much bigger for rendering (on modern graphics cards), talking about in order of 10^3 to 10^4 triangles per leaf (which is murder for CD). Each leaf can go into a separate VB batches.

I have never built a engine before, so pardon my inexperience. Although from what I know a normal quake 3 level contains about 60,000 to 80,000 triangles. Certainly I would like the engine to be expendable, although I think initially my own levels really won't contain more then this. Therefore If I was to have my leaves cut out around 10,000 triangles I would only be left with about 8-10 leaves (Counting the triangles which would be split), which to me seems more inefficient then a lower count. 1000 would seem to work though.

Quote:
 I don't see KiroNeem mention he's writing a ray tracer or doing purely ray intersections.

I will be using rays in the engine, but in no way are they going to be the only thing that I will be using to perform collision detection.

Quote:
 We have some very deep discussions on kd-tree building on ompf.org, which might help you a lot.

Actually , when first trying to figure out some of the information I needed for building this I was on ompf.org searching through the forums. There is a lot of good information, although I was at some loss since it was all geared towards ray tracing.

Quote:
 Also look out for Havran's notes on Surface Area Heuristics (ompf, too).

This is actually what I'm using to make the K-D Tree.

Quote:
 You might also be interested in bih-trees.

I didn't see that on the site, I will go and look, although I think I may have been building one without knowing it. :p
-------------------------------------------------------------------------------

So from the information I'm hearing a BVH may be the best way to go for the collision detection side of things. This is perfect since I already have the base functionality built into my system. My questions so far, and a recap of the questions above are these.

Since I already have the BVH structure built into the K-D Tree nodes do you think it would be efficient enough to just continue to split the leaves into a BVH structure for collision detection?

If I have a scene with only around 60,000-80,000 triangles wouldn't it be backwards to have the K-D Tree end at about 10,000 triangles?

Also, I will look around on the net for this information, although what would you suggest as a good way to go about splitting a static mesh into a BVH?

- Kiro

##### Share on other sites
Quote:
 Original post by KiroNeemYes, the levels would be large static triangle meshes. It's funny that you mention BVH since the system I have at the moment actually is one at heart. Each node in the scene graph has it's own bounding volume (Currently a AABB) and the node's bounding volume is guaranteed to always contain it's children's bounding boxes. The KDTree class is derived from a standard scene node so in essence the BVH is already there.If I wanted to do collision detection with a BVH, I could just use the information already created by the K-D Tree, then make sure that the collision specific nodes continue to split at the K-D Tree leaves. Or do you think it might be better to still make a new tree completely?

That sounds okay since you can (re)use the same splitting strategy as the kd-tree for the AABB tree except you don't split primitives, you just stick ones straddling the splitting plane in either side containing it's centroid, recompute the bounds of each sub-list and recurse.

The only reason why i'd prefer keeping spatial structure seperate from the scene graph and separate from each other for each task (i.e rendering, CD, etc, etc) is you might want to support other structures or other BV types etc, etc. You will have slightly more optimized structures for the task at hand and more importantly this can give loose coupling, the only downside is synchronization.

Quote:
 Original post by KiroNeemI have never built a engine before, so pardon my inexperience. Although from what I know a normal quake 3 level contains about 60,000 to 80,000 triangles. Certainly I would like the engine to be expendable, although I think initially my own levels really won't contain more then this. Therefore If I was to have my leaves cut out around 10,000 triangles I would only be left with about 8-10 leaves (Counting the triangles which would be split), which to me seems more inefficient then a lower count. 1000 would seem to work though.

There is no need to pardon yourself! i'm just giving a you a tip/advice, modern graphics cards like large batches of triangles, give them small ones is going to hurt performance, you could probably send that whole level to a VBO without any culling and still get decent performance. It's not a big deal to change, you can see for yourself just by changing a simple constant.

Quote:
 Original post by KiroNeemI will be using rays in the engine, but in no way are they going to be the only thing that I will be using to perform collision detection.

And BVHs are fine for that, granted there not as efficent as spatial partitioning structure but the difference isn't that huge and your not writing a ray-tracer so you'll hardly notice the difference. The important thing is you don't have the issues of splitting primitives and BVH are easier to update and handle dynamic/deformable meshes.

Quote:
 Original post by KiroNeemIf I have a scene with only around 60,000-80,000 triangles wouldn't it be backwards to have the K-D Tree end at about 10,000 triangles?

You can always tweak the value of your ending criteria, try around 3000-5000 triangles per leaf to start and then go and up and down see what you get.

##### Share on other sites
Quote:
Original post by snk_kid
Quote:
 Original post by greenhybridAnd I said "spatial ... schemes are *one* of the reasons".I don't see a reason why no other kinds of objects (objects in an abstract manner) than rays should benefit from spatial schemes, as they still gain much speed due to depth-first traversal (Jensen's Photon Mapping for example basically relies on sphere/kd-traversal). I don't see, too, which responder would be a good one without having the proper "nearest collision" information.

Did i say they don't benefit? NO, i'm saying BVH have some advantages over spatial paritioning structures in the context of collision detection not ray tracing and BVHs are generally preferred in this context.

Quote:
 Original post by greenhybrid... As for exponential building times: the Bounding Interval Hierarchy ....

You you keep referring to papers/discussions specifically on the subject of ray tracing, where not talking about accelerating ray intersections, he/she hasn't even mentioned anything about ray intersections yet.

Afair, Donald E. Knuth himself said once that using italics is way much nicer way to exclamate things than those phats (bold fonts are felt by readers to be kinda aggressive). Just a quick hint if you ever gonna write a paper.

The one reason why I recommend ray-tracing techniques is that they are provide the fastest way of finding, well object/scene-intersections. Other schemes are definitely easier to learn, sure. But as your going for high-performance ray/scene-intersections, a couple of randomly distributed rays might outperform true object/object intersections. For sure, then those are only be left approximations. But on the other hands, having such an engine is a really helpful and powerfull tool for an awesome wide range of applications:

(mentioning pure ray/scene intersection in the following list)

-> high performance and unbeatable ray/scene intersection
-> highly dense particle systems
-> high performace object/object intersection
-> global illumination texture baking
-> thousands up to millions of ricochets per second in a war-game ;)
-> photon mapping
-> checking percentage of visibility for objects behind other objects
-> approximating true radars or waves in general in sims
-> actually misuse the component for creating high quality stills in your game
etc.

I did not say BVH's are evil. I simply recommended ray-tracing techniques because of their wide applicability.

aaand: A lot of acceleration schemes can be borrowed from ray-tracing with at least a glimpse of imagination.

I guess the next time you gonna trun on caps-lock?

quake III ray traced to the bones (with approximated object/object detection)

KiroNeem, those are for you :)

original paper on BIH's

BIH discussions I meantioned, I hope that helps a bit :)

edit secundo:

KiroNeem, as you already use SAH (besides: building a "correct" SAH/kd-tree is pretty hard and it takes some ammount of time to test if they do what you intend): Do you also use the cost for deciding if a further split makes the crop? If not, you have simply to calculate the cost of the node you're in, and than sum up the cost of both children plus some cost for the split itself. Now, if the summed up cost+split_cost is higher than the cost of the current node, you stop further subdivision

furtherSplit = currentNode_cost > (leftChild_cost+rightChild_cost+splittingCost)

[Edited by - greenhybrid on June 4, 2007 1:44:55 PM]

##### Share on other sites

This topic is 3845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628682
• Total Posts
2984220

• 12
• 13
• 13
• 10
• 10