Concave hull 3D

[Eddie Iannuccelli]

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

--
******************************************
Eddie Iannuccelli
Laboratoire de génétique cellulaire
INRA - Castanet Tolosan
Tel: [phone] / Fax: [phone]

[dscho]

Hi,

On Thu, 9 Aug 2007, Eddie Iannuccelli wrote:

> 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).

This is not a well defined problem.  Imagine a cube.  Put points onto all
8 of its corners.  Now put a 9th point into its center.

The convex hull is well defined.  But what should a concave hull do?

Should it produce the cube? (Volume 1 for dimensions 1x1x1)

Or should it produce a cube with one "dent", i.e. replace one side by the
four triangles built by the four corners and the cube's center?  (Volume
5/6 for dimensions 1x1x1)

Or should it just produce the triangles built by any two adjacent corners
and the cube's center (Volume 0 for any dimension)?

It is highly ambiguous.

Ciao,
Dscho

[Eddie Iannuccelli]

I agree with you but I was wondering if the problem coud be solved by
using some "biological" constraints on angles and distances between 2
surface points. My objects are always more continous and curved than
your cube example, concave regions are generally made by several points
in a progressive curve so this kind of ambiguous case are not so much
encountered. I know some plugins can get isosurface from an imagestack.
Could that isosurface approach resolve my problem ?

Regards

Johannes Schindelin a écrit :

> Hi,
>
> On Thu, 9 Aug 2007, Eddie Iannuccelli wrote:
>
>  
>> 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).
>>    
>
> This is not a well defined problem.  Imagine a cube.  Put points onto all
> 8 of its corners.  Now put a 9th point into its center.
>
> The convex hull is well defined.  But what should a concave hull do?
>
> Should it produce the cube? (Volume 1 for dimensions 1x1x1)
>
> Or should it produce a cube with one "dent", i.e. replace one side by the
> four triangles built by the four corners and the cube's center?  (Volume
> 5/6 for dimensions 1x1x1)
>
> Or should it just produce the triangles built by any two adjacent corners
> and the cube's center (Volume 0 for any dimension)?
>
> It is highly ambiguous.
>
> Ciao,
> Dscho
>
>  

--
******************************************
Eddie Iannuccelli
Laboratoire de génétique cellulaire
INRA - Castanet Tolosan
Tel: [phone] / Fax: [phone]

[ctrueden]

Hi Eddie,

Googling for "concave hull" there is quite a bit of information about
this idea. One informative writeup is here:
http://ubicomp.algoritmi.uminho.pt/local/concavehull.html

It appears that the algorithm essentially works based on density and
proximity. Unfortunately the link to the online version of their
algorithm seems nonfunctional, but you could try emailing them. It is
probably worth starting from some existing code, as this problem is
certainly nontrivial.

-Curtis

On 8/9/07, Eddie Iannuccelli <[hidden email]> wrote:

> I agree with you but I was wondering if the problem coud be solved by
> using some "biological" constraints on angles and distances between 2
> surface points. My objects are always more continous and curved than
> your cube example, concave regions are generally made by several points
> in a progressive curve so this kind of ambiguous case are not so much
> encountered. I know some plugins can get isosurface from an imagestack.
> Could that isosurface approach resolve my problem ?
>
> Regards
>
> Johannes Schindelin a écrit :
> > Hi,
> >
> > On Thu, 9 Aug 2007, Eddie Iannuccelli wrote:
> >
> >
> >> 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).
> >>
> >
> > This is not a well defined problem.  Imagine a cube.  Put points onto all
> > 8 of its corners.  Now put a 9th point into its center.
> >
> > The convex hull is well defined.  But what should a concave hull do?
> >
> > Should it produce the cube? (Volume 1 for dimensions 1x1x1)
> >
> > Or should it produce a cube with one "dent", i.e. replace one side by the
> > four triangles built by the four corners and the cube's center?  (Volume
> > 5/6 for dimensions 1x1x1)
> >
> > Or should it just produce the triangles built by any two adjacent corners
> > and the cube's center (Volume 0 for any dimension)?
> >
> > It is highly ambiguous.
> >
> > Ciao,
> > Dscho
> >
> >
>
> --
> ******************************************
> Eddie Iannuccelli
> Laboratoire de génétique cellulaire
> INRA - Castanet Tolosan
> Tel: [phone] / Fax: [phone]
>

