# k-d tree compiler, need thoughts

## 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 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 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.

##### 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 on other sites
ABT is generally best used in datasets involving many thousands of polygons. I'm not sure that it'd be best for a GBA, perhaps a quake-style BSP might be better.

##### Share on other sites
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 on other sites
Quote:
 Original post by Anonymous PosterNote 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 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 on other sites
Quote:
 Original post by funkeejeffounetI 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 funkeejeffounetBy 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 on other sites
Quote:
 Original post by Anonymous PosterNote 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 on other sites
Quote:
Original post by Assassin
Quote:
 Original post by Anonymous PosterNote 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 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.

## 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

• ### Forum Statistics

• Total Topics
628354
• Total Posts
2982236

• 10
• 9
• 11
• 24
• 11