Sign in to follow this  
funkeejeffounet

k-d tree compiler, need thoughts

Recommended Posts

Hi everyone, I'm actually building an engine for a race game, and I was thinking about the structure I'll use for partitionning the space. Since I've used a lot BSP trees for indoor and that a race track is more outdoor, it was clear that I could not use them here as finding the right partition planes is really hard. I knew about quadtrees and octrees and they seem to split too "naively" the space(doesn't care about balancing the tree and might have leaves with much empty space). After searching, I discovered about k-d trees. What is wonderfull about the internet is how many pages are pointed for some threads but how poor the related articles are. Here is the best link about them, it is a PhD Thesis and treat really seriously and in depth about those trees : http://www.cgg.cvut.cz/~havran/phdthesis.html I've read it carefully (and gave me such a headache), but there are still some things I'm not clear about and I would like the advice of people who are familiar with k-d trees in the video game domain. 1) Do you think a k-d tree is the best choice for a race game à la "wipeout"? 2) Do you alternate the splitting plane consecutively(x then y then z then w then...)? If no, how do you do it? 3) I don't want to place the splitting plane as a median(half the bounding box) cause I think balancing is important. What heuristics can I use to select the good location of the plane? 4) What are your criterias for stopping the splitting, ie making the leaves? 5) When a plane splits polys in a node, do I subdivide the polys like in a BSP so that all are front facing OR back facing? 6) I've thought of stopping the node splitting when a certain number of polygones is left(like less than 20) or when the polygons left form a convex area(like in quake). How do you know if a set of polygons form a convex area? Also, I'd like to precalculate sorting, what can I do beside putting in the leaves a small bsp tree for the non convex areas? 7) Any details you estimate important :) Many many thanks in advance to the ones who will help me. Cheers, Jeff.

Share this post


Link to post
Share on other sites
try this,
it's worth the read (although the results are shown in the most unclear way)
http://www.cgg.cvut.cz/~havran/phdthesis.html

a kd tree should duit your need.
A good way to do splitting is to have a cost estimator and try many choices, then pick the best
having empty leaves is good if they contain a lot of free space

Share this post


Link to post
Share on other sites
ok more precise:

1: yes, why not
2: use a cots function
3: yes, balacing is very important
4: stop when the estimated cost increases as you split
5: the polygons are not on the split plane, so not such descision is relevant
6: cf 4
7: make it work first with an alternating, median split algo.
have some kind of a visual debug. Believe me, it WILL save you a lot of time.

Share this post


Link to post
Share on other sites
I sugest you look into ABT (Adaptive Binary Tree), as it is somehow evolved verison of KD tree. You can find alot about it together with anwsers on most your questions here. Once you'll read those threads feel free to ask some more questions, or post results of your implementation.

Share this post


Link to post
Share on other sites
Janos, thanks for the link.... lol

- I know I must use a cost functiun of course, my question is more of wich functiun it is and what parameters are involved.
- Thanks for approving that balancing is important(althought the Thesis doesn't say so exactly, weird...), but how can you achieve it?
- Kd trees are based on axis aligned planes, those split the polygons inside the node and there is 99.9% chance that at least one polygon inside the node will be crossed by the plane, so yes there is a problem : I can put these polygones as being part of the left AND right child or I can split it in two along the plane. Wich is better?
- Still have the convex area detection not cleared, I searched google but nothing came out.
- Yeah, I think I'm gonna do a world viewer in OpenGL to see the splitting process.

Thansk for the link _DarkWing_, I'm still on it, but if anybody has other ideas or advices I'd be glad to listen to them.

Cheers, Jeff.

Share this post


Link to post
Share on other sites
The link was no joke.
The pdf is in english even though the first pages are not.

you have to split the primitives as you cut the space in half, but the best in the end is to have the unsplit primitives referenced more than one leaf.

Enjoy coding that. Then you can write a small raytacer for debugging. I've done that a few weeks ago, and it's cool (and realtime)

Share this post


Link to post
Share on other sites
Sorry about the link...
Do reference the face.
You will not be able to find perfect splits all the time (almost never actually)
I use some function like this:
attempt a split
I have n original primitives, and I then obtain k and l primitives
I then have a partial score that is
pscore1 = max(k,l)
I then compensate that score for the extent of the kd tree current node. imagine that we are splitting along the x-axis
then
pscore2 = max(k,l)/(Leaf.extent.x/Leaf.diagonal.length)

I then consider the case in which all primitives are on one side of the plane, and I use the score
pscore3 = max(k,l)*Leaf.extent.x(Leaf.extent.x/Leaf.diagonal.length)*Proportion_of_full_side

Proportion_of_full_side is the extent (extent.x in this case) of the sub leaf that contains all the primitives divided by the extent of the current leaf.

the final score I use is min(pscore2, pscore3)
I add a termination criteria based on the size of the leaf to avoid infinite recursion due to numerical limits.

The resuls are great.
I get something that is about 20 steps deep on average to contain more than 1e6 triangles will about 8 triangles per leaf.

A typical ray trace goes through about 20 nodes and tests around
5 to 10 triangles.

I can send and individual ray in about 5e-6s

Share this post


Link to post
Share on other sites
I've posted that link becouse it anwsers most of your questions. :) But anyways...

1) Yes. Together with eficient culling methods this is very good.

2,3,4) This is all related. There is one big function that selects splitting plane. It selects the split axis and thare on that axis to split the node. The value of function is weightedn sum of partial criteria functions.
- space localization : splitting by largest axis first ==> max( x, y, z )
- both childs must be about the same volume ==> min( abs( volume1 - volume2 ) ) / max( volume1, volume2 )
- both childs must have about same number of triangles ==> min( abs( count1 - count2 ) ) / max( count1, count2 )
- minimum splitting triangles ==> num( num_tris_split ) / all_tris
- minimum number of materials ==> ( mat0 + mat1 ) / numMat

There are number of ways to selecting (testing) split points. You could use discreet steps on each axis, some kind progresive refinement, use the fact that some of functions are smooth, use NN or something completly different.

5) Very important point. Split only when you absolutly have to. By introduceing only a small overgrowth factor, split count goes down dramaticly on the cost of slightly worse culling. I strongly sugest doing this.

6) For stopping criteria my verison uses number of triangles in node and it's depth. For checking if set of triangles is convex there should be some existing algoritems. I don't know anyone by heart, but searching trough math forum or google should turn up something. Why do you need sorting?

7) There are number of thing to watch out about when implementing this... And one of the hardest ones is selecting weights of split criteris funtion. Here you are more or less on your own. You just have to test what turns out good for your dataset.

Share this post


Link to post
Share on other sites
Thks guys,

I need sorting cause the engine will be a software one for the GameBoyAdvance, and I will combine the drawing with a c-buffer.
Besides, even for hardware accelerated devices I think that sorting might be good cause when drawing in a front to back order with the z-buffer activated, each pixel depth will be written only once, then it will only be read memory access(as the closest pixels is already drawn). Depends how far you wanna optimize.

I'm doing computer studies and I've seen some optimization methods like tabu lists, random walk, genetic algorithms. I don't know about neural network but the things I know might help. The problem is the heuristic, it is hard to find a functiun that approches our idea(best splitting plane). Someone have some thoughts?
Or maybe I'm gonna use a standard method(vertices) or a random perturbation of the median.

Cheers, Jeff.

Share this post


Link to post
Share on other sites
As was previously stated, you need to do research on the Adaptive Binary Tree.

It's a derivation of the classic kD-tree algorithm. It has a well defined heuristic for calculating the optimal splitting plane.

A simple forum search and an hours worth of reading and you'll be an expert. Good luck.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Note that the people suggesting the use of ABT's have never in their lives implemented such a thing and are really not in a position to comment on their use for this particular problem.

