1 /* 2 * Copyright (c) 2009-2010 jMonkeyEngine 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 package com.jme3.bounding; 33 34 import com.jme3.math.FastMath; 35 import com.jme3.math.Plane; 36 import com.jme3.math.Vector3f; 37 import com.jme3.util.TempVars; 38 import static java.lang.Math.max; 39 import static java.lang.Math.min; 40 41 /** 42 * This class includes some utility methods for computing intersection 43 * between bounding volumes and triangles. 44 * @author Kirill 45 */ 46 public class Intersection { 47 48 private static final void findMinMax(float x0, float x1, float x2, Vector3f minMax) { 49 minMax.set(x0, x0, 0); 50 if (x1 < minMax.x) { 51 minMax.setX(x1); 52 } 53 if (x1 > minMax.y) { 54 minMax.setY(x1); 55 } 56 if (x2 < minMax.x) { 57 minMax.setX(x2); 58 } 59 if (x2 > minMax.y) { 60 minMax.setY(x2); 61 } 62 } 63 64 // private boolean axisTest(float a, float b, float fa, float fb, Vector3f v0, Vector3f v1, ) 65 // private boolean axisTestX01(float a, float b, float fa, float fb, 66 // Vector3f center, Vector3f ext, 67 // Vector3f v1, Vector3f v2, Vector3f v3){ 68 // float p0 = a * v0.y - b * v0.z; 69 // float p2 = a * v2.y - b * v2.z; 70 // if(p0 < p2){ 71 // min = p0; 72 // max = p2; 73 // } else { 74 // min = p2; 75 // max = p0; 76 // } 77 // float rad = fa * boxhalfsize.y + fb * boxhalfsize.z; 78 // if(min > rad || max < -rad) 79 // return false; 80 // } 81 public static boolean intersect(BoundingBox bbox, Vector3f v1, Vector3f v2, Vector3f v3) { 82 // use separating axis theorem to test overlap between triangle and box 83 // need to test for overlap in these directions: 84 // 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle 85 // we do not even need to test these) 86 // 2) normal of the triangle 87 // 3) crossproduct(edge from tri, {x,y,z}-directin) 88 // this gives 3x3=9 more tests 89 90 TempVars vars = TempVars.get(); 91 92 93 Vector3f tmp0 = vars.vect1, 94 tmp1 = vars.vect2, 95 tmp2 = vars.vect3; 96 97 Vector3f e0 = vars.vect4, 98 e1 = vars.vect5, 99 e2 = vars.vect6; 100 101 Vector3f center = bbox.getCenter(); 102 Vector3f extent = bbox.getExtent(null); 103 104 // float min,max,p0,p1,p2,rad,fex,fey,fez; 105 // float normal[3] 106 107 // This is the fastest branch on Sun 108 // move everything so that the boxcenter is in (0,0,0) 109 v1.subtract(center, tmp0); 110 v2.subtract(center, tmp1); 111 v3.subtract(center, tmp2); 112 113 // compute triangle edges 114 tmp1.subtract(tmp0, e0); // tri edge 0 115 tmp2.subtract(tmp1, e1); // tri edge 1 116 tmp0.subtract(tmp2, e2); // tri edge 2 117 118 // Bullet 3: 119 // test the 9 tests first (this was faster) 120 float min, max; 121 float p0, p1, p2, rad; 122 float fex = FastMath.abs(e0.x); 123 float fey = FastMath.abs(e0.y); 124 float fez = FastMath.abs(e0.z); 125 126 127 128 //AXISTEST_X01(e0[Z], e0[Y], fez, fey); 129 p0 = e0.z * tmp0.y - e0.y * tmp0.z; 130 p2 = e0.z * tmp2.y - e0.y * tmp2.z; 131 min = min(p0, p2); 132 max = max(p0, p2); 133 rad = fez * extent.y + fey * extent.z; 134 if (min > rad || max < -rad) { 135 vars.release(); 136 return false; 137 } 138 139 // AXISTEST_Y02(e0[Z], e0[X], fez, fex); 140 p0 = -e0.z * tmp0.x + e0.x * tmp0.z; 141 p2 = -e0.z * tmp2.x + e0.x * tmp2.z; 142 min = min(p0, p2); 143 max = max(p0, p2); 144 rad = fez * extent.x + fex * extent.z; 145 if (min > rad || max < -rad) { 146 vars.release(); 147 return false; 148 } 149 150 // AXISTEST_Z12(e0[Y], e0[X], fey, fex); 151 p1 = e0.y * tmp1.x - e0.x * tmp1.y; 152 p2 = e0.y * tmp2.x - e0.x * tmp2.y; 153 min = min(p1, p2); 154 max = max(p1, p2); 155 rad = fey * extent.x + fex * extent.y; 156 if (min > rad || max < -rad) { 157 vars.release(); 158 return false; 159 } 160 161 fex = FastMath.abs(e1.x); 162 fey = FastMath.abs(e1.y); 163 fez = FastMath.abs(e1.z); 164 165 // AXISTEST_X01(e1[Z], e1[Y], fez, fey); 166 p0 = e1.z * tmp0.y - e1.y * tmp0.z; 167 p2 = e1.z * tmp2.y - e1.y * tmp2.z; 168 min = min(p0, p2); 169 max = max(p0, p2); 170 rad = fez * extent.y + fey * extent.z; 171 if (min > rad || max < -rad) { 172 vars.release(); 173 return false; 174 } 175 176 // AXISTEST_Y02(e1[Z], e1[X], fez, fex); 177 p0 = -e1.z * tmp0.x + e1.x * tmp0.z; 178 p2 = -e1.z * tmp2.x + e1.x * tmp2.z; 179 min = min(p0, p2); 180 max = max(p0, p2); 181 rad = fez * extent.x + fex * extent.z; 182 if (min > rad || max < -rad) { 183 vars.release(); 184 return false; 185 } 186 187 // AXISTEST_Z0(e1[Y], e1[X], fey, fex); 188 p0 = e1.y * tmp0.x - e1.x * tmp0.y; 189 p1 = e1.y * tmp1.x - e1.x * tmp1.y; 190 min = min(p0, p1); 191 max = max(p0, p1); 192 rad = fey * extent.x + fex * extent.y; 193 if (min > rad || max < -rad) { 194 vars.release(); 195 return false; 196 } 197 // 198 fex = FastMath.abs(e2.x); 199 fey = FastMath.abs(e2.y); 200 fez = FastMath.abs(e2.z); 201 202 // AXISTEST_X2(e2[Z], e2[Y], fez, fey); 203 p0 = e2.z * tmp0.y - e2.y * tmp0.z; 204 p1 = e2.z * tmp1.y - e2.y * tmp1.z; 205 min = min(p0, p1); 206 max = max(p0, p1); 207 rad = fez * extent.y + fey * extent.z; 208 if (min > rad || max < -rad) { 209 vars.release(); 210 return false; 211 } 212 213 // AXISTEST_Y1(e2[Z], e2[X], fez, fex); 214 p0 = -e2.z * tmp0.x + e2.x * tmp0.z; 215 p1 = -e2.z * tmp1.x + e2.x * tmp1.z; 216 min = min(p0, p1); 217 max = max(p0, p1); 218 rad = fez * extent.x + fex * extent.y; 219 if (min > rad || max < -rad) { 220 vars.release(); 221 return false; 222 } 223 224 // AXISTEST_Z12(e2[Y], e2[X], fey, fex); 225 p1 = e2.y * tmp1.x - e2.x * tmp1.y; 226 p2 = e2.y * tmp2.x - e2.x * tmp2.y; 227 min = min(p1, p2); 228 max = max(p1, p2); 229 rad = fey * extent.x + fex * extent.y; 230 if (min > rad || max < -rad) { 231 vars.release(); 232 return false; 233 } 234 235 // Bullet 1: 236 // first test overlap in the {x,y,z}-directions 237 // find min, max of the triangle each direction, and test for overlap in 238 // that direction -- this is equivalent to testing a minimal AABB around 239 // the triangle against the AABB 240 241 242 Vector3f minMax = vars.vect7; 243 244 // test in X-direction 245 findMinMax(tmp0.x, tmp1.x, tmp2.x, minMax); 246 if (minMax.x > extent.x || minMax.y < -extent.x) { 247 vars.release(); 248 return false; 249 } 250 251 // test in Y-direction 252 findMinMax(tmp0.y, tmp1.y, tmp2.y, minMax); 253 if (minMax.x > extent.y || minMax.y < -extent.y) { 254 vars.release(); 255 return false; 256 } 257 258 // test in Z-direction 259 findMinMax(tmp0.z, tmp1.z, tmp2.z, minMax); 260 if (minMax.x > extent.z || minMax.y < -extent.z) { 261 vars.release(); 262 return false; 263 } 264 265 // // Bullet 2: 266 // // test if the box intersects the plane of the triangle 267 // // compute plane equation of triangle: normal * x + d = 0 268 // Vector3f normal = new Vector3f(); 269 // e0.cross(e1, normal); 270 Plane p = vars.plane; 271 272 p.setPlanePoints(v1, v2, v3); 273 if (bbox.whichSide(p) == Plane.Side.Negative) { 274 vars.release(); 275 return false; 276 } 277 // 278 // if(!planeBoxOverlap(normal,v0,boxhalfsize)) return false; 279 280 vars.release(); 281 282 return true; /* box and triangle overlaps */ 283 } 284 } 285
