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

[Will Schroeder]

Hi Bruno-

I'm sorry about your problem with Delaunay2D, although it
not totally unexpected. Due to numerical precision, the implemented
algorithm can be made to fail. To really fix this we would have to rewrite
the algorithm using arbitrary precision methods. (See for example
http://www.cs.cmu.edu/~jrs/jrspapers.html as a starting point.)

In the short term, you can sometimes work around the algorithm
by injecting the points in a different order, e.g., randomizing them or
changing into a more spatially dispersed order. Try that and if it doesn't
work let me know and we will try to fix the existing code to swallow
numerical degeneracies. Then one day will figure out how to get arbitrary
precision into these algorithms and do it right...

Will

On Mon, Aug 9, 2010 at 3:48 PM, wyldckat <bruno.santos at bluecape.com.pt>wrote:

>
> 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.
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtk-developers
>
>


-- 
William J. Schroeder, PhD
Kitware, Inc.
28 Corporate Drive
Clifton Park, NY 12065
will.schroeder at kitware.com
http://www.kitware.com
(518) 881-4902
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20100810/bed9ff47/attachment.html>