Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / kd-trees Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Eddy Akman

April 16, 1999, 06:06 PM

I was thinking about those kd-trees, how they are closely connected to octrees as they
also subdivide space into 8 smaller spaces.. (right?)

My questions: (as there doesn't seem to be a single paper on this subject)

- the kd-tree is like an octree, as it splits space using axis alligned 'planes'?
- the kd-tree subdivides space, keeping the polygon count on both sides the same
or almost the same? What is a fast way to do this? I figured one method out myself
but I'd like to get some input on this..

Ok

Thanks a lot and stuff

Greetz,

----------
Eddy Akman
Graphix coding dude

 
Eddy Akman

April 17, 1999, 04:19 AM



Nevermind. I figured it out.

 
panic

April 17, 1999, 08:22 AM


hmmm... yeah, well, good for you, but how about you share your knowledge?
tell us you method and how you managed to work out your problem... ok? :)

-panic

 
panic

April 17, 1999, 08:24 AM


hmmm... yeah, well, good for you, but how about you share your knowledge?
tell us you method and how you managed to work out your problem... ok? :)

-panic

 
Eddy Akman

April 19, 1999, 11:40 AM




>hmmm... yeah, well, good for you, but how about you share your knowledge?

Sure no problem.

>tell us you method and how you managed to work out your problem... ok? :)

My method? My method to do what exactly?

How did I work out my problem... hmmm, well by thinking logically (ofcourse), and
doing some simple examples in your head. I find it easy to think about these kinds
of problems when I'm doing something else (something boring, like studying ;))
And ofcourse, by reading as many articles/papers/tutorials about it, although
that didn't quite help on the kd-tree thing, as there don't seem to be any papers
on them. The concept is really easy though, and I had this chat-log of a guy called
Harmless (doesn't sound familiar, does it? :))), which let me see the light.

Hmmm, I'd rather like to talk via ICQ, if you have more questions..

ICQ UIN# 21125993

Greetz,

------
Eddy Akman



 
Harmless

April 29, 1999, 06:07 PM


Eddy Akman wrote:
>>I was thinking about those kd-trees, how they are closely connected to octrees as they
>>also subdivide space into 8 smaller spaces.. (right?)

Actually a kd-tree subdivides into 2 smaller spaces, something that subdivides into 8 smaller spaces with dynamic splitting planes is an 'adaptive octree', which is a horse of a different color.

A kd-tree is basically an axis aligned bsp tree where you choose the plane to split upon based on your height in the tree. i.e.

level 0 - split on the x plane
level 1 - split on the y plane
level 2 - split on the z plane
level 3 - split on the x plane
level 4 - split on the y plane
level 5 - split on the z plane
...

This is a classic kd-tree, and there exist papers on the subject, off the top of my head Seth Teller uses kd-trees in his paper on visibility determination in densely occluded environments.

>>My questions: (as there doesn't seem to be a single paper on this subject)
>>
>>- the kd-tree is like an octree, as it splits space using axis alligned 'planes'?
>>- the kd-tree subdivides space, keeping the polygon count on both sides the same
>> or almost the same? What is a fast way to do this? I figured one method out myself
>> but I'd like to get some input on this..

Note that a kd-tree splits on one plane at a time. This allows it to fit better than an adaptive octree, because the planes in the children can be at different offsets.

One modification to the 'classic' kd-tree structure is to allow the choice of plane to split upon to vary at each level, this drives up your preprocessing cost by about a factor of 3, and
adds a small bit of data to the tree, but can theoretically produce fewer splits, because you can choose your partitioning plane, by which plane when it would divide the child sets into two equal buckets would produce the fewest splits. Unfortunately this optimization, much like the balance vs. split optimization in a BSP tree can also into degenerately shaped kd-tree nodes if left to run unchecked.

-Harmless

 
This thread contains 6 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.