triRayCheck.cpp

Public Functions

castRayTriangle(const Point3D & orig, const Point3D & dir, const Point3D & vert0, const Point3D & vert1, const Point3D & vert2)

castRayTriangle(const Point3F & orig, const Point3F & dir, const Point3F & vert0, const Point3F & vert1, const Point3F & vert2, F32 & t, Point2F & bary)

intersect_triangle(Point3F orig, Point3F dir, Point3F vert0, Point3F vert1, Point3F vert2, F32 & t, F32 & u, F32 & v)

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24//-----------------------------------------------------------------------------
 25// Ray to triangle intersection test code originally by Tomas Akenine-Möller
 26// and Ben Trumbore.
 27// http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/
 28// Ported to TGE by DAW, 2005-7-15
 29//-----------------------------------------------------------------------------
 30
 31#include "util/triRayCheck.h"
 32#include "math/mPlane.h"
 33
 34#define EPSILON 0.000001
 35#define CROSS(dest,v1,v2) \
 36          dest[0]=v1[1]*v2[2]-v1[2]*v2[1]; \
 37          dest[1]=v1[2]*v2[0]-v1[0]*v2[2]; \
 38          dest[2]=v1[0]*v2[1]-v1[1]*v2[0];
 39#define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
 40#define SUB(dest,v1,v2) \
 41          dest[0]=v1[0]-v2[0]; \
 42          dest[1]=v1[1]-v2[1]; \
 43          dest[2]=v1[2]-v2[2]; 
 44
 45bool intersect_triangle(Point3F orig, Point3F dir,
 46                   Point3F vert0, Point3F vert1, Point3F vert2,
 47                   F32& t, F32& u, F32& v)
 48{
 49   Point3F edge1, edge2, tvec, pvec, qvec;
 50   F32 det,inv_det;
 51
 52   /* find vectors for two edges sharing vert0 */
 53   edge1.x = vert1.x - vert0.x;
 54   edge1.y = vert1.y - vert0.y;
 55   edge1.z = vert1.z - vert0.z;
 56   edge2.x = vert2.x - vert0.x;
 57   edge2.y = vert2.y - vert0.y;
 58   edge2.z = vert2.z - vert0.z;
 59
 60   /* begin calculating determinant - also used to calculate U parameter */
 61   //CROSS(pvec, dir, edge2);
 62   mCross(dir, edge2, &pvec);
 63
 64   /* if determinant is near zero, ray lies in plane of triangle */
 65   //det = DOT(edge1, pvec);
 66   det = mDot(edge1, pvec);
 67
 68#ifdef TEST_CULL           /* define TEST_CULL if culling is desired */
 69   if (det < EPSILON)
 70      return 0;
 71
 72   /* calculate distance from vert0 to ray origin */
 73   SUB(tvec, orig, vert0);
 74
 75   /* calculate U parameter and test bounds */
 76   *u = DOT(tvec, pvec);
 77   if (*u < 0.0 || *u > det)
 78      return 0;
 79
 80   /* prepare to test V parameter */
 81   CROSS(qvec, tvec, edge1);
 82
 83    /* calculate V parameter and test bounds */
 84   *v = DOT(dir, qvec);
 85   if (*v < 0.0 || *u + *v > det)
 86      return 0;
 87
 88   /* calculate t, scale parameters, ray intersects triangle */
 89   *t = DOT(edge2, qvec);
 90   inv_det = 1.0 / det;
 91   *t *= inv_det;
 92   *u *= inv_det;
 93   *v *= inv_det;
 94#else                    /* the non-culling branch */
 95   if (det > -EPSILON && det < EPSILON)
 96     return false;
 97   inv_det = 1.0 / det;
 98
 99   /* calculate distance from vert0 to ray origin */
100   //SUB(tvec, orig, vert0);
101   tvec.x = orig.x - vert0.x;
102   tvec.y = orig.y - vert0.y;
103   tvec.z = orig.z - vert0.z;
104
105   /* calculate U parameter and test bounds */
106//   *u = DOT(tvec, pvec) * inv_det;
107   u = mDot(tvec, pvec) * inv_det;
108   if (u < 0.0 || u > 1.0)
109     return false;
110
111   /* prepare to test V parameter */
112   //CROSS(qvec, tvec, edge1);
113   mCross(tvec, edge1, &qvec);
114
115   /* calculate V parameter and test bounds */
116//   *v = DOT(dir, qvec) * inv_det;
117   v = mDot(dir, qvec) * inv_det;
118   if (v < 0.0 || u + v > 1.0)
119     return false;
120
121   /* calculate t, ray intersects triangle */
122//   *t = DOT(edge2, qvec) * inv_det;
123   t = mDot(edge2, qvec) * inv_det;
124#endif
125   return true;
126}
127
128//*** Taken from TSE, and based on the above
129bool castRayTriangle(const Point3F& orig, const Point3F& dir,
130   const Point3F& vert0, const Point3F& vert1, const Point3F& vert2,
131   F32 &t, Point2F &bary)
132{
133   Point3F tvec, qvec;
134
135   // Find vectors for two edges sharing vert0
136   const Point3F edge1 = vert1 - vert0;
137   const Point3F edge2 = vert2 - vert0;
138
139   // Begin calculating determinant - also used to calculate U parameter.
140   const Point3F pvec = mCross(dir, edge2);
141
142   // If determinant is near zero, ray lies in plane of triangle.
143   const F32 det = mDot(edge1, pvec);
144
145   if (det > 0.00001)
146   {
147      // calculate distance from vert0 to ray origin
148      tvec = orig - vert0;
149
150      // calculate U parameter and test bounds
151      bary.x = mDot(tvec, pvec); // bary.x is really bary.u...
152      if (bary.x < 0.0 || bary.x > det)
153         return false;
154
155      // prepare to test V parameter
156      qvec = mCross(tvec, edge1);
157
158      // calculate V parameter and test bounds
159      bary.y = mDot(dir, qvec); // bary.y is really bary.v
160      if (bary.y < 0.0 || (bary.x + bary.y) > det)
161         return false;
162
163   }
164   else if(det < -0.00001)
165   {
166      // calculate distance from vert0 to ray origin
167      tvec = orig - vert0;
168
169      // calculate U parameter and test bounds
170      bary.x = mDot(tvec, pvec);
171      if (bary.x > 0.0 || bary.x < det)
172         return false;
173
174      // prepare to test V parameter
175      qvec = mCross(tvec, edge1);
176
177      // calculate V parameter and test bounds
178      bary.y = mDot(dir, qvec);
179      if (bary.y > 0.0 || (bary.x + bary.y) < det)
180         return false;
181   }
182   else 
183      return false;  // ray is parallel to the plane of the triangle.
184
185   const F32 inv_det = 1.0 / det;
186
187   // calculate t, ray intersects triangle
188   t = mDot(edge2, qvec) * inv_det;
189   bary *= inv_det;
190   
191   //AssertFatal((t >= 0.f && t <=1.f), "AtlasGeomTracer::castRayTriangle - invalid t!");
192
193   // Hack, check the math here!
194   return (t >= 0.f && t <=1.f);
195}
196
197bool castRayTriangle(const Point3D &orig, const Point3D &dir,
198   const Point3D &vert0, const Point3D &vert1, const Point3D &vert2)
199{
200   F64 t;
201   Point2D bary;
202   Point3D tvec, qvec;
203
204   // Find vectors for two edges sharing vert0
205   const Point3D edge1 = vert1 - vert0;
206   const Point3D edge2 = vert2 - vert0;
207
208   // Begin calculating determinant - also used to calculate U parameter.
209   Point3D pvec;
210   mCross(dir, edge2, &pvec);
211
212   // If determinant is near zero, ray lies in plane of triangle.
213   const F64 det = mDot(edge1, pvec);
214
215   if (det > 0.00001)
216   {
217      // calculate distance from vert0 to ray origin
218      tvec = orig - vert0;
219
220      // calculate U parameter and test bounds
221      bary.x = mDot(tvec, pvec); // bary.x is really bary.u...
222      if (bary.x < 0.0 || bary.x > det)
223         return false;
224
225      // prepare to test V parameter
226      mCross(tvec, edge1, &qvec);
227
228      // calculate V parameter and test bounds
229      bary.y = mDot(dir, qvec); // bary.y is really bary.v
230      if (bary.y < 0.0 || (bary.x + bary.y) > det)
231         return false;
232
233   }
234   else if(det < -0.00001)
235   {
236      // calculate distance from vert0 to ray origin
237      tvec = orig - vert0;
238
239      // calculate U parameter and test bounds
240      bary.x = mDot(tvec, pvec);
241      if (bary.x > 0.0 || bary.x < det)
242         return false;
243
244      // prepare to test V parameter
245      mCross(tvec, edge1, &qvec);
246
247      // calculate V parameter and test bounds
248      bary.y = mDot(dir, qvec);
249      if (bary.y > 0.0 || (bary.x + bary.y) < det)
250         return false;
251   }
252   else 
253      return false;  // ray is parallel to the plane of the triangle.
254
255   const F32 inv_det = 1.0 / det;
256
257   // calculate t, ray intersects triangle
258   t = mDot(edge2, qvec) * inv_det;
259   bary *= inv_det;
260   
261   //AssertFatal((t >= 0.f && t <=1.f), "AtlasGeomTracer::castRayTriangle - invalid t!");
262
263   // Hack, check the math here!
264   return (t >= 0.f && t <=1.f);
265}
266
267