I have been using vtkContourFilter quite frequently to generate surface meshes from SDF.
From what I understand, there are other options for the contour method, like vtkMarchingCubes and vtkFlyingEdges3D. Marching cubes and flying edges have descriptive names so I could look up the associated algorithms, but what algorithm is behind vtkContourFilter?
I tried to find the answer in the vtk documentation and other pages, but could not find the info. The only thing remotely close was “edge-tracking” mentioned in this page, but I wasn’t sure if this was referring to vtkContourFilter.
I would appreciate any help or insight from the community.
If you look in the vtkContourFilter source code, in particular vtkContourFilter.h, you will see this bunch of algorithms. They are delegated to depending on the type of data.
Thank you for pointing this out. By any chance, is there a list of associated publications for these algorithms? Or more verbal descriptions of what they do?
You’re going to be sorry you asked But since this is near and dear to my heart here you go…
To answer your question about publications directly:
21 (4): 163–169.
William Schroeder, Rob Maynard, and Berk Geveci. 2015. Flying edges: A high-performance scalable isocontouring algorithm. In Proceedings of the 2015 IEEE 5th Symposium on Large Data Analysis and Visualization (LDAV) (LDAV '15). IEEE Computer Society, USA, 33–40.
Marching Cubes started it all, and I humbly propose that Flying Edges represents the state of the art for single-pass (i.e., no preprocessing), high-performance isocontouring of continuous scalar fields. The algorithms used by vtkContourFilter are on a spectrum of features and performance between MC and FE. To boil it down to its essence, all algorithms compute a “case” by comparing in/out or 0/1 of vertices against the isocontour value, generating the case index, and then index into a case table which predefines a connectivity set to generate triangles. The case also defines which edges of the cell are to be interpolated to create the triangle vertices.
The spectrum of performance goes like this, I’ve glossed over lots of details I’m trying to give you the gist.
MC loads data on a voxel cell-by-voxel cell basis (i.e., the so-called cubes). While incredibly simple, it has significant performance issues. For example, edges intersection may be repeated up to four times; the generated intersection points require some sort of “merging” process to eliminate duplicates (in VTK these are point locators); and it performs incremental / repeated memory allocation which is really slow. MC is sequential.
Synchronized templates is a precursor to Flying Edges. After Ken and I first started Kitware, we designed the algorithm to eliminate multiple edge intersections. We actually thought about patenting it (before we really understood our open source business model - and eventually abandoned the idea). Ken took the lead and implemented it and for many years it was the fastest algorithm adapted to all sorts of structured data. Unfortunately, it is sequential, and performs incremental memory allocation requiring a locator.
vtkContour3DLinearGrid is threaded. It is designed for 3D unstructured grids of mixed linear cell types (e.g., tets, hexes, wedges, prisms). It uses optimized methods to access VTK data. It employs multiple passes to identify cell edges to be intercepted, using a fancy, threaded tuple sort to identify duplicate points. Because it processes structured data, some of the tricks used in FE cannot be used. But it is a lot faster than what was there before
Flying Edges is threaded. Flying edges loads each voxel data value only one time. Flying Edges intersects each voxel edge only once. FE performs one-time memory allocation for output. Flying Edges requires no bottlenecking locator. FE traverses data in multiple, independent threaded passes across volume x-edges.
Now just to round out isocontouring, there is a class of algorithms which treat “discrete” non-continuous data such as segmentation label maps. Meaning the interpolation across edges is not possible since all that is known is that one edge endpoint is labeled as belonging in material A and the other in material B. What is typically done is that edges are intersected at their midpoint. We just added a new algorithm vtkSurfaceNets3D which is influenced by Flying Edges for discrete data (the paper is under review so I can’t say too much more yet). This joins the algorithms vtkDiscreteMarchingCubes and vtkDiscreteFlyingEdges. I predict one day VTK will have a vtkDiscreteContourFilter that will delegate to the various discrete isocontouring classes.
This is amazing - I did not expect such a detailed response. Thank you so much for your explanations! Everything makes a lot more sense.
If I understand correctly, FE is the fastest / most accurate for processing voxel data, and vtkContour3DLinearGrid is a slightly slower version that can handle structured data.
While FE and vtkContour3DLinearGrid seem to have clear advantages, MC and Synchronized templates sound like worse versions of FE. Are their any use cases where they would be preferred over the other two?
vtkContour3DLinearGrid is meant for unstructured grids.
I would use Synchronized Templates in preference to MCs, they produce identical output and ST is usually much faster.
Yes, there is one use case where FE might not be desirable. In some situations, these case-based contouring algorithms will output degenerate triangles (i.e., zero area, with 2 or 3 points coincident). Both MC and ST check these pathological cases during incremental insertion of triangles (part of the reason they are slow) and cull the triangles out. FE does not check this (it would destroy parallelism - design tradeoff). Generally this is not an issue, especially for visualization applications since the appearance of the resulting isocontour is identical. However, if you are doing something like geometric modeling etc. which requires non-degenerate triangles, it might be a problem (although I’ve never seen this happen as of yet).
But since this is near and dear to my heart here you go…