[vtkusers] [patch] Speed up vtkKdTree::FindClosestPoint()

[sigmunau at idi.ntnu.no]

On Tue, Feb 01, 2005 at 02:15:21PM +0100, Sigmund.Augdal at idi.ntnu.no wrote:
> > Patch is agains current CVS as of 14.30 Norwegian time 01. februrary 2005
> Update of patch without the clutter in vtkKdNode.h. Sorry about that. Also
> note that the patch is made in the Graphics subfolder of the sources.
This time with the patch. Sorry about the noise.

Sigmund

> 
> Regards
> 
> Sigmund Augdal
> _______________________________________________
> This is the private VTK discussion list. 
> Please keep messages on-topic. Check the FAQ at: http://www.vtk.org/Wiki/VTK_FAQ
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers
-------------- next part --------------
? KdTree-2.patch
? KdTree.patch
? myvtkKdNode.h
? myvtkKdTree.cxx
Index: vtkBSPIntersections.cxx
===================================================================
RCS file: /cvsroot/VTK/VTK/Graphics/vtkBSPIntersections.cxx,v
retrieving revision 1.1
diff -u -r1.1 vtkBSPIntersections.cxx
--- vtkBSPIntersections.cxx	17 Nov 2004 19:22:43 -0000	1.1
+++ vtkBSPIntersections.cxx	1 Feb 2005 13:13:11 -0000
@@ -335,19 +335,31 @@
 // Intersection with a sphere---------------------------------------
 //
 int vtkBSPIntersections::IntersectsSphere2(int regionId, double x, double y, double z, 
-                                double rSquared) 
+                                double rSquared)
+{
+  return IntersectsSphere2( regionId, x, y, z, rSquared,
+                            this->ComputeIntersectionsUsingDataBounds );
+}
+int vtkBSPIntersections::IntersectsSphere2(int regionId, double x, double y, double z, 
+                                double rSquared, int useDataBounds) 
 {
   REGIONIDCHECK_RETURNERR(regionId, 0);
 
   vtkKdNode *node = this->RegionList[regionId];
 
-  return node->IntersectsSphere2(x, y, z, rSquared,
-                     this->ComputeIntersectionsUsingDataBounds);
+  return node->IntersectsSphere2(x, y, z, rSquared, useDataBounds);
 }
 
 //----------------------------------------------------------------------------
 int vtkBSPIntersections::IntersectsSphere2(int *ids, int len,
                        double x, double y, double z, double rSquared)
+{
+  return IntersectsSphere2(ids, len, x, y, z, rSquared,
+                           this->ComputeIntersectionsUsingDataBounds);
+}
+//----------------------------------------------------------------------------
+int vtkBSPIntersections::IntersectsSphere2(int *ids, int len,
+               double x, double y, double z, double rSquared, int useDataBounds)
 {                            
   REGIONCHECK(0)
 
@@ -356,7 +368,7 @@
   if (len > 0)
     {
     nnodes = this->_IntersectsSphere2(this->Cuts->GetKdNodeTree(), 
-      ids, len, x, y, z, rSquared);
+      ids, len, x, y, z, rSquared, useDataBounds);
     }                        
   return nnodes;
 } 
@@ -364,12 +376,18 @@
 //----------------------------------------------------------------------------
 int vtkBSPIntersections::_IntersectsSphere2(vtkKdNode *node, int *ids, int len,
                                   double x, double y, double z, double rSquared)
+{
+  return _IntersectsSphere2(node, ids, len, x, y, z, rSquared,
+                            this->ComputeIntersectionsUsingDataBounds);
+}
+
+int vtkBSPIntersections::_IntersectsSphere2(vtkKdNode *node, int *ids, int len,
+               double x, double y, double z, double rSquared, int useDataBounds)
 {                            
   int result, nnodes1, nnodes2, listlen;
   int *idlist;
   
-  result = node->IntersectsSphere2(x, y, z, rSquared,
-                             this->ComputeIntersectionsUsingDataBounds);
+  result = node->IntersectsSphere2(x, y, z, rSquared, useDataBounds);
                              
   if (!result) 
     {
@@ -382,14 +400,16 @@
     return 1;
     }
     
-  nnodes1 = _IntersectsSphere2(node->GetLeft(), ids, len, x, y, z, rSquared);
+  nnodes1 = _IntersectsSphere2(node->GetLeft(), ids, len, x, y, z, rSquared,
+                               useDataBounds);
   
   idlist = ids + nnodes1;
   listlen = len - nnodes1;
   
   if (listlen > 0)
     {
-    nnodes2 = _IntersectsSphere2(node->GetRight(), idlist, listlen, x, y, z, rSquared);
+    nnodes2 = _IntersectsSphere2(node->GetRight(), idlist, listlen, x, y, z, rSquared,
+                                 useDataBounds);
     }
   else
     {
Index: vtkBSPIntersections.h
===================================================================
RCS file: /cvsroot/VTK/VTK/Graphics/vtkBSPIntersections.h,v
retrieving revision 1.2
diff -u -r1.2 vtkBSPIntersections.h
--- vtkBSPIntersections.h	17 Nov 2004 21:52:40 -0000	1.2
+++ vtkBSPIntersections.h	1 Feb 2005 13:13:11 -0000
@@ -98,6 +98,9 @@
   //    and the square of it's radius.
   int IntersectsSphere2(int regionId, 
                         double x, double y, double z, double rSquared);
+  int IntersectsSphere2(int regionId, 
+                        double x, double y, double z, double rSquared,
+                        int useDataBounds);
 
   // Description:
   //    Compute a list of the Ids of all regions that 
@@ -106,6 +109,9 @@
   //    Returns: the number of ids in the list.
   int IntersectsSphere2(int *ids, int len, 
                         double x, double y, double z, double rSquared);
+  int IntersectsSphere2(int *ids, int len, 
+                        double x, double y, double z, double rSquared,
+                        int useDataBounds);
 
   // Description:
   //    Determine whether a region of the spatial decomposition
@@ -171,6 +177,9 @@
 
   int _IntersectsSphere2(vtkKdNode *node, int *ids, int len,
                          double x, double y, double z, double rSquared);
+  int _IntersectsSphere2(vtkKdNode *node, int *ids, int len,
+                         double x, double y, double z, double rSquared,
+                         int useDataBounds);
 
   int _IntersectsCell(vtkKdNode *node, int *ids, int len,
                       vtkCell *cell, int cellRegion=-1);
Index: vtkKdTree.cxx
===================================================================
RCS file: /cvsroot/VTK/VTK/Graphics/vtkKdTree.cxx,v
retrieving revision 1.1
diff -u -r1.1 vtkKdTree.cxx
--- vtkKdTree.cxx	17 Nov 2004 19:22:43 -0000	1.1
+++ vtkKdTree.cxx	1 Feb 2005 13:13:11 -0000
@@ -2351,12 +2351,8 @@
 {
   int *regionIds = new int [this->NumberOfRegions];
 
-  this->BSPCalculator->ComputeIntersectionsUsingDataBoundsOn();
-
   int nRegions = 
-    this->BSPCalculator->IntersectsSphere2(regionIds, this->NumberOfRegions, x, y, z, radius);
-
-  this->BSPCalculator->ComputeIntersectionsUsingDataBoundsOff();
+    this->BSPCalculator->IntersectsSphere2(regionIds, this->NumberOfRegions, x, y, z, radius, 1);
 
   double minDistance2 = 4 * this->MaxWidth * this->MaxWidth;
   int closeId = -1;