VTK/Locator Refactoring

Background

Locators are spatial search objects. The principle behind locators is that they divide 3-space into small pieces (or "buckets") that can be quickly found in response to queries like point location, line intersection, or object-object intersection.

The current class hiearchy for locators is as follows.

vtkAbstractCellLocator and vtkAbstractPointLocator provide the API for cell and point locators. vtkCellLocator and vtkPointLocator are concrete subclasses that use uniform binning. vtkMergePoints is a specialized subclass that assumes a tolerance of 0 and optimizes accordingly. vtkKdTreePointLocator uses a K-D tree instead of uniform binning.

Issues with the current implementation

vtkPointLocator and vtkCellLocator work well when the cells/points are uniformly distributed. In such cases, they end up with roughly the same number of cells/points in each bucket and the linear search that happens in each bucket is fast. However, when the cells/points are not uniformly distributed, for example in the case of finite-element simulation of a boundary layer (e.g. flow around a wing), certain buckets end up with much larger number of cells/points and the performance becomes very poor. To address this issue, we have been developing locators that use adaptive binning - K-D trees or octrees. In order to be able to use these locators in existing VTK filters, we need to make some changes to the class hierarchy.

Proposed class hierarchy

Here is what we propose.

Things to note:

We added an abstract superclass called vtkIncrementalPointLocator. Currently, filters like the contour filter allow the user to set a locator which is a vtkPointLocator or subclass. However, vtkPointLocator already implements uniform binning and subclassing it to implement an octree-based binning, for example, would be poor design. We considered using vtkAbstractPointLocator instead. This has one major flaw: not all point locators can easily implement all of the API that is in vtkPointLocator. This is because vtkPointLocator has two modes:

1. Build the search structure given the whole mesh
2. Build the search structure incrementally as user adds more points

The second mode cannot be efficiently implemented in some locators. Therefore, we introduced a new superclass called vtkIncrementalPointLocator. This has all of vtkPointLocator's API but is abstract and allows us to subclass from it. We will change all vtkPointLocators to vtkIncrementalPointLocators. This will be backwards-compatible except for subclasses that use superclass' locator directly.

We added two octree-based locators. There are vtkIncrementalOctreePointLocator and vtkOctreePointLocator. vtkOctreePointLocator is more efficient and should be used whenever possible.

We added vtkBSPTreeCellLocator. This is John Biddiscombe's cell locator that uses a BSP tree. Hopefully, he will contribute it.

We added vtkNonMergePointLocator. This is for when the user wants to skip merging of points all together, mainly for efficiency reasons.

We removed vtkKdTree from the hierarchy. vtkKdTree is not used as a locator and does not have to subclass from vtkLocator.

vtkPointSet::FindCell()

Another issue is with the implementation of FindCell() in vtkPointSet. vtkPointSet uses a point locator to find the closest point and then walks cells that contain that point. This has two issues:

1. FindCell() can actually fail when there are discontinuities in the mesh. This happens with C-type structured grids (when the mesh wraps around an airfoil for example) or when unstructured mesh adaptation causes incompatible element faces. This happens occasionally but it is a big problem when it does.
2. The point locator may be slow for non-uniform point distributions

The only guaranteed solution to (1) is to use a cell locator. (2) can be addressed by either using an adaptive point locator or an adaptive cell locator - which one performs better depends on the problem.

The cleanest solution is probably to add an option to the filters that use vtkDataSet::FindCell() to use a cell locator instead. This is still not ideal because it pushes the burden to the user. We should never use locators for vtkImageData and vtkRectilinearGrid.