[Eddie Iannuccelli]

Curtis,
thanks for your response, I already saw this url yesterday (plus
another  interresting one at
http://www.ircnet.lu/matching/completerec.cfm?BBS_ID=23334&org=106&back=true)
but before starting coding, I was hoping that someone did the job ;-)  ....
Till now, looks like no one did it :'(

Regards

Curtis Rueden a écrit :

> Hi Eddie,
>
> Googling for "concave hull" there is quite a bit of information about
> this idea. One informative writeup is here:
> http://ubicomp.algoritmi.uminho.pt/local/concavehull.html
>
> It appears that the algorithm essentially works based on density and
> proximity. Unfortunately the link to the online version of their
> algorithm seems nonfunctional, but you could try emailing them. It is
> probably worth starting from some existing code, as this problem is
> certainly nontrivial.
>
> -Curtis
>
> On 8/9/07, Eddie Iannuccelli <[hidden email]> wrote:
>  
>> I agree with you but I was wondering if the problem coud be solved by
>> using some "biological" constraints on angles and distances between 2
>> surface points. My objects are always more continous and curved than
>> your cube example, concave regions are generally made by several points
>> in a progressive curve so this kind of ambiguous case are not so much
>> encountered. I know some plugins can get isosurface from an imagestack.
>> Could that isosurface approach resolve my problem ?
>>
>> Regards
>>
>> Johannes Schindelin a écrit :
>>    
>>> Hi,
>>>
>>> On Thu, 9 Aug 2007, Eddie Iannuccelli wrote:
>>>
>>>
>>>      
>>>> 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).
>>>>
>>>>        
>>> This is not a well defined problem.  Imagine a cube.  Put points onto all
>>> 8 of its corners.  Now put a 9th point into its center.
>>>
>>> The convex hull is well defined.  But what should a concave hull do?
>>>
>>> Should it produce the cube? (Volume 1 for dimensions 1x1x1)
>>>
>>> Or should it produce a cube with one "dent", i.e. replace one side by the
>>> four triangles built by the four corners and the cube's center?  (Volume
>>> 5/6 for dimensions 1x1x1)
>>>
>>> Or should it just produce the triangles built by any two adjacent corners
>>> and the cube's center (Volume 0 for any dimension)?
>>>
>>> It is highly ambiguous.
>>>
>>> Ciao,
>>> Dscho
>>>
>>>
>>>      
>> --
>> ******************************************
>> Eddie Iannuccelli
>> Laboratoire de génétique cellulaire
>> INRA - Castanet Tolosan
>> Tel: [phone] / Fax: [phone]
>>
>>    

--
******************************************
Eddie Iannuccelli
Laboratoire de génétique cellulaire
INRA - Castanet Tolosan
Tel: [phone] / Fax: [phone]

[Kenneth Sloan-2]

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/

[Eddie Iannuccelli]

Hi Kenneth,

thank you for your suggestion :-)
Just a few reformulations/questions:
- in summary : I need to browse each hull face to find closest vertex,
triangulate using it and so on to the end condition : am I right ?
- what is end condition : complete map between hull and surface vertices
(all hull faces are on the surface), time out, minimum  vertex-face
distance, ... ? What do you think (your nasty cases afraid me a bit ;) ?

regards


Kenneth Sloan a écrit :

> 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/

--
******************************************
Eddie Iannuccelli
Laboratoire de génétique cellulaire
INRA - Castanet Tolosan
Tel: [phone] / Fax: [phone]