MeshLib C++ Docs
Loading...
Searching...
No Matches

#include <MRMesh/MRAABBTree.h>

Public Types

using Node = AABBTreeWideNode
using LeafTri = AABBTreeWideLeafTri

Public Member Functions

 AABBTree (const MeshPart &mp)
 creates tree for given mesh or its part
 AABBTree (const TriMesh &tmesh, const FaceBitSet *region=nullptr)
 AABBTree ()=default
 AABBTree (AABBTree &&) noexcept=default
AABBTree & operator= (AABBTree &&) noexcept=default
const Vector< Node, NodeId > & nodes () const
 the root is the first node, if any
Box3f getBoundingBox () const
 returns the bounding box of the whole tree (empty for an empty tree)
const Vector< LeafTri > & leafTris () const
 triangles of all leaves, the triangles of each leaf are contiguous
const Vector< Box3f > & leafBoxes () const
 the bounding boxes of the triangles in the order of leafTris(), slightly expanded for robust searches
size_t heapBytes () const
 returns the amount of memory this object occupies on heap
std::vector< NodeId > getSubtrees (int minNum) const
 returns at least given number of top-level not-intersecting subtrees, union of which contain all tree leaves
FaceBitSet getSubtreeFaces (NodeId subtreeRoot) const
 returns all triangles in the subtree with given root
NodeBitSet getNodesFromFaces (const FaceBitSet &faces) const
 returns the nodes having at least one of given triangles in their subtrees
void getLeafOrder (FaceBMap &faceMap) const
void renumber (const FaceBMap &faceMap, const VertBMap &vertMap)
 renumbers the triangles and their vertices after the mesh was packed with given maps from old to new ids
void flipOrientation (const FaceBitSet *region=nullptr)
void refit (const Mesh &mesh, const VertBitSet *changedVerts)
void addSplitFaces (const Mesh &mesh, const FaceHashMap &new2Old)

Static Public Attributes

static constexpr int MaxChildren = 4
static constexpr int MaxLeafTris = 4
static constexpr int MaxDepth = 16
 the deepest level of a node (the root is at 0): the stacks of the traversals are sized for it, and addSplitFaces rebuilds a deeper tree

Friends

class UniqueThreadSafeOwner< AABBTree >
class SharedThreadSafeOwner< AABBTree >

Detailed Description

bounding volume hierarchy of mesh triangles with up to 4 children per node and up to 4 triangles per leaf; the children of a node are stored contiguously, and every leaf keeps the vertices and the boxes of its triangles

Member Typedef Documentation

◆ LeafTri

◆ Node

Constructor & Destructor Documentation

◆ AABBTree() [1/4]

MR::AABBTree::AABBTree ( const MeshPart & mp)
explicitnodiscard

creates tree for given mesh or its part

◆ AABBTree() [2/4]

MR::AABBTree::AABBTree ( const TriMesh & tmesh,
const FaceBitSet * region = nullptr )
explicitnodiscard

creates tree for the triangles of tmesh (all if region is nullptr), faster than from a mesh; it is the tree of a mesh with tmesh.points and mesh.topology.getTriVerts( f ) == tmesh.tris[f] for all its triangles

◆ AABBTree() [3/4]

MR::AABBTree::AABBTree ( )
default

◆ AABBTree() [4/4]

MR::AABBTree::AABBTree ( AABBTree && )
defaultnoexcept

Member Function Documentation

◆ addSplitFaces()

void MR::AABBTree::addSplitFaces ( const Mesh & mesh,
const FaceHashMap & new2Old )

adds to the tree the faces that appeared after splitting some of its faces into parts (e.g. by Mesh::splitFace or Mesh::splitEdge): the leaf of each split face gets a subtree with its old triangles and the new parts; this is a faster alternative to full tree rebuild (but the tree after the update might be less efficient)

Parameters
meshsame mesh for which this tree was constructed, but after the splits
new2Oldmaps every new face (not present in the tree) to the face of this tree it was split from; it must contain only the splits made since the tree was built or last updated

◆ flipOrientation()

void MR::AABBTree::flipOrientation ( const FaceBitSet * region = nullptr)

changes the order of the vertices of the triangles of given faces (all if nullptr) as MeshTopology::flipOrientation() does; shall be called after MeshTopology::flipOrientation() if this tree is kept

◆ getBoundingBox()

Box3f MR::AABBTree::getBoundingBox ( ) const
inlinenodiscard

returns the bounding box of the whole tree (empty for an empty tree)

◆ getLeafOrder()

void MR::AABBTree::getLeafOrder ( FaceBMap & faceMap) const

fills map: FaceId -> its position in leafTris(); buffer in faceMap must be resized before the call, and caller is responsible for filling missing face elements

◆ getNodesFromFaces()

NodeBitSet MR::AABBTree::getNodesFromFaces ( const FaceBitSet & faces) const
nodiscard

returns the nodes having at least one of given triangles in their subtrees

◆ getSubtreeFaces()

FaceBitSet MR::AABBTree::getSubtreeFaces ( NodeId subtreeRoot) const
nodiscard

returns all triangles in the subtree with given root

◆ getSubtrees()

std::vector< NodeId > MR::AABBTree::getSubtrees ( int minNum) const
nodiscard

returns at least given number of top-level not-intersecting subtrees, union of which contain all tree leaves

◆ heapBytes()

size_t MR::AABBTree::heapBytes ( ) const
inlinenodiscard

returns the amount of memory this object occupies on heap

◆ leafBoxes()

const Vector< Box3f > & MR::AABBTree::leafBoxes ( ) const
inlinenodiscard

the bounding boxes of the triangles in the order of leafTris(), slightly expanded for robust searches

◆ leafTris()

const Vector< LeafTri > & MR::AABBTree::leafTris ( ) const
inlinenodiscard

triangles of all leaves, the triangles of each leaf are contiguous

◆ nodes()

const Vector< Node, NodeId > & MR::AABBTree::nodes ( ) const
inlinenodiscard

the root is the first node, if any

◆ operator=()

AABBTree & MR::AABBTree::operator= ( AABBTree && )
defaultnoexcept

◆ refit()

void MR::AABBTree::refit ( const Mesh & mesh,
const VertBitSet * changedVerts )

updates the boxes of the triangles with changed vertices and of their ancestors; this is a faster alternative to full tree rebuild (but the tree after refit might be less efficient)

Parameters
meshsame mesh for which this tree was constructed but with updated coordinates;
changedVertsvertex ids with modified coordinates (since tree construction or last refit), nullptr means all vertices

◆ renumber()

void MR::AABBTree::renumber ( const FaceBMap & faceMap,
const VertBMap & vertMap )

renumbers the triangles and their vertices after the mesh was packed with given maps from old to new ids

◆ SharedThreadSafeOwner< AABBTree >

friend class SharedThreadSafeOwner< AABBTree >
friend

◆ UniqueThreadSafeOwner< AABBTree >

friend class UniqueThreadSafeOwner< AABBTree >
friend

Member Data Documentation

◆ MaxChildren

int MR::AABBTree::MaxChildren = 4
staticconstexpr

◆ MaxDepth

int MR::AABBTree::MaxDepth = 16
staticconstexpr

the deepest level of a node (the root is at 0): the stacks of the traversals are sized for it, and addSplitFaces rebuilds a deeper tree

◆ MaxLeafTris

int MR::AABBTree::MaxLeafTris = 4
staticconstexpr

The documentation for this class was generated from the following file: