CGAL
PMP ordered faces around boundary vertices
How to get an ordered vector of faces around a boundary vertex starting from one edge? The order by default is always random, without any particular sorting around a vertex.
Issue Details
I had to do sorting by edge index, which takes quite a lot of code. Full description of the issue is here: https://github.com/CGAL/cgal/discussions/8931
Source Code - Just for ordering around a vertex part...
/////////////////////////////////////////////////////////////////////////////////
// Face Collection and Edge Extraction
/////////////////////////////////////////////////////////////////////////////////
// Collect all faces adjacent to the boundary vertex and extract their edges.
// This information will be used to determine the adjacency between faces.
std::vector<typename boost::graph_traits<compas::Mesh>::face_descriptor> vertex_faces;
std::vector<std::vector<size_t>> faces_edges;
for(auto h : CGAL::halfedges_around_target(v, mesh_a)) {
auto f = face(h, mesh_a);
if(f != boost::graph_traits<compas::Mesh>::null_face() && std::find(vertex_faces.begin(), vertex_faces.end(), f) == vertex_faces.end()) {
vertex_faces.push_back(f);
auto h = halfedge(f, mesh_a);
std::vector<size_t> edges;
for(auto h : CGAL::halfedges_around_face(h, mesh_a)) {
auto e = edge(h, mesh_a);
edges.push_back(e);
}
faces_edges.push_back(edges);
}
}
// Find the face containing the first boundary edge
int e1_face = -1;
for(int i = 0; i < faces_edges.size(); i++) {
if(std::find(faces_edges[i].begin(), faces_edges[i].end(), e1) != faces_edges[i].end()) {
e1_face = i;
break;
}
}
/////////////////////////////////////////////////////////////////////////////////
// Face Ordering Algorithm
/////////////////////////////////////////////////////////////////////////////////
// Order the faces around the boundary vertex by starting from the face
// containing the first boundary edge and traversing through adjacent faces
// based on shared non-boundary edges.
std::vector<typename boost::graph_traits<compas::Mesh>::face_descriptor> ordered_faces;
std::vector<bool> visited(vertex_faces.size(), false);
int current_face_idx = e1_face;
ordered_faces.push_back(vertex_faces[current_face_idx]);
visited[current_face_idx] = true;
while (true) {
bool found_next = false;
auto& current_edges = faces_edges[current_face_idx];
for (auto edge1 : current_edges) {
if (edge1 == e1 || edge1 == e2) continue; // Skip boundary edges
for (size_t j = 0; j < vertex_faces.size(); j++) {
if (visited[j]) continue;
if (std::find(faces_edges[j].begin(), faces_edges[j].end(), edge1) != faces_edges[j].end()) {
ordered_faces.push_back(vertex_faces[j]);
visited[j] = true;
current_face_idx = j;
found_next = true;
break;
}
}
if (found_next) break;
}
if (!found_next) break; // Exit when no more adjacent faces are found
}
Environment
- Operating system (Windows/Mac/Linux, 32/64 bits):
- Compiler:
- Release or debug mode:
- Specific flags used (if any):
- CGAL version:
- Boost version:
- Other libraries versions if used (Eigen, TBB, etc.):
The CGAL::halfedges_around_target already gives you sorted halfedges around the target: it is merely calling opposite(next()) to go from one halfedge to the next.
The only difference between a boundary halfedge and a non-boundary halfedge is that its incident face is the boost::graph_traits<Mesh>::null_face(), it does not matter at all when you are circulating around a vertex.
So
for(auto h : CGAL::halfedges_around_target(v, mesh_a)) {
face_descriptor f = face(h, mesh_a);
}
are already sorted faces around the vertex.
I think i tried that. Isnt it start from random edge? Meaning it will not start from a boundary half edge?
The halfedges_around_target starts from halfedge(v, g). If (this was wrong: this is for CGAL::Seam_mesh only).v is a border vertex, for CGAL structures then the incident edge is a border edge
I tried that again, and the order as you in some cases, does not start from one boundary edge and continues to the other:
std::vector<typename boost::graph_traits<compas::Mesh>::face_descriptor> ordered_faces;
// Use h1 as the starting point for iteration
for(auto h : CGAL::halfedges_around_target(v, mesh_a)) {
auto f = face(h, mesh_a);
if(f != boost::graph_traits<compas::Mesh>::null_face() &&
std::find(ordered_faces.begin(), ordered_faces.end(), f) == ordered_faces.end()) {
ordered_faces.push_back(f);
}
}
This is pull-request I am working on:
https://github.com/compas-dev/compas_cgal/tree/f893918ec1bae5687291da122f9f12b71b11af6d
This is the method: https://github.com/compas-dev/compas_cgal/blob/f893918ec1bae5687291da122f9f12b71b11af6d/src/meshing.cpp
It is a python wrapper, do you need only a c++ example with CGAL only?
If v is a border vertex, for CGAL structures then the incident edge is a border edge
I remembered wrongly: it's only for a specific CGAL graph class, CGAL::Seam_mesh. Still, the halfedges_around_... will loop in order, and you can use the same way of walking and the function:
template <typename FaceGraph>
std::optional<typename boost::graph_traits<FaceGraph>::halfedge_descriptor>
is_border(typename boost::graph_traits<FaceGraph>::vertex_descriptor vd,
const FaceGraph& g)
to get the boundary halfedge if you want to start from that one.
@MaelRL
No this does not work or I do not understand this.
I made for you as a standalone example using cpp: https://github.com/petrasvestartas/cgal_example/blob/main/dual_mesh_example.cpp Full video how to use this example: https://www.youtube.com/watch?v=244wFRtKPyQ
You dont need any dependencies, cmake already configures them for you. It opens a .ply file and save triangle and dual meshes. Please take a look at lines 513-613, it must be possible to do this simpler...
This long function produce this output, an lines 513-613 only do the boundary faces: