CGAL users discussion list

[Dimitris Tzionas <>]

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

        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