Spinning Topp Logo BlackTopp Studios
inc
triangle.cpp
1 // © Copyright 2010 - 2016 BlackTopp Studios Inc.
2 /* This file is part of The Mezzanine Engine.
3 
4  The Mezzanine Engine is free software: you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation, either version 3 of the License, or
7  (at your option) any later version.
8 
9  The Mezzanine Engine is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with The Mezzanine Engine. If not, see <http://www.gnu.org/licenses/>.
16 */
17 /* The original authors have included a copy of the license specified above in the
18  'Docs' folder. See 'gpl.txt'
19 */
20 /* We welcome the use of the Mezzanine engine to anyone, including companies who wish to
21  Build professional software and charge for their product.
22 
23  However there are some practical restrictions, so if your project involves
24  any of the following you should contact us and we will try to work something
25  out:
26  - DRM or Copy Protection of any kind(except Copyrights)
27  - Software Patents You Do Not Wish to Freely License
28  - Any Kind of Linking to Non-GPL licensed Works
29  - Are Currently In Violation of AnOther Copyright Holder's GPL License
30  - If You want to change our code and not add a few hundred MB of stuff to
31  your distribution
32 
33  These and Other limitations could cause serious legal problems if you ignore
34  them, so it is best to simply contact us or the Free Software Foundation, if
35  you have any questions.
36 
37  Joseph Toppi - toppij@gmail.com
38  John Blackwood - makoenergy02@gmail.com
39 */
40 /*
41 -----------------------------------------------------------------------------
42 This source file is part of ogre-procedural
43 
44 For the latest info, see http://www.ogreprocedural.org
45 
46 Copyright (c) 2010-2013 Michael Broutin
47 
48 Permission is hereby granted, free of charge, to any person obtaining a copy
49 of this software and associated documentation files (the "Software"), to deal
50 in the Software without restriction, including without limitation the rights
51 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
52 copies of the Software, and to permit persons to whom the Software is
53 furnished to do so, subject to the following conditions:
54 
55 The above copyright notice and this permission notice shall be included in
56 all copies or substantial portions of the Software.
57 
58 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
59 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
60 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
61 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
62 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
63 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
64 THE SOFTWARE.
65 -----------------------------------------------------------------------------
66 */
67 #ifndef _triangle_cpp
68 #define _triangle_cpp
69 
70 #include "triangle.h"
71 #include "linesegment.h"
72 #include "plane.h"
73 #include "ray.h"
74 #include "MathTools/mathtools.h"
75 #include "exception.h"
76 
77 namespace
78 {
79  void isect( Mezzanine::Real VV0, Mezzanine::Real VV1, Mezzanine::Real VV2,
81  Mezzanine::Real& isect0, Mezzanine::Real& isect1 )
82  {
83  isect0 = VV0 + ( VV1 - VV0 ) * D0 / ( D0 - D1 );
84  isect1 = VV0 + ( VV2 - VV0 ) * D0 / ( D0 - D2 );
85  }
86 
87  void ComputeIntervals( Mezzanine::Real VV0, Mezzanine::Real VV1, Mezzanine::Real VV2,
90  Mezzanine::Real& isect0, Mezzanine::Real& isect1 )
91  {
92  if( D0D1 > 0.0 ) {
93  /* here we know that D0D2<=0.0 */
94  /* that is D0, D1 are on the same side, D2 on the Other or on the plane */
95  isect(VV2,VV0,VV1,D2,D0,D1,isect0,isect1);
96  }else if( D0D2 > 0.0 ) {
97  /* here we know that d0d1<=0.0 */
98  isect(VV1,VV0,VV2,D1,D0,D2,isect0,isect1);
99  }else if( D1 * D2 > 0.0f || D0 != 0.0 ) {
100  /* here we know that d0d1<=0.0 or that D0!=0.0 */
101  isect(VV0,VV1,VV2,D0,D1,D2,isect0,isect1);
102  }else if( D1 != 0.0 ) {
103  isect(VV1,VV0,VV2,D1,D0,D2,isect0,isect1);
104  }else if( D2 != 0.0 ) {
105  isect(VV2,VV0,VV1,D2,D0,D1,isect0,isect1);
106  }else{
107  /* triangles are coplanar */
108  //return coplanar_tri_tri(N1,V0,V1,V2,U0,U1,U2);
109  }
110  }
111 }
112 
113 namespace Mezzanine
114 {
115  ///////////////////////////////////////////////////////////////////////////////
116  // Triangle2D Methods
117 
118  ///////////////////////////////////////////////////////////////////////////////
119  // Construction and Destruction
120 
122  { }
123 
124  Triangle2D::Triangle2D(const Vector2& A, const Vector2& B, const Vector2& C) :
125  PointA(A),
126  PointB(B),
127  PointC(C)
128  { }
129 
130  ///////////////////////////////////////////////////////////////////////////////
131  // Utility
132 
134  {
135  switch( Index )
136  {
137  case 0: return this->PointA; break;
138  case 1: return this->PointB; break;
139  case 2: return this->PointC; break;
140  default:
141  MEZZ_EXCEPTION(ExceptionBase::PARAMETERS_RANGE_EXCEPTION,"Triangle indexes are only valid if in the range of: 0-2.");
142  }
143  return this->PointA;
144  }
145 
146  const Vector2& Triangle2D::operator[](const Whole& Index) const
147  {
148  switch( Index )
149  {
150  case 0: return this->PointA; break;
151  case 1: return this->PointB; break;
152  case 2: return this->PointC; break;
153  default:
154  MEZZ_EXCEPTION(ExceptionBase::PARAMETERS_RANGE_EXCEPTION,"Triangle indexes are only valid if in the range of: 0-2.");
155  }
156  return this->PointA;
157  }
158 
159  ///////////////////////////////////////////////////////////////////////////////
160  // Triangle3D Methods
161 
162  ///////////////////////////////////////////////////////////////////////////////
163  // Construction and Destruction
164 
166  { }
167 
168  Triangle3D::Triangle3D(const Vector3& A, const Vector3& B, const Vector3& C) :
169  PointA(A),
170  PointB(B),
171  PointC(C)
172  { }
173 
174  ///////////////////////////////////////////////////////////////////////////////
175  // Utility
176 
178  {
179  // Compute plane equation of first triangle
180  Vector3 e1 = this->PointB - this->PointA;
181  Vector3 e2 = this->PointC - this->PointA;
182  Vector3 n1 = e1.CrossProduct(e2);
183  Real d1 = -( n1.DotProduct(this->PointA) );
184 
185  // Put second triangle in first plane equation to compute distances to the plane
186  Real du[3];
187  for( short i = 0 ; i < 3; i++ )
188  {
189  Vector3 Vec;
190  if( i == 0 ) Vec = Other.PointA;
191  else if( i == 1 ) Vec = Other.PointB;
192  else if( i == 2 ) Vec = Other.PointC;
193  du[i] = n1.DotProduct( Vec ) + d1;
194  if( MathTools::Abs( du[i] ) < 1e-6 )
195  du[i] = 0.0;
196  }
197 
198  Real du0du1 = du[0] * du[1];
199  Real du0du2 = du[0] * du[2];
200 
201  if( du0du1 > 0.0 && du0du2 > 0.0 ) /* same sign on all of them + not equal 0 ? */
202  return LineSegment3D(Vector3(0,0,0),Vector3(0,0,0)); /* no intersection occurs */
203 
204  // Compute plane equation of escond triangle
205  e1 = Other.PointB - Other.PointA;
206  e2 = Other.PointC - Other.PointA;
207  Vector3 n2 = e1.CrossProduct(e2);
208  Real d2 = -( n2.DotProduct(Other.PointA) );
209 
210  // Put first triangle in second plane equation to compute distances to the plane
211  Real dv[3];
212  for( short i = 0 ; i < 3 ; i++ )
213  {
214  Vector3 Vec;
215  if( i == 0 ) Vec = this->PointA;
216  else if( i == 1 ) Vec = this->PointB;
217  else if( i == 2 ) Vec = this->PointC;
218  dv[i] = n2.DotProduct( Vec ) + d2;
219  if( MathTools::Abs( dv[i] ) < 1e-6 )
220  dv[i] = 0.0;
221  }
222 
223  Real dv0dv1 = dv[0] * dv[1];
224  Real dv0dv2 = dv[0] * dv[2];
225 
226  if( dv0dv1 > 0.0 && dv0dv2 > 0.0 ) /* same sign on all of them + not equal 0 ? */
227  return LineSegment3D(Vector3(0,0,0),Vector3(0,0,0)); /* no intersection occurs */
228 
229  //Compute the direction of intersection line
230  Vector3 d = n1.CrossProduct(n2);
231 
232  // We don't do coplanar triangles
233  if( d.SquaredLength() < 1e-6 )
234  return LineSegment3D(Vector3(0,0,0),Vector3(0,0,0));
235 
236  // Project triangle points onto the intersection line
237 
238  /* compute and index to the largest component of D */
239  Real Max = MathTools::Abs( d[0] );
240  Integer index = 0;
241  Real b = MathTools::Abs( d[1] );
242  Real c = MathTools::Abs( d[2] );
243  if ( b > Max )
244  Max = b, index = 1;
245  if ( c > Max )
246  Max = c, index = 2;
247 
248  /* this is the simplified projection onto L*/
249  Real vp0 = this->PointA[index];
250  Real vp1 = this->PointB[index];
251  Real vp2 = this->PointC[index];
252 
253  Real up0 = Other.PointA[index];
254  Real up1 = Other.PointB[index];
255  Real up2 = Other.PointC[index];
256 
257  Real isect1[2];
258  Real isect2[2];
259  /* compute interval for triangle 1 */
260  ComputeIntervals(vp0,vp1,vp2,dv[0],dv[1],dv[2],dv0dv1,dv0dv2,isect1[0],isect1[1]);
261 
262  /* compute interval for triangle 2 */
263  ComputeIntervals(up0,up1,up2,du[0],du[1],du[2],du0du1,du0du2,isect2[0],isect2[1]);
264 
265  if( isect1[0] > isect1[1] )
266  std::swap(isect1[0],isect1[1]);
267  if( isect2[0] > isect2[1] )
268  std::swap(isect2[0],isect2[1]);
269 
270  if( isect1[1] < isect2[0] || isect2[1] < isect1[0] )
271  return LineSegment3D(Vector3(0,0,0),Vector3(0,0,0));
272 
273  // Deproject segment onto line
274  Real r1 = std::max( isect1[0], isect2[0] );
275  Real r2 = std::min( isect1[1], isect2[1] );
276 
277  Plane pl1(n1, d1);
278  Plane pl2(n2, d2);
279  Ray InterLine = pl1.GetOverlap(pl2);
280  Vector3 p = InterLine.GetOrigin();
281  d.Normalize();
282  Vector3 v1 = p + d * ( ( r1 - p[index] ) / d[index] );
283  Vector3 v2 = p + d * ( ( r2 - p[index] ) / d[index] );
284 
285  return LineSegment3D(v1,v2);
286  }
287 
289  {
290  switch( Index )
291  {
292  case 0: return this->PointA; break;
293  case 1: return this->PointB; break;
294  case 2: return this->PointC; break;
295  default:
296  MEZZ_EXCEPTION(ExceptionBase::PARAMETERS_RANGE_EXCEPTION,"Triangle indexes are only valid if in the range of: 0-2.");
297  }
298  return this->PointA;
299  }
300 
301  const Vector3& Triangle3D::operator[](const Whole& Index) const
302  {
303  switch( Index )
304  {
305  case 0: return this->PointA; break;
306  case 1: return this->PointB; break;
307  case 2: return this->PointC; break;
308  default:
309  MEZZ_EXCEPTION(ExceptionBase::PARAMETERS_RANGE_EXCEPTION,"Triangle indexes are only valid if in the range of: 0-2.");
310  }
311  return this->PointA;
312  }
313 }//Mezzanine
314 
315 #endif
Vector3 PointA
The first point in space making the triangle.
Definition: triangle.h:103
Vector3 CrossProduct(const Vector3 &Vec) const
This is used to calculate the crossproduct of this and another vector.
Definition: vector3.cpp:338
Triangle2D()
Blank constructor.
Definition: triangle.cpp:121
#define MEZZ_EXCEPTION(num, desc)
An easy way to throw exceptions with rich information.
Definition: exception.h:3048
int Integer
A datatype used to represent any integer close to.
Definition: datatypes.h:154
LineSegment3D GetOverlap(const Triangle3D &Other) const
Gets the overlap of two triangles.
Definition: triangle.cpp:177
Ray GetOverlap(const Plane &Other) const
Gets the overlap of two Planes expressed as a Ray.
Definition: plane.cpp:144
This is used to represent a flat infinite slice of the game world.
Definition: plane.h:65
This implements the exception hiearchy for Mezzanine.
float Real
A Datatype used to represent a real floating point number.
Definition: datatypes.h:141
A geometry math class for expressing a line connecting 2 points in 3D space.
Definition: linesegment.h:94
Vector2 PointC
The third point in space making the triangle.
Definition: triangle.h:64
This is used to represent a point on a 2 dimentional area, such as a screen.
Definition: vector2.h:63
Vector2 & operator[](const Whole &Index)
Gets the point in this triangle corresponding to the specified index. the index passed in is greater ...
Definition: triangle.cpp:133
const Vector3 & GetOrigin() const
Gets the origin of this ray.
Definition: ray.cpp:91
Vector3 & operator[](const Whole &Index)
Gets the point in this triangle corresponding to the specified index. the index passed in is greater ...
Definition: triangle.cpp:288
Vector3 & Normalize()
This will change this point into it's own normal relative to the origin.
Definition: vector3.cpp:352
A geometry math class for expressing a triangle in 3D space.
Definition: triangle.h:96
Vector3 PointC
The third point in space making the triangle.
Definition: triangle.h:107
Thrown when a passed parameter is checked at runtime and not in the expected range.
Definition: exception.h:110
Vector3 PointB
The second point in space making the triangle.
Definition: triangle.h:105
Vector2 PointB
The second point in space making the triangle.
Definition: triangle.h:62
Real DotProduct(const Vector3 &Vec) const
This is used to calculate the dotproduct of this and another vector.
Definition: vector3.cpp:347
Real SquaredLength() const
Gets the length of this vector squared.
Definition: vector3.cpp:464
This is used to represent a point in space, or a vector through space.
Definition: vector3.h:77
Triangle3D()
Blank constructor.
Definition: triangle.cpp:165
The bulk of the engine components go in this namspace.
Definition: actor.cpp:56
unsigned long Whole
Whole is an unsigned integer, it will be at least 32bits in size.
Definition: datatypes.h:151
Vector2 PointA
The first point in space making the triangle.
Definition: triangle.h:60
This represents a line placed in 3D space and is used with spacial queries.
Definition: ray.h:67