MRMesh/MRMeshTopology.h

Go to the documentation of this file.

#pragma once
 
#include "MRPch/MRBindingMacros.h"
#include "MRId.h"
#include "MRVector.h"
#include "MRBitSet.h"
#include "MRPartMapping.h"
#include "MRMeshTriPoint.h"
#include "MRProgressCallback.h"
#include "MRExpected.h"
#include <fstream>
 
namespace MR
{
 
class MeshTopology
{
public:
    [[nodiscard]] MRMESH_API EdgeId makeEdge();
 
    [[nodiscard]] MRMESH_API bool isLoneEdge( EdgeId a ) const;
 
    [[nodiscard]] MRMESH_API UndirectedEdgeId lastNotLoneUndirectedEdge() const;
 
    [[nodiscard]] EdgeId lastNotLoneEdge() const { auto ue = lastNotLoneUndirectedEdge(); return ue ? EdgeId( ue ) + 1 : EdgeId(); }
 
    MRMESH_API void excludeLoneEdges( UndirectedEdgeBitSet & edges ) const;
 
    [[nodiscard]] size_t edgeSize() const { return edges_.size(); }
 
    [[nodiscard]] size_t edgeCapacity() const { return edges_.capacity(); }
 
    [[nodiscard]] size_t undirectedEdgeSize() const { return edges_.size() >> 1; }
 
    [[nodiscard]] size_t undirectedEdgeCapacity() const { return edges_.capacity() >> 1; }
 
    [[nodiscard]] MRMESH_API size_t computeNotLoneUndirectedEdges() const;
 
    [[nodiscard]] MRMESH_API UndirectedEdgeBitSet findNotLoneUndirectedEdges() const;
 
    void edgeReserve( size_t newCapacity ) { edges_.reserve( newCapacity ); }
 
    [[nodiscard]] bool hasEdge( EdgeId e ) const { assert( e.valid() ); return e < (int)edgeSize() && !isLoneEdge( e ); }
 
    [[nodiscard]] MRMESH_API size_t heapBytes() const;
 
    MRMESH_API void shrinkToFit();
 
 
    MRMESH_API void splice( EdgeId a, EdgeId b );
 
    MRMESH_API EdgeId collapseEdge( EdgeId e, const std::function<void( EdgeId del, EdgeId rem )> & onEdgeDel );
 
 
    [[nodiscard]] EdgeId next( EdgeId he ) const { assert(he.valid()); return edges_[he].next; }
 
    [[nodiscard]] EdgeId prev( EdgeId he ) const { assert(he.valid()); return edges_[he].prev; }
 
    [[nodiscard]] VertId org( EdgeId he ) const { assert(he.valid()); return edges_[he].org; }
 
    [[nodiscard]] VertId dest( EdgeId he ) const { assert(he.valid()); return edges_[he.sym()].org; }
 
    [[nodiscard]] FaceId left( EdgeId he ) const { assert(he.valid()); return edges_[he].left; }
 
    [[nodiscard]] FaceId right( EdgeId he ) const { assert(he.valid()); return edges_[he.sym()].left; }
 
 
    MRMESH_API void setOrg( EdgeId a, VertId v );
 
    MRMESH_API void setLeft( EdgeId a, FaceId f );
 
 
    [[nodiscard]] MRMESH_API bool fromSameOriginRing( EdgeId a, EdgeId b ) const;
 
    [[nodiscard]] MRMESH_API bool fromSameLeftRing( EdgeId a, EdgeId b ) const;
 
 
    [[nodiscard]] MRMESH_API int getOrgDegree( EdgeId a ) const;
 
    [[nodiscard]] int getVertDegree( VertId v ) const { return getOrgDegree( edgeWithOrg( v ) ); }
 
    [[nodiscard]] MRMESH_API int getLeftDegree( EdgeId a ) const;
 
    [[nodiscard]] int getFaceDegree( FaceId f ) const { return getLeftDegree( edgeWithLeft( f ) ); }
 
    [[nodiscard]] MRMESH_API bool isLeftTri( EdgeId a ) const;
 
