# k-d tree compiler, need thoughts

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

## Recommended Posts

##### 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 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 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 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 on other sites
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 on other sites
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.

##### Share on other sites
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 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 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.

• 17
• 11
• 11
• 9
• 49
• ### Forum Statistics

• Total Topics
631394
• Total Posts
2999753
×