KiCad PCB EDA Suite
ccontainer2d.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) 1992-2016 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 
30 #include "ccontainer2d.h"
31 #include <vector>
32 #include <mutex>
33 #include <boost/range/algorithm/partition.hpp>
34 #include <boost/range/algorithm/nth_element.hpp>
35 #include <wx/debug.h>
36 
37 
38 // /////////////////////////////////////////////////////////////////////////////
39 // CGENERICCONTAINER2
40 // /////////////////////////////////////////////////////////////////////////////
41 
43 {
44  m_bbox.Reset();
45 }
46 
47 
49 {
50  std::lock_guard<std::mutex> lock( m_lock );
51  m_bbox.Reset();
52 
53  for( LIST_OBJECT2D::iterator ii = m_objects.begin();
54  ii != m_objects.end();
55  ++ii )
56  {
57  delete *ii;
58  *ii = NULL;
59  }
60 
61  m_objects.clear();
62 }
63 
64 
66 {
67  Clear();
68 }
69 
70 
71 
72 
73 // /////////////////////////////////////////////////////////////////////////////
74 // CCONTAINER2D
75 // /////////////////////////////////////////////////////////////////////////////
76 
78 {
79 
80 }
81 /*
82 
83 bool CCONTAINER2D::Intersects( const CBBOX2D &aBBox ) const
84 {
85  return false;
86 }
87 
88 
89 bool CCONTAINER2D::Overlaps( const CBBOX2D &aBBox ) const
90 {
91  // NOT IMPLEMENTED
92  return false;
93 }
94 
95 
96 bool CCONTAINER2D::Intersect( const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut ) const
97 {
98  if( !m_bbox.Intersect( aSegRay ) )
99  return false;
100 
101  bool hitted = false;
102 
103  for( LIST_OBJECT2D::const_iterator ii = m_objects.begin();
104  ii != m_objects.end();
105  ii++ )
106  {
107  const COBJECT2D *object = static_cast<const COBJECT2D *>(*ii);
108 
109  float t;
110  SFVEC2F hitNormal;
111  if( object->Intersect( aSegRay, &t, &hitNormal ) )
112  if( (hitted == false) || (t < *aOutT ) )
113  {
114  hitted = true;
115  *aOutT = t;
116  *aNormalOut = hitNormal;
117  }
118  }
119 
120  return hitted;
121 }
122 
123 
124 INTERSECTION_RESULT CCONTAINER2D::IsBBoxInside( const CBBOX2D &aBBox ) const
125 {
126  return INTR_MISSES;
127 }
128 
129 
130 bool CCONTAINER2D::IsPointInside( const SFVEC2F &aPoint ) const
131 {
132  if( !m_bbox.Inside( aPoint ) )
133  return false;
134 
135  for( LIST_OBJECT2D::const_iterator ii = m_objects.begin();
136  ii != m_objects.end();
137  ii++ )
138  {
139  const COBJECT2D *object = static_cast<const COBJECT2D *>(*ii);
140 
141  if( object->IsPointInside( aPoint ) )
142  return true;
143  }
144 
145  return false;
146 }
147 
148 */
149 
151  CONST_LIST_OBJECT2D &aOutList ) const
152 {
153  // !TODO:
154 }
155 
156 
157 
158 
159 // /////////////////////////////////////////////////////////////////////////////
160 // CBVHCONTAINER2D
161 // /////////////////////////////////////////////////////////////////////////////
162 
164 {
165  m_isInitialized = false;
166  m_bbox.Reset();
167  m_elements_to_delete.clear();
168  m_Tree = NULL;
169 }
170 
171 /*
172 bool CBVHCONTAINER2D::Intersects( const CBBOX2D &aBBox ) const
173 {
174  // !TODO: implement the BVH
175  return m_bbox.Intersects( aBBox );
176 }
177 
178 
179 bool CBVHCONTAINER2D::Overlaps( const CBBOX2D &aBBox ) const
180 {
181  // NOT IMPLEMENTED
182  return false;
183 }
184 
185 
186 bool CBVHCONTAINER2D::Intersect( const RAYSEG2D &aSegRay,
187  float *aOutT, SFVEC2F *aNormalOut ) const
188 {
189  // !TODO: implement the BVH
190 
191  if( !m_bbox.Intersect( aSegRay ) )
192  return false;
193 
194  bool hitted = false;
195 
196  for( LIST_OBJECT2D::const_iterator ii = m_objects.begin();
197  ii != m_objects.end();
198  ii++ )
199  {
200  const COBJECT2D *object = static_cast<const COBJECT2D *>(*ii);
201 
202  float t;
203  SFVEC2F hitNormal;
204  if( object->Intersect( aSegRay, &t, &hitNormal ) )
205  if( (hitted == false) || (t < *aOutT ) )
206  {
207  hitted = true;
208  *aOutT = t;
209  *aNormalOut = hitNormal;
210  }
211  }
212 
213  return hitted;
214 }
215 
216 
217 INTERSECTION_RESULT CBVHCONTAINER2D::IsBBoxInside( const CBBOX2D &aBBox ) const
218 {
219  return INTR_MISSES;
220 }
221 
222 
223 bool CBVHCONTAINER2D::IsPointInside( const SFVEC2F &aPoint ) const
224 {
225  // !TODO: implement the BVH
226 
227  if( !m_bbox.Inside( aPoint ) )
228  return false;
229 
230  for( LIST_OBJECT2D::const_iterator ii = m_objects.begin();
231  ii != m_objects.end();
232  ii++ )
233  {
234  const COBJECT2D *object = static_cast<const COBJECT2D *>(*ii);
235 
236  if( object->IsPointInside( aPoint ) )
237  return true;
238  }
239 
240  return false;
241 }
242 */
243 
245 {
246  for( std::list<BVH_CONTAINER_NODE_2D *>::iterator ii = m_elements_to_delete.begin();
247  ii != m_elements_to_delete.end();
248  ++ii )
249  {
250  delete *ii;
251  *ii = NULL;
252  }
253  m_elements_to_delete.clear();
254 
255  m_isInitialized = false;
256 }
257 
258 
260 {
261  destroy();
262 }
263 
264 
265 #define BVH_CONTAINER2D_MAX_OBJ_PER_LEAF 4
266 
267 
269 {
270  if( m_isInitialized )
271  destroy();
272 
273  if( m_objects.empty() )
274  {
275  return;
276  }
277 
278  m_isInitialized = true;
280 
281  m_elements_to_delete.push_back( m_Tree );
282  m_Tree->m_BBox = m_bbox;
283 
284  for( LIST_OBJECT2D::const_iterator ii = m_objects.begin();
285  ii != m_objects.end();
286  ++ii )
287  {
288  m_Tree->m_LeafList.push_back( static_cast<const COBJECT2D *>(*ii) );
289  }
290 
292 }
293 
294 
295 // Based on a blog post by VADIM KRAVCENKO
296 // http://www.vadimkravcenko.com/bvh-tree-building
297 // Implements:
298 
299 // "Split in the middle of the longest Axis"
300 // "Creates a binary tree with Top-Down approach.
301 // Fastest BVH building, but least [speed] accuracy."
302 
303 static bool sortByCentroid_X( const COBJECT2D *a, const COBJECT2D *b )
304 {
305  return a->GetCentroid()[0] < b->GetCentroid()[0];
306 }
307 
308 static bool sortByCentroid_Y( const COBJECT2D *a, const COBJECT2D *b )
309 {
310  return a->GetCentroid()[0] < b->GetCentroid()[0];
311 }
312 
313 static bool sortByCentroid_Z( const COBJECT2D *a, const COBJECT2D *b )
314 {
315  return a->GetCentroid()[0] < b->GetCentroid()[0];
316 }
317 
319 {
320  wxASSERT( aNodeParent != NULL );
321  wxASSERT( aNodeParent->m_BBox.IsInitialized() == true );
322  wxASSERT( aNodeParent->m_LeafList.size() > 0 );
323 
324  if( aNodeParent->m_LeafList.size() > BVH_CONTAINER2D_MAX_OBJ_PER_LEAF )
325  {
326  // Create Leaf Nodes
329  m_elements_to_delete.push_back( leftNode );
330  m_elements_to_delete.push_back( rightNode );
331 
332  leftNode->m_BBox.Reset();
333  rightNode->m_BBox.Reset();
334  leftNode->m_LeafList.clear();
335  rightNode->m_LeafList.clear();
336 
337  // Decide wich axis to split
338  const unsigned int axis_to_split = aNodeParent->m_BBox.MaxDimension();
339 
340  // Divide the objects
341  switch( axis_to_split )
342  {
343  case 0: aNodeParent->m_LeafList.sort( sortByCentroid_X ); break;
344  case 1: aNodeParent->m_LeafList.sort( sortByCentroid_Y ); break;
345  case 2: aNodeParent->m_LeafList.sort( sortByCentroid_Z ); break;
346  }
347 
348  unsigned int i = 0;
349 
350  for( CONST_LIST_OBJECT2D::const_iterator ii = aNodeParent->m_LeafList.begin();
351  ii != aNodeParent->m_LeafList.end();
352  ++ii )
353  {
354  const COBJECT2D *object = static_cast<const COBJECT2D *>(*ii);
355 
356  if( i < (aNodeParent->m_LeafList.size() / 2 ) )
357  {
358  leftNode->m_BBox.Union( object->GetBBox() );
359  leftNode->m_LeafList.push_back( object );
360  }
361  else
362  {
363  rightNode->m_BBox.Union( object->GetBBox() );
364  rightNode->m_LeafList.push_back( object );
365  }
366 
367  i++;
368  }
369 
370  wxASSERT( leftNode->m_LeafList.size() > 0 );
371  wxASSERT( rightNode->m_LeafList.size() > 0 );
372  wxASSERT( ( leftNode->m_LeafList.size() + rightNode->m_LeafList.size() ) ==
373  aNodeParent->m_LeafList.size() );
374 
375  aNodeParent->m_Children[0] = leftNode;
376  aNodeParent->m_Children[1] = rightNode;
377  aNodeParent->m_LeafList.clear();
378 
379  recursiveBuild_MIDDLE_SPLIT( leftNode );
380  recursiveBuild_MIDDLE_SPLIT( rightNode );
381  }
382  else
383  {
384  // It is a Leaf
385  aNodeParent->m_Children[0] = NULL;
386  aNodeParent->m_Children[1] = NULL;
387  }
388 }
389 
390 
392  CONST_LIST_OBJECT2D &aOutList ) const
393 {
394  wxASSERT( aBBox.IsInitialized() == true );
395  wxASSERT( m_isInitialized == true );
396 
397  aOutList.clear();
398 
399  if( m_Tree )
400  recursiveGetListObjectsIntersects( m_Tree, aBBox, aOutList );
401 }
402 
403 
405  const CBBOX2D & aBBox,
406  CONST_LIST_OBJECT2D &aOutList ) const
407 {
408  wxASSERT( aNode != NULL );
409  wxASSERT( aBBox.IsInitialized() == true );
410 
411  if( aNode->m_BBox.Intersects( aBBox ) )
412  {
413  if( !aNode->m_LeafList.empty() )
414  {
415  wxASSERT( aNode->m_Children[0] == NULL );
416  wxASSERT( aNode->m_Children[1] == NULL );
417 
418  // Leaf
419  for( CONST_LIST_OBJECT2D::const_iterator ii = aNode->m_LeafList.begin();
420  ii != aNode->m_LeafList.end();
421  ++ii )
422  {
423  const COBJECT2D *obj = static_cast<const COBJECT2D *>(*ii);
424 
425  if( obj->Intersects( aBBox ) )
426  aOutList.push_back( obj );
427  }
428  }
429  else
430  {
431  wxASSERT( aNode->m_Children[0] != NULL );
432  wxASSERT( aNode->m_Children[1] != NULL );
433 
434  // Node
435  recursiveGetListObjectsIntersects( aNode->m_Children[0], aBBox, aOutList );
436  recursiveGetListObjectsIntersects( aNode->m_Children[1], aBBox, aOutList );
437  }
438  }
439 }
void GetListObjectsIntersects(const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const override
GetListObjectsIntersects - Get a list of objects that intersects a bbox.
CONST_LIST_OBJECT2D m_LeafList
Store the list of objects if that node is a Leaf.
Definition: ccontainer2d.h:96
bool IsInitialized() const
Function IsInitialized check if this bounding box is already initialized.
Definition: cbbox2d.cpp:79
void Union(const SFVEC2F &aPoint)
Function Union recalculate the bounding box adding a point.
Definition: cbbox2d.cpp:95
Class CBBOX manages a bounding box defined by two SFVEC2F min max points.
Definition: cbbox2d.h:40
std::list< const COBJECT2D * > CONST_LIST_OBJECT2D
Definition: ccontainer2d.h:38
std::list< BVH_CONTAINER_NODE_2D * > m_elements_to_delete
Definition: ccontainer2d.h:110
BVH_CONTAINER_NODE_2D * m_Children[2]
Definition: ccontainer2d.h:93
bool Intersects(const CBBOX2D &aBBox) const
Function Intersects test if a bounding box intersects this box.
Definition: cbbox2d.cpp:213
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:88
#define BVH_CONTAINER2D_MAX_OBJ_PER_LEAF
void recursiveBuild_MIDDLE_SPLIT(BVH_CONTAINER_NODE_2D *aNodeParent)
static bool sortByCentroid_Y(const COBJECT2D *a, const COBJECT2D *b)
static bool sortByCentroid_X(const COBJECT2D *a, const COBJECT2D *b)
virtual ~CGENERICCONTAINER2D()
const SFVEC2F & GetCentroid() const
Definition: cobject2d.h:123
static bool sortByCentroid_Z(const COBJECT2D *a, const COBJECT2D *b)
CGENERICCONTAINER2D(OBJECT2D_TYPE aObjType)
LIST_OBJECT2D m_objects
Definition: ccontainer2d.h:45
OBJECT2D_TYPE
Definition: cobject2d.h:46
size_t i
Definition: json11.cpp:597
const CBBOX2D & GetBBox() const
Definition: cobject2d.h:121
unsigned int MaxDimension() const
Function MaxDimension.
Definition: cbbox2d.cpp:133
BVH_CONTAINER_NODE_2D * m_Tree
Definition: ccontainer2d.h:111
void recursiveGetListObjectsIntersects(const BVH_CONTAINER_NODE_2D *aNode, const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const
virtual bool Intersects(const CBBOX2D &aBBox) const =0
Function Intersects.
void GetListObjectsIntersects(const CBBOX2D &aBBox, CONST_LIST_OBJECT2D &aOutList) const override
GetListObjectsIntersects - Get a list of objects that intersects a bbox.