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 100 of file ccontainer2d.h.

Constructor & Destructor Documentation

CBVHCONTAINER2D::CBVHCONTAINER2D ( )

Definition at line 163 of file ccontainer2d.cpp.

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

164 {
165  m_isInitialized = false;
166  m_bbox.Reset();
167  m_elements_to_delete.clear();
168  m_Tree = NULL;
169 }
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:110
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:111
CBVHCONTAINER2D::~CBVHCONTAINER2D ( )

Definition at line 259 of file ccontainer2d.cpp.

References destroy().

260 {
261  destroy();
262 }

Member Function Documentation

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

Definition at line 268 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().

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

Definition at line 48 of file ccontainer2d.cpp.

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

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

49 {
50  std::lock_guard<std::mutex> lock( m_lock );
51  m_bbox.Reset();
52 
53  for( LIST_OBJECT2D::iterator ii = m_objects.begin();
54  ii != m_objects.end();
55  ++ii )
56  {
57  delete *ii;
58  *ii = NULL;
59  }
60 
61  m_objects.clear();
62 }
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:45
void CBVHCONTAINER2D::destroy ( )
private

Definition at line 244 of file ccontainer2d.cpp.

References m_elements_to_delete, and m_isInitialized.

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

245 {
246  for( std::list<BVH_CONTAINER_NODE_2D *>::iterator ii = m_elements_to_delete.begin();
247  ii != m_elements_to_delete.end();
248  ++ii )
249  {
250  delete *ii;
251  *ii = NULL;
252  }
253  m_elements_to_delete.clear();
254 
255  m_isInitialized = false;
256 }
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:110
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 391 of file ccontainer2d.cpp.

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

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

393 {
394  wxASSERT( aBBox.IsInitialized() == true );
395  wxASSERT( m_isInitialized == true );
396 
397  aOutList.clear();
398 
399  if( m_Tree )
400  recursiveGetListObjectsIntersects( m_Tree, aBBox, aOutList );
401 }
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:111
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 318 of file ccontainer2d.cpp.

References BVH_CONTAINER2D_MAX_OBJ_PER_LEAF, COBJECT2D::GetBBox(), i, 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().

319 {
320  wxASSERT( aNodeParent != NULL );
321  wxASSERT( aNodeParent->m_BBox.IsInitialized() == true );
322  wxASSERT( aNodeParent->m_LeafList.size() > 0 );
323 
324  if( aNodeParent->m_LeafList.size() > BVH_CONTAINER2D_MAX_OBJ_PER_LEAF )
325  {
326  // Create Leaf Nodes
329  m_elements_to_delete.push_back( leftNode );
330  m_elements_to_delete.push_back( rightNode );
331 
332  leftNode->m_BBox.Reset();
333  rightNode->m_BBox.Reset();
334  leftNode->m_LeafList.clear();
335  rightNode->m_LeafList.clear();
336 
337  // Decide wich axis to split
338  const unsigned int axis_to_split = aNodeParent->m_BBox.MaxDimension();
339 
340  // Divide the objects
341  switch( axis_to_split )
342  {
343  case 0: aNodeParent->m_LeafList.sort( sortByCentroid_X ); break;
344  case 1: aNodeParent->m_LeafList.sort( sortByCentroid_Y ); break;
345  case 2: aNodeParent->m_LeafList.sort( sortByCentroid_Z ); break;
346  }
347 
348  unsigned int i = 0;
349 
350  for( CONST_LIST_OBJECT2D::const_iterator ii = aNodeParent->m_LeafList.begin();
351  ii != aNodeParent->m_LeafList.end();
352  ++ii )
353  {
354  const COBJECT2D *object = static_cast<const COBJECT2D *>(*ii);
355 
356  if( i < (aNodeParent->m_LeafList.size() / 2 ) )
357  {
358  leftNode->m_BBox.Union( object->GetBBox() );
359  leftNode->m_LeafList.push_back( object );
360  }
361  else
362  {
363  rightNode->m_BBox.Union( object->GetBBox() );
364  rightNode->m_LeafList.push_back( object );
365  }
366 
367  i++;
368  }
369 
370  wxASSERT( leftNode->m_LeafList.size() > 0 );
371  wxASSERT( rightNode->m_LeafList.size() > 0 );
372  wxASSERT( ( leftNode->m_LeafList.size() + rightNode->m_LeafList.size() ) ==
373  aNodeParent->m_LeafList.size() );
374 
375  aNodeParent->m_Children[0] = leftNode;
376  aNodeParent->m_Children[1] = rightNode;
377  aNodeParent->m_LeafList.clear();
378 
379  recursiveBuild_MIDDLE_SPLIT( leftNode );
380  recursiveBuild_MIDDLE_SPLIT( rightNode );
381  }
382  else
383  {
384  // It is a Leaf
385  aNodeParent->m_Children[0] = NULL;
386  aNodeParent->m_Children[1] = NULL;
387  }
388 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:96
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:110
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: ccontainer2d.h:93
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)
size_t i
Definition: json11.cpp:597
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 404 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().

407 {
408  wxASSERT( aNode != NULL );
409  wxASSERT( aBBox.IsInitialized() == true );
410 
411  if( aNode->m_BBox.Intersects( aBBox ) )
412  {
413  if( !aNode->m_LeafList.empty() )
414  {
415  wxASSERT( aNode->m_Children[0] == NULL );
416  wxASSERT( aNode->m_Children[1] == NULL );
417 
418  // Leaf
419  for( CONST_LIST_OBJECT2D::const_iterator ii = aNode->m_LeafList.begin();
420  ii != aNode->m_LeafList.end();
421  ++ii )
422  {
423  const COBJECT2D *obj = static_cast<const COBJECT2D *>(*ii);
424 
425  if( obj->Intersects( aBBox ) )
426  aOutList.push_back( obj );
427  }
428  }
429  else
430  {
431  wxASSERT( aNode->m_Children[0] != NULL );
432  wxASSERT( aNode->m_Children[1] != NULL );
433 
434  // Node
435  recursiveGetListObjectsIntersects( aNode->m_Children[0], aBBox, aOutList );
436  recursiveGetListObjectsIntersects( aNode->m_Children[1], aBBox, aOutList );
437  }
438  }
439 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:96
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:93
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 110 of file ccontainer2d.h.

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

bool CBVHCONTAINER2D::m_isInitialized
private

Definition at line 109 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 111 of file ccontainer2d.h.

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


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