filter.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_FILTER_H
#define VCL_ALGORITHMS_MESH_FILTER_H
 
#include <vclib/mesh/requirements.h>
#include <vclib/misc/comparators.h>
 
#include <set>
 
namespace vcl {
 
namespace detail {
 
template<MeshConcept OutMeshType, uint ELEM_ID, MeshConcept InMeshType>
OutMeshType perElementMeshFilter(
    const InMeshType& m,
    Range auto&&      elemFilterRng,
    bool              saveBirthIndicesInCustomComponent = true)
{
    using OutElemType = OutMeshType::template ElementType<ELEM_ID>;
 
    std::string ccname = "birth" + elementEnumString<ELEM_ID>();
 
    OutMeshType res;
    res.enableSameOptionalComponentsOf(m);
 
    // enable the custom component birth element
    if constexpr (comp::HasCustomComponents<OutElemType>) {
        if (saveBirthIndicesInCustomComponent) {
            res.template addPerElementCustomComponent<ELEM_ID, uint>(ccname);
        }
    }
 
    for (const auto& [birthV, filter] :
         std::views::zip(m.template elements<ELEM_ID>(), elemFilterRng)) {
        if (filter) {
            uint v = res.template add<ELEM_ID>();
            // import all the components from the input mesh
            res.template element<ELEM_ID>(v).importFrom(birthV, false);
            // set the birth element
            if constexpr (comp::HasCustomComponents<OutElemType>) {
                if (saveBirthIndicesInCustomComponent) {
                    res.template element<ELEM_ID>(v)
                        .template customComponent<uint>(ccname) =
                        m.index(birthV);
                }
            }
        }
    }
 
    return res;
}
 
template<MeshConcept OutMeshType, uint ELEM_ID, MeshConcept InMeshType>
OutMeshType perElementMeshFilter(
    const InMeshType&                                                m,
    const std::function<bool(
        const typename InMeshType::template ElementType<ELEM_ID>&)>& elemFilter,
    bool saveBirthIndicesInCustomComponent = true)
{
    auto view =
        m.template elements<ELEM_ID>() | std::views::transform(elemFilter);
 
    return perElementMeshFilter<OutMeshType, ELEM_ID, InMeshType>(
        m, view, saveBirthIndicesInCustomComponent);
}
 
template<MeshConcept OutMeshType, uint ELEM_ID, MeshConcept InMeshType>
OutMeshType perElementMeshFilterWithVRefs(
    const InMeshType& m,
    Range auto&&      elemFilterRng,
    bool              saveBirthIndicesInCustomComponent = true)
{
    using InVertexType = InMeshType::VertexType;
    using OutElemType  = OutMeshType::template ElementType<ELEM_ID>;
 
    std::string ccname = "birth" + elementEnumString<ELEM_ID>();
 
    OutMeshType res;
    res.enableSameOptionalComponentsOf(m);
 
    // enable the custom component birthVertex
    if constexpr (HasPerVertexCustomComponents<OutMeshType>) {
        if (saveBirthIndicesInCustomComponent) {
            res.template addPerVertexCustomComponent<uint>("birthVertex");
        }
    }
 
    // enable the custom component birth element
    if constexpr (comp::HasCustomComponents<OutElemType>) {
        if (saveBirthIndicesInCustomComponent) {
            res.template addPerElementCustomComponent<ELEM_ID, uint>(ccname);
        }
    }
 
    std::vector<uint> vertexMapping(m.vertexContainerSize(), UINT_NULL);
 
    for (const auto& [birthF, filter] :
         std::views::zip(m.template elements<ELEM_ID>(), elemFilterRng)) {
        if (filter) {
            std::vector<uint> verts(birthF.vertexNumber(), UINT_NULL);
            uint vi = 0; // incremented with vertices of the element
            // set all the vertex indices in the verts vector
            // two cases here:
            // - the ith vertex of the face has been already added, we need just
            //   to take its id in the out mesh from the vertexMapping vector
            // - the ith vertex of the face has not been added: we need to add
            //   it and import all its components, and update the
            //   vertexMappingVector
            for (const InVertexType* v : birthF.vertices()) {
                // the vertex has not already added
                if (vertexMapping[m.index(v)] == UINT_NULL) {
                    // add the vertex to the out mesh
                    uint ov = res.addVertex();
                    // import all the components from the input mesh
                    res.vertex(ov).importFrom(*v, false);
                    if constexpr (HasPerVertexCustomComponents<OutMeshType>) {
                        // set the birth vertex
                        if (saveBirthIndicesInCustomComponent) {
                            res.vertex(ov).template customComponent<uint>(
                                "birthVertex") = m.index(v);
                        }
                    }
                    vertexMapping[m.index(v)] = ov;
                    verts[vi]                 = ov;
                }
                else {
                    verts[vi] = vertexMapping[m.index(v)];
                }
                ++vi;
            }
 
            // now all the vertices of the elements are in the out mesh, we can
            // add the actual element
            uint f = res.template add<ELEM_ID>();
            // import all the components from the input mesh
            res.template element<ELEM_ID>(f).importFrom(birthF, false);
 
            if constexpr (OutElemType::VERTEX_NUMBER < 0) {
                res.template element<ELEM_ID>(f).resizeVertices(verts.size());
            }
 
            res.template element<ELEM_ID>(f).setVertices(verts);
 
            if constexpr (comp::HasCustomComponents<OutElemType>) {
                // set the birth elements
                if (saveBirthIndicesInCustomComponent) {
                    res.template element<ELEM_ID>(f)
                        .template customComponent<uint>(ccname) =
                        m.index(birthF);
                }
            }
        }
    }
    return res;
}
 
template<MeshConcept OutMeshType, uint ELEM_ID, MeshConcept InMeshType>
OutMeshType perElementMeshFilterWithVRefs(
    const InMeshType&                                                m,
    const std::function<bool(
        const typename InMeshType::template ElementType<ELEM_ID>&)>& elemFilter,
    bool saveBirthIndicesInCustomComponent = true)
{
    auto view =
        m.template elements<ELEM_ID>() | std::views::transform(elemFilter);
 
    return perElementMeshFilterWithVRefs<OutMeshType, ELEM_ID, InMeshType>(
        m, view, saveBirthIndicesInCustomComponent);
}
 
} // namespace detail
 
template<MeshConcept InMeshType, MeshConcept OutMeshType = InMeshType>
OutMeshType perVertexMeshFilter(
    const InMeshType& m,
    const std::function<bool(const typename InMeshType::VertexType&)>&
         vertexFilter,
    bool saveBirthIndicesInCustomComponent = true)
{
    return detail::
        perElementMeshFilter<OutMeshType, ElemId::VERTEX, InMeshType>(
            m, vertexFilter, saveBirthIndicesInCustomComponent);
}
 
template<MeshConcept InMeshType, MeshConcept OutMeshType = InMeshType>
OutMeshType perVertexMeshFilter(
    const InMeshType& m,
    Range auto&&      vertexFilterRng,
    bool              saveBirthIndicesInCustomComponent = true)
{
    return detail::
        perElementMeshFilter<OutMeshType, ElemId::VERTEX, InMeshType>(
            m, vertexFilterRng, saveBirthIndicesInCustomComponent);
}
 
template<MeshConcept InMeshType, MeshConcept OutMeshType = InMeshType>
OutMeshType perVertexSelectionMeshFilter(
    const InMeshType& m,
    bool              saveBirthIndicesInCustomComponent = true)
{
    auto selView = m.vertices() | views::selection;
 
    return detail::
        perElementMeshFilter<OutMeshType, ElemId::VERTEX, InMeshType>(
            m, selView, saveBirthIndicesInCustomComponent);
}
 
template<FaceMeshConcept InMeshType, FaceMeshConcept OutMeshType = InMeshType>
OutMeshType perFaceMeshFilter(
    const InMeshType&                                                m,
    const std::function<bool(const typename InMeshType::FaceType&)>& faceFilter,
    bool saveBirthIndicesInCustomComponent = true)
{
    return detail::
        perElementMeshFilterWithVRefs<OutMeshType, ElemId::FACE, InMeshType>(
            m, faceFilter, saveBirthIndicesInCustomComponent);
}
 
template<FaceMeshConcept InMeshType, FaceMeshConcept OutMeshType = InMeshType>
OutMeshType perFaceMeshFilter(
    const InMeshType& m,
    Range auto&&      faceFilterRng,
    bool              saveBirthIndicesInCustomComponent = true)
{
    return detail::
        perElementMeshFilterWithVRefs<OutMeshType, ElemId::FACE, InMeshType>(
            m, faceFilterRng, saveBirthIndicesInCustomComponent);
}
 
template<FaceMeshConcept InMeshType, FaceMeshConcept OutMeshType = InMeshType>
OutMeshType perFaceSelectionMeshFilter(
    const InMeshType& m,
    bool              saveBirthIndicesInCustomComponent = true)
{
    auto selView = m.faces() | views::selection;
 
    return detail::
        perElementMeshFilterWithVRefs<OutMeshType, ElemId::FACE, InMeshType>(
            m, selView, saveBirthIndicesInCustomComponent);
}
 
template<EdgeMeshConcept InMeshType, EdgeMeshConcept OutMeshType = InMeshType>
OutMeshType perEdgeMeshFilter(
    const InMeshType&                                                m,
    const std::function<bool(const typename InMeshType::EdgeType&)>& edgeFilter,
    bool saveBirthIndicesInCustomComponent = true)
{
    return detail::
        perElementMeshFilterWithVRefs<OutMeshType, ElemId::EDGE, InMeshType>(
            m, edgeFilter, saveBirthIndicesInCustomComponent);
}
 
template<EdgeMeshConcept InMeshType, EdgeMeshConcept OutMeshType = InMeshType>
OutMeshType perEdgeMeshFilter(
    const InMeshType& m,
    Range auto&&      edgeFilterRng,
    bool              saveBirthIndicesInCustomComponent = true)
{
    return detail::
        perElementMeshFilterWithVRefs<OutMeshType, ElemId::EDGE, InMeshType>(
            m, edgeFilterRng, saveBirthIndicesInCustomComponent);
}
 
template<EdgeMeshConcept InMeshType, EdgeMeshConcept OutMeshType = InMeshType>
OutMeshType perEdgeSelectionMeshFilter(
    const InMeshType& m,
    bool              saveBirthIndicesInCustomComponent = true)
{
    auto selView = m.edges() | views::selection;
 
    return detail::
        perElementMeshFilterWithVRefs<OutMeshType, ElemId::EDGE, InMeshType>(
            m, selView, saveBirthIndicesInCustomComponent);
}
 
template<EdgeMeshConcept OutMeshType, FaceMeshConcept InMeshType>
OutMeshType perFaceEdgeMeshFilter(
    const InMeshType& m,
    const std::function<bool(const typename InMeshType::FaceType&, uint)>&
         faceEdgeFilter,
    bool dontDuplicateEdges                = true,
    bool saveBirthIndicesInCustomComponent = true)
{
    using InVertexType = InMeshType::VertexType;
    using OutEdgeType  = OutMeshType::EdgeType;
 
    OutMeshType res;
    // todo: enable only per vertex same optional components of m
    res.enableSameOptionalComponentsOf(m);
 
    // enable the custom component birthVertex
    if constexpr (HasPerVertexCustomComponents<OutMeshType>) {
        if (saveBirthIndicesInCustomComponent) {
            res.template addPerVertexCustomComponent<uint>("birthVertex");
        }
    }
 
    std::vector<uint> vertexMapping(m.vertexContainerSize(), UINT_NULL);
 
    std::set<std::pair<uint, uint>, UnorderedPairComparator<uint>>
        unorderedEdges;
 
    for (const auto& f : m.faces()) {
        for (uint ei = 0; ei < f.vertexNumber(); ++ei) {
            if (faceEdgeFilter(f, ei)) {
                std::array<uint, 2> verts = {UINT_NULL, UINT_NULL};
                for (uint i = 0; i < 2; ++i) {
                    const InVertexType* v = f.vertexMod(ei + i);
                    if (vertexMapping[m.index(v)] == UINT_NULL) {
                        uint ov = res.addVertex();
                        res.vertex(ov).importFrom(*v, false);
                        if constexpr (HasPerVertexCustomComponents<
                                          OutMeshType>) {
                            if (saveBirthIndicesInCustomComponent) {
                                res.vertex(ov).template customComponent<uint>(
                                    "birthVertex") = m.index(v);
                            }
                        }
                        vertexMapping[m.index(v)] = ov;
                        verts[i]                  = ov;
                    }
                    else {
                        verts[i] = vertexMapping[m.index(v)];
                    }
                }
 
                std::pair<uint, uint> ep {verts[0], verts[1]};
                if (!dontDuplicateEdges || !unorderedEdges.contains(ep)) {
                    uint e = res.addEdge(verts[0], verts[1]);
                    unorderedEdges.insert(ep);
                }
            }
        }
    }
 
    return res;
}
 
template<EdgeMeshConcept OutMeshType, FaceMeshConcept InMeshType>
OutMeshType perFaceEdgeMeshFilter(
    const InMeshType&                      m,
    const std::function<bool(uint, uint)>& faceEdgeFilter,
    bool                                   dontDuplicateEdges = true,
    bool saveBirthIndicesInCustomComponent                    = true)
{
    auto filter = [&](const typename InMeshType::FaceType& f, uint ei) {
        return faceEdgeFilter(m.index(f), ei);
    };
 
    return perFaceEdgeMeshFilter<OutMeshType, InMeshType>(
        m, filter, dontDuplicateEdges, saveBirthIndicesInCustomComponent);
}
 
template<EdgeMeshConcept OutMeshType, FaceMeshConcept InMeshType>
OutMeshType perFaceEdgeSelectionMeshFilter(
    const InMeshType& m,
    bool              dontDuplicateEdges                = true,
    bool              saveBirthIndicesInCustomComponent = true)
{
    auto filter = [&](const typename InMeshType::FaceType& f, uint ei) {
        return f.edgeSelected(ei);
    };
 
    return perFaceEdgeMeshFilter<OutMeshType, InMeshType>(
        m, filter, dontDuplicateEdges, saveBirthIndicesInCustomComponent);
}
 
} // namespace vcl
 
#endif // VCL_ALGORITHMS_MESH_FILTER_H