[vtkusers] RE: Some VTK 5 information - KD Tree searchs (Tuhin Sinha)

[lee ann fisk]

Hello.  I wrote a vtk class (vtkKdTree) that computes a k-d tree 
decomposition of the centers of the cells of a vtkDataSet, and 
responds to certain region intersection queries on the k-d tree 
regions, like which regions intersect a certain convex region.  
In another mode it will create a k-d tree based on a list of points, 
and then can be used to remove duplicate points, find points or find 
the closest point.  In my tests, vtkMergePoints is faster at finding
points if your search tolerance is 0, but vtkKdTree is faster otherwise.

I also wrote vtkPKdTree, which computes the k-d tree structure
in parallel when the data set is distributed across multiple
processors.

These classes, and a few that support them, are checked in to 
ParaView.  They implement just the functionality we need here
at Sandia, but could be expanded to suit other purposes.

Lee Ann

>Subject: RE: [vtkusers] Some VTK 5 information  - KD Tree searchs
>From: Tuhin Sinha <tk.sinha at vanderbilt.edu>
>To: "Ken Martin (Lists)" <kenlists at nycap.rr.com>
>Cc: vtkusers at vtk.org
>Date: Fri, 12 Dec 2003 10:13:20 -0600
>
>Hello users and Ken,
>
>  Is there any thought at Kitware about refining the geometric search
>capabilities in VTK?  One of the warnings in the vtkPointLocator class
>documentation is that KD-Trees are better suited to handle geometric
>searching... yet VTK has always been sans KD-Trees.
>  Our group uses Dr. David Mount's ANN package and wraps it into VTK for
>KD-tree searchs.  The wrapped code greatly enhances the performance of
>some useful VTK classes, e.g. vtkIterativeClosestPointTransform.  There
>may be some licensing issues with that package that make it unsuitable
>for VTK, however I have seen other OpenSource packages (i.e. CGAL, and
>surprisingly ITK) that also have KD-Trees in them.  Maybe some code from
>those packages could be incorporated into VTK.  Is there any desire at
>Kitware or from the users to see this functionality in VTK?

-- 
===================================================================
Lee Ann Fisk                                    Phone: 505-844-2059
Data Analysis and Visualization (9227)          FAX:   505-845-0833
Sandia National Labs, Mail Stop 0822       Email: lafisk at sandia.gov
Albuquerque, NM  87185-0822
===================================================================