afxTriBoxCheck2D_T3D.cpp

Public Functions

afxTriBoxOverlap2D(const Point3F & boxcenter, const Point3F & boxhalfsize, const Point3F & a, const Point3F & b, const Point3F & c)

  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// Arcane-FX for MIT Licensed Open Source version of Torque 3D from GarageGames
 26// Copyright (C) 2015 Faust Logic, Inc.
 27//
 28// Adapted to a 2D test for intersecting atlas triangles with zodiacs.
 29//~~~~~~~~~~~~~~~~~~~~//~~~~~~~~~~~~~~~~~~~~//~~~~~~~~~~~~~~~~~~~~//~~~~~~~~~~~~~~~~~~~~~//
 30
 31//-----------------------------------------------------------------------------
 32// AABB-triangle overlap test code originally by Tomas Akenine-Möller
 33//               Assisted by Pierre Terdiman and David Hunt
 34// http://www.cs.lth.se/home/Tomas_Akenine_Moller/code/
 35// Ported to TSE by BJG, 2005-4-14
 36//-----------------------------------------------------------------------------
 37
 38#include "afx/arcaneFX.h"
 39#include "afx/util/afxTriBoxCheck2D_T3D.h"
 40
 41#define FINDMINMAX(x0,x1,x2,min,max) \
 42   min = max = x0;   \
 43   if(x1<min) min=x1;\
 44   if(x1>max) max=x1;\
 45   if(x2<min) min=x2;\
 46   if(x2>max) max=x2;
 47
 48/*======================== Z-tests ========================*/
 49
 50#define AXISTEST_Z12(a, b, fa, fb)           \
 51   p1 = a*v1.x - b*v1.y;                    \
 52   p2 = a*v2.x - b*v2.y;                     \
 53   if(p2<p1) {min=p2; max=p1;} else {min=p1; max=p2;} \
 54   rad = fa * boxhalfsize.x + fb * boxhalfsize.y;   \
 55   if(min>rad || max<-rad) return false;
 56
 57#define AXISTEST_Z0(a, b, fa, fb)            \
 58   p0 = a*v0.x - b*v0.y;               \
 59   p1 = a*v1.x - b*v1.y;                    \
 60   if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
 61   rad = fa * boxhalfsize.x + fb * boxhalfsize.y;   \
 62   if(min>rad || max<-rad) return false;
 63
 64bool afxTriBoxOverlap2D(const Point3F& boxcenter, const Point3F& boxhalfsize, const Point3F& a, const Point3F& b, const Point3F& c)
 65{
 66   /*    use separating axis theorem to test overlap between triangle and box */
 67   /*    need to test for overlap in these directions: */
 68   /*    1) the {x,y,z}-directions (actually, since we use the AABB of the triangle */
 69   /*       we do not even need to test these) */
 70   /*    2) normal of the triangle */
 71   /*    3) crossproduct(edge from tri, {x,y,z}-directin) */
 72   /*       this gives 3x3=9 more tests */
 73
 74   F32 min,max,p0,p1,p2,rad;
 75
 76   /* move everything so that the boxcenter is in (0,0,0) */
 77   Point3F v0 = a - boxcenter;
 78   Point3F v1 = b - boxcenter;
 79   Point3F v2 = c - boxcenter;
 80
 81   /* compute triangle edges */
 82   Point3F e0 = v1 - v0;      /* tri edge 0 */
 83   Point3F e1 = v2 - v1;      /* tri edge 1 */
 84   Point3F e2 = v0 - v2;      /* tri edge 2 */
 85
 86   /* Bullet 3:  */
 87   /*  test the 3 tests first */
 88   F32 fex = mFabs(e0.x);
 89   F32 fey = mFabs(e0.y);
 90   AXISTEST_Z12(e0.y, e0.x, fey, fex);
 91
 92   fex = mFabs(e1.x);
 93   fey = mFabs(e1.y);
 94   AXISTEST_Z0(e1.y, e1.x, fey, fex);
 95
 96   fex = mFabs(e2.x);
 97   fey = mFabs(e2.y);
 98   AXISTEST_Z12(e2.y, e2.x, fey, fex);
 99
100   /* Bullet 1: */
101   /*  first test overlap in the {x,y,z}-directions */
102   /*  find min, max of the triangle each direction, and test for overlap in */
103   /*  that direction -- this is equivalent to testing a minimal AABB around */
104   /*  the triangle against the AABB */
105
106   /* test in X-direction */
107   FINDMINMAX(v0.x,v1.x,v2.x,min,max);
108   if(min>boxhalfsize.x || max<-boxhalfsize.x) return false;
109
110   /* test in Y-direction */
111   FINDMINMAX(v0.y,v1.y,v2.y,min,max);
112   if(min>boxhalfsize.y || max<-boxhalfsize.y) return false;
113
114   return true; /* box and triangle overlaps */
115}
116
117