triBoxCheck.cpp

Public Functions

planeBoxOverlap(const Point3F & normal, const Point3F & vert, const Point3F & maxbox)

triBoxOverlap(const Point3F & boxcenter, const Point3F & boxhalfsize, const Point3F triverts)

  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// AABB-triangle overlap test code originally by Tomas Akenine-Möller
 26//               Assisted by Pierre Terdiman and David Hunt
 27// http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/
 28// Ported to TSE by BJG, 2005-4-14
 29// Modified to avoid a lot of copying by ASM, 2007-9-28
 30//-----------------------------------------------------------------------------
 31
 32#include "util/triBoxCheck.h"
 33
 34#define FINDMINMAX(x0,x1,x2,theMin,theMax) \
 35   theMin = theMax = x0;   \
 36   if(x1<theMin) theMin=x1;\
 37   if(x1>theMax) theMax=x1;\
 38   if(x2<theMin) theMin=x2;\
 39   if(x2>theMax) theMax=x2;
 40
 41static bool planeBoxOverlap(const Point3F &normal, const Point3F &vert, const Point3F &maxbox)
 42{
 43   S32 q;
 44   F32 v;
 45   Point3F vmin, vmax;
 46
 47   for(q=0;q<=2;q++)
 48   {
 49      v=vert[q];
 50      if(normal[q]>0.0f)
 51      {
 52         vmin[q]=-maxbox[q] - v;
 53         vmax[q]= maxbox[q] - v;
 54      }
 55      else
 56      {
 57         vmin[q]= maxbox[q] - v;
 58         vmax[q]=-maxbox[q] - v;
 59      }
 60   }
 61
 62   if(mDot(normal, vmin) > 0.f)
 63      return false;
 64
 65   if(mDot(normal, vmax) >= 0.f)
 66      return true;
 67
 68   return false;
 69}
 70
 71
 72/*======================== X-tests ========================*/
 73#define AXISTEST_X01(a, b, fa, fb)           \
 74   p0 = a*v0.y - b*v0.z;                     \
 75   p2 = a*v2.y - b*v2.z;                     \
 76   if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
 77   rad = fa * boxhalfsize.y + fb * boxhalfsize.z;   \
 78   if(min>rad || max<-rad) return false;
 79
 80#define AXISTEST_X2(a, b, fa, fb)            \
 81   p0 = a*v0.y - b*v0.z;                    \
 82   p1 = a*v1.y - b*v1.z;                     \
 83   if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
 84   rad = fa * boxhalfsize.y + fb * boxhalfsize.z;   \
 85   if(min>rad || max<-rad) return false;
 86
 87/*======================== Y-tests ========================*/
 88#define AXISTEST_Y02(a, b, fa, fb)           \
 89   p0 = -a*v0.x + b*v0.z;                 \
 90   p2 = -a*v2.x + b*v2.z;                       \
 91   if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
 92   rad = fa * boxhalfsize.x + fb * boxhalfsize.z;   \
 93   if(min>rad || max<-rad) return false;
 94
 95#define AXISTEST_Y1(a, b, fa, fb)            \
 96   p0 = -a*v0.x + b*v0.z;                 \
 97   p1 = -a*v1.x + b*v1.z;                    \
 98   if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
 99   rad = fa * boxhalfsize.x + fb * boxhalfsize.z;   \
