[vtkusers] vtkDelaunay3D: wrong convex hull

[David Gobbi]

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
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Please keep messages on-topic and check the VTK FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ
>
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers
>
>