Visual Computing Library  devel
Loading...
Searching...
No Matches
face_topology.h
1/*****************************************************************************
2 * VCLib *
3 * Visual Computing Library *
4 * *
5 * Copyright(C) 2021-2025 *
6 * Visual Computing Lab *
7 * ISTI - Italian National Research Council *
8 * *
9 * All rights reserved. *
10 * *
11 * This program is free software; you can redistribute it and/or modify *
12 * it under the terms of the Mozilla Public License Version 2.0 as published *
13 * by the Mozilla Foundation; either version 2 of the License, or *
14 * (at your option) any later version. *
15 * *
16 * This program is distributed in the hope that it will be useful, *
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
19 * Mozilla Public License Version 2.0 *
20 * (https://www.mozilla.org/en-US/MPL/2.0/) for more details. *
21 ****************************************************************************/
22
23#ifndef VCL_ALGORITHMS_MESH_FACE_TOPOLOGY_H
24#define VCL_ALGORITHMS_MESH_FACE_TOPOLOGY_H
25
26#include <vclib/algorithms/core.h>
27#include <vclib/mesh.h>
28#include <vclib/space/complex.h>
29#include <vclib/space/core.h>
30
31#include <set>
32
33namespace vcl {
34
61template<FaceMeshConcept MeshType, FaceConcept FaceType>
62void addTriangleFacesFromPolygon(
63 MeshType& m,
64 FaceType& f,
65 const std::vector<uint>& polygon)
66{
67 using VertexType = MeshType::VertexType;
68 using PositionType = VertexType::PositionType;
69
70 // from the ids, create a polygon of positions
71 std::vector<PositionType> polPositions(polygon.size());
72 for (uint i = 0; i < polygon.size(); ++i) {
73 if (polygon[i] >= m.vertexContainerSize()) {
74 throw BadVertexIndexException(
75 "Index " + std::to_string(polygon[i]) +
76 " is out of range in Vertex Container.");
77 }
78 if (m.vertex(polygon[i]).deleted()) {
79 throw BadVertexIndexException(
80 "Vertex " + std::to_string(polygon[i]) + " is deleted.");
81 }
82 polPositions[i] = m.vertex(polygon[i]).position();
83 }
84
85 // compute earcut of the polygons
86 std::vector<uint> tris = earCut(polPositions);
87
88 // faux edges management: create a set of unordered edges of the polygon
89 // note: we use indices from 0 to polygon.size() because that are the output
90 // indices given by the earcut algorithm
91 std::set<std::pair<uint, uint>, UnorderedPairComparator<uint>>
92 unorderedEdges;
93 for (uint i = 0; i < polygon.size(); ++i)
94 unorderedEdges.emplace(i, (i + 1) % (uint) polygon.size());
95
96 if constexpr (FaceType::VERTEX_NUMBER < 0) {
97 f.resizeVertices(3);
98 }
99
100 // set the first triangle of the loaded polygon
101 for (uint i = 0; i < f.vertexNumber(); ++i) {
102 f.setVertex(i, polygon[tris[i]]);
103 }
104
105 if constexpr (face::HasFaceBitFlags<FaceType>) {
106 if (unorderedEdges.find(std::make_pair(tris[0], tris[1])) ==
107 unorderedEdges.end())
108 f.edgeFaux(0) = true;
109 if (unorderedEdges.find(std::make_pair(tris[1], tris[2])) ==
110 unorderedEdges.end())
111 f.edgeFaux(1) = true;
112 if (unorderedEdges.find(std::make_pair(tris[2], tris[0])) ==
113 unorderedEdges.end())
114 f.edgeFaux(2) = true;
115 }
116
117 // remaining triangles, need to create more faces in the mesh
118 for (uint i = 3; i < tris.size(); i += 3) {
119 uint ff = m.addFace();
120
121 if constexpr (FaceType::VERTEX_NUMBER < 0) {
122 m.face(ff).resizeVertices(3);
123 }
124
125 for (uint j = 0; j < m.face(ff).vertexNumber(); ++j) {
126 m.face(ff).setVertex(j, polygon[tris[i + j]]);
127 }
128
129 if constexpr (face::HasFaceBitFlags<FaceType>) {
130 if (unorderedEdges.find(std::make_pair(tris[i], tris[i + 1])) ==
131 unorderedEdges.end())
132 m.face(ff).edgeFaux(0) = true;
133 if (unorderedEdges.find(std::make_pair(tris[i + 1], tris[i + 2])) ==
134 unorderedEdges.end())
135 m.face(ff).edgeFaux(1) = true;
136 if (unorderedEdges.find(std::make_pair(tris[i + 2], tris[i + 0])) ==
137 unorderedEdges.end())
138 m.face(ff).edgeFaux(2) = true;
139 }
140 }
141}
142
158template<FaceMeshConcept MeshType>
159uint addTriangleFacesFromPolygon(MeshType& m, const std::vector<uint>& polygon)
160{
161 uint fid = m.addFace();
162 addTriangleFacesFromPolygon(m, m.face(fid), polygon);
163 return fid;
164}
165
182template<FaceConcept FaceType>
183bool isFaceManifoldOnEdge(const FaceType& f, uint edge)
184 requires comp::HasAdjacentFaces<FaceType>
185{
186 // Check if the AdjacentFaces component is available for the given face.
187 if (!comp::isAdjacentFacesAvailableOn(f)) {
188 throw MissingComponentException(
189 "Face has no Adjacent Faces component.");
190 }
191
192 // Check if the edge is a boundary edge.
193 if (f.adjFace(edge) == nullptr) {
194 return true;
195 }
196 else { // Check if the edge is shared by exactly two faces.
197 return f.adjFace(edge)->indexOfAdjFace(&f) != UINT_NULL;
198 }
199}
200
217template<FaceConcept FaceType>
218bool isFaceEdgeOnBorder(const FaceType& f, uint edge)
219 requires comp::HasAdjacentFaces<FaceType>
220{
221 if (!comp::isAdjacentFacesAvailableOn(f)) {
222 throw MissingComponentException(
223 "Face has no Adjacent Faces component.");
224 }
225
226 return f->adjFace(edge) == nullptr;
227}
228
263template<FaceConcept FaceType>
264bool checkFlipEdge(const FaceType& f, uint edge)
265 requires comp::HasAdjacentFaces<FaceType>
266{
267 if (!comp::isAdjacentFacesAvailableOn(f)) {
268 throw MissingComponentException(
269 "Face has no Adjacent Faces component.");
270 }
271
272 using VertexType = FaceType::VertexType;
273
274 if (f.vertexNumber() > 3)
275 return false;
276
277 if (isFaceEdgeOnBorder(f, edge))
278 return false;
279
280 const VertexType* v0 = f.vertex(edge);
281 const VertexType* v1 = f.vertexMod(edge + 1);
282
283 const FaceType* of = f.adjFace(edge);
284 uint oe = of->indexOfAdjFace(&f);
285 assert(oe != UINT_NULL);
286
287 // check if the vertices of the edge are the same
288 // e.g. the mesh has to be well oriented
289 if (of->vertex(oe) != v1 || of->vertexMod(oe + 1) != v0)
290 return false;
291
292 // check if the flipped edge is already present in the mesh
293 // f_v2 and of_v2 are the vertices of the new edge
294 const VertexType* f_v2 = f.vertexMod(edge + 2);
295 const VertexType* of_v2 = of->vertexMod(oe + 2);
296
297 MeshPos<FaceType> pos(&f, f_v2);
298 MeshPos<FaceType> startPos = pos;
299 // loop in the one ring of f_v2
300 do {
301 pos.nextEdgeAdjacentToV();
302 if (pos.adjVertex() == of_v2)
303 return false;
304 } while (pos != startPos);
305
306 return true;
307}
308
329template<FaceConcept FaceType>
330uint edgeAdjacentFacesNumber(const FaceType& f, uint edge)
331 requires comp::HasAdjacentFaces<FaceType>
332{
333 if (!comp::isAdjacentFacesAvailableOn(f)) {
334 throw MissingComponentException(
335 "Face has no Adjacent Faces component.");
336 }
337
338 ConstEdgeAdjFaceIterator<FaceType> begin(f, edge), end;
339 uint cnt = 0;
340 for (auto it = begin; it != end; ++it) {
341 ++cnt;
342 }
343
344 return cnt;
345}
346
362template<FaceConcept FaceType>
363uint faceEdgesOnBorderNumber(const FaceType& f)
364 requires comp::HasAdjacentFaces<FaceType>
365{
366 if (!comp::isAdjacentFacesAvailableOn(f)) {
367 throw MissingComponentException(
368 "Face has no Adjacent Faces component.");
369 }
370
371 uint cnt = 0;
372 for (uint i = 0; i < f.vertexNumber(); ++i)
373 if (isFaceEdgeOnBorder(f, i))
374 cnt++;
375
376 return cnt;
377}
378
398template<FaceConcept FaceType>
399auto faceDihedralAngleOnEdge(const FaceType& f, uint e)
400 requires comp::HasAdjacentFaces<FaceType>
401{
402 if (!comp::isAdjacentFacesAvailableOn(f)) {
403 throw MissingComponentException(
404 "Face has no Adjacent Faces component.");
405 }
406
407 /*
408 * v0 ___________ vf1
409 * |\ |
410 * | e\ f1 |
411 * | \e1 |
412 * |f \ |
413 * | \ |
414 * |__________\|
415 * vf0 v1
416 */
417
418 assert(f.adjFace(e) != nullptr);
419 const FaceType& f1 = *(f.adjFace(e));
420
421 uint e1 = f1.indexOfAdjFace(&f);
422 assert(e1 != UINT_NULL);
423
424 const auto& vf0 = *(f.vertexMod((int) e - 1));
425 const auto& vf1 = *(f1.vertexMod(e1 - 1));
426
427 auto n0 = faceNormal(f);
428 auto n1 = faceNormal(f1);
429
430 auto off0 = n0 * vf0.position();
431 auto off1 = n1 * vf1.position();
432
433 auto dist01 = off0 - n0 * vf1.position();
434 auto dist10 = off1 - n1 * vf0.position();
435
436 auto sign = std::abs(dist01) > std::abs(dist10) ? dist01 : dist10;
437
438 auto angleRad = n0.angle(n1);
439 return sign > 0 ? angleRad : -angleRad;
440}
441
467template<FaceConcept FaceType>
468void detachAdjacentFacesOnEdge(FaceType& f, uint edge)
469 requires comp::HasAdjacentFaces<FaceType>
470{
471 if (!comp::isAdjacentFacesAvailableOn(f)) {
472 throw MissingComponentException(
473 "Face has no Adjacent Faces component.");
474 }
475
476 FaceType* nextFace = f.adjFace(edge);
477
478 // if nextFace == nullptr there is nothing to do
479 // the face is already detached on the edge
480 if (nextFace != nullptr) {
481 FaceType* prevFace;
482 ConstEdgeAdjFaceIterator<FaceType> begin(f, edge), end;
483 for (auto it = begin; it != end; ++it) {
484 prevFace = *it;
485 }
486
487 if (nextFace == prevFace) { // manifold case
488 uint en = nextFace->indexOfAdjFace(&f);
489 assert(en != UINT_NULL);
490 nextFace->setAdjFace(en, nullptr);
491 }
492 else { // non manifold case
493 // the prev face does not have to point to f anymore, but to
494 // nextFace
495 uint pn = prevFace->indexOfAdjFace(&f);
496 assert(pn != UINT_NULL);
497 prevFace->setAdjFace(pn, nextFace);
498 }
499 f.setAdjFace(edge, nullptr);
500 }
501}
502
524template<FaceConcept FaceType>
525void detachFace(FaceType& f) requires comp::HasAdjacentFaces<FaceType>
526{
527 if (!comp::isAdjacentFacesAvailableOn(f)) {
528 throw MissingComponentException(
529 "Face has no Adjacent Faces component.");
530 }
531
532 using VertexType = FaceType::VertexType;
533
534 for (uint e = 0; e < f.vertexNumber(); ++e) {
535 detachAdjacentFacesOnEdge(f, e);
536
537 // if the vertices have adjacent faces
538 if constexpr (comp::HasAdjacentFaces<VertexType>) {
539 if (comp::isAdjacentFacesAvailableOn(f.vertex(e))) {
540 VertexType* v = f.vertex(e);
541 uint vpos = v->indexOfAdjFace(&f);
542 if (vpos != UINT_NULL) { // may happen if vertex adj faces are
543 // not initialized / updated
544 v->eraseAdjFace(vpos); // the vertex v has not anymore the
545 // adjacent face f
546 }
547 }
548 }
549 }
550}
551
565template<FaceConcept FaceType>
566std::set<const FaceType*> floodFacePatch(
567 const FaceType& seed,
568 auto&& faceSelector)
569{
570 if (!comp::isAdjacentFacesAvailableOn(seed)) {
571 throw MissingComponentException(
572 "Face has no Adjacent Faces component.");
573 }
574
575 std::set<const FaceType*> faces;
576 // only faces that satisfy the faceSelector will stay on the stack
577 std::vector<const FaceType*> stackFaces;
578
579 if (!faceSelector(seed))
580 return faces;
581
582 faces.insert(&seed);
583
584 for (const FaceType* adjacent : seed.adjFaces()) {
585 // adding neighbor faces (if faceSelector returns true) to the stack
586 if (adjacent && faceSelector(*adjacent))
587 stackFaces.push_back(adjacent);
588 }
589
590 // while there aren't other faces on the stack
591 while (stackFaces.size() > 0) {
592 const FaceType* fi = stackFaces[stackFaces.size() - 1];
593 stackFaces.pop_back(); // pop
594 faces.insert(fi);
595 for (const FaceType* adjacent : fi->adjFaces()) {
596 if (adjacent && faceSelector(*adjacent)) {
597 if (faces.find(adjacent) == faces.end())
598 stackFaces.push_back(adjacent);
599 }
600 }
601 }
602 return faces;
603}
604
605} // namespace vcl
606
607#endif // VCL_ALGORITHMS_MESH_FACE_TOPOLOGY_H
constexpr uint UINT_NULL
The UINT_NULL value represent a null value of uint that is the maximum value that can be represented ...
Definition base.h:48
FaceType::VertexType::PositionType faceNormal(const FaceType &f)
Computes the normal of a face, without modifying the face. Works both for triangle and polygonal face...
Definition geometry.h:46
std::vector< uint > earCut(Iterator begin, Iterator end)
Triangulates a simple polygon with no holes using the ear-cutting algorithm.
Definition ear_cut.h:90
constexpr detail::FacesView faces
A view that allows to iterate overt the Face elements of an object.
Definition face.h:84
constexpr detail::AdjFacesView adjFaces
The adjFaces view allows to obtain a view that access to the adjacent faces of the object that has be...
Definition adj_faces.h:65