23#ifndef VCL_ALGORITHMS_MESH_FACE_TOPOLOGY_H
24#define VCL_ALGORITHMS_MESH_FACE_TOPOLOGY_H
26#include <vclib/algorithms/core.h>
27#include <vclib/mesh.h>
28#include <vclib/space/complex.h>
29#include <vclib/space/core.h>
61template<FaceMeshConcept MeshType, FaceConcept FaceType>
62void addTriangleFacesFromPolygon(
65 const std::vector<uint>& polygon)
67 using VertexType = MeshType::VertexType;
68 using PositionType = VertexType::PositionType;
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.");
78 if (m.vertex(polygon[i]).deleted()) {
79 throw BadVertexIndexException(
80 "Vertex " + std::to_string(polygon[i]) +
" is deleted.");
82 polPositions[i] = m.vertex(polygon[i]).position();
86 std::vector<uint> tris =
earCut(polPositions);
91 std::set<std::pair<uint, uint>, UnorderedPairComparator<uint>>
93 for (uint i = 0; i < polygon.size(); ++i)
94 unorderedEdges.emplace(i, (i + 1) % (uint) polygon.size());
96 if constexpr (FaceType::VERTEX_NUMBER < 0) {
101 for (uint i = 0; i < f.vertexNumber(); ++i) {
102 f.setVertex(i, polygon[tris[i]]);
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;
118 for (uint i = 3; i < tris.size(); i += 3) {
119 uint ff = m.addFace();
121 if constexpr (FaceType::VERTEX_NUMBER < 0) {
122 m.face(ff).resizeVertices(3);
125 for (uint j = 0; j < m.face(ff).vertexNumber(); ++j) {
126 m.face(ff).setVertex(j, polygon[tris[i + j]]);
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;
158template<FaceMeshConcept MeshType>
159uint addTriangleFacesFromPolygon(MeshType& m,
const std::vector<uint>& polygon)
161 uint fid = m.addFace();
162 addTriangleFacesFromPolygon(m, m.face(fid), polygon);
182template<FaceConcept FaceType>
183bool isFaceManifoldOnEdge(
const FaceType& f, uint edge)
184 requires comp::HasAdjacentFaces<FaceType>
187 if (!comp::isAdjacentFacesAvailableOn(f)) {
188 throw MissingComponentException(
189 "Face has no Adjacent Faces component.");
193 if (f.adjFace(edge) ==
nullptr) {
197 return f.adjFace(edge)->indexOfAdjFace(&f) !=
UINT_NULL;
217template<FaceConcept FaceType>
218bool isFaceEdgeOnBorder(
const FaceType& f, uint edge)
219 requires comp::HasAdjacentFaces<FaceType>
221 if (!comp::isAdjacentFacesAvailableOn(f)) {
222 throw MissingComponentException(
223 "Face has no Adjacent Faces component.");
226 return f->adjFace(edge) ==
nullptr;
263template<FaceConcept FaceType>
264bool checkFlipEdge(
const FaceType& f, uint edge)
265 requires comp::HasAdjacentFaces<FaceType>
267 if (!comp::isAdjacentFacesAvailableOn(f)) {
268 throw MissingComponentException(
269 "Face has no Adjacent Faces component.");
272 using VertexType = FaceType::VertexType;
274 if (f.vertexNumber() > 3)
277 if (isFaceEdgeOnBorder(f, edge))
280 const VertexType* v0 = f.vertex(edge);
281 const VertexType* v1 = f.vertexMod(edge + 1);
283 const FaceType* of = f.adjFace(edge);
284 uint oe = of->indexOfAdjFace(&f);
289 if (of->vertex(oe) != v1 || of->vertexMod(oe + 1) != v0)
294 const VertexType* f_v2 = f.vertexMod(edge + 2);
295 const VertexType* of_v2 = of->vertexMod(oe + 2);
297 MeshPos<FaceType> pos(&f, f_v2);
298 MeshPos<FaceType> startPos = pos;
301 pos.nextEdgeAdjacentToV();
302 if (pos.adjVertex() == of_v2)
304 }
while (pos != startPos);
329template<FaceConcept FaceType>
330uint edgeAdjacentFacesNumber(
const FaceType& f, uint edge)
331 requires comp::HasAdjacentFaces<FaceType>
333 if (!comp::isAdjacentFacesAvailableOn(f)) {
334 throw MissingComponentException(
335 "Face has no Adjacent Faces component.");
338 ConstEdgeAdjFaceIterator<FaceType> begin(f, edge), end;
340 for (
auto it = begin; it != end; ++it) {
362template<FaceConcept FaceType>
363uint faceEdgesOnBorderNumber(
const FaceType& f)
364 requires comp::HasAdjacentFaces<FaceType>
366 if (!comp::isAdjacentFacesAvailableOn(f)) {
367 throw MissingComponentException(
368 "Face has no Adjacent Faces component.");
372 for (uint i = 0; i < f.vertexNumber(); ++i)
373 if (isFaceEdgeOnBorder(f, i))
398template<FaceConcept FaceType>
399auto faceDihedralAngleOnEdge(
const FaceType& f, uint e)
400 requires comp::HasAdjacentFaces<FaceType>
402 if (!comp::isAdjacentFacesAvailableOn(f)) {
403 throw MissingComponentException(
404 "Face has no Adjacent Faces component.");
418 assert(f.adjFace(e) !=
nullptr);
419 const FaceType& f1 = *(f.adjFace(e));
421 uint e1 = f1.indexOfAdjFace(&f);
424 const auto& vf0 = *(f.vertexMod((
int) e - 1));
425 const auto& vf1 = *(f1.vertexMod(e1 - 1));
430 auto off0 = n0 * vf0.position();
431 auto off1 = n1 * vf1.position();
433 auto dist01 = off0 - n0 * vf1.position();
434 auto dist10 = off1 - n1 * vf0.position();
436 auto sign = std::abs(dist01) > std::abs(dist10) ? dist01 : dist10;
438 auto angleRad = n0.angle(n1);
439 return sign > 0 ? angleRad : -angleRad;
467template<FaceConcept FaceType>
468void detachAdjacentFacesOnEdge(FaceType& f, uint edge)
469 requires comp::HasAdjacentFaces<FaceType>
471 if (!comp::isAdjacentFacesAvailableOn(f)) {
472 throw MissingComponentException(
473 "Face has no Adjacent Faces component.");
476 FaceType* nextFace = f.adjFace(edge);
480 if (nextFace !=
nullptr) {
482 ConstEdgeAdjFaceIterator<FaceType> begin(f, edge), end;
483 for (
auto it = begin; it != end; ++it) {
487 if (nextFace == prevFace) {
488 uint en = nextFace->indexOfAdjFace(&f);
490 nextFace->setAdjFace(en,
nullptr);
495 uint pn = prevFace->indexOfAdjFace(&f);
497 prevFace->setAdjFace(pn, nextFace);
499 f.setAdjFace(edge,
nullptr);
524template<FaceConcept FaceType>
525void detachFace(FaceType& f)
requires comp::HasAdjacentFaces<FaceType>
527 if (!comp::isAdjacentFacesAvailableOn(f)) {
528 throw MissingComponentException(
529 "Face has no Adjacent Faces component.");
532 using VertexType = FaceType::VertexType;
534 for (uint e = 0; e < f.vertexNumber(); ++e) {
535 detachAdjacentFacesOnEdge(f, e);
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);
544 v->eraseAdjFace(vpos);
565template<FaceConcept FaceType>
566std::set<const FaceType*> floodFacePatch(
567 const FaceType& seed,
570 if (!comp::isAdjacentFacesAvailableOn(seed)) {
571 throw MissingComponentException(
572 "Face has no Adjacent Faces component.");
575 std::set<const FaceType*>
faces;
577 std::vector<const FaceType*> stackFaces;
579 if (!faceSelector(seed))
584 for (
const FaceType* adjacent : seed.
adjFaces()) {
586 if (adjacent && faceSelector(*adjacent))
587 stackFaces.push_back(adjacent);
591 while (stackFaces.size() > 0) {
592 const FaceType* fi = stackFaces[stackFaces.size() - 1];
593 stackFaces.pop_back();
595 for (
const FaceType* adjacent : fi->
adjFaces()) {
596 if (adjacent && faceSelector(*adjacent)) {
598 stackFaces.push_back(adjacent);
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