cgal icon indicating copy to clipboard operation
cgal copied to clipboard

Published 20 hours ago • verified publisher icon CGAL

Add coplanar decimation

Open sloriot opened this issue 4 years ago • 10 comments

Summary of Changes

Add a function in PMP that retriangulates a coplanar patch as well as functions to detect coplanar patches. There are also overloads that are able to handle the simplification of polyhedral complexes. Retriangulation is using CDT2.

TODO:

  • [x] split the example in 2, one part should go into test (together with the data provided)
  • [x] decide license group
  • [ ] decide on the best approximate method, region growing is probably the way to go
  • [ ] find better function names
  • [ ] small feature
  • [ ] fix dependencies
  • [ ] update SMS user manual + ref manual
  • [ ] update PMP user manual + ref manual
  • [ ] demo plugins

This PR depends on PR #5563.

Release Management

  • Affected package(s): PMP, Surface Mesh Segmentation
  • Feature/Small Feature (if any): TODO
  • Link to compiled documentation (obligatory for small feature) wrong link name to be changed
  • License and copyright ownership: GF

sloriot avatar Feb 15 '21 08:02 sloriot

@danston I'd be interested to discuss region growing on a mesh again to see if I can replace the PCA approach with that.

sloriot avatar Feb 15 '21 12:02 sloriot

@danston I moved the segmentation part into the Surface_mesh_segmenation() package, into the function segment_via_plane_fitting().

sloriot avatar Feb 23 '21 16:02 sloriot

action failed because of this error: Differences in Polygon_mesh_processing: Principal_component_analysis are new and not committed.

sloriot avatar Jan 31 '22 11:01 sloriot

Looks like this fails to compile w/ Epeck (calling remesh_planar_patches(Surface_mesh<Epeck>())):

In file included from /usr/local/include/CGAL/Exact_predicates_exact_constructions_kernel.h:27:
In file included from /usr/local/include/CGAL/Lazy_kernel.h:18:
/usr/local/include/CGAL/Static_filtered_predicate.h:180:40: error: member reference base type 'const double' is not a structure or union
    std::pair<T5,bool> aa5 = convert(a5.approx());
                                     ~~^~~~~~~
/usr/local/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:130:12: note: in instantiation of function template specialization 'CGAL::Static_filtered_predicate<CGAL::Simple_cartesian<CGAL::Interval_nt<false>>, CGAL::Filtered_predicate<CGAL::CommonKernelFunctors::Compare_dihedral_angle_3<CGAL::Simple_cartesian<__gmp_expr<mpq_t, mpq_t>>>, CGAL::CommonKernelFunctors::Compare_dihedral_angle_3<CGAL::Simple_cartesian<CGAL::Interval_nt<false>>>, CGAL::Exact_converter<CGAL::Epeck, CGAL::Simple_cartesian<__gmp_expr<mpq_t, mpq_t>>>, CGAL::Approx_converter<CGAL::Epeck, CGAL::Simple_cartesian<CGAL::Interval_nt<false>>>, true>, CGAL::Filtered_predicate<CGAL::CommonKernelFunctors::Compare_dihedral_angle_3<CGAL::Simple_cartesian<CGAL::Mpzf>>, CGAL::CommonKernelFunctors::Compare_dihedral_angle_3<CGAL::Simple_cartesian<CGAL::Interval_nt<false>>>, CGAL::Cartesian_converter<CGAL::Type_equality_wrapper<CGAL::Cartesian_base_no_ref_count<double, CGAL::Epick>, CGAL::Epick>, CGAL::Simple_cartesian<CGAL::Mpzf>, CGAL::NT_converter<double, CGAL::Mpzf>>, CGAL::Cartesian_converter<CGAL::Type_equality_wrapper<CGAL::Cartesian_base_no_ref_count<double, CGAL::Epick>, CGAL::Epick>, CGAL::Simple_cartesian<CGAL::Interval_nt<false>>, CGAL::NT_converter<double, CGAL::Interval_nt<false>>>, true>>::operator()<CGAL::Point_3<CGAL::Epeck>, CGAL::Point_3<CGAL::Epeck>, CGAL::Point_3<CGAL::Epeck>, CGAL::Point_3<CGAL::Epeck>, double>' requested here
    return pred(p, q, r, s, coplanar_cos_threshold) == CGAL::LARGER;
           ^
/usr/local/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:189:12: note: in instantiation of function template specialization 'CGAL::Polygon_mesh_processing::Planar_segmentation::is_edge_between_coplanar_faces<CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>, CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>::Property_map<CGAL::SM_Vertex_index, CGAL::Point_3<CGAL::Epeck>>, CGAL::SM_Edge_index>' requested here
      if (!is_edge_between_coplanar_faces(e, tm, coplanar_cos_threshold, vpm))
           ^
