<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
</head>
<body bgcolor="#ffffff" text="#000000">
on <i>Fri, 25 Aug 2000 10:55:26 +0100 <font color="#33cc00">(Oh yes,
just 8 years ago!)</font></i><font color="#33cc00">
</font>I posted a question about Locators and cleaning up some of the
classes
to give a more consistent interface.<br>
<br>
I have finally got around to doing this and I'd like to make some
changes to the locator class heirarchy.<br>
<br>
Background<br>
-------------------<br>
vtkCellLocator and vtkOBBTree are both cell-locators, but vtkOBBTree
inherits from CellLocator although it is tree based and CellLocator is
a regular subdivision. I have my own BSP tree which I use for many
jobs, but can't be swapped for an OBB or cell locator if I give other
code that depends upon to people. In particular I've made a lot of
changes very recently to the vtkTemporalStreamTracer and related
classers to optimize searches using locatoirs and I cannot commit them
without also committing my BSP tree. A common CellLocator interface
would solve this problem. <br>
<br>
Changes<br>
-----------<br>
<tt> - vtkPointLocator<br>
</tt><tt> - vtkKdTree<br>
</tt><tt>vtkLocator - vtkAbstractCellLocator - vtkCellLocator<br>
- vtkOBBTree<br>
- vtkModifiedBSPTree (Can commit if
style accepted)<br>
<br>
</tt>I am not a big user of vtkKdTree so am not sure if it should lie
in the CellLocator heirarchy or the point locator heirarchy. Currently
it lives on it's own and it does some cell location, some point
location. It would be unaffected by my changes, but I will gladly move
it into another place if anyone would like to make suggestions. (I'd
like to see it integrated into the CellLocator family, but I need to
inspect the code to see if it is applicable)<br>
<br>
Interface changes. I'd have moved most of the
MaxDepth/NumberOfCellsPerBucket/Level type variables into
vtkAbstractCellLocator. and then used the same ones for all
CellLocators. vtkCellLocator uses 'buckets', but internally I have
re-used the inherited Nodes variable to clean up the implementation. <br>
<br>
class vtkAbstractCellLocator provides a number of common utility
functions, most of the Intersect/Find/etc methods have multiple
signatures and concrete locator implementations need only provide one,
the abstract base class will direct the code to use the implemented
version.<br>
<br>
My current interface looks like this<br>
<br>
I'd like to commit this as soon as possible, (i.e. this week), because
I cannot commit my ParticleTracer changes until this is done - and I
have made a lot of changes to it over the last week (Berk,Andy B please
take note, I have fixed a couple of big problems and changed the
interface a bit, I know you two are looking at the TemporalStreamTracer
code I sent before, but now there are many changes)<br>
<br>
Below is my current interface, which may change a little. You can see
I've added some new variables for delayed building and reusing search
structure. In an ideal worl, I'd like to rename vtkCellLocator to
vtkUniformOctTreeCellLocator - this would require quite a lot of name
changes in vtk and affect a lot of people. Anyone think its a good
thing to do?<br>
<br>
JB<br>
<br>
class VTK_FILTERING_EXPORT vtkAbstractCellLocator : public vtkLocator<br>
{<br>
public:<br>
vtkTypeRevisionMacro(vtkAbstractCellLocator,vtkLocator);<br>
void PrintSelf(ostream& os, vtkIndent indent);<br>
<br>
// Description:<br>
// Specify the preferred/maximum number of cells in each node/bucket.
<br>
// Default 32. Locators generally operate by subdividing space into <br>
// smaller regions until the number of cells in each region (or node)
<br>
// reaches the desired level.<br>
vtkSetClampMacro(NumberOfCellsPerNode,int,1,VTK_LARGE_INTEGER);<br>
vtkGetMacro(NumberOfCellsPerNode,int);<br>
<br>
// Description:<br>
// Boolean controls whether the bounds of each cell are computed only<br>
// once and then saved. Should be 10 to 20% faster if repeatedly <br>
// calling any of the Intersect/Find routines and the extra memory<br>
// won't cause disk caching (24 extra bytes per cell are required to<br>
// save the bounds).<br>
vtkSetMacro(CacheCellBounds,int);<br>
vtkGetMacro(CacheCellBounds,int);<br>
vtkBooleanMacro(CacheCellBounds,int);<br>
<br>
// Description:<br>
// Boolean controls whether to maintain list of cells in each node.<br>
// not applicable to all implementations, but if the locator is being
used<br>
// as a geometry simplification technique, there is no need to keep
them.<br>
vtkSetMacro(RetainCellLists,int);<br>
vtkGetMacro(RetainCellLists,int);<br>
vtkBooleanMacro(RetainCellLists,int);<br>
<br>
// Description:<br>
// Most Locators build their search structures during BuildLocator<br>
// but some may delay construction until it is actually needed.<br>
// If LazyEvaluation is supported, this turns on/off the feature.<br>
// if not supported, it is ignored.<br>
vtkSetMacro(LazyEvaluation,int);<br>
vtkGetMacro(LazyEvaluation,int);<br>
vtkBooleanMacro(LazyEvaluation,int);<br>
<br>
// Description:<br>
// Some locators support querying a new dataset without rebuilding<br>
// the search structure (typically this may occur when a dataset<br>
// changes due to a time update, but is actually the same topology)<br>
// Turning on this flag enables some locators to skip the rebuilding <br>
// phase<br>
vtkSetMacro(UseExistingSearchStructure,int);<br>
vtkGetMacro(UseExistingSearchStructure,int);<br>
vtkBooleanMacro(UseExistingSearchStructure,int);<br>
<br>
// Description:<br>
// Return intersection point (if any) of finite line with cells
contained<br>
// in cell locator.<br>
virtual int IntersectWithLine(double a0[3], double a1[3], double tol,<br>
double& t, double x[3], double
pcoords[3],<br>
int &subId);<br>
<br>
// Description:<br>
// Return intersection point (if any) AND the cell which was
intersected by<br>
// the finite line.<br>
virtual int IntersectWithLine(double a0[3], double a1[3], double tol,<br>
double& t, double x[3], double
pcoords[3],<br>
int &subId, vtkIdType &cellId);<br>
<br>
// Description:<br>
// Return intersection point (if any) AND the cell which was
intersected by<br>
// the finite line. The cell is returned as a cell id and as a
generic cell.<br>
virtual int IntersectWithLine(double a0[3], double a1[3], double tol,<br>
double& t, double x[3], double
pcoords[3],<br>
int &subId, vtkIdType &cellId,<br>
vtkGenericCell *cell);<br>
<br>
// Description:<br>
// Return the closest point and the cell which is closest to the
point x.<br>
// The closest point is somewhere on a cell, it need not be one of the<br>
// vertices of the cell.<br>
virtual void FindClosestPoint(double x[3], double closestPoint[3],<br>
vtkIdType &cellId, int &subId, double& dist2);<br>
<br>
// Description:<br>
// Return the closest point and the cell which is closest to the
point x.<br>
// The closest point is somewhere on a cell, it need not be one of the<br>
// vertices of the cell. This version takes in a vtkGenericCell<br>
// to avoid allocating and deallocating the cell. This is much
faster than<br>
// the version which does not take a *cell, especially when this
function is<br>
// called many times in a row such as by a for loop, where the
allocation and<br>
// deallocation can be done only once outside the for loop. If a
cell is<br>
// found, "cell" contains the points and ptIds for the cell "cellId"
upon<br>
// exit.<br>
virtual void FindClosestPoint(<br>
double x[3], double closestPoint[3],<br>
vtkGenericCell *cell, vtkIdType &cellId, <br>
int &subId, double& dist2);<br>
<br>
// Description:<br>
// Return the closest point within a specified radius and the cell
which is<br>
// closest to the point x. The closest point is somewhere on a cell,
it<br>
// need not be one of the vertices of the cell. This method returns 1
if<br>
// a point is found within the specified radius. If there are no
cells within<br>
// the specified radius, the method returns 0 and the values of
closestPoint,<br>
// cellId, subId, and dist2 are undefined.<br>
virtual vtkIdType FindClosestPointWithinRadius(<br>
double x[3], double radius,<br>
double closestPoint[3], vtkIdType &cellId,<br>
int &subId, double& dist2);<br>
<br>
// Description:<br>
// Return the closest point within a specified radius and the cell
which is<br>
// closest to the point x. The closest point is somewhere on a cell,
it<br>
// need not be one of the vertices of the cell. This method returns 1
if a<br>
// point is found within the specified radius. If there are no cells
within<br>
// the specified radius, the method returns 0 and the values of<br>
// closestPoint, cellId, subId, and dist2 are undefined. This version
takes<br>
// in a vtkGenericCell to avoid allocating and deallocating the
cell. This<br>
// is much faster than the version which does not take a *cell,
especially<br>
// when this function is called many times in a row such as by a for
loop,<br>
// where the allocation and deallocation can be done only once
outside the<br>
// for loop. If a closest point is found, "cell" contains the points
and<br>
// ptIds for the cell "cellId" upon exit.<br>
virtual vtkIdType FindClosestPointWithinRadius(<br>
double x[3], double radius,<br>
double closestPoint[3],<br>
vtkGenericCell *cell, vtkIdType &cellId,<br>
int &subId, double& dist2);<br>
<br>
// Description:<br>
// Return the closest point within a specified radius and the cell
which is<br>
// closest to the point x. The closest point is somewhere on a cell,
it<br>
// need not be one of the vertices of the cell. This method returns 1
if a<br>
// point is found within the specified radius. If there are no cells
within<br>
// the specified radius, the method returns 0 and the values of<br>
// closestPoint, cellId, subId, and dist2 are undefined. This version
takes<br>
// in a vtkGenericCell to avoid allocating and deallocating the
cell. This<br>
// is much faster than the version which does not take a *cell,
especially<br>
// when this function is called many times in a row such as by a for
loop,<br>
// where the allocation and dealloction can be done only once outside
the<br>
// for loop. If a closest point is found, "cell" contains the points
and<br>
// ptIds for the cell "cellId" upon exit. If a closest point is
found,<br>
// inside returns the return value of the EvaluatePosition call to the<br>
// closest cell; inside(=1) or outside(=0).<br>
virtual vtkIdType FindClosestPointWithinRadius(<br>
double x[3], double radius,<br>
double closestPoint[3],<br>
vtkGenericCell *cell, vtkIdType &cellId,<br>
int &subId, double& dist2, int &inside);<br>
<br>
// Description:<br>
// Return a list of unique cell ids inside of a given bounding box.
The<br>
// user must provide the vtkIdList to populate. This method returns
data<br>
// only after the locator has been built.<br>
virtual void FindCellsWithinBounds(double *bbox, vtkIdList *cells);<br>
<br>
// Description:<br>
// Given a finite line defined by the two points (p1,p2), return the
list<br>
// of unique cell ids in the buckets containing the line. It is
possible<br>
// that an empty cell list is returned. The user must provide the
vtkIdList<br>
// to populate. This method returns data only after the locator has
been<br>
// built.<br>
virtual void FindCellsAlongLine(<br>
double p1[3], double p2[3], double tolerance, vtkIdList *cells);<br>
<br>
// Description:<br>
// Find the cell containing a given point.<br>
virtual vtkIdType FindCell(<br>
double x[3], double tol2, vtkGenericCell *GenCell, <br>
double pcoords[3], double *weights);<br>
<br>
// Description:<br>
// Quickly test if a point is inside the bounds of a particular cell.<br>
// Some locators cache cell bounds and this function can make use<br>
// of fast access to the data.<br>
virtual bool InsideCellBounds(double x[3], vtkIdType cell_ID);<br>
<br>
protected:<br>
vtkAbstractCellLocator();<br>
~vtkAbstractCellLocator();<br>
<br>
int NumberOfCellsPerNode;<br>
int RetainCellLists;<br>
int CacheCellBounds;<br>
int LazyEvaluation;<br>
int UseExistingSearchStructure;<br>
<br>
private:<br>
vtkAbstractCellLocator(const vtkAbstractCellLocator&); // Not
implemented.<br>
void operator=(const vtkAbstractCellLocator&); // Not
implemented.<br>
};<br>
<br>
</body>
</html>