Improve the halfedges API

[sebmestrallet]

Summary

This PR extends the halfedges API without breaking existing functions. The only modified files are src/lib/geogram/mesh/mesh_halfedges.h/.cpp.

Motivation

I need to move on surface meshes and the halfedges API of Geogram allowed me to implement the operators I wanted. But I had several issues:

• this part of the library was not very documented (mentioned in the wiki , just the doxygen comments and almost untouched since the switch to GitHub)
• the absence of some getters (origin/extremity vertex indices, right facet) results in a lot of redundancy in my code
• the API is too low level (the user needs to know where are H.facet and H.corner in relation to H, the meaning of next and previous is unclear)
• I ended up creating a child class with custom methods and tweaking things until functions were doing was I expected

Because my code relies more and more on halfedges, I plunge into the original class to understand what was already done and to add what I needed. I found that 'next' and 'prev' don't seem to follow the same convention around facets and vertices...

Notes on existing functions

Could be helpful in the wiki

New functions

• halfedge_vertex_index_from() : because before the user could access the 3D coordinates of the origin but not the vertex index
• halfedge_vertex_index_to() : because before the user could access the 3D coordinates of the extremity but not the vertex index
• halfedge_facet_left() which is basically H.facet but now the user doesn't need to know the underlying structure
• halfedge_facet_right(), to improve readability of the user's code
• move_clockwise_around_facet() which is more explicit than move_to_prev_around_facet()
• move_counterclockwise_around_facet() which is more explicit than move_to_next_around_facet()
• move_clockwise_around_vertex() which is more explicit than move_to_next_around_vertex()
• move_counterclockwise_around_vertex() which is more explicit than move_to_prev_around_vertex()

I hope those modifications are in line with your vision for Geogram.

[sebmestrallet]

Let me know if something should be tweaked. I particular in-code documentation about 'next' and 'prev' whose meaning I must have missed.

I can share the Excalidraw file if it is useful.

[sebmestrallet]

halfedge_movements.webm

Here is a small app (can be appended to the PR) that showcase this behavior:

• move_to_prev_around_facet() → clockwise
• move_to_next_around_facet() → counterclockwise
• move_to_prev_around_vertex() → counterclockwise
• move_to_next_around_vertex() → clockwise

Maybe prev/next make more sense around facets, but I think (counter)clockwise makes more sense around vertices.

[sebmestrallet]

PLOT TWIST : I still don't understand everything but it seems like I was wrong about the halfedges representation.

• H.facet → ~left facet~ right facet
• move_to_prev_around_facet() → ~clockwise~ counterclockwise
• move_to_next_around_facet() → ~counterclockwise~ clockwise
• move_to_prev_around_vertex()→ ~counterclockwise~ clockwise
• move_to_next_around_vertex()→ ~clockwise~ counterclockwise

Incoming fix

[sebmestrallet]

@BrunoLevy my modifications are now ready for review

Addition:

• ASCII representation of a halfedge with the underlying facet and corner
• comments about the facet and corner fields
• getters for the vertex index at the origin/extremity (there were only getters for their coordinates)
• getters for the facet index at the left/right, for better abstraction
• (counter)clockwise movement around a facet (can useful when the halfedge direction is not important)
• (counter)clockwise movement around a vertex, more natural than next and previous (better abstraction)
• allow to ignore borders when moving around a vertex, to avoid to set/unset facet regions when the user need to parse all facets around a vertex, while using facet regions

[sebmestrallet]

There were inconsistencies in the facet normals direction of the meshes I tested (some inward, some outward).

This leads us to a design choice:

• Should Geogram expect outward normals? → make it explicit & provide (counter)clockwise movements
• Should Geogram expect consistent normals directions and works with both cases? → provide adaptive (counter)clockwise movements and either construct a MeshHalfedges with an additional argument, or make MeshHalfedges detect facet normals direction
• Should Geogram not expect a particular normals direction? → only add the comments, getters for vertex indices & 2nd argument of *_around_vertex()

[BrunoLevy]

Hi there ! Wow, impressive work and documentation ! It's fantastic ! (sorry for beeing not reactive at all, I was completely swamped in many projects + administrative tasks). About the names of the things, we do not trust orientation, this is why the names of the functions are not "clockwise" and "counterclockwise" because depending on the input mesh, they may be swapped ! And also, consider a non-closed surface, then it depends from which side you look at the surface. Anyway, at any moment if you want to discuss we can plan a videochat (will be easier than exchanging written messages, especially if we need to draw things).

[sebmestrallet]

Now this PR doesn't assume any orientation (3rd design choice of my last message). No more move_(counter)clockwise_around_facet(), move_(counter)clockwise_around_vertex().

In-code documentation

• Explain what MeshHalfedges, MeshHalfedges::Halfedge and MeshHalfedges::Halfedge.corner are
• MeshHalfedges::Halfedge.facet is described as the supporting facet (no more left or right)
• ASCII representation that explicitly assume counterclockwise vertices order (outward normal)

Allow to check if facet regions are defined

🆕 is_using_facet_region()

To be asserted at the beginning of functions receiving a MeshHalfedges and expecting facet regions

Allow to ignore borders when facet regions are used

with a new argument for move_to_*_around_vertex()

Useful when we need to keep track of all the facets between two border segments

Allow sub-classes to access class attributes

private → protected

Getters for the index of the halfedge's origin/extremity vertices

Currently we can have their 3D coordinates (halfedge_vertex_from() and halfedge_vertex_to()) but not their index.

Because I'm used to the "point" naming from mesh.vertices.point() for coordinates, I wanted to rename existing functions:

• halfedge_vertex_from() → halfedge_point_from() which returns a vec3
• halfedge_vertex_to() → halfedge_point_to() which returns a vec3
• 🆕 halfedge_vertex_from() which returns an index_t
• 🆕 halfedge_vertex_to() which returns an index_t

But inside, the coordinates getters use Geom::mesh_vertex() from mesh_geometry.h, so it seems "vertex" sometimes means the index, sometimes the coordinates. So, I've chosen:

• halfedge_vertex_from() which returns a vec3 (unchanged)
• halfedge_vertex_to() which returns a vec3 (unchanged)
• 🆕 halfedge_vertex_index_from() which returns an index_t
• 🆕 halfedge_vertex_index_to() which returns an index_t

Getters for both facets

• 🆕 halfedge_facet_main() = supporting facet = H.facet
• 🆕 halfedge_facet_secondary() = facet at the other side of H

Getters for facet corners

• 🆕 halfedge_bottom_main_corner() = facet corner of the main facet which is on the origin vertex
• 🆕 halfedge_bottom_secondary_corner() = facet corner of the secondary facet which is on the origin vertex
• 🆕 halfedge_top_main_corner() = facet corner of the main facet which is on the extremity vertex
• 🆕 halfedge_top_secondary_corner() = facet corner of the secondary facet which is on the extremity vertex