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

Will Schroeder will.schroeder at kitware.com
Sun Aug 15 06:52:26 EDT 2010


Bruno-

The work was influenced by Guibas and Stolfi's point walking algorithm. It
is described quickly in
http://gandalf.psych.umn.edu/groups/schraterlab/schrater_lab/publications/bc.pdf.
There are other references, but with a quick look I could not find the
original reference in
[13] Leonidas Guibas and Jorge Stol
. Primitives for the manipulation of
general subdivisions and the
computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2):75{123,
1985.

Will

On Thu, Aug 12, 2010 at 10:12 AM, wyldckat <bruno.santos at bluecape.com.pt>wrote:

>
> Greetings Will and David,
>
> @David: I don't believe it's 100% related to the bug you posted, since
> vtkDelaunay2D hasn't crashed with us (yet).
>
> @Will: Thank you for the link and we'll start on that ASAP. But could you
> please also provide the link or references for the textual information
> about
> the currently implemented code?
> Because it feels that the current code fails sometimes only because it uses
> an absolute referential for finding the triangles, instead of using various
> relative referentials for each relevant section of the geometry. So, by
> using multiple referentials, the numerical precision errors could be
> minimized/eliminated with some additional heuristic. And without some
> paper/text/document as reference for the current code, it will harder to
> analyze the current implementation.
>
> Best regards,
> Bruno
>
>
> David Doria-2 wrote:
> >
> > On Tue, Aug 10, 2010 at 2:44 PM, Will Schroeder
> > <will.schroeder at kitware.com> wrote:
> >> 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
> >
> > I submitted a bug the other day that may be related to this?
> >
> > http://public.kitware.com/Bug/view.php?id=11102
> >
> > Thanks,
> >
> > David
> > _______________________________________________
> > 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
> >
> >
> >
>
> --
> View this message in context:
> http://vtk.1045678.n5.nabble.com/vtkDelaunay2D-fails-to-tesselate-a-partially-complex-geometry-with-one-hole-tp2290262p2473259.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/20100815/473d0531/attachment.html>


More information about the vtk-developers mailing list