KiCad PCB EDA Suite
container_2d.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2015-2016 Mario Luzeiro <[email protected]>
5 * Copyright (C) 2015-2020 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, you may find one here:
19 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20 * or you may search the http://www.gnu.org website for the version 2 license,
21 * or you may write to the Free Software Foundation, Inc.,
22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23 */
24
29#include "container_2d.h"
30#include "../ray.h"
31#include <boost/range/algorithm/partition.hpp>
32#include <boost/range/algorithm/nth_element.hpp>
33#include <wx/debug.h>
34
35
37{
38 m_bbox.Reset();
39}
40
41
43{
44 std::lock_guard<std::mutex> lock( m_lock );
45 m_bbox.Reset();
46
47 for( LIST_OBJECT2D::iterator ii = m_objects.begin(); ii != m_objects.end(); ++ii )
48 {
49 delete *ii;
50 }
51
52 m_objects.clear();
53}
54
55
57{
58 Clear();
59}
60
61
63{
64
65}
66
67
69 CONST_LIST_OBJECT2D& aOutList ) const
70{
72}
73
74
75bool CONTAINER_2D::IntersectAny( const RAYSEG2D& aSegRay ) const
76{
78 return false;
79}
80
81
83{
84 m_isInitialized = false;
85 m_bbox.Reset();
86 m_elementsToDelete.clear();
87 m_tree = nullptr;
88}
89
90
92{
94 destroy();
95}
96
97
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}
111
112
114{
115 destroy();
116}
117
118
119#define BVH_CONTAINER2D_MAX_OBJ_PER_LEAF 4
120
121
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}
146
147
148// Based on a blog post by VADIM KRAVCENKO
149// http://www.vadimkravcenko.com/bvh-tree-building
150// Implements:
151
152// "Split in the middle of the longest Axis"
153// "Creates a binary tree with Top-Down approach.
154// Fastest BVH building, but least [speed] accuracy."
155static bool sortByCentroidX( const OBJECT_2D* a, const OBJECT_2D* b )
156{
157 return a->GetCentroid()[0] < b->GetCentroid()[0];
158}
159
160
161static bool sortByCentroidY( const OBJECT_2D* a, const OBJECT_2D* b )
162{
163 return a->GetCentroid()[0] < b->GetCentroid()[0];
164}
165
166
167static bool sortByCentroidZ( const OBJECT_2D* a, const OBJECT_2D* b )
168{
169 return a->GetCentroid()[0] < b->GetCentroid()[0];
170}
171
172
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}
249
250
251bool BVH_CONTAINER_2D::IntersectAny( const RAYSEG2D& aSegRay ) const
252{
253 wxASSERT( m_isInitialized == true );
254
255 if( m_tree )
256 return recursiveIntersectAny( m_tree, aSegRay );
257
258 return false;
259}
260
261
263 const RAYSEG2D& aSegRay ) const
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}
300
301
303 CONST_LIST_OBJECT2D& aOutList ) const
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}
313
314
316 const BBOX_2D& aBBox,
317 CONST_LIST_OBJECT2D& aOutList ) const
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}
void GetIntersectingObjects(const BBOX_2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const override
Get a list of objects that intersects a bounding box.
void Clear() override
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
void recursiveBuild_MIDDLE_SPLIT(BVH_CONTAINER_NODE_2D *aNodeParent)
bool recursiveIntersectAny(const BVH_CONTAINER_NODE_2D *aNode, const RAYSEG2D &aSegRay) const
bool IntersectAny(const RAYSEG2D &aSegRay) const override
Intersect and check if a segment ray hits a object or is inside it.
std::list< BVH_CONTAINER_NODE_2D * > m_elementsToDelete
Definition: container_2d.h:141
CONTAINER_2D_BASE(OBJECT_2D_TYPE aObjType)
virtual void Clear()
virtual ~CONTAINER_2D_BASE()
std::mutex m_lock
Definition: container_2d.h:90
LIST_OBJECT2D m_objects
Definition: container_2d.h:87
void GetIntersectingObjects(const BBOX_2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const override
Get a list of objects that intersects a bounding box.
bool IntersectAny(const RAYSEG2D &aSegRay) const override
Intersect and check if a segment ray hits a object or is inside it.
virtual bool Intersects(const BBOX_2D &aBBox) const =0
a.Intersects(b) ⇔ !a.Disjoint(b) ⇔ !(a ∩ b = ∅)
const SFVEC2F & GetCentroid() const
Definition: object_2d.h:105
const BBOX_2D & GetBBox() const
Definition: object_2d.h:103
virtual bool Intersect(const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut) const =0
virtual bool IsPointInside(const SFVEC2F &aPoint) const =0
#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)
std::list< const OBJECT_2D * > CONST_LIST_OBJECT2D
Definition: container_2d.h:39
OBJECT_2D_TYPE
Definition: object_2d.h:45
Manage a bounding box defined by two SFVEC2F min max points.
Definition: bbox_2d.h:42
bool Intersects(const BBOX_2D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_2d.cpp:211
unsigned int MaxDimension() const
Definition: bbox_2d.cpp:131
void Union(const SFVEC2F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_2d.cpp:93
bool IsInitialized() const
Check if this bounding box is already initialized.
Definition: bbox_2d.cpp:79
bool Inside(const SFVEC2F &aPoint) const
Check is a point is inside this bounding box.
Definition: bbox_2d.cpp:223
void Reset()
Reset the bounding box to zero and uninitialize it.
Definition: bbox_2d.cpp:86
bool Intersect(const RAY2D &aRay, float *t) const
Definition: bbox_2d.cpp:240
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
Definition: ray.h:106
SFVEC2F m_Start
Definition: ray.h:107
SFVEC2F m_End
Definition: ray.h:108