   kD Trees
  I'm asking for help and/or direction here because I didn't come up with decent results (i thought) when using google.  I need a partitioning system that I can search through to locate a point (which node the point is in).  I searched for kD Trees b/c every article says "yeah, these are good for searching."  But the explanations are crap.  Is it just as easy to search through an ordinary BSP tree, because I have a lot of sources with info about those.  Is the only difference btw a kD Tree and an ordinary BSP tree that the kD Tree trys to partition a space into half-spaces, ie convex node spaces with an equal number of polygons (or points..whatever) in each child?[edited by - leinad on July 30, 2003 3:49:43 PM]
  A KD tree is a BSP tree with axis-aligned splitting planes. Left-balanced kd trees are the most common, and they are constructed as follows:1. Pick a splitting axis (usually the axis with the most variation in the points you are trying to store)2. Sort all points along that axis3. Find the middle point (aka the median)4. Repeat step 1 using all points to the left of the median5. Repeat step 1 using all points to the right of the median (including the median point)Thus each bucket contains an equal number of points at each splitting node.If you line this up right in memory, you can store the entire tree in a flat heap and access it like an array. Each node of the tree just needs a flag of what axis it splits on (since all points eventually become a median) or if it is a leaf (has no child points).To locate a point (or many points), all you have to do is look at a median point, see what axis it is split along, and compare its value to your threshold value. Choose the left or right branch accordingly, rinse, and repeat. You can follow the tree all the way down to the leaves in O(log n) (IIRC, it may be n log n but that doesn't sound right) using this approach.   [edited by - ApochPiQ on July 30, 2003 4:38:23 PM];  The splitting planes have to be axis-alligned? and do you mean world-axis?  And are all planes paralles to only two axes of the three (x-y-z)?  Ie, is this like using a 2D quadtree in a 3D terrain engine? ;  All splitting planes simply ARE world-axis aligned. That's what a kd tree is.Each plane is parallel to ONE axis, and is either referred to by the axis it is parallel to (x plane) or the two axes it is not (yz plane, my personal preference). No, it is not like a quadtree. Each node has only two splits, not four like a quadtree. However, the binary split at each node may be one of 3 axes or a leaf terminator. [edited by - ApochPiQ on July 31, 2003 8:33:19 AM]