                   void getTriVerts( FaceId f, VertId & v0, VertId & v1, VertId & v2 ) const { getLeftTriVerts( edgeWithLeft( f ), v0, v1, v2 ); }
    MR_BIND_IGNORE void getTriVerts( FaceId f, VertId (&v)[3] ) const { getLeftTriVerts( edgeWithLeft( f ), v ); } // This one is not in the bindings because of the reference-to-array parameter.
                   void getTriVerts( FaceId f, ThreeVertIds & v ) const { getLeftTriVerts( edgeWithLeft( f ), v ); }
    [[nodiscard]] ThreeVertIds getTriVerts( FaceId f ) const { return getLeftTriVerts( edgeWithLeft( f ) ); }
 
    [[nodiscard]] bool isTriVert( FaceId f, VertId v ) const { auto vs = getTriVerts( f ); return v == vs[0] || v == vs[1] || v == vs[2]; }
 
    [[nodiscard]] MRMESH_API std::vector<ThreeVertIds> getAllTriVerts() const;
 
    [[nodiscard]] MRMESH_API Triangulation getTriangulation() const;
 
    MRMESH_API     void getLeftTriVerts( EdgeId a, VertId & v0, VertId & v1, VertId & v2 ) const;
    MR_BIND_IGNORE void getLeftTriVerts( EdgeId a, VertId (&v)[3] ) const { getLeftTriVerts( a, v[0], v[1], v[2] ); } // This one is not in the bindings because of the reference-to-array parameter.
                   void getLeftTriVerts( EdgeId a, ThreeVertIds & v ) const { getLeftTriVerts( a, v[0], v[1], v[2] ); }
    [[nodiscard]] ThreeVertIds getLeftTriVerts( EdgeId a ) const { ThreeVertIds v; getLeftTriVerts( a, v[0], v[1], v[2] ); return v; }
 
    template <typename T>
    void forEachVertex( const MeshTriPoint & p, T && callback ) const;
 
    MRMESH_API void getLeftTriEdges( EdgeId e0, EdgeId & e1, EdgeId & e2 ) const;
 
                   void getTriEdges( FaceId f, EdgeId & e0, EdgeId & e1, EdgeId & e2 ) const { getLeftTriEdges( e0 = edgeWithLeft( f ), e1, e2 ); }
    MR_BIND_IGNORE void getTriEdges( FaceId f, EdgeId (&e)[3] ) const { getLeftTriEdges( e[0] = edgeWithLeft( f ), e[1], e[2] ); } // This one is not in the bindings because of the reference-to-array parameter.
 
    [[nodiscard]] MRMESH_API bool isLeftQuad( EdgeId a ) const;
 
    [[nodiscard]] const Vector<EdgeId, VertId> & edgePerVertex() const { return edgePerVertex_; }
 
    [[nodiscard]] EdgeId edgeWithOrg( VertId a ) const { assert( a.valid() ); return a < int(edgePerVertex_.size()) ? edgePerVertex_[a] : EdgeId(); }
 
    [[nodiscard]] bool hasVert( VertId a ) const { assert( updateValids_ ); return validVerts_.test( a ); }
 
    [[nodiscard]] int numValidVerts() const { assert( updateValids_ ); return numValidVerts_; }
 
    [[nodiscard]] MRMESH_API VertId lastValidVert() const;
 
    [[nodiscard]] VertId addVertId() { edgePerVertex_.emplace_back(); if ( updateValids_ ) { validVerts_.push_back( false ); } return edgePerVertex_.backId(); }
 
    MRMESH_API void vertResize( size_t newSize );
 
    MRMESH_API void vertResizeWithReserve( size_t newSize );
 
    void vertReserve( size_t newCapacity ) { edgePerVertex_.reserve( newCapacity ); if ( updateValids_ ) { validVerts_.reserve( newCapacity ); } }
 
    [[nodiscard]] size_t vertSize() const { return edgePerVertex_.size(); }
 
    [[nodiscard]] size_t vertCapacity() const { return edgePerVertex_.capacity(); }
 
    [[nodiscard]] const VertBitSet & getValidVerts() const { assert( updateValids_ ); return validVerts_; }
 
    void flip( VertBitSet & vs ) const { vs = getValidVerts() - vs; }
 
    [[nodiscard]] const VertBitSet & getVertIds( const VertBitSet * region ) const
    {
        assert( region || updateValids_ ); // region shall be either given on input or maintained in validVerts_
        assert( !updateValids_ || !region || region->is_subset_of( validVerts_ ) ); // if region is given and all valid vertices are known, then region must be a subset of them
        return region ? *region : validVerts_;
    }
 
 
    [[nodiscard]] const Vector<EdgeId, FaceId> & edgePerFace() const { return edgePerFace_; }
 
    [[nodiscard]] EdgeId edgeWithLeft( FaceId a ) const { assert( a.valid() ); return a < int(edgePerFace_.size()) ? edgePerFace_[a] : EdgeId(); }
 
    [[nodiscard]] bool hasFace( FaceId a ) const { assert( updateValids_ ); return validFaces_.test( a ); }
 
    [[nodiscard]] MRMESH_API EdgeId sharedEdge( FaceId l, FaceId r ) const;
 
    [[nodiscard]] MRMESH_API EdgeId sharedVertInOrg( EdgeId a, EdgeId b ) const;
 
    [[nodiscard]] MRMESH_API EdgeId sharedVertInOrg( FaceId l, FaceId r ) const;
 
    [[nodiscard]] MRMESH_API FaceId sharedFace( EdgeId a, EdgeId b ) const;
 
    [[nodiscard]] int numValidFaces() const { assert( updateValids_ ); return numValidFaces_; }
 
    [[nodiscard]] MRMESH_API FaceId lastValidFace() const;
 
    [[nodiscard]] FaceId addFaceId() { edgePerFace_.emplace_back(); if ( updateValids_ ) { validFaces_.push_back( false ); } return edgePerFace_.backId(); }
 
    MRMESH_API void deleteFace( FaceId f, const UndirectedEdgeBitSet * keepEdges = nullptr );
 
    MRMESH_API void deleteFaces( const FaceBitSet & fs, const UndirectedEdgeBitSet * keepEdges = nullptr );
 
    MRMESH_API void faceResize( size_t newSize );
 
    MRMESH_API void faceResizeWithReserve( size_t newSize );
 
    void faceReserve( size_t newCapacity ) { edgePerFace_.reserve( newCapacity ); if ( updateValids_ ) { validFaces_.reserve( newCapacity ); } }
 
    [[nodiscard]] size_t faceSize() const { return edgePerFace_.size(); }
 
    [[nodiscard]] size_t faceCapacity() const { return edgePerFace_.capacity(); }
 
    [[nodiscard]] const FaceBitSet & getValidFaces() const { assert( updateValids_ ); return validFaces_; }
 
    void flip( FaceBitSet & fs ) const { fs = getValidFaces() - fs; }
 
    [[nodiscard]] const FaceBitSet & getFaceIds( const FaceBitSet * region ) const
    {
        assert( region || updateValids_ ); // region shall be either given on input or maintained in validFaces_
        assert( !updateValids_ || !region || region->is_subset_of( validFaces_ ) ); // if region is given and all valid faces are known, then region must be a subset of them
        return region ? *region : validFaces_;
    }
 
    [[nodiscard]] MRMESH_API EdgeId bdEdgeSameLeft( EdgeId e, const FaceBitSet * region = nullptr ) const;
 
    [[nodiscard]] bool isLeftBdFace( EdgeId e, const FaceBitSet * region = nullptr ) const { return contains( region, left( e ) ) && bdEdgeSameLeft( e, region ).valid(); }
 
    [[nodiscard]] EdgeId bdEdgeWithLeft( FaceId f, const FaceBitSet * region = nullptr ) const { return bdEdgeSameLeft( edgeWithLeft( f ), region ); }
 
    [[nodiscard]] bool isBdFace( FaceId f, const FaceBitSet * region = nullptr ) const { return isLeftBdFace( edgeWithLeft( f ), region ); }
 
    [[nodiscard]] MRMESH_API FaceBitSet findBdFaces( const FaceBitSet * region = nullptr ) const;
 
 
    [[nodiscard]] bool isLeftInRegion( EdgeId e, const FaceBitSet * region = nullptr ) const { return contains( region, left( e ) ); }
 
    [[nodiscard]] bool isInnerEdge( EdgeId e, const FaceBitSet * region = nullptr ) const { return isLeftInRegion( e, region ) && isLeftInRegion( e.sym(), region ); }
 
    [[nodiscard]] MRMESH_API bool isBdEdge( EdgeId e, const FaceBitSet * region = nullptr ) const;
 
    [[nodiscard]] MRMESH_API EdgeBitSet findLeftBdEdges( const FaceBitSet * region = nullptr, const EdgeBitSet * test = nullptr ) const;
 
    [[nodiscard]] MRMESH_API EdgeId bdEdgeSameOrigin( EdgeId e, const FaceBitSet * region = nullptr ) const;
 
    [[nodiscard]] bool isBdVertexInOrg( EdgeId e, const FaceBitSet * region = nullptr ) const { return bdEdgeSameOrigin( e, region ).valid(); }
 
    [[nodiscard]] EdgeId bdEdgeWithOrigin( VertId v, const FaceBitSet * region = nullptr ) const { return bdEdgeSameOrigin( edgeWithOrg( v ), region ); }
 
    [[nodiscard]] bool isBdVertex( VertId v, const FaceBitSet * region = nullptr ) const { return isBdVertexInOrg( edgeWithOrg( v ), region ); }
 
    [[nodiscard]] MRMESH_API VertBitSet findBdVerts( const FaceBitSet * region = nullptr, const VertBitSet * test = nullptr ) const;
 
    [[nodiscard]] MRMESH_API bool isInnerOrBdVertex( VertId v, const FaceBitSet * region = nullptr ) const;
 
    [[nodiscard]] bool isLeftBdEdge( EdgeId e, const FaceBitSet * region = nullptr ) const { return region ? ( isLeftInRegion( e, region ) && !isLeftInRegion( e.sym(), region ) ) : !right( e ); }
 
    [[nodiscard]] bool isInnerOrBdEdge( EdgeId e, const FaceBitSet * region = nullptr ) const { return isLeftInRegion( e, region ) || isLeftInRegion( e.sym(), region ); }
 
    [[nodiscard]] MRMESH_API EdgeId nextLeftBd( EdgeId e, const FaceBitSet * region = nullptr ) const;
 
    [[nodiscard]] MRMESH_API EdgeId prevLeftBd( EdgeId e, const FaceBitSet * region = nullptr ) const;
 
 
    [[nodiscard]] MRMESH_API EdgeId findEdge( VertId o, VertId d ) const;
 
    [[nodiscard]] MRMESH_API bool isClosed( const FaceBitSet * region = nullptr ) const;
 
    [[nodiscard]] MRMESH_API std::vector<EdgeId> findHoleRepresentiveEdges( const FaceBitSet * region = nullptr ) const;
 
    [[nodiscard]] MRMESH_API int findNumHoles( EdgeBitSet * holeRepresentativeEdges = nullptr ) const;
 
    [[nodiscard]] MRMESH_API EdgeLoop getLeftRing( EdgeId e ) const;
 
    [[nodiscard]] MRMESH_API std::vector<EdgeLoop> getLeftRings( const std::vector<EdgeId> & es ) const;
 
    [[nodiscard]] [[deprecated( "Use findLeftBdEdges")]] MRMESH_API MR_BIND_IGNORE EdgeBitSet findBoundaryEdges() const;
 
    [[nodiscard]] [[deprecated( "Use findBdFaces")]] MRMESH_API MR_BIND_IGNORE FaceBitSet findBoundaryFaces( const FaceBitSet * region = nullptr ) const;
 
    [[nodiscard]] [[deprecated( "Use findBdVerts")]] MRMESH_API MR_BIND_IGNORE VertBitSet findBoundaryVerts( const VertBitSet * region = nullptr ) const;
 
 
    [[nodiscard]] MRMESH_API VertBitSet getPathVertices( const EdgePath & path ) const;
 
    [[nodiscard]] MRMESH_API FaceBitSet getPathLeftFaces( const EdgePath & path ) const;
 
    [[nodiscard]] MRMESH_API FaceBitSet getPathRightFaces( const EdgePath & path ) const;
 
 
    MRMESH_API void flipEdge( EdgeId e );
 
    template<typename T>
    void flipEdgesIn( EdgeId e0, T && flipNeeded );
 
    template<typename T>
    void flipEdgesIn( VertId v, T && flipNeeded ) { flipEdgesIn( edgeWithOrg( v ), std::forward<T>( flipNeeded ) ); }
 
    template<typename T>
    void flipEdgesOut( EdgeId e0, T && flipNeeded );
 
    template<typename T>
    void flipEdgesOut( VertId v, T && flipNeeded ) { flipEdgesOut( edgeWithOrg( v ), std::forward<T>( flipNeeded ) ); }
 
    MRMESH_API EdgeId splitEdge( EdgeId e, FaceBitSet * region = nullptr, FaceHashMap * new2Old = nullptr );
 
    MRMESH_API VertId splitFace( FaceId f, FaceBitSet * region = nullptr, FaceHashMap * new2Old = nullptr );
 
    MRMESH_API void flipOrientation( const UndirectedEdgeBitSet * fullComponents = nullptr );
 
 
    MRMESH_API void addPart( const MeshTopology & from, const PartMapping & map = {}, bool rearrangeTriangles = false );
    MRMESH_API void addPart( const MeshTopology & from,
        FaceMap * outFmap = nullptr, VertMap * outVmap = nullptr, WholeEdgeMap * outEmap = nullptr, 
        bool rearrangeTriangles = false );
 
    MRMESH_API void addPartByMask( const MeshTopology & from, const FaceBitSet * fromFaces, const PartMapping & map = {} );
    MR_BIND_IGNORE void addPartByMask( const MeshTopology & from, const FaceBitSet & fromFaces, const PartMapping & map = {} )
        { addPartByMask( from, &fromFaces, map ); }
 
    MRMESH_API void addPartByMask( const MeshTopology & from, const FaceBitSet * fromFaces, bool flipOrientation = false,
        const std::vector<EdgePath> & thisContours = {}, const std::vector<EdgePath> & fromContours = {},
        const PartMapping & map = {} );
 
    MR_BIND_IGNORE void addPartByMask( const MeshTopology & from, const FaceBitSet & fromFaces, bool flipOrientation = false,
        const std::vector<EdgePath> & thisContours = {}, const std::vector<EdgePath> & fromContours = {},
        const PartMapping & map = {} ) { addPartByMask( from, &fromFaces, flipOrientation, thisContours, fromContours, map ); }
 
    MRMESH_API void rotateTriangles();
 
    MRMESH_API void pack( FaceMap * outFmap = nullptr, VertMap * outVmap = nullptr, WholeEdgeMap * outEmap = nullptr, bool rearrangeTriangles = false );
 
    MRMESH_API void pack( const PackMapping & map );
 
    MRMESH_API void packMinMem( const PackMapping & map );
 
 
    MRMESH_API void write( std::ostream & s ) const;
 
    MRMESH_API Expected<void> read( std::istream& s, ProgressCallback callback = {} );
 
    [[nodiscard]] MRMESH_API bool operator ==( const MeshTopology & b ) const;
 
    MRMESH_API void resizeBeforeParallelAdd( size_t edgeSize, size_t vertSize, size_t faceSize );
 
    MRMESH_API void addPackedPart( const MeshTopology & from, EdgeId toEdgeId,
        const FaceMap & fmap, const VertMap & vmap );
 
    MRMESH_API bool computeValidsFromEdges( ProgressCallback cb = {} );
 
    MRMESH_API void stopUpdatingValids();
 
    [[nodiscard]] bool updatingValids() const { return updateValids_; }
 
    MRMESH_API void preferEdges( const UndirectedEdgeBitSet & stableEdges );
 
