[vtkusers] Re: Speed up vtkKdTree::FindClosestPoint

[sigmunau at idi.ntnu.no]

On Tue, Feb 01, 2005 at 09:02:52AM -0700, lee ann fisk wrote:
> 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.

No problem. I didn't spend too much time tracking it down, and I learned a
lot in the process.

> 
> 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.

Thanks, I will be happy to see such a change.

At last a question about the KdTree: Would it be possible to extend this
class to also support finding closest point on a more general dataset?	I am
thinking about something like this: 
* Find closest point among cell-node and cell centroids
* Find closest point on cell(s) containing this point.
* Return closest point of points return in above statement.

I guess this approch isn't 100% correct in all situations, but will do very
often provided the dataset doesn't represent too exotic shapes.


Thanks once more.

Regards

Sigmund
> 
> 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
> ================================================================
> 
> 
> 
> X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on hobbes
> X-Spam-Level: 
> X-Spam-Status: No, score=-0.9 required=5.0 tests=ALL_TRUSTED,MISSING_DATE,
> 	MISSING_HEADERS,MISSING_SUBJECT autolearn=unavailable version=3.0.2
> 
> X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on hobbes
> X-Spam-Level: 
> X-Spam-Status: No, score=-0.9 required=5.0 tests=ALL_TRUSTED,MISSING_DATE,
> 	MISSING_HEADERS,MISSING_SUBJECT autolearn=unavailable version=3.0.2
> 
> X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on hobbes
> X-Spam-Level: 
> X-Spam-Status: No, score=-0.9 required=5.0 tests=ALL_TRUSTED,MISSING_DATE,
> 	MISSING_HEADERS,MISSING_SUBJECT autolearn=unavailable version=3.0.2