How to extract the convex hull

[Lisa S. Avila]

If you don't need the exact convex hull you can use vtkHull - it will take
some arbitrary set of planes and produce a convex bounding object that
contains (at most) polygons on those planes (some planes drop out).
teapotHulls.tcl is an example of how to use it. There are convenience
functions for adding planes, and it works well if your convex hull is
necessary only for visualization / rendering purposes. 

Lisa

At 08:55 AM 10/6/99 -0500, John Washbourne wrote:
>Mirco Mueller wrote:
>
>>     I wonder, if vtk supports the automatic generation of a convex hull
>> for an arbitrary set of 3D-points via a special filter. Sofar neither
>> did I find anything in the "User's Guide" nor in the FAQ.
>>
>
>Mirco,
>
>This subject comes up quite often around here. Some weeks ago I was
invoved with
>the same operation. Depending on the quantity of points, you might try
>vtkDelaunay3D, as the delaunay triangulation is a pretty similar beast to the
>convex hull. For large numbers of points this filter is EXTREMELY SLOW. I
tried
>with 70,000 or so points and gave up waiting before the filter finished.
>
>There is some free software out there for finding convex hulls, and some
of it
>works very rapidly. What I found to be the quickest in my brief survey is at:
>
>http://cm.bell-labs.com/netlib/voronoi/hull.html
>
>I hacked at this code and eventually ended up with a subroutine that I
call with
>pointers to a set of 3D points (not passed as a vtkDataSet, merely as a
list of
>float* X, float *Y, float *Z points). The subroutine returns the number of
faces
>in the hull and the integer connection list of the faces of the hull as
>triangles (with the integer refering to the original list of points). This is
>not a TriangleList as in vtk, so you do have random duplication, and you also
>have to keep track of the original list of points even though you don't
use the
>interior points.
>
>With some more time this could be adapted to vtk ...
>
>Anyway, one tip on using the hull software: I used the randomize feature
(this
>shuffles the list of input points). This increased speed by at least an
order of
>magnitude for my data. Also, if you have Geomview (www.geom.umn.edu), you can
>have the hull program (not my hack), produce an output OFF file that you can
>look at to quickly QC the convex hull.
>
>If you are interested I can provide you with my hack/kludge for your
programming
>pleasure.
>
>If you later decide that you need to evaluate whether a point is inside the
>hull, we should consult with David Pont (david.pont at forestresearch.co.nz),
as he
>has written a VTK polygonal surface Implicit Function.
>
>regards,
>
>john
>
> 



-----------------------------------------------------------------------------
This is the private VTK discussion list.  Please keep messages on-topic.
Check the FAQ at: <http://www.automatrix.com/cgi-bin/vtkfaq>
To UNSUBSCRIBE, send message body containing "unsubscribe vtkusers" to
<majordomo at gsao.med.ge.com>.  For help, send message body containing
"info vtkusers" to the same address.     Live long and prosper.
-----------------------------------------------------------------------------