[vtk-developers] Delaunay2D infinite recursion

David Gobbi david.gobbi at gmail.com
Thu Feb 11 07:42:44 EST 2010


Hi Luca,

It worries me that Shewchuks' code comes with the following disclaimer:

"Warning: This code will not work correctly on a processor that uses
extended precision internal floating-point registers, such as the
Intel 80486 and Pentium, unless the processor is configured to round
internally to double precision. See the Predicates on PCs page for
details."

There are tricks to force a certain precision without resorting to
compiler flags (in fact VTK's fixed-point code does similar things),
but these tricks can make the code look ugly.

   David


On Thu, Feb 11, 2010 at 5:08 AM, Luca Antiga <luca.antiga at gmail.com> wrote:
> Hi Will and David,
>  a good tool for these kinds of problems is Shewchuks' public domain robust
> geometric predicates code (http://www.cs.cmu.edu/~quake/robust.html).
> I'm sure you know about it, just thought I'd drop in a note.
> Best regards
> Luca
>
> On Feb 11, 2010, at 12:18 PM, Will Schroeder wrote:
>
> David-
> One of these days we are going to have to fix the Delaunay classes properly.
> For such a beautiful algorithm it suffers from insidious numerical issues.
> Either discretize space or use some sort of infinite / higher precision.....
> I'll take a look, it'll likely be this weekend at the earliest.
> Will
>
> On Wed, Feb 10, 2010 at 11:41 PM, David Gobbi <david.gobbi at gmail.com> wrote:
>>
>> Hi All,
>>
>> I've written a clipping filter that uses constrained Delaunay to
>> triangulate the contours that result from the clipping.  The
>> vtkPolygon can triangulate these contours by ear-cut with no
>> difficulty at all, but vtkDelaunay gives me lots of warnings (Edge not
>> recovered, polygon fill suspect) and often crashes.  These contours of
>> mine have no interior points and about 10 unevenly-spaced points on
>> the perimeter.
>>
>> Below is one of the data sets that causes Delaunay2D to crash on my
>> Linux64 gcc-4.2 system.  Specifically,  FindTriangle() goes into
>> infinite recursion.  Can anyone confirm this?  I've also written a
>> python program that displays the problem data and runs delaunay on the
>> data.
>>
>>   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
>>
>>
>
>
>
> --
> 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
> _______________________________________________
> 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
>
>
>



More information about the vtk-developers mailing list