/usr/local/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:374:3: note: in instantiation of function template specialization 'CGAL::Polygon_mesh_processing::Planar_segmentation::mark_constrained_edges<CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>, CGAL::internal::Dynamic<CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>, CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>::Property_map<CGAL::SM_Edge_index, bool>>, CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>::Property_map<CGAL::SM_Vertex_index, CGAL::Point_3<CGAL::Epeck>>>' requested here
  mark_constrained_edges(tm, edge_is_constrained, coplanar_cos_threshold, vpm);
  ^
/usr/local/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:989:26: note: in instantiation of function template specialization 'CGAL::Polygon_mesh_processing::Planar_segmentation::tag_corners_and_constrained_edges<CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>, CGAL::internal::Dynamic<CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>, CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>::Property_map<CGAL::SM_Vertex_index, unsigned long>>, CGAL::internal::Dynamic<CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>, CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>::Property_map<CGAL::SM_Edge_index, bool>>, CGAL::internal::Dynamic<CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>, CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>::Property_map<CGAL::SM_Face_index, unsigned long>>, CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>::Property_map<CGAL::SM_Vertex_index, CGAL::Point_3<CGAL::Epeck>>>' requested here
    Planar_segmentation::tag_corners_and_constrained_edges(tm, coplanar_cos_threshold, vertex_corner_id, edge_is_constrained, face_cc_ids, vpm);
                         ^
cgalutils-repair.cc:24:34: note: in instantiation of function template specialization 'CGAL::Polygon_mesh_processing::remesh_planar_patches<CGAL::Surface_mesh<CGAL::Point_3<CGAL::Epeck>>, CGAL::Named_function_parameters<bool, CGAL::internal_np::all_default_t>>' requested here
  CGAL::Polygon_mesh_processing::remesh_planar_patches(mesh);
                                 ^
I

ochafik avatar Feb 10 '22 14:02 ochafik

@ochafik Should be fixed now.

sloriot avatar Feb 10 '22 14:02 sloriot

@sloriot Wow thanks! This code works amazingly and seems to fixe exponential growth of nested unions in this model.

Are there any caveats to using it? Would be amazing if this could land, even if just in the experimental namespace.

Edit: pasted the problematic part of the model here for reference

ochafik avatar Feb 10 '22 14:02 ochafik

In your case, it might be even faster to keep track of the original faces to avoid the re-detection of planar parts. This can be done with the visitor of the corefinement function.

sloriot avatar Feb 10 '22 15:02 sloriot

The goal is to have it in 5.5

sloriot avatar Feb 10 '22 15:02 sloriot

@sloriot oh I see... "just" need to see which of these sibling faces are still standing at the end of the corefinement? Are there any existing helpers to do the job?

ochafik avatar Feb 10 '22 17:02 ochafik

In your case, it might be even faster to keep track of the original faces to avoid the re-detection of planar parts. This can be done with the visitor of the corefinement function.

@sloriot I've taken a stab at this in https://github.com/openscad/openscad/pull/4117, with moderate success (prevents some combinatorial explosions but also explodes in many cases). I'd highly welcome any feedback on it :-)

ochafik avatar Feb 12 '22 21:02 ochafik

/build:v0

sloriot avatar Feb 13 '23 18:02 sloriot

There was an error while building the doc: /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command `\TODO'

github-actions[bot] avatar Feb 13 '23 18:02 github-actions[bot]

/build:v0

sloriot avatar Feb 14 '23 07:02 sloriot

There was an error while building the doc: /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:40: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:41: warning: Found unknown command \TODO' /home/runner/work/cgal/cgal/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/remesh_planar_patches.h:42: warning: Found unknown command `\TODO'

github-actions[bot] avatar Feb 14 '23 07:02 github-actions[bot]

/build:v0

sloriot avatar Feb 14 '23 07:02 sloriot

The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/5461/v0/Manual/index.html

github-actions[bot] avatar Feb 14 '23 07:02 github-actions[bot]

/build:v1

sloriot avatar Feb 27 '23 14:02 sloriot

The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/5461/v1/Manual/index.html

github-actions[bot] avatar Feb 27 '23 14:02 github-actions[bot]

/force-build:v1

sloriot avatar Feb 27 '23 16:02 sloriot

The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/5461/v1/Manual/index.html

github-actions[bot] avatar Feb 27 '23 16:02 github-actions[bot]

New warnings in CGAL-5.6-Ic-197/Polyhedron_Demo

sloriot avatar Mar 15 '23 15:03 sloriot

/force-build:v1

afabri avatar Mar 20 '23 09:03 afabri

The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/5461/v1/Manual/index.html

github-actions[bot] avatar Mar 20 '23 09:03 github-actions[bot]

/force-build:v1

sloriot avatar Mar 20 '23 18:03 sloriot

The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/5461/v1/Manual/index.html

github-actions[bot] avatar Mar 20 '23 18:03 github-actions[bot]

@afabri @MaelRL @soesau the user manual is here.

sloriot avatar Mar 20 '23 19:03 sloriot

Runtime error here

sloriot avatar Apr 11 '23 07:04 sloriot

Successfully tested in CGAL-5.6-Ic-223

sloriot avatar Apr 16 '23 20:04 sloriot