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