Re: Concave hull 3D

Posted by Kenneth Sloan-2 on Aug 09, 2007; 7:50pm
URL: http://imagej.273.s1.nabble.com/Concave-hull-3D-tp3698649p3698650.html

On Aug 9, 2007, at 2:58 AM, Eddie Iannuccelli wrote:

> Hello,
>
> I am currently using QuickHull3D java lib to build a 3D shape from  
> a surface Point3f list. My biological objects (cell nucleus) are  
> not always convex and QuickHull3D always returns convex shapes so  
> now  I am looking for a way to produce concave 3D shapes from  
> surface points (no image available, only surface points list).
>
> Thanks for your advices

This is highly application dependent - both because of wildly  
different data sources and wildly different "ground truth" objects.

Allow me to suggest a method that lies somewhere in the middle ground  
between theoretical purity and practical usefulness:

a) compute the convex hull
b) find the interior vertex (not on the hull) that is CLOSEST TO the  
hull and the FACE of the hull that is closest to that interior vertex  
(your basic tool will be Distance(point,face).  Be careful - there  
are a lot of cases to consider.  Be especially wary of points where  
the closest point on the hull is an edge or vertex of the hull!!!
c) subdivide the hull face by inserting the interior vertex and  
triangulating.  Here, you are replacing one face with several -  
effectively pushing in on the face so that the interior vertex is  
exposed.
In the nasty cases I mention above, you will want to modify TWO OR  
MORE existing hull faces.
d) go back to b) and repeat, as needed

As always in geometric computation - be VERY WARY of numerical  
issues, long-skinny faces, coincidental arrangements, etc., etc., etc.

For a more theoretical treatment, you might want to Google "Alpha  
Shapes".  But, my recommendation is to implement the above method so  
that you can get useful work done while you are digesting the  
literature on Alpha Shapes.

For "almost convex" blobs, you might consider finding the centroid  
and seeing if you can build a "museum viewable" surface that includes  
all of the vertices.  But, this is unlikely to work for all but the  
most simple shapes.  The first method (above) is about as easy to  
implement, and will handle more complex shapes.

As others have noted, the result MAY NOT be unique, and there may be  
application-dependent constraints that you want to add.  Convex Hull  
is so common partly because it's useful, but also because it has a  
clean mathematical description.  Your problem does not - so expect  
things to be messy.

--
Kenneth Sloan                                          
[hidden email]
Computer and Information Sciences                        [phone]
University of Alabama at Birmingham              FAX [phone]
Birmingham, AL 35294-1170                http://www.cis.uab.edu/sloan/