vtkContourTriangulator hangs for complex input
vtkContourTriangulator does a great job in creating triangulation from 2D contours - most of the time. It solves the problem of contours filled multiple times or not filled that we had with naive concatenation of line segments.
Unfortunately, it very often hangs if the input lines are generated by the high-performance vtkPlaneCutter class (followed by vtkCompositeDataGeometryFilter).
If vtkContourTriangulator input points are not merged:
- There is a long delay (tens of minutes in debug mode) caused by badPoint check in vtkCCSJoinLooseEnds (https://github.com/lassoan/VTK/blob/d533da973a44596f220b39ea95955998596c3028/Filters/General/vtkContourTriangulator.cxx#L795-L818). I’ve found that it never finds a bad point, so it might be useful to make this check optional. For now, we always merge points using CleanPolyDataFilter, so it is not a problem, but at least it might be good to document this limitation.
- Execution gets into an infinite loop very quickly in vtkCCSCutHoleyPolys. It never gets out of this while loop https://github.com/lassoan/VTK/blob/trainglecutter-hang/Filters/General/vtkContourTriangulator.cxx#L2326 because innerPolyId == groupId and we put back the item in the same vector we removed it from.
If vtkContourTriangulator input points are merged:
- vtkCCSJoinLooseEnds does not cause significant delay.
- vtkCCSCutHoleyPolys succeed several times but typically fails within 10-20 slices the same way as described above. Each time it fails on a different slice, probably because vtkPlaneCutter is multithreaded and it generates slightly different cuts each time.
It would be OK to get incorrect output or no output for highly irregular input, just the filter should never hang or crash.
To reproduce the issue: run this modified “TestContourTriangulatorCutter” test: https://github.com/lassoan/VTK/commit/d533da973a44596f220b39ea95955998596c3028
With this polydata as input: https://1drv.ms/u/s!Arm_AFxB9yqHt4EXBxdHfHghYYymSw
The mesh was generated by standard VTK image thresholding, flying edge contouring, smoothing, and decimation pipeline, so others can run into this issue, too.