KiCad PCB EDA Suite
triangle_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-2016 Mario Luzeiro <mrluzeiro@ua.pt>
5  * Copyright (C) 1992-2016 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 
25 
31 #include "triangle_3d.h"
32 
33 
35 {
36  const SFVEC3F& A = m_vertex[0];
37  const SFVEC3F& B = m_vertex[1];
38  const SFVEC3F& C = m_vertex[2];
39  const SFVEC3F c = B - A;
40  const SFVEC3F b = C - A;
41 
42  m_bbox.Reset();
43  m_bbox.Set( A );
44  m_bbox.Union( B );
45  m_bbox.Union( C );
48 
49  m_n = glm::cross( b, c );
50 
51  if( glm::abs( m_n.x ) > glm::abs( m_n.y ) )
52  {
53  if( glm::abs( m_n.x ) > glm::abs( m_n.z ) )
54  m_k = 0;
55  else
56  m_k = 2;
57  }
58  else
59  {
60  if( glm::abs( m_n.y ) > glm::abs( m_n.z ) )
61  m_k = 1;
62  else
63  m_k = 2;
64  }
65 
66  int u = ( m_k + 1 ) % 3;
67  int v = ( m_k + 2 ) % 3;
68 
69  // precomp
70  float krec = 1.0f / m_n[m_k];
71 
72  m_nu = m_n[u] * krec;
73  m_nv = m_n[v] * krec;
74  m_nd = glm::dot( m_n, A ) * krec;
75 
76  // first line equation
77  float reci = 1.0f / (b[u] * c[v] - b[v] * c[u]);
78 
79  m_bnu = b[u] * reci;
80  m_bnv = -b[v] * reci;
81 
82  // second line equation
83  m_cnu = c[v] * reci;
84  m_cnv = -c[u] * reci;
85 
86  // finalize normal
87  m_n = glm::normalize( m_n );
88 
89  m_normal[0] = m_n;
90  m_normal[1] = m_n;
91  m_normal[2] = m_n;
92 }
93 
94 
95 TRIANGLE::TRIANGLE( const SFVEC3F& aV1, const SFVEC3F& aV2, const SFVEC3F& aV3 )
97 {
98  m_vertex[0] = aV1;
99  m_vertex[1] = aV2;
100  m_vertex[2] = aV3;
101 
102  m_vertexColorRGBA[0] = 0xFFFFFFFF;
103  m_vertexColorRGBA[1] = 0xFFFFFFFF;
104  m_vertexColorRGBA[2] = 0xFFFFFFFF;
105 
106  pre_calc_const();
107 }
108 
109 
110 TRIANGLE::TRIANGLE( const SFVEC3F& aV1, const SFVEC3F& aV2, const SFVEC3F& aV3,
111  const SFVEC3F& aFaceNormal )
113 {
114  m_vertex[0] = aV1;
115  m_vertex[1] = aV2;
116  m_vertex[2] = aV3;
117 
118  m_vertexColorRGBA[0] = 0xFFFFFFFF;
119  m_vertexColorRGBA[1] = 0xFFFFFFFF;
120  m_vertexColorRGBA[2] = 0xFFFFFFFF;
121 
122  pre_calc_const();
123 
124  m_normal[0] = aFaceNormal;
125  m_normal[1] = aFaceNormal;
126  m_normal[2] = aFaceNormal;
127 }
128 
129 
130 TRIANGLE::TRIANGLE( const SFVEC3F& aV1, const SFVEC3F& aV2, const SFVEC3F& aV3,
131  const SFVEC3F& aN1, const SFVEC3F& aN2, const SFVEC3F& aN3 )
133 {
134  m_vertex[0] = aV1;
135  m_vertex[1] = aV2;
136  m_vertex[2] = aV3;
137 
138  m_vertexColorRGBA[0] = 0xFFFFFFFF;
139  m_vertexColorRGBA[1] = 0xFFFFFFFF;
140  m_vertexColorRGBA[2] = 0xFFFFFFFF;
141 
142  pre_calc_const();
143 
144  m_normal[0] = aN1;
145  m_normal[1] = aN2;
146  m_normal[2] = aN3;
147 }
148 
149 
150 void TRIANGLE::SetColor( const SFVEC3F& aColor )
151 {
152  m_vertexColorRGBA[0] = ( (unsigned int) ( aColor.r * 255 ) << 24 )
153  | ( (unsigned int) ( aColor.g * 255 ) << 16 )
154  | ( (unsigned int) ( aColor.b * 255 ) << 8 ) | 0xFF;
157 }
158 
159 
160 void TRIANGLE::SetColor( const SFVEC3F& aVC0, const SFVEC3F& aVC1, const SFVEC3F& aVC2 )
161 {
162  m_vertexColorRGBA[0] = ( (unsigned int) ( aVC0.r * 255 ) << 24 )
163  | ( (unsigned int) ( aVC0.g * 255 ) << 16 )
164  | ( (unsigned int) ( aVC0.b * 255 ) << 8 ) | 0xFF;
165  m_vertexColorRGBA[1] = ( (unsigned int) ( aVC1.r * 255 ) << 24 )
166  | ( (unsigned int) ( aVC1.g * 255 ) << 16 )
167  | ( (unsigned int) ( aVC1.b * 255 ) << 8 ) | 0xFF;
168  m_vertexColorRGBA[2] = ( (unsigned int) ( aVC2.r * 255 ) << 24 )
169  | ( (unsigned int) ( aVC2.g * 255 ) << 16 )
170  | ( (unsigned int) ( aVC2.b * 255 ) << 8 ) | 0xFF;
171 }
172 
173 
174 void TRIANGLE::SetColor( unsigned int aFaceColorRGBA )
175 {
176  m_vertexColorRGBA[0] = aFaceColorRGBA;
177  m_vertexColorRGBA[1] = aFaceColorRGBA;
178  m_vertexColorRGBA[2] = aFaceColorRGBA;
179 }
180 
181 
182 void TRIANGLE::SetColor( unsigned int aVertex1ColorRGBA, unsigned int aVertex2ColorRGBA,
183  unsigned int aVertex3ColorRGBA )
184 {
185  m_vertexColorRGBA[0] = aVertex1ColorRGBA;
186  m_vertexColorRGBA[1] = aVertex2ColorRGBA;
187  m_vertexColorRGBA[2] = aVertex3ColorRGBA;
188 }
189 
190 
191 void TRIANGLE::SetUV( const SFVEC2F& aUV1, const SFVEC2F& aUV2, const SFVEC2F& aUV3 )
192 {
193  m_uv[0] = aUV1;
194  m_uv[1] = aUV2;
195  m_uv[2] = aUV3;
196 }
197 
198 
199 static const unsigned int s_modulo[] = { 0, 1, 2, 0, 1 };
200 
201 
202 bool TRIANGLE::Intersect( const RAY& aRay, HITINFO& aHitInfo ) const
203 {
205 #define ku s_modulo[m_k + 1]
206 #define kv s_modulo[m_k + 2]
207 
208  const SFVEC3F& O = aRay.m_Origin;
209  const SFVEC3F& D = aRay.m_Dir;
210  const SFVEC3F& A = m_vertex[0];
211 
212  const float lnd = 1.0f / (D[m_k] + m_nu * D[ku] + m_nv * D[kv]);
213  const float t = ( m_nd - O[m_k] - m_nu * O[ku] - m_nv * O[kv] ) * lnd;
214 
215  if( !( ( aHitInfo.m_tHit > t ) && ( t > 0.0f ) ) )
216  return false;
217 
218  const float hu = O[ku] + t * D[ku] - A[ku];
219  const float hv = O[kv] + t * D[kv] - A[kv];
220  const float beta = hv * m_bnu + hu * m_bnv;
221 
222  if( beta < 0.0f )
223  return false;
224 
225  const float gamma = hu * m_cnu + hv * m_cnv;
226 
227  if( gamma < 0 )
228  return false;
229 
230  const float v = gamma;
231  const float u = beta;
232 
233  if( (u + v) > 1.0f )
234  return false;
235 
236  if( glm::dot( D, m_n ) > 0.0f )
237  return false;
238 
239  aHitInfo.m_tHit = t;
240  aHitInfo.m_HitPoint = aRay.at( t );
241 
242  // interpolate vertex normals with UVW using Gouraud's shading
243  aHitInfo.m_HitNormal =
244  glm::normalize( ( 1.0f - u - v ) * m_normal[0] + u * m_normal[1] + v * m_normal[2] );
245 
246  m_material->Generate( aHitInfo.m_HitNormal, aRay, aHitInfo );
247 
248  aHitInfo.pHitObject = this;
249 
250  return true;
251 #undef ku
252 #undef kv
253 }
254 
255 
256 bool TRIANGLE::IntersectP( const RAY& aRay, float aMaxDistance ) const
257 {
259 #define ku s_modulo[m_k + 1]
260 #define kv s_modulo[m_k + 2]
261 
262  const SFVEC3F O = aRay.m_Origin;
263  const SFVEC3F D = aRay.m_Dir;
264  const SFVEC3F A = m_vertex[0];
265 
266  const float lnd = 1.0f / (D[m_k] + m_nu * D[ku] + m_nv * D[kv]);
267  const float t = ( m_nd - O[m_k] - m_nu * O[ku] - m_nv * O[kv] ) * lnd;
268 
269  if( !( ( aMaxDistance > t ) && ( t > 0.0f ) ) )
270  return false;
271 
272  const float hu = O[ku] + t * D[ku] - A[ku];
273  const float hv = O[kv] + t * D[kv] - A[kv];
274  const float beta = hv * m_bnu + hu * m_bnv;
275 
276  if( beta < 0.0f )
277  return false;
278 
279  const float gamma = hu * m_cnu + hv * m_cnv;
280 
281  if( gamma < 0.0f )
282  return false;
283 
284  const float v = gamma;
285  const float u = beta;
286 
287  if( (u + v) > 1.0f )
288  return false;
289 
290  if( glm::dot( D, m_n ) > 0.0f )
291  return false;
292 
293  return true;
294 #undef ku
295 #undef kv
296 }
297 
298 
299 bool TRIANGLE::Intersects( const BBOX_3D& aBBox ) const
300 {
302  return m_bbox.Intersects( aBBox );
303 }
304 
305 
306 SFVEC3F TRIANGLE::GetDiffuseColor( const HITINFO& aHitInfo ) const
307 {
308  const unsigned int rgbC1 = m_vertexColorRGBA[0];
309  const unsigned int rgbC2 = m_vertexColorRGBA[1];
310  const unsigned int rgbC3 = m_vertexColorRGBA[2];
311 
312  const SFVEC3F c1 = SFVEC3F( (float) ( ( rgbC1 >> 24 ) & 0xFF ) / 255.0f,
313  (float) ( ( rgbC1 >> 16 ) & 0xFF ) / 255.0f,
314  (float) ( ( rgbC1 >> 8 ) & 0xFF ) / 255.0f );
315  const SFVEC3F c2 = SFVEC3F( (float) ( ( rgbC2 >> 24 ) & 0xFF ) / 255.0f,
316  (float) ( ( rgbC2 >> 16 ) & 0xFF ) / 255.0f,
317  (float) ( ( rgbC2 >> 8 ) & 0xFF ) / 255.0f );
318  const SFVEC3F c3 = SFVEC3F( (float) ( ( rgbC3 >> 24 ) & 0xFF ) / 255.0f,
319  (float) ( ( rgbC3 >> 16 ) & 0xFF ) / 255.0f,
320  (float) ( ( rgbC3 >> 8 ) & 0xFF ) / 255.0f );
321 
322  const float u = aHitInfo.m_UV.x;
323  const float v = aHitInfo.m_UV.y;
324  const float w = 1.0f - u - v;
325 
326  return w * c1 + u * c2 + v * c3;
327 }
float m_nu
Definition: triangle_3d.h:77
#define ku
Implement a triangle ray intersection based on article http://www.flipcode.com/archives/Raytracing_To...
bool Intersect(const RAY &aRay, HITINFO &aHitInfo) const override
SFVEC3F m_n
Definition: triangle_3d.h:74
float m_bnu
Definition: triangle_3d.h:79
float m_cnu
Definition: triangle_3d.h:80
#define kv
Manage a bounding box defined by two SFVEC3F min max points.
Definition: bbox_3d.h:41
void Generate(SFVEC3F &aNormal, const RAY &aRay, const HITINFO &aHitInfo) const
Definition: material.cpp:93
Definition: ray.h:67
void SetUV(const SFVEC2F &aUV1, const SFVEC2F &aUV2, const SFVEC2F &aUV3)
float m_tHit
( 4) distance
Definition: hitinfo.h:43
SFVEC3F at(float t) const
Definition: ray.h:89
void Union(const SFVEC3F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_3d.cpp:102
static const unsigned int s_modulo[]
SFVEC3F m_HitPoint
(12) hit position
Definition: hitinfo.h:49
void SetColor(const SFVEC3F &aColor)
SFVEC3F GetCenter() const
Return the center point of the bounding box.
Definition: bbox_3d.cpp:132
float m_bnv
Definition: triangle_3d.h:79
SFVEC2F m_uv[3]
Definition: triangle_3d.h:75
glm::vec2 SFVEC2F
Definition: xv3d_types.h:42
BBOX_3D m_bbox
Definition: object_3d.h:97
SFVEC3F GetDiffuseColor(const HITINFO &aHitInfo) const override
SFVEC3F m_vertex[3]
Definition: triangle_3d.h:73
float m_nd
Definition: triangle_3d.h:77
SFVEC3F m_normal[3]
Definition: triangle_3d.h:72
const MATERIAL * m_material
Definition: object_3d.h:100
const OBJECT_3D * pHitObject
( 4) Object that was hitted
Definition: hitinfo.h:45
SFVEC3F m_Dir
Definition: ray.h:72
bool IntersectP(const RAY &aRay, float aMaxDistance) const override
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
A triangle object.
Definition: triangle_3d.h:42
TRIANGLE(const SFVEC3F &aV1, const SFVEC3F &aV2, const SFVEC3F &aV3)
Definition: triangle_3d.cpp:95
void ScaleNextUp()
Scale a bounding box to the next float representation making it larger.
Definition: bbox_3d.cpp:203
SFVEC3F m_centroid
Definition: object_3d.h:98
Stores the hit information of a ray with a point on the surface of a object.
Definition: hitinfo.h:40
glm::vec3 SFVEC3F
Definition: xv3d_types.h:44
SFVEC3F m_HitNormal
(12) normal at the hit point
Definition: hitinfo.h:42
unsigned int m_vertexColorRGBA[3]
Definition: triangle_3d.h:76
OBJECT_3D_TYPE
Definition: object_3d.h:38
unsigned int m_k
Definition: triangle_3d.h:78
float m_nv
Definition: triangle_3d.h:77
float m_cnv
Definition: triangle_3d.h:80
bool Intersects(const BBOX_3D &aBBox) const override
void Reset()
Reset the bounding box to zero and de-initialize it.
Definition: bbox_3d.cpp:95
SFVEC2F m_UV
( 8) 2-D texture coordinates
Definition: hitinfo.h:46
bool Intersects(const BBOX_3D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_3d.cpp:227
void pre_calc_const()
Definition: triangle_3d.cpp:34