KiCad PCB EDA Suite
cbbox.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-2017 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 "cbbox.h"
32 #include <stdio.h>
33 #include <wx/debug.h> // For the wxASSERT
34 
35 
37 {
38  Reset();
39 }
40 
41 
42 CBBOX::CBBOX( const SFVEC3F &aPbInit )
43 {
44  m_min = aPbInit;
45  m_max = aPbInit;
46 }
47 
48 
49 CBBOX::CBBOX( const SFVEC3F &aPbMin, const SFVEC3F &aPbMax )
50 {
51  Set( aPbMin, aPbMax );
52 }
53 
54 
56 {
57 }
58 
59 
60 void CBBOX::Set( const SFVEC3F &aPoint )
61 {
62  m_min = aPoint;
63  m_max = aPoint;
64 }
65 
66 
67 void CBBOX::Set( const SFVEC3F &aPbMin, const SFVEC3F &aPbMax )
68 {
69  m_min.x = fminf( aPbMin.x, aPbMax.x );
70  m_min.y = fminf( aPbMin.y, aPbMax.y );
71  m_min.z = fminf( aPbMin.z, aPbMax.z );
72 
73  m_max.x = fmaxf( aPbMin.x, aPbMax.x );
74  m_max.y = fmaxf( aPbMin.y, aPbMax.y );
75  m_max.z = fmaxf( aPbMin.z, aPbMax.z );
76 }
77 
78 
79 void CBBOX::Set( const CBBOX &aBBox )
80 {
81  wxASSERT( aBBox.IsInitialized() );
82 
83  Set( aBBox.Min(), aBBox.Max() );
84 }
85 
86 
88 {
89  return !( ( FLT_MAX == m_min.x) ||
90  ( FLT_MAX == m_min.y) ||
91  ( FLT_MAX == m_min.z) ||
92  (-FLT_MAX == m_max.x) ||
93  (-FLT_MAX == m_max.y) ||
94  (-FLT_MAX == m_max.z) );
95 }
96 
97 
99 {
100  m_min = SFVEC3F( FLT_MAX, FLT_MAX, FLT_MAX );
101  m_max = SFVEC3F(-FLT_MAX,-FLT_MAX,-FLT_MAX );
102 }
103 
104 
105 void CBBOX::Union( const SFVEC3F &aPoint )
106 {
107  // get the minimun value between the added point and the existent bounding box
108  m_min.x = fminf( m_min.x, aPoint.x );
109  m_min.y = fminf( m_min.y, aPoint.y );
110  m_min.z = fminf( m_min.z, aPoint.z );
111 
112  // get the maximun value between the added point and the existent bounding box
113  m_max.x = fmaxf( m_max.x, aPoint.x );
114  m_max.y = fmaxf( m_max.y, aPoint.y );
115  m_max.z = fmaxf( m_max.z, aPoint.z );
116 }
117 
118 
119 void CBBOX::Union( const CBBOX &aBBox )
120 {
121  wxASSERT( aBBox.IsInitialized() );
122 
123  // get the minimun value between the added bounding box and the existent bounding box
124  m_min.x = fmin( m_min.x, aBBox.m_min.x );
125  m_min.y = fmin( m_min.y, aBBox.m_min.y );
126  m_min.z = fmin( m_min.z, aBBox.m_min.z );
127 
128  // get the maximun value between the added bounding box and the existent bounding box
129  m_max.x = fmax( m_max.x, aBBox.m_max.x );
130  m_max.y = fmax( m_max.y, aBBox.m_max.y );
131  m_max.z = fmax( m_max.z, aBBox.m_max.z );
132 }
133 
134 
136 {
137  return (m_max + m_min) * 0.5f;
138 }
139 
140 
141 float CBBOX::GetCenter( unsigned int aAxis ) const
142 {
143  wxASSERT( aAxis < 3 );
144  return (m_max[aAxis] + m_min[aAxis]) * 0.5f;
145 }
146 
147 
149 {
150  return m_max - m_min;
151 }
152 
153 
154 unsigned int CBBOX::MaxDimension() const
155 {
156  unsigned int result = 0;
157 
158  SFVEC3F extent = GetExtent();
159 
160  if( extent.y > extent.x )
161  result = 1;
162  if( extent.z > extent.y )
163  result = 2;
164 
165  return result;
166 }
167 
168 
170 {
171  unsigned int max_dimensions_idx = 0;
172 
173  SFVEC3F extent = GetExtent();
174 
175  if( extent.y > extent.x )
176  max_dimensions_idx = 1;
177  if( extent.z > extent.y )
178  max_dimensions_idx = 2;
179 
180  return extent[max_dimensions_idx];
181 }
182 
183 
184 float CBBOX::SurfaceArea() const
185 {
186  SFVEC3F extent = GetExtent();
187 
188  return 2.0f * ( extent.x * extent.z +
189  extent.x * extent.y +
190  extent.y * extent.z );
191 }
192 
193 
194 void CBBOX::Scale( float aScale )
195 {
196  wxASSERT( IsInitialized() );
197 
198  SFVEC3F scaleV = SFVEC3F( aScale, aScale, aScale );
199  SFVEC3F centerV = GetCenter();
200 
201  m_min = (m_min - centerV) * scaleV + centerV;
202  m_max = (m_max - centerV) * scaleV + centerV;
203 }
204 
205 
207 {
208  m_min.x = NextFloatDown( m_min.x );
209  m_min.y = NextFloatDown( m_min.y );
210  m_min.z = NextFloatDown( m_min.z );
211 
212  m_max.x = NextFloatUp( m_max.x );
213  m_max.y = NextFloatUp( m_max.y );
214  m_max.z = NextFloatUp( m_max.z );
215 }
216 
217 
219 {
220  m_min.x = NextFloatUp( m_min.x );
221  m_min.y = NextFloatUp( m_min.y );
222  m_min.z = NextFloatUp( m_min.z );
223 
224  m_max.x = NextFloatDown( m_max.x );
225  m_max.y = NextFloatDown( m_max.y );
226  m_max.z = NextFloatDown( m_max.z );
227 }
228 
229 
230 bool CBBOX::Intersects( const CBBOX &aBBox ) const
231 {
232  wxASSERT( IsInitialized() );
233  wxASSERT( aBBox.IsInitialized() );
234 
235  bool x = ( m_max.x >= aBBox.m_min.x ) && ( m_min.x <= aBBox.m_max.x );
236  bool y = ( m_max.y >= aBBox.m_min.y ) && ( m_min.y <= aBBox.m_max.y );
237  bool z = ( m_max.z >= aBBox.m_min.z ) && ( m_min.z <= aBBox.m_max.z );
238 
239  return ( x && y && z );
240 }
241 
242 
243 bool CBBOX::Inside( const SFVEC3F &aPoint ) const
244 {
245  wxASSERT( IsInitialized() );
246 
247  return (( aPoint.x >= m_min.x ) && ( aPoint.x <= m_max.x ) &&
248  ( aPoint.y >= m_min.y ) && ( aPoint.y <= m_max.y ) &&
249  ( aPoint.z >= m_min.z ) && ( aPoint.z <= m_max.z ));
250 }
251 
252 
253 float CBBOX::Volume() const
254 {
255  wxASSERT( IsInitialized() );
256 
257  SFVEC3F extent = GetExtent();
258 
259  return extent.x * extent.y * extent.z;
260 }
261 
262 
263 SFVEC3F CBBOX::Offset( const SFVEC3F &p ) const
264 {
265  return (p - m_min) / (m_max - m_min);
266 }
267 
268 
269 // Intersection code based on the book:
270 // "Physical Based Ray Tracing" (by Matt Pharr and Greg Humphrey)
271 // https://github.com/mmp/pbrt-v2/blob/master/src/core/geometry.cpp#L68
272 // /////////////////////////////////////////////////////////////////////////
273 #if 0
274 bool CBBOX::Intersect( const RAY &aRay, float *aOutHitt0, float *aOutHitt1 )
275 {
276  float t0 = 0.0f;
277  float t1 = FLT_MAX;
278 
279  for( unsigned int i = 0; i < 3; ++i )
280  {
281  // Update interval for _i_th bounding box slab
282  float tNear = (m_min[i] - aRay.m_Origin[i]) * aRay.m_InvDir[i];
283  float tFar = (m_max[i] - aRay.m_Origin[i]) * aRay.m_InvDir[i];
284 
285  // Update parametric interval from slab intersection
286  if( tNear > tFar )
287  {
288  // Swap
289  float ftemp = tNear;
290  tNear = tFar;
291  tFar = ftemp;
292  }
293 
294  t0 = tNear > t0 ? tNear : t0;
295  t1 = tFar < t1 ? tFar : t1;
296 
297  if( t0 > t1 )
298  return false;
299  }
300 
301  if( aOutHitt0 )
302  *aOutHitt0 = t0;
303  if( aOutHitt1 )
304  *aOutHitt1 = t1;
305 
306  return true;
307 }
308 #else
309 // https://github.com/mmp/pbrt-v2/blob/master/src/accelerators/bvh.cpp#L126
310 bool CBBOX::Intersect( const RAY &aRay,
311  float *aOutHitt0,
312  float *aOutHitt1 ) const
313 {
314  wxASSERT( aOutHitt0 );
315  wxASSERT( aOutHitt1 );
316 
317  const SFVEC3F bounds[2] = {m_min, m_max};
318 
319  // Check for ray intersection against x and y slabs
320  float tmin = (bounds[ aRay.m_dirIsNeg[0]].x - aRay.m_Origin.x) * aRay.m_InvDir.x;
321  float tmax = (bounds[1 - aRay.m_dirIsNeg[0]].x - aRay.m_Origin.x) * aRay.m_InvDir.x;
322  const float tymin = (bounds[ aRay.m_dirIsNeg[1]].y - aRay.m_Origin.y) * aRay.m_InvDir.y;
323  const float tymax = (bounds[1 - aRay.m_dirIsNeg[1]].y - aRay.m_Origin.y) * aRay.m_InvDir.y;
324 
325  if( (tmin > tymax) || (tymin > tmax) )
326  return false;
327 
328  tmin = (tymin > tmin)? tymin : tmin;
329  tmax = (tymax < tmax)? tymax : tmax;
330 
331  // Check for ray intersection against z slab
332  const float tzmin = (bounds[ aRay.m_dirIsNeg[2]].z - aRay.m_Origin.z) * aRay.m_InvDir.z;
333  const float tzmax = (bounds[1 - aRay.m_dirIsNeg[2]].z - aRay.m_Origin.z) * aRay.m_InvDir.z;
334 
335  if( (tmin > tzmax) || (tzmin > tmax) )
336  return false;
337 
338  tmin = (tzmin > tmin)? tzmin : tmin;
339  tmin = ( tmin < 0.0f)? 0.0f : tmin;
340 
341  tmax = (tzmax < tmax)? tzmax : tmax;
342 
343  *aOutHitt0 = tmin;
344  *aOutHitt1 = tmax;
345 
346  return true;
347 }
348 #endif
349 
350 
351 void CBBOX::ApplyTransformation( glm::mat4 aTransformMatrix )
352 {
353  wxASSERT( IsInitialized() );
354 
355  const SFVEC3F v1 = SFVEC3F( aTransformMatrix *
356  glm::vec4( m_min.x, m_min.y, m_min.z, 1.0f ) );
357 
358  const SFVEC3F v2 = SFVEC3F( aTransformMatrix *
359  glm::vec4( m_max.x, m_max.y, m_max.z, 1.0f ) );
360 
361  Reset();
362  Union( v1 );
363  Union( v2 );
364 }
365 
366 
367 void CBBOX::ApplyTransformationAA( glm::mat4 aTransformMatrix )
368 {
369  wxASSERT( IsInitialized() );
370 
371  // apply the transformation matrix for each of vertices of the bounding box
372  // and make a union with all vertices
373  CBBOX tmpBBox = CBBOX(
374  SFVEC3F( aTransformMatrix *
375  glm::vec4( m_min.x, m_min.y, m_min.z, 1.0f ) ) );
376  tmpBBox.Union( SFVEC3F( aTransformMatrix *
377  glm::vec4( m_max.x, m_min.y, m_min.z, 1.0f ) ) );
378  tmpBBox.Union( SFVEC3F( aTransformMatrix *
379  glm::vec4( m_min.x, m_max.y, m_min.z, 1.0f ) ) );
380  tmpBBox.Union( SFVEC3F( aTransformMatrix *
381  glm::vec4( m_min.x, m_min.y, m_max.z, 1.0f ) ) );
382  tmpBBox.Union( SFVEC3F( aTransformMatrix *
383  glm::vec4( m_min.x, m_max.y, m_max.z, 1.0f ) ) );
384  tmpBBox.Union( SFVEC3F( aTransformMatrix *
385  glm::vec4( m_max.x, m_max.y, m_min.z, 1.0f ) ) );
386  tmpBBox.Union( SFVEC3F( aTransformMatrix *
387  glm::vec4( m_max.x, m_min.y, m_max.z, 1.0f ) ) );
388  tmpBBox.Union( SFVEC3F( aTransformMatrix *
389  glm::vec4( m_max.x, m_max.y, m_max.z, 1.0f ) ) );
390 
391  m_min = tmpBBox.m_min;
392  m_max = tmpBBox.m_max;
393 }
394 
395 
396 void CBBOX::debug() const
397 {
398  printf( "min(%f, %f, %f) - max(%f, %f, %f)\n", m_min.x, m_min.y, m_min.z,
399  m_max.x, m_max.y, m_max.z );
400 }
bool Inside(const SFVEC3F &aPoint) const
Function Inside check is a point is inside this bounding box.
Definition: cbbox.cpp:243
Defines math related functions.
float SurfaceArea() const
Function SurfaceArea.
Definition: cbbox.cpp:184
void ScaleNextDown()
Function ScaleNextDown scales a bounding box to the next float representation making it smaller...
Definition: cbbox.cpp:218
const SFVEC3F & Min() const
Function Min return the minimun vertex pointer.
Definition: cbbox.h:205
SFVEC3F Offset(const SFVEC3F &p) const
Function Offset.
Definition: cbbox.cpp:263
bool Intersects(const CBBOX &aBBox) const
Function Intersects test if a bounding box intersects this box.
Definition: cbbox.cpp:230
bool IsInitialized() const
Function IsInitialized check if this bounding box is already initialized.
Definition: cbbox.cpp:87
SFVEC3F m_min
(12) point of the lower position of the bounding box
Definition: cbbox.h:255
CBBOX()
Constructor CBBOX Create with default values a bounding box (not inizialized)
Definition: cbbox.cpp:36
Definition: ray.h:43
float Volume() const
Function Volume calculate the volume of a bounding box.
Definition: cbbox.cpp:253
float GetMaxDimension() const
GetMaxDimension.
Definition: cbbox.cpp:169
void Set(const SFVEC3F &aPbMin, const SFVEC3F &aPbMax)
Function Set Set bounding box with new parameters.
Definition: cbbox.cpp:67
void Union(const SFVEC3F &aPoint)
Function Union recalculate the bounding box adding a point.
Definition: cbbox.cpp:105
SFVEC3F m_InvDir
Definition: ray.h:51
float NextFloatDown(float v)
Definition: 3d_fastmath.h:157
unsigned int m_dirIsNeg[3]
Definition: ray.h:56
void debug() const
Function debug output to stdout.
Definition: cbbox.cpp:396
const SFVEC3F & Max() const
Function Max return the maximum vertex pointer.
Definition: cbbox.h:212
void ScaleNextUp()
Function ScaleNextUp scales a bounding box to the next float representation making it larger...
Definition: cbbox.cpp:206
SFVEC3F m_max
(12) point of the higher position of the bounding box
Definition: cbbox.h:256
bool Intersect(const RAY &aRay, float *t) const
Function Intersect.
Definition: cbbox_ray.cpp:46
void Scale(float aScale)
Function Scale scales a bounding box by its center.
Definition: cbbox.cpp:194
SFVEC3F GetCenter() const
Function GetCenter return the center point of the bounding box.
Definition: cbbox.cpp:135
SFVEC3F m_Origin
Definition: ray.h:45
unsigned int MaxDimension() const
Function MaxDimension.
Definition: cbbox.cpp:154
~CBBOX()
Definition: cbbox.cpp:55
glm::vec3 SFVEC3F
Definition: xv3d_types.h:47
float NextFloatUp(float v)
Definition: 3d_fastmath.h:136
void ApplyTransformationAA(glm::mat4 aTransformMatrix)
Function ApplyTransformationAA apply a transformation matrix to the box points and recalculate it to ...
Definition: cbbox.cpp:367
const SFVEC3F GetExtent() const
Function GetExtent.
Definition: cbbox.cpp:148
Class CBBOX manages a bounding box defined by two SFVEC3F min max points.
Definition: cbbox.h:40
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox.cpp:98
Bounding Box class definition.
void ApplyTransformation(glm::mat4 aTransformMatrix)
Function ApplyTransformation apply a transformation matrix to the box points.
Definition: cbbox.cpp:351