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. Here is what we propose.