Background: Over the past few years there have been substantial speed improvements due to the addition of systems like vtk-m and vtkSMPTools. Additionally, C++11 constructs like std::atomic provide facilities for multithreading etc. In particular, some of the core VTK data structures like cell and point locators, and the process of building topological links (e.g., cell links) have been undergoing renovation, producing speedups of multiple factors approaching an order of magnitude. Several years ago the new classes vtkStaticCellLocator, vtkStaticPointLocator, and vtkStaticCellLinks were added but used only in specialized circumstances. Due to their significant speed improvements (and in many cases significant reductions in memory usage), and the inexorable increases in data size, it’s time to mainstream these classes. For example, using vtkSMPTools and std::atomic, vtkStaticCellLinks is about 10x faster (to build) than the vtkCellLinks equivalent, and also much faster to destroy (asingle delete versus many).
Over the past week we have begun switching out vtkCellLinks with vtkStaticCellLinks in vtkUnstructuredGrid, and vtkPointLocator with vtkStaticPointLocator (in vtkPointSet - superclass of vtkUnstructuredGrid). Once these efforts stabilize, this process will move into vtkPolyData. Of course feedback is welcome - generally there will be no noticeable changes except for indeterminate queries like “find the closest point” when more than one “closest points” are all exactly the same distance away from the query point.
Nasty Details: One of the challenges moving forward is dealing with aspects of the dataset API, in particular portions of the vtkUnstructuredGrid and vtkPolyData API enable dynamic “editing” of the dataset - for example, after the dataset is constructed and point locator and/or cell links are built, new points/cells can be dynamically added/deleted. This behavior is inconsistent with the “static” classes which are meant to be built once, at high speed. Currently the overwhelming use cases for VTK datasets are as static data, with a handful of filters (like Delaunay triangulation, etc) incrementally editing their output datasets. To deal with this, vtkUnstructuredGrid and vtkPolyData have a new data member “Editable” which by default is off, with static locators and cell links being used. However, if Editable is enabled, then the old-fashioned locators and cell links classes are used, and the iterative, editing API works as expected.
Apologetic Aside: Whenever you dig into the guts of a complex system like VTK with a more than 25 year history behind it, you are likely to find cobwebs and coding artifacts that no longer make sense. I noticed this when changing out cell links - in ancient times the links were represented as a list of cell ids using a given point, with a count of cell ids represented with an unsigned short. Along the way much changed including the introduction of vtkIdType and associated changes to the cell locators - however the usage of “unsigned short” remained for some strange reason (nobody wanted to mess with the API I suppose). While making the changes described here I did the “bull in the china shop” thing and changed the unsigned int to vtkIdType - I’m sure annoying several folks, but thankfully several VTK developers are helping clean up my mess - thank you!
Extra Credit Challenge: While I am very pleased with the speed increases, I am frustrated by one remaining method: vtkUnstructuredGrid::GetCellNeighbors(). It turns out this method is key to further improving the performance of topological filters like vtkGeometryFilter. My suspicion is that there is a clever way to speed this up but so far I’ve come up dry. Maybe someone out there can crack this nut