[vtkusers] 3D constrained delaunay triangulation

[Luca Antiga]

Hi,
 Tetgen will give you proper constrained Delaunay in 3D. However,
there is an all-VTK workaround if your surface is reasonably dense and
regular (real computational geometrists, I apologize :-) ).
Compute the 3D Delaunay with vtkDelaunay3D, you'll get a
tetrahedralized convex hull. Then peel off the tets for which the dot
product between the vectors from each vertex to the tet circumcenter
and each vertex outward normal is positive. If the original surface is
dense and regular, you'll be left with something that is very close to
a constrained Delaunay (albeit without theoretical guarantees). I used
this method a lot in practice and it worked well for my needs.
You can get a simple class implementing the above at www.vmtk.org, the
class is vmtk/vtkVmtk/ComutationalGeometry/vtkvmtkInternalDelaunayExtractor.h
and .cxx.
Best regards

Luca

2008/11/8, Peter Wainwright <peter.wainwright at ieee.org>:
> On Sat, 2008-11-08 at 11:42 -0500, Bill Lorensen wrote:
>> Peter,
>>
>> Have you looked at
>> vtkDelaunay3D http://www.vtk.org/doc/nightly/html/classvtkDelaunay3D.html
>>
>> Bill
>
> Yes, but AFAICT it cannot be *constrained* to respect a region boundary
> (specified for example as a "piecewise linear complex").  If VTK can do
> this I'll be over the moon... I think this is what the original poster
> was asking for. (see  http://www.imr.sandia.gov/papers/imr14/si.pdf)
>
> Peter
>
>>
>> On Sat, Nov 8, 2008 at 4:30 AM, Peter Wainwright
>> <peter.wainwright at ieee.org> wrote:
>> > On Fri, 2008-11-07 at 16:41 -0800, Rapo Li wrote:
>> >> Hi
>> >> I'm wondering if vtk has any 3D constrained delaunay triangulation
>> >> algorithms implemented. The 2D constrained delaunay triangulation
>> >> works pretty well, but I need to do 3D cases. I know extension from 2D
>> >> to 3D is extremely difficult, and still an open problem for mesh
>> >> generation.
>> > I don't know whether there is any such facility directly available in
>> > VTK. I know that gmsh (http://www.geuz.org/gmsh) can be compiled with
>> > tetgen (http://tetgen.berlios.de/) to create a CDT, and can output
>> > meshes in the VTK file format.
>> >
>> > Peter
>> >>
>> >> Thankxx.
>> >>
>> >>
>> >> _______________________________________________
>> >> This is the private VTK discussion list.
>> >> Please keep messages on-topic. Check the FAQ at:
>> >> http://www.vtk.org/Wiki/VTK_FAQ
>> >> Follow this link to subscribe/unsubscribe:
>> >> http://www.vtk.org/mailman/listinfo/vtkusers
>> > _______________________________________________
>> > This is the private VTK discussion list.
>> > Please keep messages on-topic. Check the FAQ at:
>> > http://www.vtk.org/Wiki/VTK_FAQ
>> > Follow this link to subscribe/unsubscribe:
>> > http://www.vtk.org/mailman/listinfo/vtkusers
>> >
> _______________________________________________
> This is the private VTK discussion list.
> Please keep messages on-topic. Check the FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers
>

-- 
Inviato dal mio dispositivo mobile

Luca Antiga, PhD
 Biomedical Technologies Laboratory
 Biomedical Engineering Department,
 Mario Negri Institute
mail: Villa Camozzi, 24020, Ranica (BG), Italy
phone: +39 035 4535-381
email: antiga at marionegri.it
web: http://villacamozzi.marionegri.it/~luca