KiCad PCB EDA Suite
CBVHCONTAINER2D Class Reference

#include <ccontainer2d.h>

Inheritance diagram for CBVHCONTAINER2D:
CGENERICCONTAINER2D

Public Member Functions

 CBVHCONTAINER2D ()
 
 ~CBVHCONTAINER2D ()
 
void BuildBVH ()
 
void GetListObjectsIntersects (const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const override
 GetListObjectsIntersects - Get a list of objects that intersects a bbox. More...
 
void Add (COBJECT2D *aObject)
 
void Clear ()
 
const LIST_OBJECT2DGetList () const
 

Protected Attributes

CBBOX2D m_bbox
 
LIST_OBJECT2D m_objects
 

Private Member Functions

void destroy ()
 
void recursiveBuild_MIDDLE_SPLIT (BVH_CONTAINER_NODE_2D *aNodeParent)
 
void recursiveGetListObjectsIntersects (const BVH_CONTAINER_NODE_2D *aNode, const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const
 

Private Attributes

bool m_isInitialized
 
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
 
BVH_CONTAINER_NODE_2Dm_Tree
 

Detailed Description

Definition at line 97 of file ccontainer2d.h.

Constructor & Destructor Documentation

CBVHCONTAINER2D::CBVHCONTAINER2D ( )

Definition at line 161 of file ccontainer2d.cpp.

References CGENERICCONTAINER2D::m_bbox, m_elements_to_delete, m_isInitialized, m_Tree, and CBBOX2D::Reset().

162 {
163  m_isInitialized = false;
164  m_bbox.Reset();
165  m_elements_to_delete.clear();
166  m_Tree = NULL;
167 }
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:107
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:88
CGENERICCONTAINER2D(OBJECT2D_TYPE aObjType)
BVH_CONTAINER_NODE_2D * m_Tree
Definition: ccontainer2d.h:108
CBVHCONTAINER2D::~CBVHCONTAINER2D ( )

Definition at line 257 of file ccontainer2d.cpp.

References destroy().

258 {
259  destroy();
260 }

Member Function Documentation

void CGENERICCONTAINER2D::Add ( COBJECT2D aObject)
inlineinherited
void CBVHCONTAINER2D::BuildBVH ( )

Definition at line 266 of file ccontainer2d.cpp.

References destroy(), CGENERICCONTAINER2D::m_bbox, BVH_CONTAINER_NODE_2D::m_BBox, m_elements_to_delete, m_isInitialized, BVH_CONTAINER_NODE_2D::m_LeafList, CGENERICCONTAINER2D::m_objects, m_Tree, and recursiveBuild_MIDDLE_SPLIT().

Referenced by CINFO3D_VISU::createLayers().

267 {
268  if( m_isInitialized )
269  destroy();
270 
271  if( m_objects.empty() )
272  {
273  return;
274  }
275 
276  m_isInitialized = true;
278 
279  m_elements_to_delete.push_back( m_Tree );
280  m_Tree->m_BBox = m_bbox;
281 
282  for( LIST_OBJECT2D::const_iterator ii = m_objects.begin();
283  ii != m_objects.end();
284  ++ii )
285  {
286  m_Tree->m_LeafList.push_back( static_cast<const COBJECT2D *>(*ii) );
287  }
288 
290 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:93
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:107
void recursiveBuild_MIDDLE_SPLIT(BVH_CONTAINER_NODE_2D *aNodeParent)
LIST_OBJECT2D m_objects
Definition: ccontainer2d.h:44
BVH_CONTAINER_NODE_2D * m_Tree
Definition: ccontainer2d.h:108
void CGENERICCONTAINER2D::Clear ( )
inherited

Definition at line 47 of file ccontainer2d.cpp.

References CGENERICCONTAINER2D::m_bbox, CGENERICCONTAINER2D::m_objects, and CBBOX2D::Reset().

Referenced by CINFO3D_VISU::CINFO3D_VISU(), CINFO3D_VISU::destroyLayers(), C3D_RENDER_RAYTRACING::reload(), and CGENERICCONTAINER2D::~CGENERICCONTAINER2D().

48 {
49  m_bbox.Reset();
50 
51  for( LIST_OBJECT2D::iterator ii = m_objects.begin();
52  ii != m_objects.end();
53  ++ii )
54  {
55  delete *ii;
56  *ii = NULL;
57  }
58 
59  m_objects.clear();
60 }
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:88
LIST_OBJECT2D m_objects
Definition: ccontainer2d.h:44
void CBVHCONTAINER2D::destroy ( )
private

Definition at line 242 of file ccontainer2d.cpp.

References m_elements_to_delete, and m_isInitialized.

Referenced by BuildBVH(), and ~CBVHCONTAINER2D().

243 {
244  for( std::list<BVH_CONTAINER_NODE_2D *>::iterator ii = m_elements_to_delete.begin();
245  ii != m_elements_to_delete.end();
246  ++ii )
247  {
248  delete *ii;
249  *ii = NULL;
250  }
251  m_elements_to_delete.clear();
252 
253  m_isInitialized = false;
254 }
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:107
const LIST_OBJECT2D& CGENERICCONTAINER2D::GetList ( ) const
inlineinherited
void CBVHCONTAINER2D::GetListObjectsIntersects ( const CBBOX2D aBBox,
CONST_LIST_OBJECT2D aOutList 
) const
overridevirtual

GetListObjectsIntersects - Get a list of objects that intersects a bbox.

Parameters
aBBox- a bbox to make the query
aOutList- A list of objects that intersects the bbox

Implements CGENERICCONTAINER2D.

Definition at line 389 of file ccontainer2d.cpp.

References CBBOX2D::IsInitialized(), m_isInitialized, m_Tree, and recursiveGetListObjectsIntersects().

Referenced by C3D_RENDER_RAYTRACING::insert3DPadHole(), and C3D_RENDER_RAYTRACING::reload().

391 {
392  wxASSERT( aBBox.IsInitialized() == true );
393  wxASSERT( m_isInitialized == true );
394 
395  aOutList.clear();
396 
397  if( m_Tree )
398  recursiveGetListObjectsIntersects( m_Tree, aBBox, aOutList );
399 }
bool IsInitialized() const
Function IsInitialized check if this bounding box is already initialized.
Definition: cbbox2d.cpp:79
BVH_CONTAINER_NODE_2D * m_Tree
Definition: ccontainer2d.h:108
void recursiveGetListObjectsIntersects(const BVH_CONTAINER_NODE_2D *aNode, const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const
void CBVHCONTAINER2D::recursiveBuild_MIDDLE_SPLIT ( BVH_CONTAINER_NODE_2D aNodeParent)
private

Definition at line 316 of file ccontainer2d.cpp.

References BVH_CONTAINER2D_MAX_OBJ_PER_LEAF, COBJECT2D::GetBBox(), CBBOX2D::IsInitialized(), BVH_CONTAINER_NODE_2D::m_BBox, BVH_CONTAINER_NODE_2D::m_Children, m_elements_to_delete, BVH_CONTAINER_NODE_2D::m_LeafList, CBBOX2D::MaxDimension(), CBBOX2D::Reset(), sortByCentroid_X(), sortByCentroid_Y(), sortByCentroid_Z(), and CBBOX2D::Union().

Referenced by BuildBVH().

317 {
318  wxASSERT( aNodeParent != NULL );
319  wxASSERT( aNodeParent->m_BBox.IsInitialized() == true );
320  wxASSERT( aNodeParent->m_LeafList.size() > 0 );
321 
322  if( aNodeParent->m_LeafList.size() > BVH_CONTAINER2D_MAX_OBJ_PER_LEAF )
323  {
324  // Create Leaf Nodes
327  m_elements_to_delete.push_back( leftNode );
328  m_elements_to_delete.push_back( rightNode );
329 
330  leftNode->m_BBox.Reset();
331  rightNode->m_BBox.Reset();
332  leftNode->m_LeafList.clear();
333  rightNode->m_LeafList.clear();
334 
335  // Decide wich axis to split
336  const unsigned int axis_to_split = aNodeParent->m_BBox.MaxDimension();
337 
338  // Divide the objects
339  switch( axis_to_split )
340  {
341  case 0: aNodeParent->m_LeafList.sort( sortByCentroid_X ); break;
342  case 1: aNodeParent->m_LeafList.sort( sortByCentroid_Y ); break;
343  case 2: aNodeParent->m_LeafList.sort( sortByCentroid_Z ); break;
344  }
345 
346  unsigned int i = 0;
347 
348  for( CONST_LIST_OBJECT2D::const_iterator ii = aNodeParent->m_LeafList.begin();
349  ii != aNodeParent->m_LeafList.end();
350  ++ii )
351  {
352  const COBJECT2D *object = static_cast<const COBJECT2D *>(*ii);
353 
354  if( i < (aNodeParent->m_LeafList.size() / 2 ) )
355  {
356  leftNode->m_BBox.Union( object->GetBBox() );
357  leftNode->m_LeafList.push_back( object );
358  }
359  else
360  {
361  rightNode->m_BBox.Union( object->GetBBox() );
362  rightNode->m_LeafList.push_back( object );
363  }
364 
365  i++;
366  }
367 
368  wxASSERT( leftNode->m_LeafList.size() > 0 );
369  wxASSERT( rightNode->m_LeafList.size() > 0 );
370  wxASSERT( ( leftNode->m_LeafList.size() + rightNode->m_LeafList.size() ) ==
371  aNodeParent->m_LeafList.size() );
372 
373  aNodeParent->m_Children[0] = leftNode;
374  aNodeParent->m_Children[1] = rightNode;
375  aNodeParent->m_LeafList.clear();
376 
377  recursiveBuild_MIDDLE_SPLIT( leftNode );
378  recursiveBuild_MIDDLE_SPLIT( rightNode );
379  }
380  else
381  {
382  // It is a Leaf
383  aNodeParent->m_Children[0] = NULL;
384  aNodeParent->m_Children[1] = NULL;
385  }
386 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:93
bool IsInitialized() const
Function IsInitialized check if this bounding box is already initialized.
Definition: cbbox2d.cpp:79
void Union(const SFVEC2F &aPoint)
Function Union recalculate the bounding box adding a point.
Definition: cbbox2d.cpp:95
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:107
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: ccontainer2d.h:90
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:88
#define BVH_CONTAINER2D_MAX_OBJ_PER_LEAF
void recursiveBuild_MIDDLE_SPLIT(BVH_CONTAINER_NODE_2D *aNodeParent)
static bool sortByCentroid_Y(const COBJECT2D *a, const COBJECT2D *b)
static bool sortByCentroid_X(const COBJECT2D *a, const COBJECT2D *b)
static bool sortByCentroid_Z(const COBJECT2D *a, const COBJECT2D *b)
const CBBOX2D & GetBBox() const
Definition: cobject2d.h:121
unsigned int MaxDimension() const
Function MaxDimension.
Definition: cbbox2d.cpp:133
void CBVHCONTAINER2D::recursiveGetListObjectsIntersects ( const BVH_CONTAINER_NODE_2D aNode,
const CBBOX2D aBBox,
CONST_LIST_OBJECT2D aOutList 
) const
private

Definition at line 402 of file ccontainer2d.cpp.

References COBJECT2D::Intersects(), CBBOX2D::Intersects(), CBBOX2D::IsInitialized(), BVH_CONTAINER_NODE_2D::m_BBox, BVH_CONTAINER_NODE_2D::m_Children, and BVH_CONTAINER_NODE_2D::m_LeafList.

Referenced by GetListObjectsIntersects().

405 {
406  wxASSERT( aNode != NULL );
407  wxASSERT( aBBox.IsInitialized() == true );
408 
409  if( aNode->m_BBox.Intersects( aBBox ) )
410  {
411  if( !aNode->m_LeafList.empty() )
412  {
413  wxASSERT( aNode->m_Children[0] == NULL );
414  wxASSERT( aNode->m_Children[1] == NULL );
415 
416  // Leaf
417  for( CONST_LIST_OBJECT2D::const_iterator ii = aNode->m_LeafList.begin();
418  ii != aNode->m_LeafList.end();
419  ++ii )
420  {
421  const COBJECT2D *obj = static_cast<const COBJECT2D *>(*ii);
422 
423  if( obj->Intersects( aBBox ) )
424  aOutList.push_back( obj );
425  }
426  }
427  else
428  {
429  wxASSERT( aNode->m_Children[0] != NULL );
430  wxASSERT( aNode->m_Children[1] != NULL );
431 
432  // Node
433  recursiveGetListObjectsIntersects( aNode->m_Children[0], aBBox, aOutList );
434  recursiveGetListObjectsIntersects( aNode->m_Children[1], aBBox, aOutList );
435  }
436  }
437 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:93
bool IsInitialized() const
Function IsInitialized check if this bounding box is already initialized.
Definition: cbbox2d.cpp:79
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: ccontainer2d.h:90
bool Intersects(const CBBOX2D &aBBox) const
Function Intersects test if a bounding box intersects this box.
Definition: cbbox2d.cpp:213
void recursiveGetListObjectsIntersects(const BVH_CONTAINER_NODE_2D *aNode, const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const
virtual bool Intersects(const CBBOX2D &aBBox) const =0
Function Intersects.

Member Data Documentation

CBBOX2D CGENERICCONTAINER2D::m_bbox
protectedinherited
std::list<BVH_CONTAINER_NODE_2D *> CBVHCONTAINER2D::m_elements_to_delete
private

Definition at line 107 of file ccontainer2d.h.

Referenced by BuildBVH(), CBVHCONTAINER2D(), destroy(), and recursiveBuild_MIDDLE_SPLIT().

bool CBVHCONTAINER2D::m_isInitialized
private

Definition at line 106 of file ccontainer2d.h.

Referenced by BuildBVH(), CBVHCONTAINER2D(), destroy(), and GetListObjectsIntersects().

LIST_OBJECT2D CGENERICCONTAINER2D::m_objects
protectedinherited
BVH_CONTAINER_NODE_2D* CBVHCONTAINER2D::m_Tree
private

Definition at line 108 of file ccontainer2d.h.

Referenced by BuildBVH(), CBVHCONTAINER2D(), and GetListObjectsIntersects().


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