    // constructs triangular grid mesh topology in parallel
    MRMESH_API bool buildGridMesh( const GridSettings& settings, ProgressCallback cb = {} );
 
    MRMESH_API bool checkValidity( ProgressCallback cb = {}, bool allVerts = true ) const;
 
private:
    friend class MeshTopologyDiff;
    MRMESH_API void computeAllFromEdges_();
 
private:
    void setOrg_( EdgeId a, VertId v );
 
    void fillOrg_();
 
    void setLeft_( EdgeId a, FaceId f );
 
    void fillLeft_();
 
    struct alignas( 16 ) HalfEdgeRecord
    {
        EdgeId next; 
        EdgeId prev; 
        VertId org;  
        FaceId left; 
 
        bool operator ==( const HalfEdgeRecord& b ) const
        {
            return next == b.next && prev == b.prev && org == b.org && left == b.left;
        }
        HalfEdgeRecord() noexcept = default;
        explicit HalfEdgeRecord( NoInit ) noexcept : next( noInit ), prev( noInit ), org( noInit ), left( noInit ) {}
    };
    static_assert( sizeof( HalfEdgeRecord ) == 16 );
 
    template<typename FM, typename VM, typename WEM>
    void translateNoFlip_( HalfEdgeRecord & r, const FM & fmap, const VM & vmap, const WEM & emap ) const;
    template<typename FM, typename VM, typename WEM>
    void translate_( HalfEdgeRecord & r, HalfEdgeRecord & rsym,
        const FM & fmap, const VM & vmap, const WEM & emap, bool flipOrientation ) const;
 
    Vector<HalfEdgeRecord, EdgeId> edges_;
 
    Vector<EdgeId, VertId> edgePerVertex_;
    VertBitSet validVerts_; 
 
    Vector<EdgeId, FaceId> edgePerFace_;
    FaceBitSet validFaces_; 
 
    int numValidVerts_ = 0; 
    int numValidFaces_ = 0; 
 
    bool updateValids_ = true; 
};
 
template <typename T>
void MeshTopology::forEachVertex( const MeshTriPoint & p, T && callback ) const
{
    if ( auto v = p.inVertex( *this ) )
    {
        callback( v );
        return;
    }
    if ( auto e = p.onEdge( *this ) )
    {
        callback( org( e.e ) );
        callback( dest( e.e ) );
        return;
    }
 
    VertId v[3];
    getLeftTriVerts( p.e, v );
    for ( int i = 0; i < 3; ++i )
        callback( v[i] );
}
 
template<typename T>
void MeshTopology::flipEdgesIn( const EdgeId e0, T && flipNeeded )
{
    EdgeId e = e0;
    for (;;)
    {
        auto testEdge = prev( e.sym() );
        if ( left( testEdge ) && right( testEdge ) && flipNeeded( testEdge ) )
            flipEdge( testEdge );
        else
        {
            e = next( e );
            if ( e == e0 )
                break; // full ring has been inspected
        }
    }
}
 
template<typename T>
void MeshTopology::flipEdgesOut( EdgeId e0, T && flipNeeded )
{
    EdgeId e = e0;
    for (;;)
    {
        if ( left( e ) && right( e ) && flipNeeded( e ) )
        {
            e0 = next( e );
            flipEdge( e );
            e = e0;
        }
        else
        {
            e = next( e );
            if ( e == e0 )
                break; // full ring has been inspected
        }
    }
}
 
// rearrange vector values by map (old.id -> new.id)
template<typename T, typename I>
[[nodiscard]] Vector<T, I> rearrangeVectorByMap( const Vector<T, I>& oldVector, const BMap<I, I>& map )
{
    Vector<T, I> newVector;
    newVector.resize( map.tsize );
 
    const auto& mData = map.b.data();
    const auto sz = std::min( oldVector.size(), map.b.size() );
    for ( I i = I(0); i < sz; ++i)
    {
        I newV = mData[i];
        if ( newV.valid() )
            newVector[newV] = oldVector[i];
    }
    return newVector;
}
 
} // namespace MR