[vtkusers] vtkDelaunay3D: wrong convex hull

[David Gobbi]

Hi Miguel,

By applying vtkDelaunay3D to a flat (or nearly-flat) mesh, you are
asking it to create degenerate tetrahedrons, so it should not be
surprising that it fails on one or more of the points.

Checking to see if a neighbor is within a 2D convex hull should be
easy, you can use vtkPolygon::PointInPolygon() or, since the hull is
convex, you can do a quick orientation check with the closest edge
of the polygon.

 - David


2011/7/25 Miguel Sotaquirá <msotaquira at gmail.com>:
> Hi David,
>
> Yes indeed, it is a triangle mesh... However as I mentioned vtkDelaunay3D
> seems to work on all of the other vertices of my mesh, except on the one
> included the previous e-mail... This seems so odd!
>
> The problem is that I need the 3-D convex hull, since I later want to know
> if current vertex is enclosed by its neighbors' convex hull... If I use
> delaunay2D (by projecting my mesh onto a flat surface) would still be
> possible to check if the point is contained in this convex hull.
>
> Thanks,
>
> Miguel
>
> 2011/7/26 David Gobbi <david.gobbi at gmail.com>
>>
>> Hi Miguel,
>>
>> The vtkDelaunay3D filter is for tetrahedral meshes, but your mesh
>> looks like a triangle mesh.  So my guess is that you should be using
>> vtkDelaunay2D instead.  But since Delanay2D is a 2D filter, you might
>> have to project your mesh onto a flat surface first.
>>
>> Also, Delaunay often performs worse on noiseless data.  If you are
>> working with synthetic data, you will get better results if you
>> perturb each point with a small, random displacement.  With noiseless
>> data, it is often the case that three points will lie along a straight
>> line, and the Delaunay algorithm will consider three such points as
>> forming a degenerate triangle.  Another problem with noiseless data,
>> specifically for rectangular grids, is that they can result in
>> situations where there is more than one valid Delaunay triangulation.
>> These will cause the algorithm to go into deep recursion.
>>
>>  - David
>>
>>
>> 2011/7/25 Miguel Sotaquirá <msotaquira at gmail.com>:
>> > Hi,
>> > I'm using vtkDelaunay3D to create the local (1-ring neighborhood) convex
>> > hull for each point in a mesh. For now I'm using a synthetic, perfectly
>> > regular, noiseless mesh, where each vertex has exactly 6 neighbors.
>> > I'm having troubles creating this convex hull only on one of the
>> > vertices
>> > (the others are computed correctly). In this particular case the convex
>> > hull
>> > computed does NOT include one of the six neighbors, as seen on the image
>> > below:
>> > http://tinypic.com/r/2944hag/7
>> > the purple point being the center of the neighborhood, the gray spheres
>> > its
>> > neighbors and the gray lines the convex hull obtained from
>> > vtkDelaunay3D.
>> > Here's the code I'm using (neighbors are introduced as a polydata named
>> > "pointcloud"):
>> > vtkSmartPointer<vtkDelaunay3D> delaunay3D =
>> > vtkSmartPointer<vtkDelaunay3D>::New();
>> > delaunay3D->SetInput(pointCloud);
>> > delaunay3D->Update();
>> > during execution I get this warning: "vtkDelaunay3D (0x10345a490): 1
>> > degenerate triangles encountered, mesh quality suspect"
>> > How come, since I'm using a synthetic and perfectly regular mesh? As I
>> > mentioned before, for other points (which have the exact same
>> > characteristics) the convex hull is computed correctly.... Also, I've
>> > tried
>> > using the methods "SetTolerance" and "BoundingTriangulationOn" of
>> > vtkDelaunay3D but with no success
>> > Thanks!
>> > Miguel