[vtkusers] Re: Speed up vtkKdTree::FindClosestPoint

[lee ann fisk]

Hello Sigmund.  I'm sorry my code caused you this trouble.  A
few months ago I pulled the intersection calculations out of
vtkKdTree into vtkBSPIntersections so that we could someday use the
intersection calculations also with partitionings calculated
using the Zoltan library.  I did it quickly, and didn't notice
that every time ComputeIntersectionsUsingDataBoundary was set,
the region list would be needlessly recalculated.

I will fix the class so it's Mtime is only updated
when the actual spatial partitioning changes.  I will test this
and check it in today.

Lee Ann

================================================================
Date: Tue, 1 Feb 2005 13:59:29 +0100
From: sigmunau at idi.ntnu.no
Subject: [vtkusers] [patch] Speed up vtkKdTree::FindClosestPoint()

I was very happy to see vtk implementing a Kd-tree, and wanted to try it
out
for speeding up vtkIterativeClosestPointTransform. However, I found it
to be
much much slower than vtkCellLocator, which is currently used. After
quite a
bit of investigation I figured out that this was because
vtkKdTree::FindClosestPoint regularly calls
vtkKdTree::FindClosestPointInSphere. This method calls
BSPCalculator->ComputeIntersectionsUsingDataBoundaryOn() which causes
BSPCalculator's MTime to be updated, which triggers a full rebuild of
BSPCalculators regionlist in BSPCalculator->IntersectsSphere2(). This
causes
the entire tree to be traversed and it is very very slow.

It also turns out that BSPCalculators region list does not depend on the
status of ComputeIntersectionsUsingDataBounds so this rebuild is totally
unnecessary. I do however not now if it is allways safe to drop
rebuilding
the region list when it is older than BSPCalculator, so I didn't want to
disable the rebuild. My solution was to introduce new methods in the
BSPIntersections class for IntersectsSphere2 where whether to use data
bounds is read from a parameter to the method, and not from the member
variable. An alternative solution might be to also trigger the mtime on
the
region list after setting ComputeIntersectionsUsingDataBounds, but since
the
region list actually didn't change I figured that to be a bad thing.

If this patch get accepted I will consider writing a patch to make
vtkIterativeClosestPointTransform able to use both vtkKdTree and
vtkCellLocator.
-- 
================================================================
Lee Ann Fisk                                 lafisk at sandia.gov
Department 9215                             Phone 505-844-2059
Discrete Algorithms and Math                  Fax 505-845-7442
Sandia National Laboratories                    Mail stop 1110
Albuquerque, NM, USA                             Office 980/15
================================================================