[vtk-developers] vtkDelaunay2D fails to tesselate a partially complex geometry with one hole

[wyldckat]

Dear VTK developers,

We at blueCAPE have been using VTK 5.4 for about a year now with success
with two of our applications currently being developed: 
http://www.bluecape.com.pt/gbXML2STL gbXML2STL  and 
http://www.bluecape.com.pt/blueAIR blueAIR 
Both of these rely on VTK for the most part of the geometrical and modeling
needs, including vtkDelaunay2D which we use on a daily basis for generating
tessellated "2D" surfaces, of namely: walls, floors, roofs and so on,
including making the respective openings for windows and doors on those
surfaces.
So far, we have had little trouble with vtkDelaunay2D (the issues were
mainly our fault) until last week, when a somewhat complex floor with a
single opening fails to be properly tessellated.

Attached to this email are three tcl files that have been executed with both
VTK 5.4 and 5.6 TCL command line for Windows. They are:
- constrainedDelaunayCustom.tcl - the original geometry, where two large
triangles were generated with the wrong vertices;
- constrainedDelaunayCustomDisc.tcl - the points of the geometry were
discretized with a custom made script in Octave and the results aren't
completely satisfactory, although at least one side does get properly
tessellated.
- constrainedDelaunayCustomStrictDisc.tcl - the points of the geometry were
strictly discretized. In other words, every point as its own discrete
position. Ironically, this results in a properly tessellated surface with
the desired hole in it.

NOTE: The discretization is made along X and Y axis independently, using
only integer values.

The discretization process tested was based on what was said on another
thread in this mailing list, namely: "Delaunay2D infinite recursion".
The conclusion I've reached so far is that there are some points that are on
the same "line of sight" of the base triangles that are used as reference
for the decision part of the "delaunay triangularization". And for some
reason, even when the points are discretized, the problem still occurs.

We wish to resolve this issue ASAP and we are willing to help resolving this
issue in vtkDelaunay2D. But we will need some text/paper references about
the implemented algorithm, so we can try and figure out what the best
solution will be. I've search for a while now and haven't been able to
figure out on which papers/texts/books has the vtkDelaunay2D algorithm been
based on.

Best regards,
Bruno Santos
Attachments:
http://vtk.1045678.n5.nabble.com/file/n2290262/constrainedDelaunayCustom.tcl
constrainedDelaunayCustom.tcl 
http://vtk.1045678.n5.nabble.com/file/n2290262/constrainedDelaunayCustomDisc.tcl
constrainedDelaunayCustomDisc.tcl 
http://vtk.1045678.n5.nabble.com/file/n2290262/constrainedDelaunayCustomStrictDisc.tcl
constrainedDelaunayCustomStrictDisc.tcl 
-- 
View this message in context: http://vtk.1045678.n5.nabble.com/vtkDelaunay2D-fails-to-tesselate-a-partially-complex-geometry-with-one-hole-tp2290262p2290262.html
Sent from the VTK - Dev mailing list archive at Nabble.com.