I broke up the times between kdtree build time and search time and the search time dominates the build time. <br><br>I'm guessing that the problem is that the grid isn't suited for the kd tree point locator. This happens when the points have some "uneven" clustering that results in the geometry of the bins in the kd tree to have large aspect ratios (1 or 2 direction lengths dominates the others). If you try an image data/uniform grid with the cells having equal lengths on each side you should see the timing drop down as the number of kd tree levels is increased.<br>
<br>Andy<br><br><div class="gmail_quote">On Wed, Sep 29, 2010 at 12:28 PM, David Doria <span dir="ltr"><<a href="mailto:daviddoria@gmail.com">daviddoria@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div class="gmail_quote"><div class="im">On Wed, Sep 29, 2010 at 11:36 AM, Andy Bauer <span dir="ltr"><<a href="mailto:andy.bauer@kitware.com" target="_blank">andy.bauer@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
You may want to break up the timing into the cost of building the tree and the time to do the searches. I'm not sure a 1000 searches is enough to see that much of a difference</blockquote><div><br></div></div><div>The octree demo: <a href="http://www.vtk.org/Wiki/VTK/Examples/Cxx/DataStructures/OctreeTimingDemo" target="_blank">http://www.vtk.org/Wiki/VTK/Examples/Cxx/DataStructures/OctreeTimingDemo</a> shows a nice trend with only 1k trials. I also tried with 10k and the result is no better.</div>
<div class="im">
<div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Also, at some point there will only be 1 point per kdtree bin in which case refining the kdtree more is useless.</blockquote>
<div><br></div></div><div>Yes, this is exactly what I am trying to see :) In the octree demo, there is a decay in runtime and then it is very flat after a point (this is where you should set the tree/hopefully the automatic parameters end up here). With the KDTree the runtime doesn't seem to vary in a sane way with the depth of the tree.</div>
</div><div><br clear="all"><font color="#888888">David</font></div>
</blockquote></div><br>