distance, ... ? What do you think (your nasty cases afraid me a bit ;) ?
> 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 +1-205-934-2213
> University of Alabama at Birmingham FAX +1-205-934-5473
> Birmingham, AL 35294-1170
http://www.cis.uab.edu/sloan/