[vtkusers] KDTree timing demo

[Andy Bauer]

I broke up the times between kdtree build time and search time and the
search time dominates the build time.

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.

Andy

On Wed, Sep 29, 2010 at 12:28 PM, David Doria <daviddoria at gmail.com> wrote:

> On Wed, Sep 29, 2010 at 11:36 AM, Andy Bauer <andy.bauer at kitware.com>wrote:
>
>> 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
>
>
> The octree demo:
> http://www.vtk.org/Wiki/VTK/Examples/Cxx/DataStructures/OctreeTimingDemo shows
> a nice trend with only 1k trials. I also tried with 10k and the result is no
> better.
>
>
>> Also, at some point there will only be 1 point per kdtree bin in which
>> case refining the kdtree more is useless.
>
>
> 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.
>
> David
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20100929/dbf5c742/attachment.htm>