CGAL users discussion list

[Dimitris Tzionas <>]

Hi Andreas,

As part of my tracking pipeline, I need physics simulation.

In a physics simulation world (using bullet-physics) I have very non-realistic simulation for concave objects.

I would like to decompose them, so that each concave mesh is represented as a compound/collection of (more-or-less) convex meshes.

This decomposition should be approximate (as previous emails state) because the mesh itshelf is noisy.

If we take a hand for example, a decomposition into parts based just on the skinning weights (not enforcing convexity) is like this:

(color is the same for each zone, but for example the 4 yellow parts or the 5 cyan parts are separate)

I was hoping to get something that is a bit finer than the illustrated result (e.g. fight the non-convexity of cyan parts), mainly because areas between fingers (cyan color) might cause problems.
​

To be honest, I didn't think of the modules that you propose..

Luckily enough my meshes are watertight with no holes (e.g. no torus-like objects), but handling objects with holes might cover a future need.

Another approach would be the HACD library (https://www.youtube.com/watch?v=T0U0_9M9LTw, http://www.khaledmammou.com/hacd.html), which has been used by others with Bullet, 

but I wanted to try CGAL first for added robustness and less additional dependencies in my project.

Best,

Dimitris

On Fri, Sep 12, 2014 at 11:04 AM, Andreas Fabri <> wrote:

Hi Dimitris,

What would you like to compute?  Wouldn't the segmentation
http://doc.cgal.org/latest/Manual/packages.html#PkgSurfaceSegmentationSummary
be a solution? You might cut the surface and fill the holes
to make each part a closed surface again.

andreas

On 12/09/2014 10:59, Dimitris Tzionas wrote:

Hi Sebastien,

The double number of vertices was because of a non commented-out code
snippet that was doing the same thing twice (converting into Polygon
representation the same mesh, both from memory and the .off file).
My fault.

However, the most important thing I saw after experiments is exactly
what you say.
It seems that the convex decomposition that CGAL does is an exact one
(no approximations).
Meshes that are the result of scanning real-life surfaces will have a
somewhat noisy surface and this will result in a large number convex
sub-parts, that is too big for practical scenarios.
So, I totally agree with what you say.

For the record, this is the output for the mesh that I attached:

POL.size_of_vertices = 10002

POL.size_of_facets = 20000

POL.is_closed = 1

POL.is_pure_triangle = 1


NEF.is_empty: 0

Nef vertices: 10002

Nef edges: 30000

Nef facets: 20000

Nef volumes: 2

Nef is_simple: 1


decomposition into 12780 convex parts


The decomposition took more than 30 minutes (I don't have exact timing),
but probably this was exactly because of the noisy mesh,

and thus (probably) because of added workload. Hopefully with clean
meshes one can get much better timings.


Thanks for the valuable feedback!


Dimitris




On Fri, Sep 12, 2014 at 10:05 AM, Sebastien Loriot (GeometryFactory)

< <mailto:>> wrote:

    I loaded the model in the polyhedron demo, converted it into nef and
    I got 10002 vertices.
    Then I ran the convex decomposition which indeed took some time but
    provided a convex decomposition that is valid but obviously not the
    minimal one.

    The kind of model the algorithm was written for is more for mechanical
    parts rather than "noisy" or smooth surfaces.
    IMO, it should not be used in such cases.

    Sebastien.

    On 09/11/2014 08:56 PM, Dimitris Tzionas wrote:

        Some additional info, sorry for the 2nd email:

        POL.is_pure_triangle = 1 -> that means that luckily I don't have
        degenerate triangles.


        Also, step 3 (CGAL::convex_decomposition_3(__NEF))  finished
        after much
        time (~1 hour?) and returned 25642 convex parts,

        while the original OFF file (attached) has 20000 triangles (problem
        correlated with what I reported about 2x the number of vertices).


        OFF

        10002 20000 0


        59.297 -0.455242 -70.6708

        66.3921 -1.96008 -58.9775


        On Thu, Sep 11, 2014 at 8:54 PM, Dimitris Tzionas
        < <mailto:>
        <mailto: <mailto:>>__>
        wrote:

             Some additional info, sorry for the 2nd email:

             POL.is_pure_triangle = 1 -> that means that luckily I don't
        have
             degenerate triangles.


             Also, step 3 (CGAL::convex_decomposition_3(__NEF))
        finished after
             much time (~1 hour?) and returned 25642 convex parts,

             while the original OFF file (attached) has 20000 triangles
        (problem
             correlated with what I reported about 2x the number of
        vertices).


             OFF

             10002 20000 0


             59.297 -0.455242 -70.6708

             66.3921 -1.96008 -58.9775

             ...




             On Thu, Sep 11, 2014 at 8:09 PM, Dimitris Tzionas
             < <mailto:>
        <mailto: <mailto:>>__>
        wrote:

                 Hi all,

                 In a physics simulation I have a problem with concave
        meshes, so
                 it seems that I really have to do decomposition in convex
                 mesh-parts.

                 Since CGAL covered successfully past needs, I was
        hoping to use
                 this again.

                 It seems that it is doable only by using Nef_polyhedron_3.
        http://doc.cgal.org/latest/__Convex_decomposition_3/index.__html
        <http://doc.cgal.org/latest/Convex_decomposition_3/index.html>

                 In order to have this representation:
                 - I first read a .off file (ideally this should happen from
                 memory, but my code is slower than CGAL's built-in
        reader from
                 file) in a Polyhedron_3. My mesh is closed and depicted
        fine
                 with the Polyhedron viewer demo.
                 - then I convert to a Nef_polyhedron_3.
                 - Finally I try to use CGAL::convex_decomposition_3

                 - The first part is very fast.

                 std::ifstream  file("/home/dimitris/Model___Hand_R.off");

                 file  >>  POL;

                 However instead of 10002 vertices I noticed that I get

                 POL.size_of_vertices = 20004

                 POL.is_closed = 1


                 - The second part takes ~15sec for 20k vertices.

                 Nef_polyhedron_3  NEF(  POL  );

                 NEF.is_empty: 0

                 Nef vertices: 20004

                 Nef edges: 60000

                 Nef facets: 40000

                 Nef volumes: 3


                 - The third part takes forever and never returns anything.

                 CGAL::convex_decomposition_3(  NEF  );


                 Could it be that I'm doing something very obviously wrong?

                 Could I get best practices hints for this problem?

                 What is a sensible run-time for CGAL's approach?


                 Some extra info on the current setup:


                 typedef
        CGAL::Exact_predicates_exact___constructions_kernel        Kernel;

                 typedef  CGAL::Polyhedron_3<Kernel>
                    Polyhedron;

                 typedef  CGAL::Nef_polyhedron_3<Kernel,
        CGAL::SNC_indexed_items>  Nef_polyhedron_3;


                 Thank you in advance for potential hints,

                 Dimitris





    --
    You are currently subscribed to cgal-discuss.
    To unsubscribe or access the archives, go to
    https://sympa.inria.fr/sympa/__info/cgal-discuss
    <https://sympa.inria.fr/sympa/info/cgal-discuss>

--
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss