#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 > |
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
| using MR::AABBTree::Node = AABBTreeWideNode |
|
explicitnodiscard |
creates tree for given mesh or its part
|
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
|
default |
|
defaultnoexcept |
| 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)
| mesh | same mesh for which this tree was constructed, but after the splits |
| new2Old | maps 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 |
| 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
|
inlinenodiscard |
returns the bounding box of the whole tree (empty for an empty tree)
| 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
|
nodiscard |
returns the nodes having at least one of given triangles in their subtrees
|
nodiscard |
returns all triangles in the subtree with given root
|
nodiscard |
returns at least given number of top-level not-intersecting subtrees, union of which contain all tree leaves
|
inlinenodiscard |
returns the amount of memory this object occupies on heap
|
inlinenodiscard |
the bounding boxes of the triangles in the order of leafTris(), slightly expanded for robust searches
triangles of all leaves, the triangles of each leaf are contiguous
the root is the first node, if any
| 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)
| mesh | same mesh for which this tree was constructed but with updated coordinates; |
| changedVerts | vertex ids with modified coordinates (since tree construction or last refit), nullptr means all vertices |
| 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
|
friend |
|
friend |
|
staticconstexpr |
|
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
|
staticconstexpr |