# Some KD-tree construction help please

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

## Recommended Posts

i have a purely programming related question about kd-tree construction. however, im asking it here nonetheless, since i know there are people in this forum who have tackeled this precise problem before, so im most likely to get an answer here. usually im not too fond of people handing me a solution, but i dont find this problem particulair interesting, id rather get on with the things that do interest me. im pretty much done with my kd-tree construction code, or atleast i hope so. my problem is with splitting the primitives and splitlists for passing down into children. i dont plan on rebuilding the list of splitlists at each level, since that would be quite bad for the timecomplexity of the algorithm. however, the problem is both lists can be split completely, but are partly duplicated. this means that maintaining the pointers between them is nontrivial, and is what my problem boils down to. if you havnt been working on this yourself, dont bother with my code below. however, can someone who has already done this give me a solution? am i even on the right track? couple of notes: primitive is an array of type Carrier. Carrier is a class that basicly consists of a pointer to a primitive, its potentially reduced boundingbox, and six pointers to the splitplanes it gives rise to (but im not even sure if i need these). split is an array of three(one for each axis) sorted linkedlists of type Plane. a plane has two dynamic arrays of pointers: one pointing to the carriers that formed it from the left and one from the right. this information will be used to determine the amount of primitives left and right of a plane. the code is now in broken state. however its very clean imo, and it should be obvious which piece of code should be doing what. if you can tell me how to alter this, or give me another solution, id be most gratefull.
if (currentcost < bestcost){
//tie off
return new Node.Leaf(primitive);
}else{
//split primitives
Carrier[] leftprimitive = new Carrier[bestplane.left+bestplane.split];
Carrier[] rightprimitive = new Carrier[bestplane.right+bestplane.split];

uint l = 0, r = 0;

for (uint i = 0; i < primitive.length; i++){
if (primitive.aabb.min.component[bestaxis] >= bestplane.position)
primitive.left = false; else primitive.left = true;
if (primitive.aabb.max.component[bestaxis] <= bestplane.position)
primitive.right = false; else primitive.right = true;

if (primitive.left && primitive.right){
leftprimitive[l] = primitive; l+=1;
rightprimitive[r] = new Carrier(primitive); r+=1;
}else if (primitive.left){
leftprimitive[l] = primitive; l+=1;
}else if (primitive.right){
rightprimitive[r] = primitive; r+=1;
}
}

//split planes
for (ubyte axis = 0; axis < 3; axis += 1){

if (axis == bestaxis){
//list split
for (i; !(i.data is bestplane); i = i.next){
}
bestplane.max = null;
for (i; !(i is null); i = i.next){
}

}else{
//list ripped
Plane plane = i.data;

Carrier[] leftmin, leftmax, rightmin, rightmax;

for (uint j = 0; j < plane.min.length; j+=1){
if (plane.min[j].left) leftmin ~= plane.min[j];
if (plane.min[j].right) rightmin ~= plane.min[j];
}
for (uint j = 0; j < plane.max.length; j+=1){
if (plane.max[j].left) leftmax ~= plane.max[j];
if (plane.max[j].right) rightmax ~= plane.max[j];
}

if (leftmin.length != 0 || leftmax.length != 0)
if (rightmin.length != 0 || rightmax.length != 0)

}
}
}

//split aabb
leftaabb = rightaabb = aabb;
leftaabb.max.component[bestaxis] = rightaabb.min.component[bestaxis] = bestplane.position;

//recurse
return new Node.Split(bestplane.position, bestaxis,
Refine(leftaabb, leftplane, leftprimitive, level+1),
Refine(rightaabb, rightplane, rightprimitive, level+1));



