KiCad PCB EDA Suite
bbox_3d.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-2017 Mario Luzeiro <[email protected]>
5 * Copyright (C) 1992-2021 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
29#include "3d_fastmath.h"
30
31#include "bbox_3d.h"
32#include "../ray.h"
33#include <wx/log.h>
34#include <wx/debug.h> // For the wxASSERT
35
36
38{
39 Reset();
40}
41
42
43BBOX_3D::BBOX_3D( const SFVEC3F& aPbInit )
44{
45 m_min = aPbInit;
46 m_max = aPbInit;
47}
48
49
50BBOX_3D::BBOX_3D( const SFVEC3F& aPbMin, const SFVEC3F& aPbMax )
51{
52 Set( aPbMin, aPbMax );
53}
54
55
57{
58}
59
60
61void BBOX_3D::Set( const SFVEC3F& aPoint )
62{
63 m_min = aPoint;
64 m_max = aPoint;
65}
66
67
68void BBOX_3D::Set( const SFVEC3F& aPbMin, const SFVEC3F& aPbMax )
69{
70 m_min.x = fminf( aPbMin.x, aPbMax.x );
71 m_min.y = fminf( aPbMin.y, aPbMax.y );
72 m_min.z = fminf( aPbMin.z, aPbMax.z );
73
74 m_max.x = fmaxf( aPbMin.x, aPbMax.x );
75 m_max.y = fmaxf( aPbMin.y, aPbMax.y );
76 m_max.z = fmaxf( aPbMin.z, aPbMax.z );
77}
78
79
80void BBOX_3D::Set( const BBOX_3D& aBBox )
81{
82 wxASSERT( aBBox.IsInitialized() );
83
84 Set( aBBox.Min(), aBBox.Max() );
85}
86
87
89{
90 return !( ( FLT_MAX == m_min.x ) || ( FLT_MAX == m_min.y ) || ( FLT_MAX == m_min.z )
91 || ( -FLT_MAX == m_max.x ) || ( -FLT_MAX == m_max.y ) || ( -FLT_MAX == m_max.z ) );
92}
93
94
96{
97 m_min = SFVEC3F( FLT_MAX, FLT_MAX, FLT_MAX );
98 m_max = SFVEC3F( -FLT_MAX, -FLT_MAX, -FLT_MAX );
99}
100
101
102void BBOX_3D::Union( const SFVEC3F& aPoint )
103{
104 // get the minimum value between the added point and the existent bounding box
105 m_min.x = fminf( m_min.x, aPoint.x );
106 m_min.y = fminf( m_min.y, aPoint.y );
107 m_min.z = fminf( m_min.z, aPoint.z );
108
109 // get the maximum value between the added point and the existent bounding box
110 m_max.x = fmaxf( m_max.x, aPoint.x );
111 m_max.y = fmaxf( m_max.y, aPoint.y );
112 m_max.z = fmaxf( m_max.z, aPoint.z );
113}
114
115
116void BBOX_3D::Union( const BBOX_3D& aBBox )
117{
118 wxASSERT( aBBox.IsInitialized() );
119
120 // get the minimum value between the added bounding box and the existent bounding box
121 m_min.x = fmin( m_min.x, aBBox.m_min.x );
122 m_min.y = fmin( m_min.y, aBBox.m_min.y );
123 m_min.z = fmin( m_min.z, aBBox.m_min.z );
124
125 // get the maximum value between the added bounding box and the existent bounding box
126 m_max.x = fmax( m_max.x, aBBox.m_max.x );
127 m_max.y = fmax( m_max.y, aBBox.m_max.y );
128 m_max.z = fmax( m_max.z, aBBox.m_max.z );
129}
130
131
133{
134 return ( m_max + m_min ) * 0.5f;
135}
136
137
138float BBOX_3D::GetCenter( unsigned int aAxis ) const
139{
140 wxASSERT( aAxis < 3 );
141 return ( m_max[aAxis] + m_min[aAxis] ) * 0.5f;
142}
143
144
146{
147 return m_max - m_min;
148}
149
150
151unsigned int BBOX_3D::MaxDimension() const
152{
153 unsigned int result = 0;
154
155 SFVEC3F extent = GetExtent();
156
157 if( extent.y > extent.x )
158 result = 1;
159
160 if( extent.z > extent.y )
161 result = 2;
162
163 return result;
164}
165
166
168{
169 SFVEC3F extent = GetExtent();
170 return std::max( std::max( extent.x, extent.y ), extent.z );
171}
172
173
175{
176 SFVEC3F extent = GetExtent();
177
178 return 2.0f * ( extent.x * extent.z + extent.x * extent.y + extent.y * extent.z );
179}
180
181
182void BBOX_3D::Scale( float aScale )
183{
184 wxASSERT( IsInitialized() );
185
186 SFVEC3F scaleV = SFVEC3F( aScale, aScale, aScale );
187 SFVEC3F centerV = GetCenter();
188
189 m_min = ( m_min - centerV ) * scaleV + centerV;
190 m_max = ( m_max - centerV ) * scaleV + centerV;
191}
192
193
195{
196 m_min.x = NextFloatDown( m_min.x );
197 m_min.y = NextFloatDown( m_min.y );
198 m_min.z = NextFloatDown( m_min.z );
199
200 m_max.x = NextFloatUp( m_max.x );
201 m_max.y = NextFloatUp( m_max.y );
202 m_max.z = NextFloatUp( m_max.z );
203}
204
205
207{
208 m_min.x = NextFloatUp( m_min.x );
209 m_min.y = NextFloatUp( m_min.y );
210 m_min.z = NextFloatUp( m_min.z );
211
212 m_max.x = NextFloatDown( m_max.x );
213 m_max.y = NextFloatDown( m_max.y );
214 m_max.z = NextFloatDown( m_max.z );
215}
216
217
218bool BBOX_3D::Intersects( const BBOX_3D& aBBox ) const
219{
220 wxASSERT( IsInitialized() );
221 wxASSERT( aBBox.IsInitialized() );
222
223 bool x = ( m_max.x >= aBBox.m_min.x ) && ( m_min.x <= aBBox.m_max.x );
224 bool y = ( m_max.y >= aBBox.m_min.y ) && ( m_min.y <= aBBox.m_max.y );
225 bool z = ( m_max.z >= aBBox.m_min.z ) && ( m_min.z <= aBBox.m_max.z );
226
227 return ( x && y && z );
228}
229
230
231bool BBOX_3D::Inside( const SFVEC3F& aPoint ) const
232{
233 wxASSERT( IsInitialized() );
234
235 return ( aPoint.x >= m_min.x ) && ( aPoint.x <= m_max.x ) &&
236 ( aPoint.y >= m_min.y ) && ( aPoint.y <= m_max.y ) &&
237 ( aPoint.z >= m_min.z ) && ( aPoint.z <= m_max.z );
238}
239
240
241float BBOX_3D::Volume() const
242{
243 wxASSERT( IsInitialized() );
244
245 SFVEC3F extent = GetExtent();
246
247 return extent.x * extent.y * extent.z;
248}
249
250
252{
253 return (p - m_min) / (m_max - m_min);
254}
255
256
257// https://github.com/mmp/pbrt-v2/blob/master/src/accelerators/bvh.cpp#L126
258bool BBOX_3D::Intersect( const RAY& aRay, float* aOutHitt0, float* aOutHitt1 ) const
259{
260 wxASSERT( aOutHitt0 );
261 wxASSERT( aOutHitt1 );
262
263 const SFVEC3F bounds[2] = {m_min, m_max};
264
265 // Check for ray intersection against x and y slabs
266 float tmin = ( bounds[aRay.m_dirIsNeg[0]].x - aRay.m_Origin.x ) * aRay.m_InvDir.x;
267 float tmax = ( bounds[1 - aRay.m_dirIsNeg[0]].x - aRay.m_Origin.x ) * aRay.m_InvDir.x;
268 const float tymin = ( bounds[aRay.m_dirIsNeg[1]].y - aRay.m_Origin.y ) * aRay.m_InvDir.y;
269 const float tymax = ( bounds[1 - aRay.m_dirIsNeg[1]].y - aRay.m_Origin.y ) * aRay.m_InvDir.y;
270
271 if( ( tmin > tymax ) || ( tymin > tmax ) )
272 return false;
273
274 tmin = ( tymin > tmin ) ? tymin : tmin;
275 tmax = ( tymax < tmax ) ? tymax : tmax;
276
277 // Check for ray intersection against z slab
278 const float tzmin = ( bounds[aRay.m_dirIsNeg[2]].z - aRay.m_Origin.z ) * aRay.m_InvDir.z;
279 const float tzmax = ( bounds[1 - aRay.m_dirIsNeg[2]].z - aRay.m_Origin.z ) * aRay.m_InvDir.z;
280
281 if( ( tmin > tzmax ) || ( tzmin > tmax ) )
282 return false;
283
284 tmin = (tzmin > tmin)? tzmin : tmin;
285 tmin = ( tmin < 0.0f)? 0.0f : tmin;
286
287 tmax = (tzmax < tmax)? tzmax : tmax;
288
289 *aOutHitt0 = tmin;
290 *aOutHitt1 = tmax;
291
292 return true;
293}
294
295
296void BBOX_3D::ApplyTransformation( glm::mat4 aTransformMatrix )
297{
298 wxASSERT( IsInitialized() );
299
300 const SFVEC3F v1 = SFVEC3F( aTransformMatrix * glm::vec4( m_min.x, m_min.y, m_min.z, 1.0f ) );
301
302 const SFVEC3F v2 = SFVEC3F( aTransformMatrix * glm::vec4( m_max.x, m_max.y, m_max.z, 1.0f ) );
303
304 Reset();
305 Union( v1 );
306 Union( v2 );
307}
308
309
Defines math related functions.
float NextFloatDown(float v)
Definition: 3d_fastmath.h:157
float NextFloatUp(float v)
Definition: 3d_fastmath.h:136
Bounding Box class definition.
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:42
void ScaleNextUp()
Scale a bounding box to the next float representation making it larger.
Definition: bbox_3d.cpp:194
BBOX_3D()
Create with default values a bounding box (not initialized)
Definition: bbox_3d.cpp:37
const SFVEC3F GetExtent() const
Definition: bbox_3d.cpp:145
bool Intersect(const RAY &aRay, float *t) const
Definition: bbox_3d_ray.cpp:46
void Union(const SFVEC3F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_3d.cpp:102
SFVEC3F m_min
(12) point of the lower position of the bounding box
Definition: bbox_3d.h:228
SFVEC3F GetCenter() const
Return the center point of the bounding box.
Definition: bbox_3d.cpp:132
const SFVEC3F & Min() const
Return the minimum vertex pointer.
Definition: bbox_3d.h:183
SFVEC3F Offset(const SFVEC3F &p) const
Definition: bbox_3d.cpp:251
SFVEC3F m_max
(12) point of the higher position of the bounding box
Definition: bbox_3d.h:229
const SFVEC3F & Max() const
Return the maximum vertex pointer.
Definition: bbox_3d.h:190
void Set(const SFVEC3F &aPbMin, const SFVEC3F &aPbMax)
Set bounding box with new parameters.
Definition: bbox_3d.cpp:68
void Reset()
Reset the bounding box to zero and de-initialize it.
Definition: bbox_3d.cpp:95
void ApplyTransformation(glm::mat4 aTransformMatrix)
Apply a transformation matrix to the box points.
Definition: bbox_3d.cpp:296
unsigned int MaxDimension() const
Definition: bbox_3d.cpp:151
bool Intersects(const BBOX_3D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_3d.cpp:218
float SurfaceArea() const
Definition: bbox_3d.cpp:174
float Volume() const
Calculate the volume of a bounding box.
Definition: bbox_3d.cpp:241
float GetMaxDimension() const
Definition: bbox_3d.cpp:167
void ScaleNextDown()
Scale a bounding box to the next float representation making it smaller.
Definition: bbox_3d.cpp:206
~BBOX_3D()
Definition: bbox_3d.cpp:56
bool IsInitialized() const
Check if this bounding box is already initialized.
Definition: bbox_3d.cpp:88
bool Inside(const SFVEC3F &aPoint) const
Check if a point is inside this bounding box.
Definition: bbox_3d.cpp:231
void Scale(float aScale)
Scales a bounding box by its center.
Definition: bbox_3d.cpp:182
Definition: ray.h:63
unsigned int m_dirIsNeg[3]
Definition: ray.h:75
SFVEC3F m_InvDir
Definition: ray.h:70
SFVEC3F m_Origin
Definition: ray.h:64
VECTOR2I v2(1, 0)
Test suite for KiCad math code.
v1
glm::vec3 SFVEC3F
Definition: xv3d_types.h:44