k-d tree compiler, need thoughts
Author
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.
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
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
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.
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.
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.
Author
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.
- 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.
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)
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)
Author
Janos, I know it was no joke, but I gave the same link in my first post ;-)
So your telling me to reference a same face(the problematic ones) in more than one leaf instead of slicing them?
Cheers, Jeff.
So your telling me to reference a same face(the problematic ones) in more than one leaf instead of slicing them?
Cheers, Jeff.
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
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
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.
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.
Author
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
