I am testing how to put surfaces with holes on screen in VTK. I am using constrained vtkDelaunay2D filter to generate the triangulations such that the surface can be displayed in solid manner. I am working with rectangular shapes currently (but might need more complex shapes in future). I have come to a particular configuration, which causes problems, see definition in left part of the illustration:
I define all the rectangles with 4 corner points and following the appropriate (counter-)clockwise notation. The original Python code can be found here: 20241106_py_standAlone_SurfaceWith3Holes_Fail.py (3.2 KB)
Running this gives me surface without holes and spits out the following warning:
vtkDelaunay2D.cxx:1435 WARN| vtkDelaunay2D (0000017C93208030): Edge not recovered, polygon fill not possible
Of course, one could expect that there might be issues with bad aspect ratio triangles in the gap, so I tried to add an extra point (see red dot in the illustration) and then it worked and produced the expected output. Modified python code here: 20241106_py_standAlone_SurfaceWith3Holes_Success.py (3.4 KB)
However, I did some experiments with a single hole. With just one rectangular hole, I could triangulate and display gaps down to width of 1e-5 (1e-6 did fail and fill the whole surface with triangles), see image below:
So the second test makes me second-guess the argument that the example with 3 holes fails due to bad triangles, because the gap (although somewhat small) is still much much bigger (0.1 vs 1e-5) compared to example with 1 hole. So I wonder if there currently exists a way to triangulate this without the extra point or could this be considered as a bug?
In this particular example adding additional point was simple, but I will mostly likely encounter more complex cases in which adding these extra points will be highly non-trivial.
week has passed but I have had no reactions on this topic. Perhaps you are very busy, but I would appreciate at least some sort of reaction (is/isn’t bug, plans/no-plans to fix it, maybe some robust workaround exists)?
@will.schroeder , perhaps you have any ideas, you have provided previously very good insight about tessellation and rendering to me here. Or perhaps @amaclean , @lassoan , @Paulo_Carvalho (I have seen you guys in forum talking about vtkDelaunay2D filter in different occasions)?
I suspect that the issue is with the constraint edge recovery process. Currently this uses a very simple process of swapping edge diagonals which works much of the time. However, I am pretty sure that in certain situations this won’t work without inserting additional points. It would be interesting to triangulate without constraint edges and see what you start with, and then see if swapping can produce a correct final result or whether new points need inserting. Maybe we can learn something and improve the algorithm.
Since all your points are already connected with edges, you can use a more robust filter, such as vtkContourTriangulator. vtkContourTriangulator does not even care about polygon winding, but it knows that every contour in a solid region designate a hole (and a contour in a hole means solid).
Interesting, thank you for the responses. I was aware of vtkTriangleFilter alternative (but does not work with holes), but not of vtkContourTriangulator. I gave it a try and it worked perfectly. Had to define line by line instead (as David suggested) and triangulation worked just fine. For reference, here is an updated Python code with vtkContourTriangulator. 20241115_py_standAlone_SurfaceWith3Holes_vtkContourTriangulator.py (3.0 KB)
Problem solved. At least in a way, I suppose vtkDelaunay2D is still a bit buggy then.
vtkDelaunay2D documentation describes the limitations of the filter in great detail, including potential failure in case of non-convex shapes and lack of points, so I don’t think the filter could be considered buggy.
The main problem I see is that vtkContourTriangulator was not mentioned in the “See also” section of vtkDelaunay2D documentation, so VTK users may not be aware that a better alternative exists. I’ve submitted a merge request that adds it: https://gitlab.kitware.com/vtk/vtk/-/merge_requests/11669
