Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

PMP: Add a function to find edges with smallest/largest dihedral angle #8676

Open
wants to merge 39 commits into
base: master
Choose a base branch
from
Open

PMP: Add a function to find edges with smallest/largest dihedral angle #8676

wants to merge 39 commits into from

Conversation

afabri
Copy link
Member

@afabri afabri commented Jan 3, 2025 •
edited
Loading

Summary of Changes

Add the function minmax_dihedral_angle() to identify the non-border edges with smallest/largest dihedral angle.
It returns the edge descriptors and the angles in degree.

  • Deal with non-triangle case
  • What to do with edges adjacent to degenerate faces?
  • Add to statistics in Lab
  • Small Feature

Release Management

  • Affected package(s): Polygon Mesh Processing
  • Feature/Small Feature (if any): link
  • Link to compiled documentation (obligatory for small feature) wrong link name to be changed
  • License and copyright ownership: GeometryFactory

hoskillua and others added 16 commits April 19, 2022 01:04
@hoskillua
adding longest_edge()
be7c1fd
@hoskillua
added check for empty mesh and updated doc
fef670d
@hoskillua
update using compare_squared_distance_3()
6beaea6
@hoskillua
updated changes, reference manual and measures_test.cpp with longest_…
c460c0e 
…edge()
@hoskillua
removed trailing spaces.
d20cb49
@sloriot
null_edge() is actually not part of the concept :(
83a9e2c
@hoskillua
Merge remote-tracking branch 'upstream/master'
f5f2b3f
@hoskillua
Merge remote-tracking branch 'cgal/master' into master
440eef1
@MaelRL
Merge remote-tracking branch 'cgal/master' into PMP-Add_longest_borde…
eb4dcdc 
…r-hoskillua
@MaelRL
Clean code
dcc85a7
@MaelRL
Do not require the full Kernel
83b8e47
@MaelRL
Minor fixes
3f6ce22
@MaelRL
Add more tests
e0719dd
@MaelRL
Re-implement without std::max_element
a5b79b9 
std::max_element demands a forward iterator, which we do not have
for Polyhedron_3: its iterator type is a boost transform_iterator
with the edge_descriptor built on-the-fly when dereferenced.

The error in practice is a static assertion for compilers
that do in fact enforce the requirement of the iterator category
like:

error: static assertion failed due to requirement
'std::is_same<
   boost::iterators::detail::iterator_category_with_traversal<
     std::input_iterator_tag,
     boost::iterators::bidirectional_traversal_tag>,
   std::forward_iterator_tag>::value'

We could probably have an iterator with state or something, but
it is not worth it for now...
@MaelRL
Minor text fix
7313b98
@afabri
PMP: Add overload of detect_sharp_edges()
2777ec7
@afabri afabri requested review from sloriot and janetournois January 3, 2025 10:10
@afabri afabri self-assigned this Jan 3, 2025
@afabri afabri added this to the 6.1-beta milestone Jan 3, 2025
@afabri

This comment was marked as outdated.

Sign in to view
@github-actions GitHub Actions

This comment was marked as outdated.

Sign in to view
@afabri

This comment was marked as outdated.

Sign in to view
@MaelRL
Copy link
Member

MaelRL commented Jan 13, 2025

Both functions now have the same API:

std::pair<std::pair<boost::graph_traits<PolygonMesh>::edge_descriptor`, FT>,
          std::pair<boost::graph_traits<PolygonMesh>::edge_descriptor`, FT> >
minmax_XXX(const EdgeRange& edge_range,
           const PolygonMesh& pmesh,
           const CGAL_NP_CLASS& np = parameters::default_values())

An annoying detail is that we compute and compare to current min/max rather than using compare_dihedral / compare_squared_distance so we are not using predicates.

@afabri
Copy link
Member Author

afabri commented Jan 13, 2025

These functions are trivially paralleliozable. Do we take care of that?

@MaelRL MaelRL force-pushed the PMP-dihedral_angle-GF branch from 6486b94 to 48d74ca Compare January 15, 2025 16:32
sloriot
sloriot reviewed Jan 16, 2025
View reviewed changes
Installation/CHANGES.md Outdated Show resolved Hide resolved
@MaelRL
Copy link
Member

MaelRL commented Jan 17, 2025 •
edited
Loading

Here is some benchmark data for comparison

== Version with pure sequential for() ==
Test Surface_mesh Data/data/meshes/ultra_refined_elephant.off with Kernel N4CGAL5EpickE [refined_elephant + a few loop subdivision iterations, 11.4M vertices]
minmax edge length (Sequential) took: 2.483997106552124
shortest edge is: 0.19143556239568818 0.43660117747950594 0.065395353183125629 -> 0.19143235224852481 0.4366109497942196 0.065392072742199991, length = 1.0796502782843833e-05
longest edge is: 0.11678651407976268 0.019038259873648222 -0.07872823190072567 -> 0.11762225347327011 0.018338970401551753 -0.079917521353354407, length = 0.0016130330132328645

== Version CGAL::for_each + mutex ==
Test Surface_mesh Data/data/meshes/ultra_refined_elephant.off with Kernel N4CGAL5EpickE
minmax edge length (Sequential) took: 2.7448878288269043
minmax edge length (Parallel if available) took: 6.6493420600891113 // 3x slower
shortest edge is: 0.19143556239568818 0.43660117747950594 0.065395353183125629 -> 0.19143235224852481 0.4366109497942196 0.065392072742199991, length = 1.0796502782843833e-05
longest edge is: 0.11678651407976268 0.019038259873648222 -0.07872823190072567 -> 0.11762225347327011 0.018338970401551753 -0.079917521353354407, length = 0.0016130330132328645

== Version with tbb::parallel_reduce ==
Test Surface_mesh Data/data/meshes/ultra_refined_elephant.off with Kernel N4CGAL5EpickE
minmax edge length (Sequential) took: 2.4808948040008545
minmax edge length (Parallel if available) took: 0.21971297264099121
shortest edge is: 0.19143556239568818 0.43660117747950594 0.065395353183125629 -> 0.19143235224852481 0.4366109497942196 0.065392072742199991, length = 1.0796502782843833e-05
longest edge is: 0.11678651407976268 0.019038259873648222 -0.07872823190072567 -> 0.11762225347327011 0.018338970401551753 -0.079917521353354407, length = 0.0016130330132328645

Test Polyhedron Data/data/meshes/ultra_refined_elephant.off with Kernel N4CGAL5EpickE
minmax edge length (Sequential) took: 0.47276496887207031 // 5x faster than Surface_mesh sequential ???
minmax edge length (Parallel if available) took: 1.6012129783630371 // 3x slower than sequential ???

So the mutex ruins parallel gains but there is more to investiguate.

@sloriot
Copy link
Member

sloriot commented Jan 20, 2025

Successfully tested in CGAL-6.1-Ic-66

@afabri
Copy link
Member Author

afabri commented Jan 20, 2025

Successfully tested in CGAL-6.1-Ic-66

But not ready to get merged as parallel sometimes slower than sequential.

@MaelRL @sloriot
Prevent bad edge_descriptor links
13c1e4c 
Co-authored-by: Sebastien Loriot <sloriot.ml@gmail.com>
@github-actions github-actions bot removed the Tested label Jan 20, 2025
@github-actions GitHub Actions
Copy link

This pull-request was previously marked with the label Tested, but has been modified with new commits. That label has been removed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@sloriot sloriot sloriot left review comments

@janetournois janetournois Awaiting requested review from janetournois

Assignees

@afabri afabri

Labels
CHANGES.md not updated Not yet approved The feature or pull-request has not yet been approved. Pkg::PMP Small feature Work in progress
Projects
None yet
Milestone
6.1-beta
Development

Successfully merging this pull request may close these issues.
4 participants
@afabri @sloriot @MaelRL @hoskillua