CGAL users discussion list

[Dimitris Tzionas <>]

Hi Andreas,

I hadn't realize that the demo provides full functionality for so many components, that's actually very useful for the future.

Thank you for your answer, it is of great help!

Best,

Dimitris

On Fri, Sep 12, 2014 at 12:20 PM, Andreas Fabri <> wrote:

Hi Dimitris,

Attached is what the segmentation could give you.
It is in the Polyhedron demo.

Note that a torus is still watertight.  It only
has another genus than a sphere or pretzel.
And the segmentation also works for them.

andreas

On 12/09/2014 12:03, Dimitris Tzionas wrote:

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
<andreas.fabri@geometryfactory.com
<mailto:andreas.fabri@geometryfactory.com>> wrote:

    Hi Dimitris,

    What would you like to compute?  Wouldn't the segmentation
    http://doc.cgal.org/latest/__Manual/packages.html#__PkgSurfaceSegmentationSummary

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

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

        <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>
             <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 <tel:%2B33.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
    <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