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 <mrluzeiro@ua.pt>
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 
75 bool 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 );
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 }
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."
155 static bool sortByCentroidX( const OBJECT_2D* a, const OBJECT_2D* b )
156 {
157  return a->GetCentroid()[0] < b->GetCentroid()[0];
158 }
159 
160 
161 static bool sortByCentroidY( const OBJECT_2D* a, const OBJECT_2D* b )
162 {
163  return a->GetCentroid()[0] < b->GetCentroid()[0];
164 }
165 
166 
167 static 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 
251 bool 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 }
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: container_2d.h:112
std::list< const OBJECT_2D * > CONST_LIST_OBJECT2D
Definition: container_2d.h:39
bool IntersectAny(const RAYSEG2D &aSegRay) const override
Intersect and check if a segment ray hits a object or is inside it.
LIST_OBJECT2D m_objects
Definition: container_2d.h:87
bool IntersectAny(const RAYSEG2D &aSegRay) const override
Intersect and check if a segment ray hits a object or is inside it.
void recursiveBuild_MIDDLE_SPLIT(BVH_CONTAINER_NODE_2D *aNodeParent)
const SFVEC2F & GetCentroid() const
Definition: object_2d.h:105
CONTAINER_2D_BASE(OBJECT_2D_TYPE aObjType)
std::list< BVH_CONTAINER_NODE_2D * > m_elementsToDelete
Definition: container_2d.h:141
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
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
SFVEC2F m_End
Definition: ray.h:113
virtual bool Intersect(const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut) const =0
static bool sortByCentroidX(const OBJECT_2D *a, const OBJECT_2D *b)
Manage a bounding box defined by two SFVEC2F min max points.
Definition: bbox_2d.h:41
std::mutex m_lock
Definition: container_2d.h:90
BVH_CONTAINER_NODE_2D * m_tree
Definition: container_2d.h:142
bool Intersect(const RAY2D &aRay, float *t) const
Definition: bbox_2d.cpp:240
void GetIntersectingObjects(const BBOX_2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const override
Get a list of objects that intersects a bounding box.
void Union(const SFVEC2F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_2d.cpp:93
SFVEC2F m_Start
Definition: ray.h:112
static bool sortByCentroidZ(const OBJECT_2D *a, const OBJECT_2D *b)
void GetIntersectingObjects(const BBOX_2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const override
Get a list of objects that intersects a bounding box.
static bool sortByCentroidY(const OBJECT_2D *a, const OBJECT_2D *b)
unsigned int MaxDimension() const
Definition: bbox_2d.cpp:131
OBJECT_2D_TYPE
Definition: object_2d.h:44
bool Intersects(const BBOX_2D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_2d.cpp:211
virtual ~CONTAINER_2D_BASE()
void recursiveGetListObjectsIntersects(const BVH_CONTAINER_NODE_2D *aNode, const BBOX_2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const
virtual bool IsPointInside(const SFVEC2F &aPoint) const =0
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
void Clear() override
virtual void Clear()
Definition: ray.h:110