CGAL users discussion list

[Andreas Fabri <>]

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