100   if(min>rad || max<-rad) return false;
101
102/*======================== Z-tests ========================*/
103
104#define AXISTEST_Z12(a, b, fa, fb)           \
105   p1 = a*v1.x - b*v1.y;                    \
106   p2 = a*v2.x - b*v2.y;                     \
107   if(p2<p1) {min=p2; max=p1;} else {min=p1; max=p2;} \
108   rad = fa * boxhalfsize.x + fb * boxhalfsize.y;   \
109   if(min>rad || max<-rad) return false;
110
111#define AXISTEST_Z0(a, b, fa, fb)            \
112   p0 = a*v0.x - b*v0.y;               \
113   p1 = a*v1.x - b*v1.y;                    \
114   if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
115   rad = fa * boxhalfsize.x + fb * boxhalfsize.y;   \
116   if(min>rad || max<-rad) return false;
117
118bool triBoxOverlap(const Point3F &boxcenter, const Point3F &boxhalfsize, const Point3F triverts[3])
119{
120   /*    use separating axis theorem to test overlap between triangle and box */
121   /*    need to test for overlap in these directions: */
122   /*    1) the {x,y,z}-directions (actually, since we use the AABB of the triangle */
123   /*       we do not even need to test these) */
124   /*    2) normal of the triangle */
125   /*    3) crossproduct(edge from tri, {x,y,z}-directin) */
126   /*       this gives 3x3=9 more tests */
127
128   Point3F v0,v1,v2;
129
130   F32 min,max,p0,p1,p2,rad,fex,fey,fez;     // -NJMP- "d" local variable removed
131   Point3F normal,e0,e1,e2;
132
133   /* This is the fastest branch on Sun */
134   /* move everything so that the boxcenter is in (0,0,0) */
135   v0 = triverts[0] - boxcenter;
136   v1 = triverts[1] - boxcenter;
137   v2 = triverts[2] - boxcenter;
138
139   /* compute triangle edges */
140   e0 = v1 - v0;      /* tri edge 0 */
141   e1 = v2 - v1;      /* tri edge 1 */
142   e2 = v0 - v2;      /* tri edge 2 */
143
144   /* Bullet 3:  */
145   /*  test the 9 tests first (this was faster) */
146   fex = mFabs(e0.x);
147   fey = mFabs(e0.y);
148   fez = mFabs(e0.z);
149   AXISTEST_X01(e0.z, e0.y, fez, fey);
150   AXISTEST_Y02(e0.z, e0.x, fez, fex);
151   AXISTEST_Z12(e0.y, e0.x, fey, fex);
152
153   fex = mFabs(e1.x);
154   fey = mFabs(e1.y);
155   fez = mFabs(e1.z);
156   AXISTEST_X01(e1.z, e1.y, fez, fey);
157   AXISTEST_Y02(e1.z, e1.x, fez, fex);
158   AXISTEST_Z0(e1.y, e1.x, fey, fex);
159
160   fex = mFabs(e2.x);
161   fey = mFabs(e2.y);
162   fez = mFabs(e2.z);
163   AXISTEST_X2(e2.z, e2.y, fez, fey);
164   AXISTEST_Y1(e2.z, e2.x, fez, fex);
165   AXISTEST_Z12(e2.y, e2.x, fey, fex);
166
167   /* Bullet 1: */
168   /*  first test overlap in the {x,y,z}-directions */
169   /*  find min, max of the triangle each direction, and test for overlap in */
170   /*  that direction -- this is equivalent to testing a minimal AABB around */
171   /*  the triangle against the AABB */
172
173   /* test in X-direction */
174   FINDMINMAX(v0.x,v1.x,v2.x,min,max);
175   if(min>boxhalfsize.x || max<-boxhalfsize.x) return false;
176
177   /* test in Y-direction */
178   FINDMINMAX(v0.y,v1.y,v2.y,min,max);
179   if(min>boxhalfsize.y || max<-boxhalfsize.y) return false;
180
181   /* test in Z-direction */
182   FINDMINMAX(v0.z,v1.z,v2.z,min,max);
183   if(min>boxhalfsize.z || max<-boxhalfsize.z) return false;
184
185   /* Bullet 2: */
186   /*  test if the box intersects the plane of the triangle */
187   /*  compute plane equation of triangle: normal*x+d=0 */
188   normal = mCross(e0, e1);
189
190   if(!planeBoxOverlap(normal,v0,boxhalfsize)) return false;
191
192   return true; /* box and triangle overlaps */
193}
194