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 <mrluzeiro@ua.pt>
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 
43 BBOX_3D::BBOX_3D( const SFVEC3F& aPbInit )
44 {
45  m_min = aPbInit;
46  m_max = aPbInit;
47 }
48 
49 
50 BBOX_3D::BBOX_3D( const SFVEC3F& aPbMin, const SFVEC3F& aPbMax )
51 {
52  Set( aPbMin, aPbMax );
53 }
54 
55 
57 {
58 }
59 
60 
61 void BBOX_3D::Set( const SFVEC3F& aPoint )
62 {
63  m_min = aPoint;
64  m_max = aPoint;
65 }
66 
67 
68 void 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 
80 void 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 
102 void 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 
116 void 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 
138 float 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 
151 unsigned 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  unsigned int max_dimensions_idx = 0;
170 
171  SFVEC3F extent = GetExtent();
172 
173  if( extent.y > extent.x )
174  max_dimensions_idx = 1;
175 
176  if( extent.z > extent.y )
177  max_dimensions_idx = 2;
178 
179  return extent[max_dimensions_idx];
180 }
181 
182 
183 float BBOX_3D::SurfaceArea() const
184 {
185  SFVEC3F extent = GetExtent();
186 
187  return 2.0f * ( extent.x * extent.z + extent.x * extent.y + extent.y * extent.z );
188 }
189 
190 
191 void BBOX_3D::Scale( float aScale )
192 {
193  wxASSERT( IsInitialized() );
194 
195  SFVEC3F scaleV = SFVEC3F( aScale, aScale, aScale );
196  SFVEC3F centerV = GetCenter();
197 
198  m_min = ( m_min - centerV ) * scaleV + centerV;
199  m_max = ( m_max - centerV ) * scaleV + centerV;
200 }
201 
202 
204 {
205  m_min.x = NextFloatDown( m_min.x );
206  m_min.y = NextFloatDown( m_min.y );
207  m_min.z = NextFloatDown( m_min.z );
208 
209  m_max.x = NextFloatUp( m_max.x );
210  m_max.y = NextFloatUp( m_max.y );
211  m_max.z = NextFloatUp( m_max.z );
212 }
213 
214 
216 {
217  m_min.x = NextFloatUp( m_min.x );
218  m_min.y = NextFloatUp( m_min.y );
219  m_min.z = NextFloatUp( m_min.z );
220 
221  m_max.x = NextFloatDown( m_max.x );
222  m_max.y = NextFloatDown( m_max.y );
223  m_max.z = NextFloatDown( m_max.z );
224 }
225 
226 
227 bool BBOX_3D::Intersects( const BBOX_3D& aBBox ) const
228 {
229  wxASSERT( IsInitialized() );
230  wxASSERT( aBBox.IsInitialized() );
231 
232  bool x = ( m_max.x >= aBBox.m_min.x ) && ( m_min.x <= aBBox.m_max.x );
233  bool y = ( m_max.y >= aBBox.m_min.y ) && ( m_min.y <= aBBox.m_max.y );
234  bool z = ( m_max.z >= aBBox.m_min.z ) && ( m_min.z <= aBBox.m_max.z );
235 
236  return ( x && y && z );
237 }
238 
239 
240 bool BBOX_3D::Inside( const SFVEC3F& aPoint ) const
241 {
242  wxASSERT( IsInitialized() );
243 
244  return ( aPoint.x >= m_min.x ) && ( aPoint.x <= m_max.x ) &&
245  ( aPoint.y >= m_min.y ) && ( aPoint.y <= m_max.y ) &&
246  ( aPoint.z >= m_min.z ) && ( aPoint.z <= m_max.z );
247 }
248 
249 
250 float BBOX_3D::Volume() const
251 {
252  wxASSERT( IsInitialized() );
253 
254  SFVEC3F extent = GetExtent();
255 
256  return extent.x * extent.y * extent.z;
257 }
258 
259 
260 SFVEC3F BBOX_3D::Offset( const SFVEC3F& p ) const
261 {
262  return (p - m_min) / (m_max - m_min);
263 }
264 
265 
267 // Intersection code based on the book:
268 // "Physical Based Ray Tracing" (by Matt Pharr and Greg Humphrey)
269 // https://github.com/mmp/pbrt-v2/blob/master/src/core/geometry.cpp#L68
270 #if 0
271 bool BBOX_3D::Intersect( const RAY& aRay, float* aOutHitt0, float* aOutHitt1 ) const
272 {
273  float t0 = 0.0f;
274  float t1 = FLT_MAX;
275 
276  for( unsigned int i = 0; i < 3; ++i )
277  {
278  // Update interval for _i_th bounding box slab
279  float tNear = ( m_min[i] - aRay.m_Origin[i] ) * aRay.m_InvDir[i];
280  float tFar = ( m_max[i] - aRay.m_Origin[i] ) * aRay.m_InvDir[i];
281 
282  // Update parametric interval from slab intersection
283  if( tNear > tFar )
284  {
285  // Swap
286  float ftemp = tNear;
287  tNear = tFar;
288  tFar = ftemp;
289  }
290 
291  t0 = tNear > t0 ? tNear : t0;
292  t1 = tFar < t1 ? tFar : t1;
293 
294  if( t0 > t1 )
295  return false;
296  }
297 
298  if( aOutHitt0 )
299  *aOutHitt0 = t0;
300 
301  if( aOutHitt1 )
302  *aOutHitt1 = t1;
303 
304  return true;
305 }
306 #else
307 // https://github.com/mmp/pbrt-v2/blob/master/src/accelerators/bvh.cpp#L126
308 bool BBOX_3D::Intersect( const RAY& aRay, float* aOutHitt0, float* aOutHitt1 ) const
309 {
310  wxASSERT( aOutHitt0 );
311  wxASSERT( aOutHitt1 );
312 
313  const SFVEC3F bounds[2] = {m_min, m_max};
314 
315  // Check for ray intersection against x and y slabs
316  float tmin = ( bounds[aRay.m_dirIsNeg[0]].x - aRay.m_Origin.x ) * aRay.m_InvDir.x;
317  float tmax = ( bounds[1 - aRay.m_dirIsNeg[0]].x - aRay.m_Origin.x ) * aRay.m_InvDir.x;
318  const float tymin = ( bounds[aRay.m_dirIsNeg[1]].y - aRay.m_Origin.y ) * aRay.m_InvDir.y;
319  const float tymax = ( bounds[1 - aRay.m_dirIsNeg[1]].y - aRay.m_Origin.y ) * aRay.m_InvDir.y;
320 
321  if( ( tmin > tymax ) || ( tymin > tmax ) )
322  return false;
323 
324  tmin = ( tymin > tmin ) ? tymin : tmin;
325  tmax = ( tymax < tmax ) ? tymax : tmax;
326 
327  // Check for ray intersection against z slab
328  const float tzmin = ( bounds[aRay.m_dirIsNeg[2]].z - aRay.m_Origin.z ) * aRay.m_InvDir.z;
329  const float tzmax = ( bounds[1 - aRay.m_dirIsNeg[2]].z - aRay.m_Origin.z ) * aRay.m_InvDir.z;
330 
331  if( ( tmin > tzmax ) || ( tzmin > tmax ) )
332  return false;
333 
334  tmin = (tzmin > tmin)? tzmin : tmin;
335  tmin = ( tmin < 0.0f)? 0.0f : tmin;
336 
337  tmax = (tzmax < tmax)? tzmax : tmax;
338 
339  *aOutHitt0 = tmin;
340  *aOutHitt1 = tmax;
341 
342  return true;
343 }
344 #endif
345 
346 
347 void BBOX_3D::ApplyTransformation( glm::mat4 aTransformMatrix )
348 {
349  wxASSERT( IsInitialized() );
350 
351  const SFVEC3F v1 = SFVEC3F( aTransformMatrix * glm::vec4( m_min.x, m_min.y, m_min.z, 1.0f ) );
352 
353  const SFVEC3F v2 = SFVEC3F( aTransformMatrix * glm::vec4( m_max.x, m_max.y, m_max.z, 1.0f ) );
354 
355  Reset();
356  Union( v1 );
357  Union( v2 );
358 }
359 
360 
361 void BBOX_3D::ApplyTransformationAA( glm::mat4 aTransformMatrix )
362 {
363  wxASSERT( IsInitialized() );
364 
365  // apply the transformation matrix for each of vertices of the bounding box
366  // and make a union with all vertices
367  BBOX_3D tmpBBox = BBOX_3D(
368  SFVEC3F( aTransformMatrix * glm::vec4( m_min.x, m_min.y, m_min.z, 1.0f ) ) );
369  tmpBBox.Union( SFVEC3F( aTransformMatrix * glm::vec4( m_max.x, m_min.y, m_min.z, 1.0f ) ) );
370  tmpBBox.Union( SFVEC3F( aTransformMatrix * glm::vec4( m_min.x, m_max.y, m_min.z, 1.0f ) ) );
371  tmpBBox.Union( SFVEC3F( aTransformMatrix * glm::vec4( m_min.x, m_min.y, m_max.z, 1.0f ) ) );
372  tmpBBox.Union( SFVEC3F( aTransformMatrix * glm::vec4( m_min.x, m_max.y, m_max.z, 1.0f ) ) );
373  tmpBBox.Union( SFVEC3F( aTransformMatrix * glm::vec4( m_max.x, m_max.y, m_min.z, 1.0f ) ) );
374  tmpBBox.Union( SFVEC3F( aTransformMatrix * glm::vec4( m_max.x, m_min.y, m_max.z, 1.0f ) ) );
375  tmpBBox.Union( SFVEC3F( aTransformMatrix * glm::vec4( m_max.x, m_max.y, m_max.z, 1.0f ) ) );
376 
377  m_min = tmpBBox.m_min;
378  m_max = tmpBBox.m_max;
379 }
const SFVEC3F GetExtent() const
Definition: bbox_3d.cpp:145
VECTOR2I v2(1, 0)
Test suite for KiCad math code.
Defines math related functions.
unsigned int MaxDimension() const
Definition: bbox_3d.cpp:151
const SFVEC3F & Max() const
Return the maximum vertex pointer.
Definition: bbox_3d.h:198
~BBOX_3D()
Definition: bbox_3d.cpp:56
void ApplyTransformation(glm::mat4 aTransformMatrix)
Apply a transformation matrix to the box points.
Definition: bbox_3d.cpp:347
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:41
bool Intersect(const RAY &aRay, float *t) const
Definition: bbox_3d_ray.cpp:46
void ApplyTransformationAA(glm::mat4 aTransformMatrix)
Apply a transformation matrix to the box points and recalculate it to fit an axis aligned bounding bo...
Definition: bbox_3d.cpp:361
Definition: ray.h:67
SFVEC3F Offset(const SFVEC3F &p) const
Definition: bbox_3d.cpp:260
void Union(const SFVEC3F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_3d.cpp:102
bool Inside(const SFVEC3F &aPoint) const
Check if a point is inside this bounding box.
Definition: bbox_3d.cpp:240
float SurfaceArea() const
Definition: bbox_3d.cpp:183
const SFVEC3F & Min() const
Return the minimum vertex pointer.
Definition: bbox_3d.h:191
SFVEC3F m_InvDir
Definition: ray.h:75
SFVEC3F m_max
(12) point of the higher position of the bounding box
Definition: bbox_3d.h:237
SFVEC3F GetCenter() const
Return the center point of the bounding box.
Definition: bbox_3d.cpp:132
void ScaleNextDown()
Scale a bounding box to the next float representation making it smaller.
Definition: bbox_3d.cpp:215
void Scale(float aScale)
Scales a bounding box by its center.
Definition: bbox_3d.cpp:191
float NextFloatDown(float v)
Definition: 3d_fastmath.h:157
float GetMaxDimension() const
Definition: bbox_3d.cpp:167
unsigned int m_dirIsNeg[3]
Definition: ray.h:80
bool IsInitialized() const
Check if this bounding box is already initialized.
Definition: bbox_3d.cpp:88
Bounding Box class definition.
void Set(const SFVEC3F &aPbMin, const SFVEC3F &aPbMax)
Set bounding box with new parameters.
Definition: bbox_3d.cpp:68
SFVEC3F m_Origin
Definition: ray.h:69
void ScaleNextUp()
Scale a bounding box to the next float representation making it larger.
Definition: bbox_3d.cpp:203
BBOX_3D()
Create with default values a bounding box (not initialized)
Definition: bbox_3d.cpp:37
glm::vec3 SFVEC3F
Definition: xv3d_types.h:44
float NextFloatUp(float v)
Definition: 3d_fastmath.h:136
float Volume() const
Calculate the volume of a bounding box.
Definition: bbox_3d.cpp:250
SFVEC3F m_min
(12) point of the lower position of the bounding box
Definition: bbox_3d.h:236
void Reset()
Reset the bounding box to zero and de-initialize it.
Definition: bbox_3d.cpp:95
bool Intersects(const BBOX_3D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_3d.cpp:227