[vtkusers] vtkDelaunay3D: wrong convex hull

[Miguel Sotaquirá]

Hi David,

You're right, vtkDelaunay3D is not the correct approach in this case. Now
I'm trying to obtain a 2D convex hull (vtkDelaunay2D) by projecting the 3-D
points onto a plane. Here's the code:

// create a plane, seting its origin in (0,0,0) and its normal N (N is the
normal to  the current vertex, the center of the neighborhood)
vtkSmartPointer<vtkPlane> plane = vtkSmartPointer<vtkPlane>::New();
plane->SetOrigin(0.0, 0.0, 0.0);
plane->SetNormal(N[0], N[1], N[2]);

 // project each point in the neighborhood onto the plane
vtkSmartPointer<vtkPoints> ptsProj = vtkSmartPointer<vtkPoints>::New();
double origin[3] = {0.0, 0.0, 0.0};
double normal[3] = {N[0], N[1], N[2]};
double projected[3];
for ( int i = 0; i < pts->GetNumberOfPoints(); i++ ) {
  pts->GetPoint(i,p);
  plane->ProjectPoint( p, origin, normal, projected );
  ptsProj->InsertNextPoint(projected);}

// store projected points in a polydata
vtkSmartPointer<vtkPolyData> ptsForTriang =
vtkSmartPointer<vtkPolyData>::New();
ptsForTriang->SetPoints(ptsProj);

// apply delaunay2D
vtkSmartPointer<vtkDelaunay2D> delaunay2D =
vtkSmartPointer<vtkDelaunay2D>::New();
delaunay2D->SetInput(ptsForTriang);
delaunay2D->Update();

When using this approach to my initial problem I get this:
http://tinypic.com/r/2mre8ma/7

again, some vertices were not included in the convex hull . When I check the
2D convex hull info it says that has 6 points (which is correct) but only 2
cells (the ones that can be seen in the image)...

Is this the correct approach for computing the 2D convex hull (using
projections)? Am I missing something?
Thanks again,
Miguel

2011/7/26 David Gobbi <david.gobbi at gmail.com>

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20110726/594b08d0/attachment.htm>