Extras/CDTestFramework/Opcode/OPC_RayTriOverlap.h

   1 /*
   2  *      OPCODE - Optimized Collision Detection
   3  * http://www.codercorner.com/Opcode.htm
   4  *
   5  * Copyright (c) 2001-2008 Pierre Terdiman,  pierre@codercorner.com
   6
   7 This software is provided 'as-is', without any express or implied warranty.
   8 In no event will the authors be held liable for any damages arising from the use of this software.
   9 Permission is granted to anyone to use this software for any purpose,
  10 including commercial applications, and to alter it and redistribute it freely,
  11 subject to the following restrictions:
  12
  13 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
  14 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
  15 3. This notice may not be removed or altered from any source distribution.
  16 */
  17
  18 #define LOCAL_EPSILON 0.000001f
  19
  20 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  21 /**
  22  *      Computes a ray-triangle intersection test.
  23  *      Original code from Tomas Möller's "Fast Minimum Storage Ray-Triangle Intersection".
  24  *      It's been optimized a bit with integer code, and modified to return a non-intersection if distance from
  25  *      ray origin to triangle is negative.
  26  *
  27  *      \param          vert0   [in] triangle vertex
  28  *      \param          vert1   [in] triangle vertex
  29  *      \param          vert2   [in] triangle vertex
  30  *      \return         true on overlap. mStabbedFace is filled with relevant info.
  31  */
  32 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  33 inline_ BOOL RayCollider::RayTriOverlap(const Point& vert0, const Point& vert1, const Point& vert2)
  34 {
  35         // Stats
  36         mNbRayPrimTests++;
  37
  38         // Find vectors for two edges sharing vert0
  39         Point edge1 = vert1 - vert0;
  40         Point edge2 = vert2 - vert0;
  41
  42         // Begin calculating determinant - also used to calculate U parameter
  43         Point pvec = mDir^edge2;
  44
  45         // If determinant is near zero, ray lies in plane of triangle
  46         float det = edge1|pvec;
  47
  48         if(mCulling)
  49         {
  50                 if(det<LOCAL_EPSILON)                                                                                                           return FALSE;
  51                 // From here, det is > 0. So we can use integer cmp.
  52
  53                 // Calculate distance from vert0 to ray origin
  54                 Point tvec = mOrigin - vert0;
  55
  56                 // Calculate U parameter and test bounds
  57                 mStabbedFace.mU = tvec|pvec;
  58 //              if(IR(u)&0x80000000 || u>det)                                   return FALSE;
  59                 if(IS_NEGATIVE_FLOAT(mStabbedFace.mU) || IR(mStabbedFace.mU)>IR(det))           return FALSE;
  60
  61                 // Prepare to test V parameter
  62                 Point qvec = tvec^edge1;
  63
  64                 // Calculate V parameter and test bounds
  65                 mStabbedFace.mV = mDir|qvec;
  66                 if(IS_NEGATIVE_FLOAT(mStabbedFace.mV) || mStabbedFace.mU+mStabbedFace.mV>det)   return FALSE;
  67
  68                 // Calculate t, scale parameters, ray intersects triangle
  69                 mStabbedFace.mDistance = edge2|qvec;
  70                 // Det > 0 so we can early exit here
  71                 // Intersection point is valid if distance is positive (else it can just be a face behind the orig point)
  72                 if(IS_NEGATIVE_FLOAT(mStabbedFace.mDistance))                                                           return FALSE;
  73                 // Else go on
  74                 float OneOverDet = 1.0f / det;
  75                 mStabbedFace.mDistance *= OneOverDet;
  76                 mStabbedFace.mU *= OneOverDet;
  77                 mStabbedFace.mV *= OneOverDet;
  78         }
  79         else
  80         {
  81                 // the non-culling branch
  82                 if(det>-LOCAL_EPSILON && det<LOCAL_EPSILON)                                                                     return FALSE;
  83                 float OneOverDet = 1.0f / det;
  84
  85                 // Calculate distance from vert0 to ray origin
  86                 Point tvec = mOrigin - vert0;
  87
  88                 // Calculate U parameter and test bounds
  89                 mStabbedFace.mU = (tvec|pvec) * OneOverDet;
  90 //              if(IR(u)&0x80000000 || u>1.0f)                                  return FALSE;
  91                 if(IS_NEGATIVE_FLOAT(mStabbedFace.mU) || IR(mStabbedFace.mU)>IEEE_1_0)          return FALSE;
  92
  93                 // prepare to test V parameter
  94                 Point qvec = tvec^edge1;
  95
  96                 // Calculate V parameter and test bounds
  97                 mStabbedFace.mV = (mDir|qvec) * OneOverDet;
  98                 if(IS_NEGATIVE_FLOAT(mStabbedFace.mV) || mStabbedFace.mU+mStabbedFace.mV>1.0f)  return FALSE;
  99
 100                 // Calculate t, ray intersects triangle
 101                 mStabbedFace.mDistance = (edge2|qvec) * OneOverDet;
 102                 // Intersection point is valid if distance is positive (else it can just be a face behind the orig point)
 103                 if(IS_NEGATIVE_FLOAT(mStabbedFace.mDistance))                                                           return FALSE;
 104         }
 105         return TRUE;
 106 }