title: Nearest neighbor search in Octree
body: <p>How does a NN algorithm work on an octree? I have searched for a good explanation, but most of the time people just say used KD-tree instead. I cant do it, i need to visualize NN algorithm on octree step-by-step.</p>
  
  <p>As i can think the most logical way would be to:</p>
  
  <p>1) Find the sub-octant where the point belongs to. </p>
  
  <p>2) Calculate distance to the nearest point in that octant</p>
  
  <p>3) Check if there is any overlap with neighboring octants within that distance</p>
  
  <p>4) If a closer point is found, recalculate the search distance.</p>
  
  <p>5) Repeat until all possible octants have been traversed</p>
  
  <p>6) Return the closest point</p>
  
  <p>But i cant think up a good step by step visualization for this one.</p>