Blender V5.0
Classes | Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
btDbvt Struct Reference

#include <btDbvt.h>

Classes

struct  sStkNN
struct  sStkNP
struct  sStkNPS
struct  sStkCLN
struct  sStknNN
struct  ICollide
struct  IWriter
struct  IClone

Public Types

enum  { SIMPLE_STACKSIZE = 64 , DOUBLE_STACKSIZE = SIMPLE_STACKSIZE * 2 }

Public Member Functions

 btDbvt ()
 ~btDbvt ()
void clear ()
bool empty () const
void optimizeBottomUp ()
void optimizeTopDown (int bu_treshold=128)
void optimizeIncremental (int passes)
btDbvtNode * insert (const btDbvtVolume &box, void *data)
void update (btDbvtNode *leaf, int lookahead=-1)
void update (btDbvtNode *leaf, btDbvtVolume &volume)
bool update (btDbvtNode *leaf, btDbvtVolume &volume, const btVector3 &velocity, btScalar margin)
bool update (btDbvtNode *leaf, btDbvtVolume &volume, const btVector3 &velocity)
bool update (btDbvtNode *leaf, btDbvtVolume &volume, btScalar margin)
void remove (btDbvtNode *leaf)
void write (IWriter *iwriter) const
void clone (btDbvt &dest, IClone *iclone=0) const
DBVT_PREFIX void collideTT (const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
DBVT_PREFIX void selfCollideT (const btDbvntNode *root, DBVT_IPOLICY)
DBVT_PREFIX void selfCollideTT (const btDbvtNode *root, DBVT_IPOLICY)
DBVT_PREFIX void collideTTpersistentStack (const btDbvtNode *root0, const btDbvtNode *root1, DBVT_IPOLICY)
DBVT_PREFIX void collideTV (const btDbvtNode *root, const btDbvtVolume &volume, DBVT_IPOLICY) const
DBVT_PREFIX void collideTVNoStackAlloc (const btDbvtNode *root, const btDbvtVolume &volume, btNodeStack &stack, DBVT_IPOLICY) const
DBVT_PREFIX void rayTestInternal (const btDbvtNode *root, const btVector3 &rayFrom, const btVector3 &rayTo, const btVector3 &rayDirectionInverse, unsigned int signs[3], btScalar lambda_max, const btVector3 &aabbMin, const btVector3 &aabbMax, btAlignedObjectArray< const btDbvtNode * > &stack, DBVT_IPOLICY) const

Static Public Member Functions

static int maxdepth (const btDbvtNode *node)
static int countLeaves (const btDbvtNode *node)
static void extractLeaves (const btDbvtNode *node, btAlignedObjectArray< const btDbvtNode * > &leaves)
static void benchmark ()
static DBVT_PREFIX void enumNodes (const btDbvtNode *root, DBVT_IPOLICY)
static DBVT_PREFIX void enumLeaves (const btDbvtNode *root, DBVT_IPOLICY)
static DBVT_PREFIX void rayTest (const btDbvtNode *root, const btVector3 &rayFrom, const btVector3 &rayTo, DBVT_IPOLICY)
static DBVT_PREFIX void collideKDOP (const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, int count, DBVT_IPOLICY)
static DBVT_PREFIX void collideOCL (const btDbvtNode *root, const btVector3 *normals, const btScalar *offsets, const btVector3 &sortaxis, int count, DBVT_IPOLICY, bool fullsort=true)
static DBVT_PREFIX void collideTU (const btDbvtNode *root, DBVT_IPOLICY)
static DBVT_INLINE int nearest (const int *i, const btDbvt::sStkNPS *a, btScalar v, int l, int h)
static DBVT_INLINE int allocate (btAlignedObjectArray< int > &ifree, btAlignedObjectArray< sStkNPS > &stock, const sStkNPS &value)

Public Attributes

btDbvtNode * m_root
btDbvtNode * m_free
int m_lkhd
int m_leaves
unsigned m_opath
btAlignedObjectArray< sStkNN > m_stkStack

Detailed Description

The btDbvt class implements a fast dynamic bounding volume tree based on axis aligned bounding boxes (aabb tree). This btDbvt is used for soft body collision detection and for the btDbvtBroadphase. It has a fast insert, remove and update of nodes. Unlike the btQuantizedBvh, nodes can be dynamically moved around, which allows for change in topology of the underlying data structure.

Definition at line 228 of file btDbvt.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum
Enumerator
SIMPLE_STACKSIZE 
DOUBLE_STACKSIZE 

Definition at line 295 of file btDbvt.h.

Constructor & Destructor Documentation

◆ btDbvt()

btDbvt::btDbvt ( )

Definition at line 461 of file btDbvt.cpp.

References m_free, m_leaves, m_lkhd, m_opath, and m_root.

Referenced by clone().

◆ ~btDbvt()

btDbvt::~btDbvt ( )

Definition at line 471 of file btDbvt.cpp.

References clear().

Member Function Documentation

◆ allocate()

DBVT_INLINE int btDbvt::allocate ( btAlignedObjectArray< int > & ifree,
btAlignedObjectArray< sStkNPS > & stock,
const sStkNPS & value )
inlinestatic

Definition at line 436 of file btDbvt.h.

References DBVT_INLINE, i, btAlignedObjectArray< T >::pop_back(), btAlignedObjectArray< T >::push_back(), and btAlignedObjectArray< T >::size().

Referenced by collideOCL().

◆ benchmark()

void btDbvt::benchmark ( )
inlinestatic

Definition at line 333 of file btDbvt.h.

◆ clear()

void btDbvt::clear ( )

Definition at line 477 of file btDbvt.cpp.

References btAlignedFree, m_free, m_lkhd, m_opath, m_root, m_stkStack, and recursedeletenode().

Referenced by clone(), btDeformableBodySolver::predictDeformableMotion(), and ~btDbvt().

◆ clone()

void btDbvt::clone ( btDbvt & dest,
IClone * iclone = 0 ) const

Definition at line 644 of file btDbvt.cpp.

References btDbvt(), clear(), btDbvt::IClone::CloneLeaf(), createnode(), e, i, m_leaves, m_root, btAlignedObjectArray< T >::pop_back(), btAlignedObjectArray< T >::push_back(), btAlignedObjectArray< T >::reserve(), and btAlignedObjectArray< T >::size().

◆ collideKDOP()

DBVT_PREFIX void btDbvt::collideKDOP ( const btDbvtNode * root,
const btVector3 * normals,
const btScalar * offsets,
int count,
DBVT_IPOLICY  )
inlinestatic

Definition at line 1350 of file btDbvt.h.

References btAssert, btVector3, btDbvtNode::childs, btDbvtAabbMm::Classify(), count, DBVT_CHECKTYPE, DBVT_IPOLICY, enumLeaves(), i, btDbvtNode::isinternal(), btDbvt::sStkNP::mask, btDbvt::sStkNP::node, normals, out, btAlignedObjectArray< T >::pop_back(), btAlignedObjectArray< T >::push_back(), btAlignedObjectArray< T >::reserve(), SIMPLE_STACKSIZE, btAlignedObjectArray< T >::size(), unsigned, and btDbvtNode::volume.

◆ collideOCL()

DBVT_PREFIX void btDbvt::collideOCL ( const btDbvtNode * root,
const btVector3 * normals,
const btScalar * offsets,
const btVector3 & sortaxis,
int count,
DBVT_IPOLICY ,
bool fullsort = true )
inlinestatic

Definition at line 1410 of file btDbvt.h.

References allocate(), btAssert, btVector3, btDbvtNode::childs, btDbvtAabbMm::Classify(), count, DBVT_CHECKTYPE, DBVT_IPOLICY, i, btDbvtNode::isinternal(), btDbvt::sStkNPS::mask, nearest(), btDbvt::sStkNPS::node, normals, out, btAlignedObjectArray< T >::pop_back(), btDbvtAabbMm::ProjectMinimum(), btAlignedObjectArray< T >::push_back(), btAlignedObjectArray< T >::reserve(), SIMPLE_STACKSIZE, btAlignedObjectArray< T >::size(), unsigned, btDbvt::sStkNPS::value, and btDbvtNode::volume.

◆ collideTT()

DBVT_PREFIX void btDbvt::collideTT ( const btDbvtNode * root0,
const btDbvtNode * root1,
DBVT_IPOLICY  )
inline

Definition at line 822 of file btDbvt.h.

References btDbvt::sStkNN::a, btDbvt::sStkNN::b, btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, DOUBLE_STACKSIZE, Intersect(), btDbvtNode::isinternal(), btAlignedObjectArray< T >::resize(), btAlignedObjectArray< T >::size(), and btDbvtNode::volume.

Referenced by btSoftBody::defaultCollisionHandler(), btSoftBody::geometricCollisionHandler(), and btSoftColliders::CollideCL_SS::ProcessSoftSoft().

◆ collideTTpersistentStack()

DBVT_PREFIX void btDbvt::collideTTpersistentStack ( const btDbvtNode * root0,
const btDbvtNode * root1,
DBVT_IPOLICY  )
inline

Definition at line 1015 of file btDbvt.h.

References btDbvt::sStkNN::a, btDbvt::sStkNN::b, btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, DOUBLE_STACKSIZE, Intersect(), btDbvtNode::isinternal(), m_stkStack, and btDbvtNode::volume.

◆ collideTU()

DBVT_PREFIX void btDbvt::collideTU ( const btDbvtNode * root,
DBVT_IPOLICY  )
inlinestatic

Definition at line 1531 of file btDbvt.h.

References btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, btDbvtNode::isinternal(), btAlignedObjectArray< T >::pop_back(), btAlignedObjectArray< T >::push_back(), btAlignedObjectArray< T >::reserve(), SIMPLE_STACKSIZE, and btAlignedObjectArray< T >::size().

◆ collideTV()

DBVT_PREFIX void btDbvt::collideTV ( const btDbvtNode * root,
const btDbvtVolume & volume,
DBVT_IPOLICY  ) const
inline

Definition at line 1148 of file btDbvt.h.

References ATTRIBUTE_ALIGNED16, btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, btAlignedObjectArray< T >::initializeFromBuffer(), Intersect(), btDbvtNode::isinternal(), btAlignedObjectArray< T >::pop_back(), btAlignedObjectArray< T >::push_back(), btAlignedObjectArray< T >::reserve(), btAlignedObjectArray< T >::resize(), SIMPLE_STACKSIZE, btAlignedObjectArray< T >::size(), and btDbvtNode::volume.

Referenced by btDbvtBroadphase::collide(), and btSoftColliders::CollideCL_RS::ProcessColObj().

◆ collideTVNoStackAlloc()

DBVT_PREFIX void btDbvt::collideTVNoStackAlloc ( const btDbvtNode * root,
const btDbvtVolume & volume,
btNodeStack & stack,
DBVT_IPOLICY  ) const
inline

Definition at line 1189 of file btDbvt.h.

References ATTRIBUTE_ALIGNED16, btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, Intersect(), btDbvtNode::isinternal(), btAlignedObjectArray< T >::pop_back(), btAlignedObjectArray< T >::push_back(), btAlignedObjectArray< T >::reserve(), btAlignedObjectArray< T >::resize(), SIMPLE_STACKSIZE, btAlignedObjectArray< T >::size(), and btDbvtNode::volume.

◆ countLeaves()

int btDbvt::countLeaves ( const btDbvtNode * node)
static

Definition at line 684 of file btDbvt.cpp.

References btDbvtNode::childs, countLeaves(), and btDbvtNode::isinternal().

Referenced by countLeaves().

◆ empty()

bool btDbvt::empty ( ) const
inline

Definition at line 314 of file btDbvt.h.

References m_root.

Referenced by btDeformableBodySolver::predictDeformableMotion().

◆ enumLeaves()

DBVT_PREFIX void btDbvt::enumLeaves ( const btDbvtNode * root,
DBVT_IPOLICY  )
inlinestatic

Definition at line 805 of file btDbvt.h.

References btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, enumLeaves(), and btDbvtNode::isinternal().

Referenced by collideKDOP(), and enumLeaves().

◆ enumNodes()

DBVT_PREFIX void btDbvt::enumNodes ( const btDbvtNode * root,
DBVT_IPOLICY  )
inlinestatic

Definition at line 791 of file btDbvt.h.

References btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, enumNodes(), and btDbvtNode::isinternal().

Referenced by enumNodes(), and write().

◆ extractLeaves()

void btDbvt::extractLeaves ( const btDbvtNode * node,
btAlignedObjectArray< const btDbvtNode * > & leaves )
static

Definition at line 693 of file btDbvt.cpp.

References btDbvtNode::childs, extractLeaves(), btDbvtNode::isinternal(), and btAlignedObjectArray< T >::push_back().

Referenced by extractLeaves().

◆ insert()

btDbvtNode * btDbvt::insert ( const btDbvtVolume & box,
void * data )

Definition at line 535 of file btDbvt.cpp.

References createnode(), data, insertleaf(), m_leaves, and m_root.

◆ maxdepth()

int btDbvt::maxdepth ( const btDbvtNode * node)
static

Definition at line 676 of file btDbvt.cpp.

References getmaxdepth().

◆ nearest()

DBVT_INLINE int btDbvt::nearest ( const int * i,
const btDbvt::sStkNPS * a,
btScalar v,
int l,
int h )
inlinestatic

Definition at line 423 of file btDbvt.h.

References DBVT_INLINE, i, l, and v.

Referenced by collideOCL().

◆ optimizeBottomUp()

void btDbvt::optimizeBottomUp ( )

Definition at line 489 of file btDbvt.cpp.

References bottomup(), fetchleaves(), m_leaves, m_root, btAlignedObjectArray< T >::reserve(), and btAlignedObjectArray< T >::size().

◆ optimizeIncremental()

void btDbvt::optimizeIncremental ( int passes)

Definition at line 514 of file btDbvt.cpp.

References btDbvtNode::childs, btDbvtNode::isinternal(), m_leaves, m_opath, m_root, sort(), and update().

◆ optimizeTopDown()

void btDbvt::optimizeTopDown ( int bu_treshold = 128)

Definition at line 502 of file btDbvt.cpp.

References fetchleaves(), m_leaves, m_root, btAlignedObjectArray< T >::reserve(), btAlignedObjectArray< T >::size(), and topdown().

◆ rayTest()

DBVT_PREFIX void btDbvt::rayTest ( const btDbvtNode * root,
const btVector3 & rayFrom,
const btVector3 & rayTo,
DBVT_IPOLICY  )
inlinestatic

rayTest is a re-entrant ray test, and can be called in parallel as long as the btAlignedAlloc is thread-safe (uses locking etc) rayTest is slower than rayTestInternal, because it builds a local stack, using memory allocations, and it recomputes signs/rayDirectionInverses each time

what about division by zero? --> just set rayDirection[i] to INF/BT_LARGE_FLOAT

Definition at line 1276 of file btDbvt.h.

References bounds(), BT_LARGE_FLOAT, btAssert, btRayAabb(), btRayAabb2(), btVector3, btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, DOUBLE_STACKSIZE, btAlignedObjectArray< T >::initializeFromBuffer(), btDbvtNode::isinternal(), btDbvtAabbMm::Maxs(), btDbvtAabbMm::Mins(), btAlignedObjectArray< T >::resize(), btAlignedObjectArray< T >::size(), and btDbvtNode::volume.

Referenced by btSoftBody::rayFaceTest(), btSoftBody::rayTest(), and btCollisionWorld::rayTestSingleInternal().

◆ rayTestInternal()

DBVT_PREFIX void btDbvt::rayTestInternal ( const btDbvtNode * root,
const btVector3 & rayFrom,
const btVector3 & rayTo,
const btVector3 & rayDirectionInverse,
unsigned int signs[3],
btScalar lambda_max,
const btVector3 & aabbMin,
const btVector3 & aabbMax,
btAlignedObjectArray< const btDbvtNode * > & stack,
DBVT_IPOLICY  ) const
inline

rayTestInternal is faster than rayTest, because it uses a persistent stack (to reduce dynamic memory allocations to a minimum) and it uses precomputed signs/rayInverseDirections rayTestInternal is used by btDbvtBroadphase to accelerate world ray casts

Definition at line 1223 of file btDbvt.h.

References bounds(), btRayAabb2(), btVector3, btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, DOUBLE_STACKSIZE, btDbvtNode::isinternal(), btDbvtAabbMm::Maxs(), btDbvtAabbMm::Mins(), btAlignedObjectArray< T >::resize(), btAlignedObjectArray< T >::size(), and btDbvtNode::volume.

◆ remove()

void btDbvt::remove ( btDbvtNode * leaf)

Definition at line 611 of file btDbvt.cpp.

References deletenode(), m_leaves, and removeleaf().

◆ selfCollideT()

DBVT_PREFIX void btDbvt::selfCollideT ( const btDbvntNode * root,
DBVT_IPOLICY  )
inline

Definition at line 887 of file btDbvt.h.

References btDbvt::sStknNN::a, btDbvntNode::angle, btDbvt::sStknNN::b, btDbvntNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, DOUBLE_STACKSIZE, Intersect(), btDbvntNode::isinternal(), btAlignedObjectArray< T >::resize(), SIMD_PI, btAlignedObjectArray< T >::size(), and btDbvntNode::volume.

◆ selfCollideTT()

DBVT_PREFIX void btDbvt::selfCollideTT ( const btDbvtNode * root,
DBVT_IPOLICY  )
inline

Definition at line 951 of file btDbvt.h.

References btDbvt::sStkNN::a, btDbvt::sStkNN::b, btDbvtNode::childs, DBVT_CHECKTYPE, DBVT_IPOLICY, DOUBLE_STACKSIZE, Intersect(), btDbvtNode::isinternal(), btAlignedObjectArray< T >::resize(), btAlignedObjectArray< T >::size(), and btDbvtNode::volume.

◆ update() [1/5]

void btDbvt::update ( btDbvtNode * leaf,
btDbvtVolume & volume )

Definition at line 563 of file btDbvt.cpp.

References i, insertleaf(), m_lkhd, m_root, btDbvtNode::parent, removeleaf(), and btDbvtNode::volume.

◆ update() [2/5]

bool btDbvt::update ( btDbvtNode * leaf,
btDbvtVolume & volume,
btScalar margin )

Definition at line 602 of file btDbvt.cpp.

References btVector3, btDbvtAabbMm::Contain(), btDbvtAabbMm::Expand(), update(), and btDbvtNode::volume.

◆ update() [3/5]

bool btDbvt::update ( btDbvtNode * leaf,
btDbvtVolume & volume,
const btVector3 & velocity )

Definition at line 593 of file btDbvt.cpp.

References btVector3, btDbvtAabbMm::Contain(), btDbvtAabbMm::SignedExpand(), update(), and btDbvtNode::volume.

◆ update() [4/5]

bool btDbvt::update ( btDbvtNode * leaf,
btDbvtVolume & volume,
const btVector3 & velocity,
btScalar margin )

Definition at line 583 of file btDbvt.cpp.

References btVector3, btDbvtAabbMm::Contain(), btDbvtAabbMm::Expand(), btDbvtAabbMm::SignedExpand(), update(), and btDbvtNode::volume.

◆ update() [5/5]

void btDbvt::update ( btDbvtNode * leaf,
int lookahead = -1 )

Definition at line 544 of file btDbvt.cpp.

References i, insertleaf(), m_root, btDbvtNode::parent, and removeleaf().

Referenced by optimizeIncremental(), update(), update(), and update().

◆ write()

void btDbvt::write ( IWriter * iwriter) const

Definition at line 619 of file btDbvt.cpp.

References btDbvtNode::childs, enumNodes(), btAlignedObjectArray< T >::findLinearSearch(), i, btDbvtNode::isinternal(), m_leaves, m_root, btDbvtNodeEnumerator::nodes, btDbvtNode::parent, btDbvt::IWriter::Prepare(), btAlignedObjectArray< T >::reserve(), btAlignedObjectArray< T >::size(), btDbvt::IWriter::WriteLeaf(), and btDbvt::IWriter::WriteNode().

Member Data Documentation

◆ m_free

btDbvtNode* btDbvt::m_free

Definition at line 303 of file btDbvt.h.

Referenced by btDbvt(), clear(), createnode(), and deletenode().

◆ m_leaves

int btDbvt::m_leaves

Definition at line 305 of file btDbvt.h.

Referenced by btDbvt(), clone(), insert(), optimizeBottomUp(), optimizeIncremental(), optimizeTopDown(), remove(), and write().

◆ m_lkhd

int btDbvt::m_lkhd

Definition at line 304 of file btDbvt.h.

Referenced by btDbvt(), clear(), and update().

◆ m_opath

unsigned btDbvt::m_opath

Definition at line 306 of file btDbvt.h.

Referenced by btDbvt(), clear(), and optimizeIncremental().

◆ m_root

btDbvtNode* btDbvt::m_root

Definition at line 302 of file btDbvt.h.

Referenced by btDbvt(), clear(), clone(), btSoftBody::defaultCollisionHandler(), btSoftBodyHelpers::DrawClusterTree(), btSoftBodyHelpers::DrawFaceTree(), btSoftBodyHelpers::DrawNodeTree(), empty(), btSoftBody::geometricCollisionHandler(), insert(), insertleaf(), optimizeBottomUp(), optimizeIncremental(), optimizeTopDown(), btCompoundCompoundCollisionAlgorithm::processCollision(), btSoftColliders::CollideCL_RS::ProcessColObj(), btSoftColliders::CollideCL_SS::ProcessSoftSoft(), btCollisionWorld::rayTestSingleInternal(), recursedeletenode(), removeleaf(), update(), update(), and write().

◆ m_stkStack

btAlignedObjectArray<sStkNN> btDbvt::m_stkStack

Definition at line 308 of file btDbvt.h.

Referenced by clear(), and collideTTpersistentStack().

The documentation for this struct was generated from the following files:
Generated on for Blender by  doxygen 1.16.1