MRAABBTreePoints.h

Go to the documentation of this file.

#pragma once
 
#include "MRBox.h"
#include "MRId.h"
#include "MRVector.h"
#include "MRVector3.h"
 
namespace MR
{
 
 
class AABBTreePoints
{
public:
    struct Node
    {
        Box3f box; 
        NodeId l;  
        NodeId r;  
        bool leaf() const { return !l.valid(); }
        std::pair<int, int> getLeafPointRange() const { assert( leaf() ); return { -( l + 1 ),-( r + 1 ) }; }
        void setLeafPointRange( int first, int last ) { l = NodeId( -( first + 1 ) ); r = NodeId( -( last + 1 ) ); }
    };
    using NodeVec = Vector<Node, NodeId>;
    using NodeBitSet = TaggedBitSet<NodeTag>;
    [[nodiscard]] const NodeVec& nodes() const { return nodes_; }
    [[nodiscard]] const Node& operator[]( NodeId nid ) const { return nodes_[nid]; }
    [[nodiscard]] static NodeId rootNodeId() { return NodeId{0}; }
    [[nodiscard]] Box3f getBoundingBox() const { return nodes_.empty() ? Box3f{} : nodes_[rootNodeId()].box; }
 
    struct Point
    {
        Vector3f coord;
        VertId id;
    };
    [[nodiscard]] const std::vector<Point>& orderedPoints() const { return orderedPoints_; }
 
    MRMESH_API AABBTreePoints( const PointCloud& pointCloud );
    MRMESH_API AABBTreePoints( const Mesh& mesh );
    MRMESH_API AABBTreePoints( const VertCoords & points, const VertBitSet * validPoints = nullptr );
 
    MR_BIND_IGNORE AABBTreePoints( const VertCoords & points, const VertBitSet & validPoints ) : AABBTreePoints( points, &validPoints ) {}
 
    constexpr static int MaxNumPointsInLeaf = 16;
 
    AABBTreePoints( AABBTreePoints && ) noexcept = default;
    AABBTreePoints & operator =( AABBTreePoints && ) noexcept = default;
 
    MRMESH_API void getLeafOrder( VertBMap & vertMap ) const;
    MRMESH_API void getLeafOrderAndReset( VertBMap & vertMap );
 
    [[nodiscard]] MRMESH_API size_t heapBytes() const;
 
    MRMESH_API void refit( const VertCoords & newCoords, const VertBitSet & changedVerts );
 
private:
    std::vector<Point> orderedPoints_;
    NodeVec nodes_;
 
    AABBTreePoints( const AABBTreePoints & ) = default;
    AABBTreePoints & operator =( const AABBTreePoints & ) = default;
    friend class UniqueThreadSafeOwner<AABBTreePoints>;
    friend class SharedThreadSafeOwner<AABBTreePoints>;
};
 
// returns the number of nodes in the binary tree with given number of points
inline int getNumNodesPoints( int numPoints )
{
    assert( numPoints > 0 );
    return 2 * ( ( numPoints + AABBTreePoints::MaxNumPointsInLeaf - 1 ) / AABBTreePoints::MaxNumPointsInLeaf ) - 1;
}
 
 
} // namespace MR