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
 
std::mutex m_lock
 

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}
BVH_CONTAINER_NODE_2D * m_tree
Definition: container_2d.h:142
std::list< BVH_CONTAINER_NODE_2D * > m_elementsToDelete
Definition: container_2d.h:141
CONTAINER_2D_BASE(OBJECT_2D_TYPE aObjType)
void Reset()
Reset the bounding box to zero and uninitialize it.
Definition: bbox_2d.cpp:86

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()

void CONTAINER_2D_BASE::Add ( OBJECT_2D aObject)
inlineinherited

◆ 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 );
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}
void recursiveBuild_MIDDLE_SPLIT(BVH_CONTAINER_NODE_2D *aNodeParent)
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: container_2d.h:112

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}

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}
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

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}
#define BVH_CONTAINER2D_MAX_OBJ_PER_LEAF
static bool sortByCentroidX(const OBJECT_2D *a, const OBJECT_2D *b)
static bool sortByCentroidY(const OBJECT_2D *a, const OBJECT_2D *b)
static bool sortByCentroidZ(const OBJECT_2D *a, const OBJECT_2D *b)
unsigned int MaxDimension() const
Definition: bbox_2d.cpp:131
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: container_2d.h:109

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(), recursiveBuild_MIDDLE_SPLIT(), BBOX_2D::Reset(), sortByCentroidX(), sortByCentroidY(), sortByCentroidZ(), and BBOX_2D::Union().

Referenced by BuildBVH(), and recursiveBuild_MIDDLE_SPLIT().

◆ 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}
virtual bool Intersects(const BBOX_2D &aBBox) const =0
a.Intersects(b) ⇔ !a.Disjoint(b) ⇔ !(a ∩ b = ∅)
bool Intersects(const BBOX_2D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_2d.cpp:211

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

Referenced by GetIntersectingObjects(), and recursiveGetListObjectsIntersects().

◆ 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}
virtual bool Intersect(const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut) const =0
virtual bool IsPointInside(const SFVEC2F &aPoint) const =0
bool Inside(const SFVEC2F &aPoint) const
Check is a point is inside this bounding box.
Definition: bbox_2d.cpp:223
bool Intersect(const RAY2D &aRay, float *t) const
Definition: bbox_2d.cpp:240
SFVEC2F m_Start
Definition: ray.h:107
SFVEC2F m_End
Definition: ray.h:108

References BBOX_2D::Inside(), BBOX_2D::Intersect(), OBJECT_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, RAYSEG2D::m_Start, and recursiveIntersectAny().

Referenced by IntersectAny(), and recursiveIntersectAny().

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_lock

std::mutex CONTAINER_2D_BASE::m_lock
privateinherited

Definition at line 90 of file container_2d.h.

Referenced by CONTAINER_2D_BASE::Add(), and CONTAINER_2D_BASE::Clear().

◆ 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: