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 */
32package com.jme3.bounding;
33
34import com.jme3.math.FastMath;
35import com.jme3.math.Plane;
36import com.jme3.math.Vector3f;
37import com.jme3.util.TempVars;
38import static java.lang.Math.max;
39import 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 */
46public 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