topology.h

/*****************************************************************************
 * VCLib                                                                     *
 * Visual Computing Library                                                  *
 *                                                                           *
 * Copyright(C) 2021-2025                                                    *
 * Visual Computing Lab                                                      *
 * ISTI - Italian National Research Council                                  *
 *                                                                           *
 * All rights reserved.                                                      *
 *                                                                           *
 * This program is free software; you can redistribute it and/or modify      *
 * it under the terms of the Mozilla Public License Version 2.0 as published *
 * by the Mozilla Foundation; either version 2 of the License, or            *
 * (at your option) any later version.                                       *
 *                                                                           *
 * This program is distributed in the hope that it will be useful,           *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the              *
 * Mozilla Public License Version 2.0                                        *
 * (https://www.mozilla.org/en-US/MPL/2.0/) for more details.                *
 ****************************************************************************/
 
#ifndef VCL_ALGORITHMS_MESH_UPDATE_TOPOLOGY_H
#define VCL_ALGORITHMS_MESH_UPDATE_TOPOLOGY_H
 
#include <vclib/algorithms/mesh/sort.h>
 
#include <vclib/mesh.h>
 
namespace vcl {
 
template<uint ELEM_ID, FaceMeshConcept MeshType>
void clearPerElementAdjacentFaces(MeshType& mesh)
{
    requirePerElementComponent<ELEM_ID, CompId::ADJACENT_FACES>(mesh);
 
    using AdjacentFacesType = comp::ComponentTypeFromID<
        CompId::ADJACENT_FACES,
        typename MeshType::template ElementType<ELEM_ID>::Components>;
 
    for (auto& e : mesh.template elements<ELEM_ID>()) {
        if constexpr (comp::IsTiedToVertexNumber<AdjacentFacesType>) {
            for (uint i = 0; i < e.adjFacesNumber(); ++i) {
                e.setAdjFace(i, nullptr);
            }
        }
        else {
            e.clearAdjFaces();
        }
    }
}
 
template<uint ELEM_ID, EdgeMeshConcept MeshType>
void clearPerElementAdjacentEdges(MeshType& mesh)
{
    requirePerElementComponent<ELEM_ID, CompId::ADJACENT_EDGES>(mesh);
 
    using AdjacentEdgesType = comp::ComponentTypeFromID<
        CompId::ADJACENT_EDGES,
        typename MeshType::template ElementType<ELEM_ID>::Components>;
 
    for (auto& e : mesh.template elements<ELEM_ID>()) {
        if constexpr (comp::IsTiedToVertexNumber<AdjacentEdgesType>) {
            for (uint i = 0; i < e.adjEdgesNumber(); ++i) {
                e.setAdjEdges(i, nullptr);
            }
        }
        else {
            e.clearAdjEdges();
        }
    }
}
 
template<uint ELEM_ID, MeshConcept MeshType>
void clearPerElementAdjacentVertices(MeshType& mesh)
{
    requirePerElementComponent<ELEM_ID, CompId::ADJACENT_VERTICES>(mesh);
 
    for (auto& e : mesh.template elements<ELEM_ID>()) {
        e.clearAdjVertices();
    }
}
 
template<FaceMeshConcept MeshType>
void clearPerVertexAdjacentFaces(MeshType& mesh)
{
    clearPerElementAdjacentFaces<ElemId::VERTEX>(mesh);
}
 
template<FaceMeshConcept MeshType>
void updatePerVertexAdjacentFaces(MeshType& mesh)
{
    clearPerVertexAdjacentFaces(mesh);
 
    using VertexType = MeshType::VertexType;
    using FaceType   = MeshType::FaceType;
 
    for (VertexType& v : mesh.vertices()) {
        v.clearAdjFaces();
    }
 
    for (FaceType& f : mesh.faces()) {
        for (VertexType* v : f.vertices()) {
            v->pushAdjFace(&f);
        }
    }
}
 
template<MeshConcept MeshType>
void clearPerVertexAdjacentVertices(MeshType& mesh)
{
    clearPerElementAdjacentVertices<ElemId::VERTEX>(mesh);
}
 
template<MeshConcept MeshType>
void updatePerVertexAdjacentVertices(
    MeshType& mesh,
    bool      includeOnlyFaces = false)
{
    clearPerVertexAdjacentVertices(mesh);
 
    using VertexType = MeshType::VertexType;
 
    if constexpr (FaceMeshConcept<MeshType>) {
        // vector that contains edges sorted trough unordered vertex pointers
        // it contains clusters of "same" edges, but each one of them has its
        // face pointer note that in case on non-manifold mesh, clusters may be
        // of size
        // >= 2
        std::vector<MeshEdgeUtil<MeshType>> vec =
            fillAndSortMeshEdgeUtilVector(mesh);
 
        // store the last pair of vertices
        VertexType* v1 = nullptr;
        VertexType* v2 = nullptr;
        for (uint i = 0; i < vec.size(); ++i) {
            // if this pair is different from the last pair
            if (vec[i].v[0] != v1 || vec[i].v[1] != v2) {
                // update last pair
                v1 = vec[i].v[0];
                v2 = vec[i].v[1];
                v1->pushAdjVertex(v2); // set the pair as adjacent
                v2->pushAdjVertex(v1);
            }
        }
    }
 
    if (!includeOnlyFaces) {
        if constexpr (EdgeMeshConcept<MeshType>) {
            using EdgeType = MeshType::EdgeType;
 
            for (EdgeType& e : mesh.edges()) {
                // set the pair as adjacent only if not already present
                if (!e.vertex(0)->containsAdjVertex(e.vertex(1)))
                    e.vertex(0)->pushAdjVertex(e.vertex(1));
                if (!e.vertex(1)->containsAdjVertex(e.vertex(0)))
                    e.vertex(1)->pushAdjVertex(e.vertex(0));
            }
        }
    }
}
 
template<EdgeMeshConcept MeshType>
void clearPerVertexAdjacentEdges(MeshType& mesh)
{
    clearPerElementAdjacentEdges<ElemId::VERTEX>(mesh);
}
 
template<EdgeMeshConcept MeshType>
void updatePerVertexAdjacentEdges(MeshType& mesh)
{
    clearPerVertexAdjacentEdges(mesh);
 
    using EdgeType = MeshType::EdgeType;
 
    for (EdgeType& e : mesh.edges()) {
        e.vertex(0)->pushAdjEdge(&e);
        e.vertex(1)->pushAdjEdge(&e);
    }
}
 
template<FaceMeshConcept MeshType>
void clearPerFaceAdjacentFaces(MeshType& mesh)
{
    clearPerElementAdjacentFaces<ElemId::FACE>(mesh);
}
 
template<FaceMeshConcept MeshType>
void updatePerFaceAdjacentFaces(MeshType& mesh)
{
    requirePerFaceAdjacentFaces(mesh);
 
    // vector that contains edges sorted trough unordered vertex pointers
    // it contains clusters of "same" edges, but each one of them has its face
    // pointer. note that in case on non-manifold mesh, clusters may be of size
    // >= 2
    std::vector<MeshEdgeUtil<MeshType>> vec =
        fillAndSortMeshEdgeUtilVector(mesh);
 
    if (vec.size() > 0) {
        // in this loop, base will point to the first element of a cluster of
        // edges
        // increment of clusters into loop
        for (auto base = vec.begin(); base != vec.end();) {
            auto first = base; // remember the first to set adj to the last
 
            // i and j will increment together, and if i == j, i will be adj to
            // j, but j will not be adj to i (to manage non manifold edges and
            // make cyclic adj on the same edge)
            auto i = base;
            auto j = i + 1;
            if (j != vec.end()) {
                // case of cluster composed of one element. adj of i is nullptr
                if (*i != *j) {
                    i->f->setAdjFace(i->e, nullptr);
                }
                else { // at least two edges in the cluster
                    while (j != vec.end() && *i == *j) {
                        i->f->setAdjFace(i->e, j->f);
                        ++i;
                        ++j;
                    }
                    // i now is the last element that was equal to first
                    i->f->setAdjFace(i->e, first->f);
                }
            }
 
            // j is the first different edge from first (or it is vec.end()!)
            base = j;
        }
    }
}
 
template<FaceMeshConcept MeshType>
void clearPerFaceAdjacentEdges(MeshType& mesh)
    requires EdgeMeshConcept<MeshType>
{
    clearPerElementAdjacentEdges<ElemId::FACE>(mesh);
}
 
template<FaceMeshConcept MeshType>
void updatePerFaceAdjacentEdges(MeshType& mesh)
    requires EdgeMeshConcept<MeshType>
{
    using FaceType = MeshType::FaceType;
 
    using AdjacentEdgesType = comp::ComponentTypeFromID<
        CompId::ADJACENT_EDGES,
        typename FaceType::Components>;
 
    clearPerFaceAdjacentEdges(mesh);
 
    // vector that contains edges sorted trough unordered vertex pointers
    std::vector<MeshEdgeUtil<MeshType>> vec =
        fillAndSortMeshEdgeUtilVector(mesh);
 
    for (auto& e : mesh.edges()) {
        MeshEdgeUtil<MeshType> meu(e.vertex(0), e.vertex(1));
 
        // binary search for the edge in the sorted vector
        auto it = std::lower_bound(vec.begin(), vec.end(), meu);
 
        while (it != vec.end() && *it == meu) {
            auto* f = it->f; // the face adjacent to the edge e
            if constexpr (comp::IsTiedToVertexNumber<AdjacentEdgesType>) {
                f->setAdjEdges(it->e, &e);
            }
            else {
                f->pushAdjEdge(&e);
            }
            ++it;
        }
    }
}
 
template<EdgeMeshConcept MeshType>
void clearPerEdgeAdjacentFaces(MeshType& mesh)
    requires FaceMeshConcept<MeshType>
{
    clearPerElementAdjacentFaces<ElemId::EDGE>(mesh);
}
 
template<EdgeMeshConcept MeshType>
void updatePerEdgeAdjacentFaces(MeshType& mesh)
    requires FaceMeshConcept<MeshType>
{
    clearPerEdgeAdjacentFaces(mesh);
 
    // vector that contains edges sorted trough unordered vertex pointers
    std::vector<MeshEdgeUtil<MeshType>> vec =
        fillAndSortMeshEdgeUtilVector(mesh);
 
    for (auto& e : mesh.edges()) {
        MeshEdgeUtil<MeshType> meu(e.vertex(0), e.vertex(1));
 
        // binary search for the edge in the sorted vector
        auto it = std::lower_bound(vec.begin(), vec.end(), meu);
 
        while (it != vec.end() && *it == meu) {
            auto* f = it->f; // the face adjacent to the edge e
            e.pushAdjFace(f);
            ++it;
        }
    }
}
 
template<EdgeMeshConcept MeshType>
void clearPerEdgeAdjacentEdges(MeshType& mesh)
{
    clearPerElementAdjacentEdges<ElemId::EDGE>(mesh);
}
 
template<EdgeMeshConcept MeshType>
void updatePerEdgeAdjacentEdges(MeshType& mesh)
{
    using EdgeType = MeshType::EdgeType;
 
    // for each vertex, save the edges incident in it
    std::vector<std::list<EdgeType*>> edgeMap(mesh.vertexContainerSize());
 
    clearPerEdgeAdjacentEdges(mesh);
 
    for (EdgeType& e : mesh.edges()) {
        edgeMap[e.vertex(0)->index()].push_back(&e);
        edgeMap[e.vertex(1)->index()].push_back(&e);
    }
 
    for (const std::list<EdgeType*>& edges : edgeMap) {
        // all the edges in edges are adjacent to each other
        for (auto it1 = edges.begin(); it1 != edges.end(); ++it1) {
            for (auto it2 = std::next(it1); it2 != edges.end(); ++it2) {
                (*it1)->pushAdjEdge(*it2);
                (*it2)->pushAdjEdge(*it1);
            }
        }
    }
}
 
} // namespace vcl
 
#endif // VCL_ALGORITHMS_MESH_UPDATE_TOPOLOGY_H