KiCad PCB EDA Suite
CBVHCONTAINER2D Class Reference

#include <ccontainer2d.h>

Inheritance diagram for CBVHCONTAINER2D:
CGENERICCONTAINER2D

Public Member Functions

 CBVHCONTAINER2D ()
 
 ~CBVHCONTAINER2D ()
 
void BuildBVH ()
 
void Clear () override
 
void GetListObjectsIntersects (const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const override
 GetListObjectsIntersects - Get a list of objects that intersects a bbox. More...
 
bool IntersectAny (const RAYSEG2D &aSegRay) const override
 IntersectAny - Intersect and check if a segment ray hits a object or is inside it. More...
 
void Add (COBJECT2D *aObject)
 
const CBBOX2DGetBBox () const
 
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
 
bool recursiveIntersectAny (const BVH_CONTAINER_NODE_2D *aNode, const RAYSEG2D &aSegRay) 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 114 of file ccontainer2d.h.

Constructor & Destructor Documentation

◆ CBVHCONTAINER2D()

CBVHCONTAINER2D::CBVHCONTAINER2D ( )

Definition at line 168 of file ccontainer2d.cpp.

169 {
170  m_isInitialized = false;
171  m_bbox.Reset();
172  m_elements_to_delete.clear();
173  m_Tree = NULL;
174 }
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:126
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:87
#define NULL
CGENERICCONTAINER2D(OBJECT2D_TYPE aObjType)
BVH_CONTAINER_NODE_2D * m_Tree
Definition: ccontainer2d.h:127

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

◆ ~CBVHCONTAINER2D()

CBVHCONTAINER2D::~CBVHCONTAINER2D ( )

Definition at line 269 of file ccontainer2d.cpp.

270 {
271  destroy();
272 }

References destroy().

Member Function Documentation

◆ Add()

void CGENERICCONTAINER2D::Add ( COBJECT2D aObject)
inlineinherited

◆ BuildBVH()

void CBVHCONTAINER2D::BuildBVH ( )

Definition at line 278 of file ccontainer2d.cpp.

279 {
280  if( m_isInitialized )
281  destroy();
282 
283  m_isInitialized = true;
284 
285  if( m_objects.empty() )
286  {
287  return;
288  }
289 
291 
292  m_elements_to_delete.push_back( m_Tree );
293  m_Tree->m_BBox = m_bbox;
294 
295  for( LIST_OBJECT2D::const_iterator ii = m_objects.begin();
296  ii != m_objects.end();
297  ++ii )
298  {
299  m_Tree->m_LeafList.push_back( static_cast<const COBJECT2D *>(*ii) );
300  }
301 
303 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:110
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:126
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:127

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 BOARD_ADAPTER::createLayers(), and C3D_RENDER_RAYTRACING::Reload().

◆ Clear()

void CBVHCONTAINER2D::Clear ( )
overridevirtual

Reimplemented from CGENERICCONTAINER2D.

Definition at line 249 of file ccontainer2d.cpp.

250 {
252  destroy();
253 }
virtual void Clear()

References CGENERICCONTAINER2D::Clear(), and destroy().

Referenced by BOARD_ADAPTER::BOARD_ADAPTER(), and BOARD_ADAPTER::destroyLayers().

◆ destroy()

void CBVHCONTAINER2D::destroy ( )
private

Definition at line 255 of file ccontainer2d.cpp.

256 {
257  for( std::list<BVH_CONTAINER_NODE_2D *>::iterator ii = m_elements_to_delete.begin();
258  ii != m_elements_to_delete.end();
259  ++ii )
260  {
261  delete *ii;
262  }
263  m_elements_to_delete.clear();
264  m_Tree = nullptr;
265  m_isInitialized = false;
266 }
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:126
BVH_CONTAINER_NODE_2D * m_Tree
Definition: ccontainer2d.h:127

References m_elements_to_delete, m_isInitialized, and m_Tree.

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

◆ GetBBox()

const CBBOX2D& CGENERICCONTAINER2D::GetBBox ( ) const
inlineinherited

Definition at line 62 of file ccontainer2d.h.

63  {
64  return m_bbox;
65  }

References CGENERICCONTAINER2D::m_bbox.

◆ GetList()

◆ GetListObjectsIntersects()

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 457 of file ccontainer2d.cpp.

459 {
460  wxASSERT( aBBox.IsInitialized() == true );
461  wxASSERT( m_isInitialized == true );
462 
463  aOutList.clear();
464 
465  if( m_Tree )
466  recursiveGetListObjectsIntersects( m_Tree, aBBox, aOutList );
467 }
void recursiveGetListObjectsIntersects(const BVH_CONTAINER_NODE_2D *aNode, const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const
bool IsInitialized() const
Function IsInitialized check if this bounding box is already initialized.
Definition: cbbox2d.cpp:78
BVH_CONTAINER_NODE_2D * m_Tree
Definition: ccontainer2d.h:127

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

Referenced by C3D_RENDER_RAYTRACING::createItemsFromContainer(), C3D_RENDER_RAYTRACING::insert3DPadHole(), and C3D_RENDER_RAYTRACING::Reload().

◆ IntersectAny()

bool CBVHCONTAINER2D::IntersectAny ( const RAYSEG2D aSegRay) const
overridevirtual

IntersectAny - Intersect and check if a segment ray hits a object or is inside it.

Parameters
aSegRay- a segment to intersect with objects
Returns
true - if it hits any of the objects or is inside any object

Implements CGENERICCONTAINER2D.

Definition at line 407 of file ccontainer2d.cpp.

408 {
409  wxASSERT( m_isInitialized == true );
410 
411  if( m_Tree )
412  return recursiveIntersectAny( m_Tree, aSegRay );
413 
414  return false;
415 }
bool recursiveIntersectAny(const BVH_CONTAINER_NODE_2D *aNode, const RAYSEG2D &aSegRay) const
BVH_CONTAINER_NODE_2D * m_Tree
Definition: ccontainer2d.h:127

References m_isInitialized, m_Tree, and recursiveIntersectAny().

Referenced by CLAYER_TRIANGLES::AddToMiddleContourns().

◆ recursiveBuild_MIDDLE_SPLIT()

void CBVHCONTAINER2D::recursiveBuild_MIDDLE_SPLIT ( BVH_CONTAINER_NODE_2D aNodeParent)
private

Definition at line 329 of file ccontainer2d.cpp.

330 {
331  wxASSERT( aNodeParent != NULL );
332  wxASSERT( aNodeParent->m_BBox.IsInitialized() == true );
333  wxASSERT( aNodeParent->m_LeafList.size() > 0 );
334 
335  if( aNodeParent->m_LeafList.size() > BVH_CONTAINER2D_MAX_OBJ_PER_LEAF )
336  {
337  // Create Leaf Nodes
340  m_elements_to_delete.push_back( leftNode );
341  m_elements_to_delete.push_back( rightNode );
342 
343  leftNode->m_BBox.Reset();
344  rightNode->m_BBox.Reset();
345  leftNode->m_LeafList.clear();
346  rightNode->m_LeafList.clear();
347 
348  // Decide wich axis to split
349  const unsigned int axis_to_split = aNodeParent->m_BBox.MaxDimension();
350 
351  // Divide the objects
352  switch( axis_to_split )
353  {
354  case 0: aNodeParent->m_LeafList.sort( sortByCentroid_X ); break;
355  case 1: aNodeParent->m_LeafList.sort( sortByCentroid_Y ); break;
356  case 2: aNodeParent->m_LeafList.sort( sortByCentroid_Z ); break;
357  }
358 
359  unsigned int i = 0;
360 
361  for( CONST_LIST_OBJECT2D::const_iterator ii = aNodeParent->m_LeafList.begin();
362  ii != aNodeParent->m_LeafList.end();
363  ++ii )
364  {
365  const COBJECT2D *object = static_cast<const COBJECT2D *>(*ii);
366 
367  if( i < (aNodeParent->m_LeafList.size() / 2 ) )
368  {
369  leftNode->m_BBox.Union( object->GetBBox() );
370  leftNode->m_LeafList.push_back( object );
371  }
372  else
373  {
374  rightNode->m_BBox.Union( object->GetBBox() );
375  rightNode->m_LeafList.push_back( object );
376  }
377 
378  i++;
379  }
380 
381  wxASSERT( leftNode->m_LeafList.size() > 0 );
382  wxASSERT( rightNode->m_LeafList.size() > 0 );
383  wxASSERT( ( leftNode->m_LeafList.size() + rightNode->m_LeafList.size() ) ==
384  aNodeParent->m_LeafList.size() );
385 
386  aNodeParent->m_Children[0] = leftNode;
387  aNodeParent->m_Children[1] = rightNode;
388  aNodeParent->m_LeafList.clear();
389 
390  recursiveBuild_MIDDLE_SPLIT( leftNode );
391  recursiveBuild_MIDDLE_SPLIT( rightNode );
392 
393  wxASSERT( aNodeParent->m_LeafList.size() == 0 );
394  }
395  else
396  {
397  // It is a Leaf
398  aNodeParent->m_Children[0] = NULL;
399  aNodeParent->m_Children[1] = NULL;
400  }
401 
402  wxASSERT( aNodeParent != NULL );
403  wxASSERT( aNodeParent->m_BBox.IsInitialized() == true );
404 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:110
void Union(const SFVEC2F &aPoint)
Function Union recalculate the bounding box adding a point.
Definition: cbbox2d.cpp:94
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:126
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: ccontainer2d.h:107
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:87
#define BVH_CONTAINER2D_MAX_OBJ_PER_LEAF
void recursiveBuild_MIDDLE_SPLIT(BVH_CONTAINER_NODE_2D *aNodeParent)
#define NULL
static bool sortByCentroid_Y(const COBJECT2D *a, const COBJECT2D *b)
bool IsInitialized() const
Function IsInitialized check if this bounding box is already initialized.
Definition: cbbox2d.cpp:78
static bool sortByCentroid_X(const COBJECT2D *a, const COBJECT2D *b)
static bool sortByCentroid_Z(const COBJECT2D *a, const COBJECT2D *b)
unsigned int MaxDimension() const
Function MaxDimension.
Definition: cbbox2d.cpp:132
const CBBOX2D & GetBBox() const
Definition: cobject2d.h:121

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(), NULL, CBBOX2D::Reset(), sortByCentroid_X(), sortByCentroid_Y(), sortByCentroid_Z(), and CBBOX2D::Union().

Referenced by BuildBVH().

◆ recursiveGetListObjectsIntersects()

void CBVHCONTAINER2D::recursiveGetListObjectsIntersects ( const BVH_CONTAINER_NODE_2D aNode,
const CBBOX2D aBBox,
CONST_LIST_OBJECT2D aOutList 
) const
private

Definition at line 470 of file ccontainer2d.cpp.

473 {
474  wxASSERT( aNode != NULL );
475  wxASSERT( aBBox.IsInitialized() == true );
476 
477  if( aNode->m_BBox.Intersects( aBBox ) )
478  {
479  if( !aNode->m_LeafList.empty() )
480  {
481  wxASSERT( aNode->m_Children[0] == NULL );
482  wxASSERT( aNode->m_Children[1] == NULL );
483 
484  // Leaf
485  for( CONST_LIST_OBJECT2D::const_iterator ii = aNode->m_LeafList.begin();
486  ii != aNode->m_LeafList.end();
487  ++ii )
488  {
489  const COBJECT2D *obj = static_cast<const COBJECT2D *>(*ii);
490 
491  if( obj->Intersects( aBBox ) )
492  aOutList.push_back( obj );
493  }
494  }
495  else
496  {
497  wxASSERT( aNode->m_Children[0] != NULL );
498  wxASSERT( aNode->m_Children[1] != NULL );
499 
500  // Node
501  recursiveGetListObjectsIntersects( aNode->m_Children[0], aBBox, aOutList );
502  recursiveGetListObjectsIntersects( aNode->m_Children[1], aBBox, aOutList );
503  }
504  }
505 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:110
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: ccontainer2d.h:107
void recursiveGetListObjectsIntersects(const BVH_CONTAINER_NODE_2D *aNode, const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const
#define NULL
bool Intersects(const CBBOX2D &aBBox) const
Function Intersects test if a bounding box intersects this box.
Definition: cbbox2d.cpp:212
bool IsInitialized() const
Function IsInitialized check if this bounding box is already initialized.
Definition: cbbox2d.cpp:78
virtual bool Intersects(const CBBOX2D &aBBox) const =0
Function Intersects.

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

Referenced by GetListObjectsIntersects().

◆ recursiveIntersectAny()

bool CBVHCONTAINER2D::recursiveIntersectAny ( const BVH_CONTAINER_NODE_2D aNode,
const RAYSEG2D aSegRay 
) const
private

Definition at line 418 of file ccontainer2d.cpp.

420 {
421  wxASSERT( aNode != NULL );
422 
423  if( aNode->m_BBox.Inside( aSegRay.m_Start ) ||
424  aNode->m_BBox.Inside( aSegRay.m_End ) ||
425  aNode->m_BBox.Intersect( aSegRay ) )
426  {
427  if( !aNode->m_LeafList.empty() )
428  {
429  wxASSERT( aNode->m_Children[0] == NULL );
430  wxASSERT( aNode->m_Children[1] == NULL );
431 
432  // Leaf
433  for( const COBJECT2D *obj : aNode->m_LeafList )
434  {
435  if( obj->IsPointInside( aSegRay.m_Start ) ||
436  obj->IsPointInside( aSegRay.m_End ) ||
437  obj->Intersect( aSegRay, nullptr, nullptr ) )
438  return true;
439  }
440  }
441  else
442  {
443  wxASSERT( aNode->m_Children[0] != NULL );
444  wxASSERT( aNode->m_Children[1] != NULL );
445 
446  // Node
447  if( recursiveIntersectAny( aNode->m_Children[0], aSegRay ) )
448  return true;
449  if( recursiveIntersectAny( aNode->m_Children[1], aSegRay ) )
450  return true;
451  }
452  }
453 
454  return false;
455 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:110
bool recursiveIntersectAny(const BVH_CONTAINER_NODE_2D *aNode, const RAYSEG2D &aSegRay) const
bool Inside(const SFVEC2F &aPoint) const
Function Inside check is a point is inside this bounding box.
Definition: cbbox2d.cpp:224
virtual bool Intersect(const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut) const =0
Function Intersect.
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: ccontainer2d.h:107
#define NULL
SFVEC2F m_End
Definition: ray.h:113
SFVEC2F m_Start
Definition: ray.h:112
virtual bool IsPointInside(const SFVEC2F &aPoint) const =0
bool Intersect(const RAY2D &aRay, float *t) const
Function Intersect.
Definition: cbbox2d.cpp:241

References CBBOX2D::Inside(), COBJECT2D::Intersect(), CBBOX2D::Intersect(), COBJECT2D::IsPointInside(), BVH_CONTAINER_NODE_2D::m_BBox, BVH_CONTAINER_NODE_2D::m_Children, RAYSEG2D::m_End, BVH_CONTAINER_NODE_2D::m_LeafList, RAYSEG2D::m_Start, and NULL.

Referenced by IntersectAny().

Member Data Documentation

◆ m_bbox

◆ m_elements_to_delete

std::list<BVH_CONTAINER_NODE_2D *> CBVHCONTAINER2D::m_elements_to_delete
private

Definition at line 126 of file ccontainer2d.h.

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

◆ m_isInitialized

bool CBVHCONTAINER2D::m_isInitialized
private

◆ m_objects

LIST_OBJECT2D CGENERICCONTAINER2D::m_objects
protectedinherited

◆ m_Tree

BVH_CONTAINER_NODE_2D* CBVHCONTAINER2D::m_Tree
private

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