People, throwing buzzwords around doesn't benefit anyone.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Note that the people suggesting the use of ABT's have never in their lives implemented such a thing and are really not in a position to comment on their use for this particular problem.

Alot of people here (including me) have sucesfuly implemented ABTs, BSPs and alot of other scene-structures. So stop posting as AP and give some usefull anwsers.

The OP didn't mention he was working on GBA engine until the last post so that may change things a bit.

Share this post


Link to post
Share on other sites
It changes absolutely nothing if it is for the GBA or not, the engine will be software but I still need a structure for partitionning.

BSP are great for some levels, especially the ones where you have a geometry that can help choosing a good splitting plane. That is why in indoor games it is used, because there are many "vertical" polygones representing walls, and by testing all of them in each node you can find the best(linear method) one.
Unlike indoor games, outdoors games are more problematic, you cannot benefit from the geometry for finding spliiting planes. That is why you use quadtree(or octrees). But balancing cannot be achieved especially in levels where the polygones are not equally distributed int he space.

That is why I begun thinking of a more intelligent way of positioning the plane and I found on the net about kd trees. I don't see what is the problem of using them on the GBA, if you are referring to the number of polygones usually contained in the leaves(1000 to 2000 from what I read), you are using these numbers because of the GPU's and to take benefits of vertex buffers(lesser polygones wouldn't be worth).
I'll definitely go to like 200 polygones or less, and a small BSP tree will be in each non convex leaf for Z-sorting.

By the way, couldn't find docs about detecting convex areas so please someone help, at least give me a hint :) (I've searched the forums and posted in the math section).

Cheers, Jeff.

Share this post


Link to post
Share on other sites
Quote:
Original post by funkeejeffounet
I don't see what is the problem of using them on the GBA, if you are referring to the number of polygones usually contained in the leaves(1000 to 2000 from what I read), you are using these numbers because of the GPU's and to take benefits of vertex buffers(lesser polygones wouldn't be worth).
I'll definitely go to like 200 polygones or less, and a small BSP tree will be in each non convex leaf for Z-sorting.

Yes, I was mainly refering to this. I don't know how many polys GBA/your engine can handle. I'm also not sure how number of triangles versus size of triangles works in your case.

Quote:
Original post by funkeejeffounet
By the way, couldn't find docs about detecting convex areas so please someone help, at least give me a hint :) (I've searched the forums and posted in the math section).

Here is one of top of my head for connected meshes, so I don't know if it works. For each edge, calculate angle between triangles that share it (counting winding, so you get angle in range 0-360). If angle is more than 180 degrees then it's not convex. I have no idea how to do it with "loose" triangles.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Note that the people suggesting the use of ABT's have never in their lives implemented such a thing and are really not in a position to comment on their use for this particular problem.

People, throwing buzzwords around doesn't benefit anyone.


Well, I'd like to say that I've implemented both ABT and BSP, with quite good results, but that my experience shows ABT to be suboptimal when not being used to accelerate the rendering of large batches (2000+ polygons). BSP is better suited to a renderer based on a c-buffer, as it can give you absolute front-to-back visiblity of all polygons in the scene.

Share this post


Link to post
Share on other sites
Quote:
Original post by Assassin
Quote:
Original post by Anonymous Poster
Note that the people suggesting the use of ABT's have never in their lives implemented such a thing and are really not in a position to comment on their use for this particular problem.

People, throwing buzzwords around doesn't benefit anyone.


Image Hosted by ImageShack.us

Share this post


Link to post
Share on other sites
I'm gonna use bsp for the polygon inside the leaves.
But I cannot BSP the whole map, I said why earlier.

If someone has another idea for sorting polys inside the leaves I'm curious about it cause splitting is scaring me here.
Maybe can I stop recursing when only a poly is left in the leaf?
But then what about the depth of the tree?(levels will have approximatively 5000 polygones cause it is a GBA).

Cheers, Jeff.

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