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