KiCad PCB EDA Suite
cbbox2d.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 "3d_fastmath.h"
31 
32 #include "cbbox2d.h"
33 #include <fctsys.h>
34 #include <wx/debug.h>
35 
36 
38 {
39  Reset();
40 }
41 
42 
43 CBBOX2D::CBBOX2D( const SFVEC2F &aPbInit )
44 {
45  m_min = aPbInit;
46  m_max = aPbInit;
47 }
48 
49 
50 CBBOX2D::CBBOX2D( const SFVEC2F &aPbMin, const SFVEC2F &aPbMax )
51 {
52  Set( aPbMin, aPbMax );
53 }
54 
55 
57 {
58 }
59 
60 
61 void CBBOX2D::Set( const SFVEC2F &aPbMin, const SFVEC2F &aPbMax )
62 {
63  m_min.x = fminf( aPbMin.x, aPbMax.x );
64  m_min.y = fminf( aPbMin.y, aPbMax.y );
65 
66  m_max.x = fmaxf( aPbMin.x, aPbMax.x );
67  m_max.y = fmaxf( aPbMin.y, aPbMax.y );
68 }
69 
70 
71 void CBBOX2D::Set( const CBBOX2D &aBBox )
72 {
73  wxASSERT( aBBox.IsInitialized() );
74 
75  Set( aBBox.Min(), aBBox.Max() );
76 }
77 
78 
80 {
81  return !( ( FLT_MAX == m_min.x) ||
82  ( FLT_MAX == m_min.y) ||
83  (-FLT_MAX == m_max.x) ||
84  (-FLT_MAX == m_max.y) );
85 }
86 
87 
89 {
90  m_min = SFVEC2F( FLT_MAX, FLT_MAX );
91  m_max = SFVEC2F(-FLT_MAX,-FLT_MAX );
92 }
93 
94 
95 void CBBOX2D::Union( const SFVEC2F &aPoint )
96 {
97  // get the minimun value between the added point and the existent bounding box
98  m_min.x = fminf( m_min.x, aPoint.x );
99  m_min.y = fminf( m_min.y, aPoint.y );
100 
101  // get the maximun value between the added point and the existent bounding box
102  m_max.x = fmaxf( m_max.x, aPoint.x );
103  m_max.y = fmaxf( m_max.y, aPoint.y );
104 }
105 
106 
107 void CBBOX2D::Union( const CBBOX2D &aBBox )
108 {
109  // get the minimun value between the added bounding box and
110  // the existent bounding box
111  m_min.x = fminf( m_min.x, aBBox.m_min.x );
112  m_min.y = fminf( m_min.y, aBBox.m_min.y );
113 
114  // get the maximun value between the added bounding box and
115  // the existent bounding box
116  m_max.x = fmaxf( m_max.x, aBBox.m_max.x );
117  m_max.y = fmaxf( m_max.y, aBBox.m_max.y );
118 }
119 
120 
122 {
123  return (m_max + m_min) * 0.5f;
124 }
125 
126 
128 {
129  return m_max - m_min;
130 }
131 
132 
133 unsigned int CBBOX2D::MaxDimension() const
134 {
135  unsigned int result = 0;
136  const SFVEC2F extent = GetExtent();
137 
138  if( extent.y > extent.x ) result = 1;
139 
140  return result;
141 }
142 
143 
144 float CBBOX2D::Perimeter() const
145 {
146  const SFVEC2F extent = GetExtent();
147 
148  return 2.0f * ( extent.x + extent.y );
149 }
150 
151 
152 void CBBOX2D::Scale( float aScale )
153 {
154  wxASSERT( IsInitialized() );
155 
156  const SFVEC2F scaleV( aScale, aScale );
157  const SFVEC2F centerV = GetCenter();
158 
159  m_min = (m_min - centerV) * scaleV + centerV;
160  m_max = (m_max - centerV) * scaleV + centerV;
161 }
162 
163 
165 {
166  m_min.x = NextFloatDown( m_min.x );
167  m_min.y = NextFloatDown( m_min.y );
168 
169  m_max.x = NextFloatUp( m_max.x );
170  m_max.y = NextFloatUp( m_max.y );
171 }
172 
173 
175 {
176  m_min.x = NextFloatUp( m_min.x );
177  m_min.y = NextFloatUp( m_min.y );
178 
179  m_max.x = NextFloatDown( m_max.x );
180  m_max.y = NextFloatDown( m_max.y );
181 }
182 
183 
184 // http://goanna.cs.rmit.edu.au/~gl/teaching/rtr&3dgp/notes/intersection.pdf
185 // http://www.mrtc.mdh.se/projects/3Dgraphics/paperF.pdf
186 bool CBBOX2D::Intersects( const SFVEC2F &aCenter, float aRadiusSquared ) const
187 {
188  float fDistSq = 0.0f;
189 
190  for( unsigned int i = 0; i < 2; i++ )
191  {
192  if( aCenter[i] < m_min[i] )
193  {
194  const float fDist = aCenter[i] - m_min[i];
195 
196  fDistSq += fDist * fDist;
197  }
198  else
199  {
200  if( aCenter[i] > m_max[i] )
201  {
202  const float fDist = aCenter[i] - m_max[i];
203 
204  fDistSq += fDist * fDist;
205  }
206  }
207  }
208 
209  return ( fDistSq <= aRadiusSquared );
210 }
211 
212 
213 bool CBBOX2D::Intersects( const CBBOX2D &aBBox ) const
214 {
215  wxASSERT( IsInitialized() );
216  wxASSERT( aBBox.IsInitialized() );
217 
218  const bool x = ( m_max.x >= aBBox.m_min.x ) && ( m_min.x <= aBBox.m_max.x );
219  const bool y = ( m_max.y >= aBBox.m_min.y ) && ( m_min.y <= aBBox.m_max.y );
220 
221  return ( x && y );
222 }
223 
224 
225 bool CBBOX2D::Inside( const SFVEC2F &aPoint ) const
226 {
227  wxASSERT( IsInitialized() );
228 
229  return ( ( aPoint.x >= m_min.x ) && ( aPoint.x <= m_max.x ) &&
230  ( aPoint.y >= m_min.y ) && ( aPoint.y <= m_max.y ) );
231 }
232 
233 
234 float CBBOX2D::Area() const
235 {
236  SFVEC2F extent = GetExtent();
237  return extent.x * extent.y;
238 }
239 
240 
241 // http://tavianator.com/fast-branchless-raybounding-box-intersections/
242 bool CBBOX2D::Intersect( const RAY2D &aRay, float *t ) const
243 {
244  wxASSERT( t );
245 
246  const float tx1 = (m_min.x - aRay.m_Origin.x) * aRay.m_InvDir.x;
247  const float tx2 = (m_max.x - aRay.m_Origin.x) * aRay.m_InvDir.x;
248 
249  float tmin = glm::min( tx1, tx2 );
250  float tmax = glm::max( tx1, tx2 );
251 
252  const float ty1 = (m_min.y - aRay.m_Origin.y) * aRay.m_InvDir.y;
253  const float ty2 = (m_max.y - aRay.m_Origin.y) * aRay.m_InvDir.y;
254 
255  tmin = glm::max( tmin, glm::min( ty1, ty2 ) );
256  tmax = glm::min( tmax, glm::max( ty1, ty2 ) );
257 
258  if( tmin > 0.0f )
259  *t = tmin;
260  else
261  *t = tmax;
262 
263  return (tmax >= 0.0f) && (tmax >= tmin);
264 }
265 
266 
267 bool CBBOX2D::Intersect( const RAYSEG2D &aRaySeg ) const
268 {
269  const float tx1 = (m_min.x - aRaySeg.m_Start.x) * aRaySeg.m_InvDir.x;
270  const float tx2 = (m_max.x - aRaySeg.m_Start.x) * aRaySeg.m_InvDir.x;
271 
272  float tmin = glm::min( tx1, tx2 );
273  float tmax = glm::max( tx1, tx2 );
274 
275  const float ty1 = (m_min.y - aRaySeg.m_Start.y) * aRaySeg.m_InvDir.y;
276  const float ty2 = (m_max.y - aRaySeg.m_Start.y) * aRaySeg.m_InvDir.y;
277 
278  tmin = glm::max( tmin, glm::min( ty1, ty2 ) );
279  tmax = glm::min( tmax, glm::max( ty1, ty2 ) );
280 
281  if( (tmax >= 0.0f) && (tmax >= tmin) )
282  {
283  const float t = (tmin > 0.0f)?tmin:tmax;
284 
285  return ( t < aRaySeg.m_Length );
286  }
287 
288  return false;
289 }
290 
291 
292 bool CBBOX2D::Intersect( const RAY2D &aRay, float *aOutHitT0, float *aOutHitT1 ) const
293 {
294  wxASSERT( aOutHitT0 );
295  wxASSERT( aOutHitT1 );
296 
297  const float tx1 = (m_min.x - aRay.m_Origin.x) * aRay.m_InvDir.x;
298  const float tx2 = (m_max.x - aRay.m_Origin.x) * aRay.m_InvDir.x;
299 
300  float tmin = glm::min( tx1, tx2 );
301  float tmax = glm::max( tx1, tx2 );
302 
303  const float ty1 = (m_min.y - aRay.m_Origin.y) * aRay.m_InvDir.y;
304  const float ty2 = (m_max.y - aRay.m_Origin.y) * aRay.m_InvDir.y;
305 
306  tmin = glm::max( tmin, glm::min( ty1, ty2 ) );
307  tmax = glm::min( tmax, glm::max( ty1, ty2 ) );
308 
309  *aOutHitT0 = (tmin > 0.0f)?tmin:0.0f;
310  *aOutHitT1 = tmax;
311 
312  return (tmax >= 0.0f) && (tmax >= tmin);
313 }
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
Defines math related functions.
float Perimeter() const
Function Perimeter.
Definition: cbbox2d.cpp:144
CBBOX2D()
Constructor CBBOX2D Create with default values a bounding box (not inizialized)
Definition: cbbox2d.cpp:37
void ScaleNextDown()
Function ScaleNextDown scales a bounding box to the next float representation making it smaller...
Definition: cbbox2d.cpp:174
Class CBBOX manages a bounding box defined by two SFVEC2F min max points.
Definition: cbbox2d.h:40
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
SFVEC2F m_max
point of the higher position of the bounding box
Definition: cbbox2d.h:212
glm::vec2 SFVEC2F
Definition: xv3d_types.h:45
float NextFloatDown(float v)
Definition: 3d_fastmath.h:157
float m_Length
Definition: ray.h:93
void Scale(float aScale)
Function Scale scales a bounding box by its center.
Definition: cbbox2d.cpp:152
void Set(const SFVEC2F &aPbMin, const SFVEC2F &aPbMax)
Function Set Set bounding box with new parameters.
Definition: cbbox2d.cpp:61
float Area() const
Function Area calculate the area of a bounding box.
Definition: cbbox2d.cpp:234
~CBBOX2D()
Definition: cbbox2d.cpp:56
SFVEC2F m_InvDir
Definition: ray.h:92
void ScaleNextUp()
Function ScaleNextUp scales a bounding box to the next float representation making it larger...
Definition: cbbox2d.cpp:164
2D Bounding Box class definition
SFVEC2F GetCenter() const
Function GetCenter return the center point of the bounding box.
Definition: cbbox2d.cpp:121
SFVEC2F m_Start
Definition: ray.h:88
Definition: ray.h:74
#define max(a, b)
Definition: auxiliary.h:86
float NextFloatUp(float v)
Definition: 3d_fastmath.h:136
SFVEC2F m_min
point of the lower position of the bounding box
Definition: cbbox2d.h:211
SFVEC2F m_InvDir
Definition: ray.h:78
unsigned int MaxDimension() const
Function MaxDimension.
Definition: cbbox2d.cpp:133
bool Inside(const SFVEC2F &aPoint) const
Function Inside check is a point is inside this bounding box.
Definition: cbbox2d.cpp:225
const SFVEC2F & Min() const
Function Min return the minimun vertex pointer.
Definition: cbbox2d.h:176
SFVEC2F GetExtent() const
Function GetExtent.
Definition: cbbox2d.cpp:127
SFVEC2F m_Origin
Definition: ray.h:76
const SFVEC2F & Max() const
Function Max return the maximum vertex pointer.
Definition: cbbox2d.h:183
#define min(a, b)
Definition: auxiliary.h:85
bool Intersect(const RAY2D &aRay, float *t) const
Function Intersect.
Definition: cbbox2d.cpp:242
Definition: ray.h:86