KiCad PCB EDA Suite
BVH_CONTAINER_2D Class Reference

#include <container_2d.h>

Inheritance diagram for BVH_CONTAINER_2D:
CONTAINER_2D_BASE

Public Member Functions

 BVH_CONTAINER_2D ()
 
 ~BVH_CONTAINER_2D ()
 
void BuildBVH ()
 
void Clear () override
 
void GetIntersectingObjects (const BBOX_2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const override
 Get a list of objects that intersects a bounding box. More...
 
bool IntersectAny (const RAYSEG2D &aSegRay) const override
 Intersect and check if a segment ray hits a object or is inside it. More...
 
void Add (OBJECT_2D *aObject)
 
const BBOX_2DGetBBox () const
 
const LIST_OBJECT2DGetList () const
 

Protected Attributes

BBOX_2D 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 BBOX_2D &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_elementsToDelete
 
BVH_CONTAINER_NODE_2Dm_tree
 

Detailed Description

Definition at line 116 of file container_2d.h.

Constructor & Destructor Documentation

◆ BVH_CONTAINER_2D()

BVH_CONTAINER_2D::BVH_CONTAINER_2D ( )

Definition at line 82 of file container_2d.cpp.

83 {
84  m_isInitialized = false;
85  m_bbox.Reset();
86  m_elementsToDelete.clear();
87  m_tree = nullptr;
88 }
CONTAINER_2D_BASE(OBJECT_2D_TYPE aObjType)
std::list< BVH_CONTAINER_NODE_2D * > m_elementsToDelete
Definition: container_2d.h:141
void Reset()
Reset the bounding box to zero and uninitialize it.
Definition: bbox_2d.cpp:86
BVH_CONTAINER_NODE_2D * m_tree
Definition: container_2d.h:142

References BVHCONTAINER, CONTAINER_2D_BASE::m_bbox, m_elementsToDelete, m_isInitialized, m_tree, and BBOX_2D::Reset().

◆ ~BVH_CONTAINER_2D()

BVH_CONTAINER_2D::~BVH_CONTAINER_2D ( )

Definition at line 113 of file container_2d.cpp.

114 {
115  destroy();
116 }

References destroy().

Member Function Documentation

◆ Add()

◆ BuildBVH()

void BVH_CONTAINER_2D::BuildBVH ( )

Definition at line 122 of file container_2d.cpp.

123 {
124  if( m_isInitialized )
125  destroy();
126 
127  m_isInitialized = true;
128 
129  if( m_objects.empty() )
130  {
131  return;
132  }
133 
135 
136  m_elementsToDelete.push_back( m_tree );
137  m_tree->m_BBox = m_bbox;
138 
139  for( LIST_OBJECT2D::const_iterator ii = m_objects.begin(); ii != m_objects.end(); ++ii )
140  {
141  m_tree->m_LeafList.push_back( static_cast<const OBJECT_2D*>( *ii ) );
142  }
143 
145 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: container_2d.h:112
LIST_OBJECT2D m_objects
Definition: container_2d.h:87
void recursiveBuild_MIDDLE_SPLIT(BVH_CONTAINER_NODE_2D *aNodeParent)
std::list< BVH_CONTAINER_NODE_2D * > m_elementsToDelete
Definition: container_2d.h:141
BVH_CONTAINER_NODE_2D * m_tree
Definition: container_2d.h:142

References destroy(), CONTAINER_2D_BASE::m_bbox, BVH_CONTAINER_NODE_2D::m_BBox, m_elementsToDelete, m_isInitialized, BVH_CONTAINER_NODE_2D::m_LeafList, CONTAINER_2D_BASE::m_objects, m_tree, and recursiveBuild_MIDDLE_SPLIT().

Referenced by BOARD_ADAPTER::createLayers(), and RENDER_3D_RAYTRACE::Reload().

◆ Clear()

void BVH_CONTAINER_2D::Clear ( )
overridevirtual

Reimplemented from CONTAINER_2D_BASE.

Definition at line 91 of file container_2d.cpp.

92 {
94  destroy();
95 }
virtual void Clear()

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

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

◆ destroy()

void BVH_CONTAINER_2D::destroy ( )
private

Definition at line 98 of file container_2d.cpp.

99 {
100  for( std::list<BVH_CONTAINER_NODE_2D*>::iterator ii = m_elementsToDelete.begin();
101  ii != m_elementsToDelete.end();
102  ++ii )
103  {
104  delete *ii;
105  }
106 
107  m_elementsToDelete.clear();
108  m_tree = nullptr;
109  m_isInitialized = false;
110 }
std::list< BVH_CONTAINER_NODE_2D * > m_elementsToDelete
Definition: container_2d.h:141
BVH_CONTAINER_NODE_2D * m_tree
Definition: container_2d.h:142

References m_elementsToDelete, m_isInitialized, and m_tree.

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

◆ GetBBox()

const BBOX_2D& CONTAINER_2D_BASE::GetBBox ( ) const
inlineinherited

Definition at line 59 of file container_2d.h.

60  {
61  return m_bbox;
62  }

References CONTAINER_2D_BASE::m_bbox.

◆ GetIntersectingObjects()

void BVH_CONTAINER_2D::GetIntersectingObjects ( const BBOX_2D aBBox,
CONST_LIST_OBJECT2D aOutList 
) const
overridevirtual

Get a list of objects that intersects a bounding box.

Parameters
aBBoxThe bounding box to test.
aOutListThe list of objects that intersects the bounding box.

Implements CONTAINER_2D_BASE.

Definition at line 302 of file container_2d.cpp.

304 {
305  wxASSERT( aBBox.IsInitialized() == true );
306  wxASSERT( m_isInitialized == true );
307 
308  aOutList.clear();
309 
310  if( m_tree )
311  recursiveGetListObjectsIntersects( m_tree, aBBox, aOutList );
312 }
BVH_CONTAINER_NODE_2D * m_tree
Definition: container_2d.h:142
void recursiveGetListObjectsIntersects(const BVH_CONTAINER_NODE_2D *aNode, const BBOX_2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const
bool IsInitialized() const
Check if this bounding box is already initialized.
Definition: bbox_2d.cpp:79

References BBOX_2D::IsInitialized(), m_isInitialized, m_tree, and recursiveGetListObjectsIntersects().

Referenced by RENDER_3D_RAYTRACE::createItemsFromContainer(), RENDER_3D_RAYTRACE::insertHole(), and RENDER_3D_RAYTRACE::Reload().

◆ GetList()

◆ IntersectAny()

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

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

Parameters
aSegRayThe segment to intersect with objects.
Returns
true if it hits any of the objects or is inside any object.

Implements CONTAINER_2D_BASE.

Definition at line 251 of file container_2d.cpp.

252 {
253  wxASSERT( m_isInitialized == true );
254 
255  if( m_tree )
256  return recursiveIntersectAny( m_tree, aSegRay );
257 
258  return false;
259 }
bool recursiveIntersectAny(const BVH_CONTAINER_NODE_2D *aNode, const RAYSEG2D &aSegRay) const
BVH_CONTAINER_NODE_2D * m_tree
Definition: container_2d.h:142

References m_isInitialized, m_tree, and recursiveIntersectAny().

Referenced by TRIANGLE_DISPLAY_LIST::AddToMiddleContourns().

◆ recursiveBuild_MIDDLE_SPLIT()

void BVH_CONTAINER_2D::recursiveBuild_MIDDLE_SPLIT ( BVH_CONTAINER_NODE_2D aNodeParent)
private

Definition at line 173 of file container_2d.cpp.

174 {
175  wxASSERT( aNodeParent != nullptr );
176  wxASSERT( aNodeParent->m_BBox.IsInitialized() == true );
177  wxASSERT( aNodeParent->m_LeafList.size() > 0 );
178 
179  if( aNodeParent->m_LeafList.size() > BVH_CONTAINER2D_MAX_OBJ_PER_LEAF )
180  {
181  // Create Leaf Nodes
184  m_elementsToDelete.push_back( leftNode );
185  m_elementsToDelete.push_back( rightNode );
186 
187  leftNode->m_BBox.Reset();
188  rightNode->m_BBox.Reset();
189  leftNode->m_LeafList.clear();
190  rightNode->m_LeafList.clear();
191 
192  // Decide which axis to split
193  const unsigned int axis_to_split = aNodeParent->m_BBox.MaxDimension();
194 
195  // Divide the objects
196  switch( axis_to_split )
197  {
198  case 0: aNodeParent->m_LeafList.sort( sortByCentroidX ); break;
199  case 1: aNodeParent->m_LeafList.sort( sortByCentroidY ); break;
200  case 2: aNodeParent->m_LeafList.sort( sortByCentroidZ ); break;
201  }
202 
203  unsigned int i = 0;
204 
205  for( CONST_LIST_OBJECT2D::const_iterator ii = aNodeParent->m_LeafList.begin();
206  ii != aNodeParent->m_LeafList.end();
207  ++ii )
208  {
209  const OBJECT_2D* object = static_cast<const OBJECT_2D*>( *ii );
210 
211  if( i < (aNodeParent->m_LeafList.size() / 2 ) )
212  {
213  leftNode->m_BBox.Union( object->GetBBox() );
214  leftNode->m_LeafList.push_back( object );
215  }
216  else
217  {
218  rightNode->m_BBox.Union( object->GetBBox() );
219  rightNode->m_LeafList.push_back( object );
220  }
221 
222  i++;
223  }
224 
225  wxASSERT( leftNode->m_LeafList.size() > 0 );
226  wxASSERT( rightNode->m_LeafList.size() > 0 );
227  wxASSERT( ( leftNode->m_LeafList.size() + rightNode->m_LeafList.size() ) ==
228  aNodeParent->m_LeafList.size() );
229 
230  aNodeParent->m_Children[0] = leftNode;
231  aNodeParent->m_Children[1] = rightNode;
232  aNodeParent->m_LeafList.clear();
233 
234  recursiveBuild_MIDDLE_SPLIT( leftNode );
235  recursiveBuild_MIDDLE_SPLIT( rightNode );
236 
237  wxASSERT( aNodeParent->m_LeafList.size() == 0 );
238  }
239  else
240  {
241  // It is a Leaf
242  aNodeParent->m_Children[0] = nullptr;
243  aNodeParent->m_Children[1] = nullptr;
244  }
245 
246  wxASSERT( aNodeParent != nullptr );
247  wxASSERT( aNodeParent->m_BBox.IsInitialized() == true );
248 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: container_2d.h:112
void recursiveBuild_MIDDLE_SPLIT(BVH_CONTAINER_NODE_2D *aNodeParent)
std::list< BVH_CONTAINER_NODE_2D * > m_elementsToDelete
Definition: container_2d.h:141
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: container_2d.h:109
void Reset()
Reset the bounding box to zero and uninitialize it.
Definition: bbox_2d.cpp:86
const BBOX_2D & GetBBox() const
Definition: object_2d.h:103
#define BVH_CONTAINER2D_MAX_OBJ_PER_LEAF
static bool sortByCentroidX(const OBJECT_2D *a, const OBJECT_2D *b)
void Union(const SFVEC2F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_2d.cpp:93
static bool sortByCentroidZ(const OBJECT_2D *a, const OBJECT_2D *b)
static bool sortByCentroidY(const OBJECT_2D *a, const OBJECT_2D *b)
unsigned int MaxDimension() const
Definition: bbox_2d.cpp:131
bool IsInitialized() const
Check if this bounding box is already initialized.
Definition: bbox_2d.cpp:79

References BVH_CONTAINER2D_MAX_OBJ_PER_LEAF, OBJECT_2D::GetBBox(), BBOX_2D::IsInitialized(), BVH_CONTAINER_NODE_2D::m_BBox, BVH_CONTAINER_NODE_2D::m_Children, m_elementsToDelete, BVH_CONTAINER_NODE_2D::m_LeafList, BBOX_2D::MaxDimension(), BBOX_2D::Reset(), sortByCentroidX(), sortByCentroidY(), sortByCentroidZ(), and BBOX_2D::Union().

Referenced by BuildBVH().

◆ recursiveGetListObjectsIntersects()

void BVH_CONTAINER_2D::recursiveGetListObjectsIntersects ( const BVH_CONTAINER_NODE_2D aNode,
const BBOX_2D aBBox,
CONST_LIST_OBJECT2D aOutList 
) const
private

Definition at line 315 of file container_2d.cpp.

318 {
319  wxASSERT( aNode != nullptr );
320  wxASSERT( aBBox.IsInitialized() == true );
321 
322  if( aNode->m_BBox.Intersects( aBBox ) )
323  {
324  if( !aNode->m_LeafList.empty() )
325  {
326  wxASSERT( aNode->m_Children[0] == nullptr );
327  wxASSERT( aNode->m_Children[1] == nullptr );
328 
329  // Leaf
330  for( CONST_LIST_OBJECT2D::const_iterator ii = aNode->m_LeafList.begin();
331  ii != aNode->m_LeafList.end();
332  ++ii )
333  {
334  const OBJECT_2D* obj = static_cast<const OBJECT_2D*>( *ii );
335 
336  if( obj->Intersects( aBBox ) )
337  aOutList.push_back( obj );
338  }
339  }
340  else
341  {
342  wxASSERT( aNode->m_Children[0] != nullptr );
343  wxASSERT( aNode->m_Children[1] != nullptr );
344 
345  // Node
346  recursiveGetListObjectsIntersects( aNode->m_Children[0], aBBox, aOutList );
347  recursiveGetListObjectsIntersects( aNode->m_Children[1], aBBox, aOutList );
348  }
349  }
350 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: container_2d.h:112
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: container_2d.h:109
bool Intersects(const BBOX_2D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_2d.cpp:211
void recursiveGetListObjectsIntersects(const BVH_CONTAINER_NODE_2D *aNode, const BBOX_2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const
virtual bool Intersects(const BBOX_2D &aBBox) const =0
a.Intersects(b) ⇔ !a.Disjoint(b) ⇔ !(a ∩ b = ∅)
bool IsInitialized() const
Check if this bounding box is already initialized.
Definition: bbox_2d.cpp:79

References OBJECT_2D::Intersects(), BBOX_2D::Intersects(), BBOX_2D::IsInitialized(), BVH_CONTAINER_NODE_2D::m_BBox, BVH_CONTAINER_NODE_2D::m_Children, and BVH_CONTAINER_NODE_2D::m_LeafList.

Referenced by GetIntersectingObjects().

◆ recursiveIntersectAny()

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

Definition at line 262 of file container_2d.cpp.

264 {
265  wxASSERT( aNode != nullptr );
266 
267  if( aNode->m_BBox.Inside( aSegRay.m_Start ) || aNode->m_BBox.Inside( aSegRay.m_End ) ||
268  aNode->m_BBox.Intersect( aSegRay ) )
269  {
270  if( !aNode->m_LeafList.empty() )
271  {
272  wxASSERT( aNode->m_Children[0] == nullptr );
273  wxASSERT( aNode->m_Children[1] == nullptr );
274 
275  // Leaf
276  for( const OBJECT_2D* obj : aNode->m_LeafList )
277  {
278  if( obj->IsPointInside( aSegRay.m_Start ) ||
279  obj->IsPointInside( aSegRay.m_End ) ||
280  obj->Intersect( aSegRay, nullptr, nullptr ) )
281  return true;
282  }
283  }
284  else
285  {
286  wxASSERT( aNode->m_Children[0] != nullptr );
287  wxASSERT( aNode->m_Children[1] != nullptr );
288 
289  // Node
290  if( recursiveIntersectAny( aNode->m_Children[0], aSegRay ) )
291  return true;
292 
293  if( recursiveIntersectAny( aNode->m_Children[1], aSegRay ) )
294  return true;
295  }
296  }
297 
298  return false;
299 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: container_2d.h:112
bool recursiveIntersectAny(const BVH_CONTAINER_NODE_2D *aNode, const RAYSEG2D &aSegRay) const
bool Inside(const SFVEC2F &aPoint) const
Check is a point is inside this bounding box.
Definition: bbox_2d.cpp:223
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: container_2d.h:109
SFVEC2F m_End
Definition: ray.h:113
virtual bool Intersect(const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut) const =0
bool Intersect(const RAY2D &aRay, float *t) const
Definition: bbox_2d.cpp:240
SFVEC2F m_Start
Definition: ray.h:112
virtual bool IsPointInside(const SFVEC2F &aPoint) const =0

References BBOX_2D::Inside(), OBJECT_2D::Intersect(), BBOX_2D::Intersect(), OBJECT_2D::IsPointInside(), BVH_CONTAINER_NODE_2D::m_BBox, BVH_CONTAINER_NODE_2D::m_Children, RAYSEG2D::m_End, BVH_CONTAINER_NODE_2D::m_LeafList, and RAYSEG2D::m_Start.

Referenced by IntersectAny().

Member Data Documentation

◆ m_bbox

◆ m_elementsToDelete

std::list<BVH_CONTAINER_NODE_2D*> BVH_CONTAINER_2D::m_elementsToDelete
private

Definition at line 141 of file container_2d.h.

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

◆ m_isInitialized

bool BVH_CONTAINER_2D::m_isInitialized
private

◆ m_objects

LIST_OBJECT2D CONTAINER_2D_BASE::m_objects
protectedinherited

◆ m_tree

BVH_CONTAINER_NODE_2D* BVH_CONTAINER_2D::m_tree
private

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