##### Share on other sites
My question will be why are you bothering about an hypothetic "timecomplexity" problem (which solution wouldn't be trivial) if you don't have, *first*, a working implementation to profile?

On the first glance of your self proclaimed very clean source i see a profusion of dynamic allocation in every loops. That would worry me.

And i've done what you describe for a BVH SAH compiler. I wouldn't do it that way for a kd-tree, and in fact didn't.

##### Share on other sites
Quote:
 Original post by tbpMy question will be why are you bothering about an hypothetic "timecomplexity" problem (which solution wouldn't be trivial) if you don't have, *first*, a working implementation to profile?

well, its not really hypothetic. adding another loop inside the existing ones is going to have quite a predicatable effect, no?

Quote:
 On the first glance of your self proclaimed very clean source i see a profusion of dynamic allocation in every loops. That would worry me.

clean in terms of readability. if i was a good programmer, which i am by no means, i wouldnt be asking this question. what dynamic allocation (that might be avoided) are you referring to btw? primitivepointers and splitplane-linkedlistnodes will need to be duplicated no matter what, which requires storage unfortunatly. i planned on reusing linkedlistnodes where possible, but id rather first get it working before playing with readability and bugsensitivity like that.

Quote:
 And i've done what you describe for a BVH SAH compiler. I wouldn't do it that way for a kd-tree, and in fact didn't.

can you give me any reasons? i know someone on this forum claimed he had archieved O(nlog(n)) treebuilding time. afaik that requires sorting and reusing your splitplanes, because if you dont, counting the amount of primitives on either sides of your planes is going to turn timecomplexity into O(n^2log(n))

Quote:

i know that is something important aswell. however, if i actually want to try out different heuristics before i turn 60, being able to build my tree in reasonable time isnt a bad idea.

however, if i cant find a good solution, ill try it the brute force way for now. i dont like leaving a piece of code thinking itssuboptimal, but then again i have more important things right now.

##### Share on other sites
Quote:
 Original post by Eelcowell, its not really hypothetic. adding another loop inside the existing ones is going to have quite a predicatable effect, no?

Predictable? Locally, yes. And that tells nothing about the relative merit of your alternative. So...
Have you profiled that code? If not, then it's hypothetic.

Quote:
 what dynamic allocation (that might be avoided) are you referring to btw?

There's no need to dynamically allocate anything (beside nodes themselves) as everything can be bounded right when you start the compilation.
It might not be practical, or desirable tho.

On the other hand allocating things in a hot loop is a no-no in my book and you do that in every single one of them.

Quote:
 can you give me any reasons?

That would be barking at the wrong tree.
Too complex (because of tracking induced by clipping, duplication etc), hence little chances to be more efficient.
And it makes it pretty impossible to throw in some splits in out of the wazzo on the fly. And you'll want to be able to do that.

Quote:
 however, if i actually want to try out different heuristics before i turn 60, being able to build my tree in reasonable time isnt a bad idea.

I reconstruct my potential split list at every level and then some, yet i get a tree compiled for 120k tri in like 30s... give or take 30s ;)
I must say that it could be faster and without doubt, cleaner.

##### Share on other sites
Quote:
Original post by tbp
Quote:
 what dynamic allocation (that might be avoided) are you referring to btw?

There's no need to dynamically allocate anything (beside nodes themselves) as everything can be bounded right when you start the compilation.
It might not be practical, or desirable tho.

On the other hand allocating things in a hot loop is a no-no in my book and you do that in every single one of them.

in conditional statements though. if i have to split a primitive, i have to create a new carrier object, but i dont see how this is compilation bounded. using a memory manager for things like listnodes would probably be a good idea. however, this is probably pretty much taken care of by D's garbage collector. anyway, i dont realy care about all that yet: i want my basic algorithm working first.

Quote:

Quote:
 can you give me any reasons?

That would be barking at the wrong tree.
Too complex (because of tracking induced by clipping, duplication etc), hence little chances to be more efficient.
And it makes it pretty impossible to throw in some splits in out of the wazzo on the fly. And you'll want to be able to do that.

yeah, its pretty complex indeed, much more complex than i anticipated, hence why i came here to ask for help. a good thing for my ego its not just me. :P

Quote:

Quote:
 however, if i actually want to try out different heuristics before i turn 60, being able to build my tree in reasonable time isnt a bad idea.

I reconstruct my potential split list at every level and then some, yet i get a tree compiled for 120k tri in like 30s... give or take 30s ;)
I must say that it could be faster and without doubt, cleaner.

that certainly sounds promising. id be content with that kind of performance.

would you mind telling me what your method of counting left/split/right counts for splitplanes is then? how do you handle double planes, for instance?

right now i generate my initial list like this: create all planes in an array, radixsort it, and take out the doubles while converting it to a list. i could do away with the whole list thing if i regenerate splitplanes anyway, but taking out doubles is still needed later on.

the sortedness and uniqueness is exploited to do left/split/right counts in linear time. so thats all linear so far.

some whopping constants getting introduced, but doing one node will be linear nonetheless. certainly a lot simpler to code. thanks for helping me realize this! im curious as to how it will perform.

##### Share on other sites
Quote:
 Original post by Eelcoif i have to split a primitive, i have to create a new carrier object, but i dont see how this is compilation bounded.

You have a triangle soup. Let's pretend that none gets created along the way.
The further you recurse, the less you have to deal with (or something's wrong).
And you can generate a maximum of 2 splits per triangle (well, using the origial heuristic).
It's bounded.

Quote:
 would you mind telling me what your method of counting left/split/right counts for splitplanes is then?

I think i've used every possible schemes at one point or another :)

Right now i'm using a variation of Jacco's method, not because it's more efficient but because it allows for, graceful, arbitral injection of new splits.

Quote:
 how do you handle double planes, for instance?

I don't get what you mean by double planes exactly.

##### Share on other sites
Did you try my approach that I described in detail in another thread (search function disabled, can't look it up)? I also get 30s builds for 100k sets.

##### Share on other sites
Quote:
 Original post by phantomusDid you try my approach that I described in detail in another thread (search function disabled, can't look it up)? I also get 30s builds for 100k sets.

yes, indeed im using (i believe it was yours atleast) method for doing left/split/right counts. create splits with left=1 or right=1, sort the splitlist, merge doubles, and go trough the list once to integrate left/right counts. works perfectly fine, and is linear in the number of splits if you use radixsort. cant be beaten afaik. im not too happy about having to do all that on a per-split basis, but i suppose its the best compomise between simplicity and speed.

1. 1
2. 2
Rutin
23
3. 3
JoeJ
20
4. 4
5. 5
gaxio
13

• 24
• 40
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631734
• Total Posts
3001933
×