[vtkusers] [patch] Speed up vtkKdTree::FindClosestPoint()
sigmunau at idi.ntnu.no
sigmunau at idi.ntnu.no
Tue Feb 1 07:59:29 EST 2005
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.
Patch is agains current CVS as of 14.30 Norwegian time 01. februrary 2005
Regards
Sigmund Augdal
-------------- next part --------------
? KdTree.patch
? 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 12:33:06 -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 12:33:06 -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: vtkKdNode.h
===================================================================
RCS file: /cvsroot/VTK/VTK/Graphics/vtkKdNode.h,v
retrieving revision 1.3
diff -u -r1.3 vtkKdNode.h
--- vtkKdNode.h 17 Nov 2004 21:52:40 -0000 1.3
+++ vtkKdNode.h 1 Feb 2005 12:33:06 -0000
@@ -242,6 +242,9 @@
void PrintNode(int depth);
void PrintVerboseNode(int depth);
+ vtkKdNode *Left;
+ vtkKdNode *Right;
+
protected:
vtkKdNode();
@@ -260,9 +263,6 @@
vtkKdNode *Up;
- vtkKdNode *Left;
- vtkKdNode *Right;
-
int Dim;
int ID; // region id
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 12:33:06 -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;
More information about the vtkusers
mailing list