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
43BBOX_2D::BBOX_2D( const SFVEC2F& aPbInit )
44{
45 m_min = aPbInit;
46 m_max = aPbInit;
47}
48
49
50BBOX_2D::BBOX_2D( const SFVEC2F& aPbMin, const SFVEC2F& aPbMax )
51{
52 Set( aPbMin, aPbMax );
53}
54
55
57{
58}
59
60
61void 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
71void 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
93void 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
105void 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
131unsigned 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
143{
144 const SFVEC2F extent = GetExtent();
145
146 return 2.0f * ( extent.x + extent.y );
147}
148
149
150void 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
184bool 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
211bool 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
223bool 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
232float 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/
240bool 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
265bool 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
290bool 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}
Defines math related functions.
float NextFloatDown(float v)
Definition: 3d_fastmath.h:157
float NextFloatUp(float v)
Definition: 3d_fastmath.h:136
2D bounding box class definition.
Manage a bounding box defined by two SFVEC2F min max points.
Definition: bbox_2d.h:42
float Perimeter() const
Definition: bbox_2d.cpp:142
SFVEC2F GetCenter() const
Definition: bbox_2d.cpp:119
bool Intersects(const BBOX_2D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_2d.cpp:211
~BBOX_2D()
Definition: bbox_2d.cpp:56
unsigned int MaxDimension() const
Definition: bbox_2d.cpp:131
SFVEC2F m_min
point of the lower position of the bounding box
Definition: bbox_2d.h:197
void ScaleNextDown()
Scale a bounding box to the next float representation making it smaller.
Definition: bbox_2d.cpp:172
SFVEC2F GetExtent() const
Definition: bbox_2d.cpp:125
SFVEC2F m_max
point of the higher position of the bounding box
Definition: bbox_2d.h:198
void Union(const SFVEC2F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_2d.cpp:93
void Scale(float aScale)
Scale a bounding box by its center.
Definition: bbox_2d.cpp:150
bool IsInitialized() const
Check if this bounding box is already initialized.
Definition: bbox_2d.cpp:79
const SFVEC2F & Min() const
Definition: bbox_2d.h:167
float Area() const
Calculate the area of a bounding box.
Definition: bbox_2d.cpp:232
bool Inside(const SFVEC2F &aPoint) const
Check is a point is inside this bounding box.
Definition: bbox_2d.cpp:223
BBOX_2D()
Create with default values a bounding box (not initialized).
Definition: bbox_2d.cpp:37
void Reset()
Reset the bounding box to zero and uninitialize it.
Definition: bbox_2d.cpp:86
const SFVEC2F & Max() const
Definition: bbox_2d.h:172
void Set(const SFVEC2F &aPbMin, const SFVEC2F &aPbMax)
Set bounding box with new parameters.
Definition: bbox_2d.cpp:61
void ScaleNextUp()
Scale a bounding box to the next float representation making it larger.
Definition: bbox_2d.cpp:162
bool Intersect(const RAY2D &aRay, float *t) const
Definition: bbox_2d.cpp:240
Definition: ray.h:94
SFVEC2F m_Origin
Definition: ray.h:95
SFVEC2F m_InvDir
Definition: ray.h:97
Definition: ray.h:106
float m_Length
Definition: ray.h:112
SFVEC2F m_InvDir
Definition: ray.h:111
SFVEC2F m_Start
Definition: ray.h:107
glm::vec2 SFVEC2F
Definition: xv3d_types.h:42