MRPolylineTopology.h

Go to the documentation of this file.

#pragma once
 
#include "MRMeshFwd.h"
#include "MRVector.h"
#include "MRId.h"
#include "MRBitSet.h"
 
namespace MR
{
 

class PolylineTopology
{
public:
    template<typename T, typename F1, typename F2>
    void buildFromContours( const std::vector<std::vector<T>> & contours, F1 && reservePoints, F2 && addPoint );

    MRMESH_API void buildOpenLines( const std::vector<VertId> & comp2firstVert );

    template<typename T, typename F>
    [[nodiscard]] std::vector<std::vector<T>> convertToContours( F&& getPoint, std::vector<std::vector<VertId>>* vertMap = nullptr ) const;

    [[nodiscard]] MRMESH_API EdgeId makeEdge();

    MRMESH_API EdgeId makeEdge( VertId a, VertId b, EdgeId e = {} );

    MRMESH_API int makeEdges( const Edges & edges );

    [[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(); }

    [[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;

    void edgeReserve( size_t newCapacity ) { edges_.reserve( newCapacity ); }

    [[nodiscard]] bool hasEdge( EdgeId e ) const { assert( e.valid() ); return e < (int)edgeSize() && !isLoneEdge( e ); }

    MRMESH_API void deleteEdge( UndirectedEdgeId ue );

    MRMESH_API void deleteEdges( const UndirectedEdgeBitSet & es );

    [[nodiscard]] MRMESH_API size_t heapBytes() const;

    MRMESH_API void splice( EdgeId a, EdgeId b );
    
    [[nodiscard]] EdgeId next( EdgeId he ) const { assert(he.valid()); return edges_[he].next; }

    [[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; }

    MRMESH_API void setOrg( EdgeId a, VertId v );

    [[nodiscard]] const Vector<EdgeId, VertId> & edgePerVertex() const { return edgePerVertex_; }

    [[nodiscard]] MRMESH_API Vector<VertId, EdgeId> getOrgs() const;

    [[nodiscard]] EdgeId edgeWithOrg( VertId a ) const { assert( a.valid() ); return a < int(edgePerVertex_.size()) && edgePerVertex_[a].valid() ? edgePerVertex_[a] : EdgeId(); }

    [[nodiscard]] bool hasVert( VertId a ) const { return validVerts_.test( a ); }

    [[nodiscard]] MRMESH_API int getVertDegree( VertId a ) const;

    [[nodiscard]] int numValidVerts() const { return numValidVerts_; }

    [[nodiscard]] MRMESH_API VertId lastValidVert() const;

    [[nodiscard]] VertId addVertId() { edgePerVertex_.push_back( {} ); validVerts_.push_back( false ); return VertId( (int)edgePerVertex_.size() - 1 ); }

    MRMESH_API void vertResize( size_t newSize );

    MRMESH_API void vertResizeWithReserve( size_t newSize );

    void vertReserve( size_t newCapacity ) { edgePerVertex_.reserve( newCapacity ); validVerts_.reserve( newCapacity ); }

    [[nodiscard]] size_t vertSize() const { return edgePerVertex_.size(); }

    [[nodiscard]] size_t vertCapacity() const { return edgePerVertex_.capacity(); }

    [[nodiscard]] const VertBitSet & getValidVerts() const { return validVerts_; }

    [[nodiscard]] const VertBitSet & getVertIds( const VertBitSet * region ) const { return region ? *region : validVerts_; }

    [[nodiscard]] MRMESH_API EdgeId findEdge( VertId o, VertId d ) const;

    [[nodiscard]] MRMESH_API VertBitSet getPathVertices( const EdgePath & path ) const;

    MRMESH_API EdgeId splitEdge( EdgeId e );

    MRMESH_API EdgeId makePolyline( const VertId * vs, size_t num );

    MRMESH_API void addPart( const PolylineTopology & from,
        VertMap * outVmap = nullptr, WholeEdgeMap * outEmap = nullptr );

    MRMESH_API void addPartByMask( const PolylineTopology& from, const UndirectedEdgeBitSet& mask,
        VertMap* outVmap = nullptr, EdgeMap* outEmap = nullptr );

    MRMESH_API void pack( VertMap * outVmap = nullptr, WholeEdgeMap * outEmap = nullptr );

    MRMESH_API void write( std::ostream & s ) const;

    MRMESH_API bool read( std::istream & s );

    [[nodiscard]] bool operator ==( const PolylineTopology & b ) const { return edges_ == b.edges_; }
    [[nodiscard]] bool operator !=( const PolylineTopology & b ) const { return edges_ != b.edges_; }

    [[nodiscard]] MRMESH_API bool isConsistentlyOriented() const;

    MRMESH_API void flip();

    MRMESH_API bool checkValidity() const;

    MRMESH_API void computeValidsFromEdges();

    [[nodiscard]] MRMESH_API bool isClosed() const;
 
private:
    void setOrg_( EdgeId a, VertId v );

    struct HalfEdgeRecord
    {
        EdgeId next; 
        VertId org;  
 
        bool operator ==( const HalfEdgeRecord& b ) const
        {
            return next == b.next && org == b.org;
        }
        HalfEdgeRecord() noexcept = default;
        explicit HalfEdgeRecord( NoInit ) noexcept : next( noInit ), org( noInit ) {}
    };

    Vector<HalfEdgeRecord, EdgeId> edges_;

    Vector<EdgeId, VertId> edgePerVertex_;
    VertBitSet validVerts_; 
    int numValidVerts_ = 0; 
};
 
template<typename T, typename F1, typename F2>
void PolylineTopology::buildFromContours( const std::vector<std::vector<T>> & contours, F1 && reservePoints, F2 && addPoint )
{
    *this = {};
    size_t size = 0;
    std::vector<bool> closed;
    closed.reserve( contours.size() );
    int numClosed = 0;
    for ( const auto& c : contours )
    {
        const auto csize = c.size();
        if ( csize > 2 )
        {
            closed.push_back( c.front() == c.back() );
        }
        else
        {
            closed.push_back( false );
        }
        if ( csize < 2 )
            continue; 
        size += c.size();
        if ( closed.back() )
            ++numClosed;
    }
 
    reservePoints( size - numClosed );
    vertResize( size - numClosed );
 
    for ( int i = 0; i < contours.size(); ++i )
    {
        const auto& c = contours[i];
        if ( c.size() < 2 )
            continue; 
        const auto e0 = makeEdge();
        const auto v0 = addPoint( c[0] );
        setOrg( e0, v0 );
        auto e = e0;
        for ( int j = 1; j + 1 < c.size(); ++j )
            {
            const auto ej = makeEdge();
            splice( ej, e.sym() );
            const auto vj = addPoint( c[j] );
            setOrg( ej, vj );
            e = ej;
        }
        if ( closed[i] )
        {
            splice( e0, e.sym() );
        }
        else
        {
            const auto vx = addPoint( c.back() );
            setOrg( e.sym(), vx );
        }
    }
    assert( isConsistentlyOriented() );
    assert( edgePerVertex_.size() ==  size - numClosed );
}
 
template<typename T, typename F>
std::vector<std::vector<T>> PolylineTopology::convertToContours( F&& getPoint, std::vector<std::vector<VertId>>* vertMap ) const
{
    std::vector<std::vector<T>> res;
 
    UndirectedEdgeBitSet linesUsed;
    linesUsed.autoResizeSet( UndirectedEdgeId{ undirectedEdgeSize() } );
    linesUsed.flip();
    for ( EdgeId e0 : linesUsed )
    {
        if ( isLoneEdge( e0 ) )
            continue;
 
        EdgeId curLine = e0;
        while ( curLine != next( curLine ) ) 
        {
            curLine = next( curLine ).sym();
            if ( curLine == e0 )
                break; 
        }
 
        linesUsed.set( curLine.undirected(), false );
 
        EdgeId e = curLine;
        std::vector<T> cont;
        std::vector<VertId> map;
        auto orgV = org( e );
        cont.push_back( getPoint( orgV ) );
        if ( vertMap )
            map.push_back( orgV );
        for ( ;; )
        {
            e = e.sym();
            cont.push_back( getPoint( org( e ) ) );
            e = next( e );
            if ( !linesUsed.test_set( e.undirected(), false ) )
                break;
        }
        res.push_back( std::move( cont ) );
        if ( vertMap )
            vertMap->push_back( std::move( map ) );
    }
 
    return res;
}

struct PolylineMaker
{
    PolylineTopology & topology;
    PolylineMaker( PolylineTopology & t ) : topology( t ) {}

    EdgeId start( VertId v )
    {
        assert( !e0_ && !eLast_ );
        e0_ = eLast_ = topology.makeEdge();
        topology.setOrg( e0_, v );
        return e0_;
    }

    EdgeId proceed( VertId v )
    {
        assert( eLast_ );
        const auto ej = topology.makeEdge();
        topology.splice( ej, eLast_.sym() );
        topology.setOrg( ej, v );
        return eLast_ = ej;
    }

    void close()
    {
        assert( e0_ && eLast_ );
        topology.splice( e0_, eLast_.sym() );
        e0_ = eLast_ = {};
    }

    void finishOpen( VertId v )
    {
        assert( eLast_ );
        topology.setOrg( eLast_.sym(), v );
        e0_ = eLast_ = {};
    }
 
private:
    EdgeId e0_, eLast_;
};
 
}