1//
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions
4// are met:
5// * Redistributions of source code must retain the above copyright
6// notice, this list of conditions and the following disclaimer.
7// * Redistributions in binary form must reproduce the above copyright
8// notice, this list of conditions and the following disclaimer in the
9// documentation and/or other materials provided with the distribution.
10// * Neither the name of NVIDIA CORPORATION nor the names of its
11// contributors may be used to endorse or promote products derived
12// from this software without specific prior written permission.
13//
14// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ''AS IS'' AND ANY
15// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
18// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22// OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25//
26// Copyright (c) 2008-2021 NVIDIA Corporation. All rights reserved.
27// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
28// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
29
30#ifndef GU_INTERSECTION_TRIANGLE_BOX_REF_H
31#define GU_INTERSECTION_TRIANGLE_BOX_REF_H
32
33#include "CmPhysXCommon.h"
34#include "foundation/PxVec3.h"
35
36
37/********************************************************/
38/* AABB-triangle overlap test code */
39/* by Tomas Akenine-M?r */
40/* Function: int triBoxOverlap(float boxcenter[3], */
41/* float boxhalfsize[3],float triverts[3][3]); */
42/* History: */
43/* 2001-03-05: released the code in its first version */
44/* 2001-06-18: changed the order of the tests, faster */
45/* */
46/* Acknowledgement: Many thanks to Pierre Terdiman for */
47/* suggestions and discussions on how to optimize code. */
48/* Thanks to David Hunt for finding a ">="-bug! */
49/********************************************************/
50
51
52namespace physx
53{
54
55#define CROSS(dest,v1,v2) \
56 dest.x=v1.y*v2.z-v1.z*v2.y; \
57 dest.y=v1.z*v2.x-v1.x*v2.z; \
58 dest.z=v1.x*v2.y-v1.y*v2.x;
59
60#define DOT(v1,v2) (v1.x*v2.x+v1.y*v2.y+v1.z*v2.z)
61
62#define FINDMINMAX(x0, x1, x2, minimum, maximum) \
63 minimum = physx::intrinsics::selectMin(x0, x1); \
64 maximum = physx::intrinsics::selectMax(x0, x1); \
65 minimum = physx::intrinsics::selectMin(minimum, x2); \
66 maximum = physx::intrinsics::selectMax(maximum, x2);
67
68 static PX_CUDA_CALLABLE PX_FORCE_INLINE Ps::IntBool planeBoxOverlap(const PxVec3& normal, PxReal d, const PxVec3& maxbox)
69 {
70 PxVec3 vmin, vmax;
71
72 if (normal.x>0.0f)
73 {
74 vmin.x = -maxbox.x;
75 vmax.x = maxbox.x;
76 }
77 else
78 {
79 vmin.x = maxbox.x;
80 vmax.x = -maxbox.x;
81 }
82
83 if (normal.y>0.0f)
84 {
85 vmin.y = -maxbox.y;
86 vmax.y = maxbox.y;
87 }
88 else
89 {
90 vmin.y = maxbox.y;
91 vmax.y = -maxbox.y;
92 }
93
94 if (normal.z>0.0f)
95 {
96 vmin.z = -maxbox.z;
97 vmax.z = maxbox.z;
98 }
99 else
100 {
101 vmin.z = maxbox.z;
102 vmax.z = -maxbox.z;
103 }
104
105 if (normal.dot(v: vmin) + d > 0.0f) return Ps::IntFalse;
106 if (normal.dot(v: vmax) + d >= 0.0f) return Ps::IntTrue;
107 return Ps::IntFalse;
108 }
109
110 /*======================== X-tests ========================*/
111#define AXISTEST_X01(a, b, fa, fb) \
112 p0 = a*v0.y - b*v0.z; \
113 p2 = a*v2.y - b*v2.z; \
114 minimum = physx::intrinsics::selectMin(p0, p2); \
115 maximum = physx::intrinsics::selectMax(p0, p2); \
116 rad = fa * extents.y + fb * extents.z; \
117 if(minimum>rad || maximum<-rad) return Ps::IntFalse;
118
119#define AXISTEST_X2(a, b, fa, fb) \
120 p0 = a*v0.y - b*v0.z; \
121 p1 = a*v1.y - b*v1.z; \
122 minimum = physx::intrinsics::selectMin(p0, p1); \
123 maximum = physx::intrinsics::selectMax(p0, p1); \
124 rad = fa * extents.y + fb * extents.z; \
125 if(minimum>rad || maximum<-rad) return Ps::IntFalse;
126
127 /*======================== Y-tests ========================*/
128#define AXISTEST_Y02(a, b, fa, fb) \
129 p0 = -a*v0.x + b*v0.z; \
130 p2 = -a*v2.x + b*v2.z; \
131 minimum = physx::intrinsics::selectMin(p0, p2); \
132 maximum = physx::intrinsics::selectMax(p0, p2); \
133 rad = fa * extents.x + fb * extents.z; \
134 if(minimum>rad || maximum<-rad) return Ps::IntFalse;
135
136#define AXISTEST_Y1(a, b, fa, fb) \
137 p0 = -a*v0.x + b*v0.z; \
138 p1 = -a*v1.x + b*v1.z; \
139 minimum = physx::intrinsics::selectMin(p0, p1); \
140 maximum = physx::intrinsics::selectMax(p0, p1); \
141 rad = fa * extents.x + fb * extents.z; \
142 if(minimum>rad || maximum<-rad) return Ps::IntFalse;
143
144 /*======================== Z-tests ========================*/
145#define AXISTEST_Z12(a, b, fa, fb) \
146 p1 = a*v1.x - b*v1.y; \
147 p2 = a*v2.x - b*v2.y; \
148 minimum = physx::intrinsics::selectMin(p1, p2); \
149 maximum = physx::intrinsics::selectMax(p1, p2); \
150 rad = fa * extents.x + fb * extents.y; \
151 if(minimum>rad || maximum<-rad) return Ps::IntFalse;
152
153#define AXISTEST_Z0(a, b, fa, fb) \
154 p0 = a*v0.x - b*v0.y; \
155 p1 = a*v1.x - b*v1.y; \
156 minimum = physx::intrinsics::selectMin(p0, p1); \
157 maximum = physx::intrinsics::selectMax(p0, p1); \
158 rad = fa * extents.x + fb * extents.y; \
159 if(minimum>rad || maximum<-rad) return Ps::IntFalse;
160
161 namespace Gu
162 {
163
164 static PX_CUDA_CALLABLE PX_FORCE_INLINE Ps::IntBool intersectTriangleBox_RefImpl(const PxVec3& boxcenter, const PxVec3& extents, const PxVec3& tp0, const PxVec3& tp1, const PxVec3& tp2)
165 {
166 /* use separating axis theorem to test overlap between triangle and box */
167 /* need to test for overlap in these directions: */
168 /* 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle */
169 /* we do not even need to test these) */
170 /* 2) normal of the triangle */
171 /* 3) crossproduct(edge from tri, {x,y,z}-directin) */
172 /* this gives 3x3=9 more tests */
173
174 // This is the fastest branch on Sun - move everything so that the boxcenter is in (0,0,0)
175 const PxVec3 v0 = tp0 - boxcenter;
176 const PxVec3 v1 = tp1 - boxcenter;
177 const PxVec3 v2 = tp2 - boxcenter;
178
179 // compute triangle edges
180 const PxVec3 e0 = v1 - v0; // tri edge 0
181 const PxVec3 e1 = v2 - v1; // tri edge 1
182 const PxVec3 e2 = v0 - v2; // tri edge 2
183
184 float minimum, maximum, rad, p0, p1, p2;
185
186 // Bullet 3: test the 9 tests first (this was faster)
187 float fex = PxAbs(a: e0.x);
188 float fey = PxAbs(a: e0.y);
189 float fez = PxAbs(a: e0.z);
190 AXISTEST_X01(e0.z, e0.y, fez, fey);
191 AXISTEST_Y02(e0.z, e0.x, fez, fex);
192 AXISTEST_Z12(e0.y, e0.x, fey, fex);
193
194 fex = PxAbs(a: e1.x);
195 fey = PxAbs(a: e1.y);
196 fez = PxAbs(a: e1.z);
197 AXISTEST_X01(e1.z, e1.y, fez, fey);
198 AXISTEST_Y02(e1.z, e1.x, fez, fex);
199 AXISTEST_Z0(e1.y, e1.x, fey, fex);
200
201 fex = PxAbs(a: e2.x);
202 fey = PxAbs(a: e2.y);
203 fez = PxAbs(a: e2.z);
204 AXISTEST_X2(e2.z, e2.y, fez, fey);
205 AXISTEST_Y1(e2.z, e2.x, fez, fex);
206 AXISTEST_Z12(e2.y, e2.x, fey, fex);
207
208 // Bullet 1:
209 // first test overlap in the {x,y,z}-directions
210 // find minimum, maximum of the triangle each direction, and test for overlap in
211 // that direction -- this is equivalent to testing a minimal AABB around
212 // the triangle against the AABB
213
214 // test in X-direction
215 FINDMINMAX(v0.x, v1.x, v2.x, minimum, maximum);
216 if (minimum>extents.x || maximum<-extents.x) return Ps::IntFalse;
217
218 // test in Y-direction
219 FINDMINMAX(v0.y, v1.y, v2.y, minimum, maximum);
220 if (minimum>extents.y || maximum<-extents.y) return Ps::IntFalse;
221
222 // test in Z-direction
223 FINDMINMAX(v0.z, v1.z, v2.z, minimum, maximum);
224 if (minimum>extents.z || maximum<-extents.z) return Ps::IntFalse;
225
226 // Bullet 2:
227 // test if the box intersects the plane of the triangle
228 // compute plane equation of triangle: normal*x+d=0
229 PxVec3 normal;
230 CROSS(normal, e0, e1);
231 const float d = -DOT(normal, v0); // plane eq: normal.x+d=0
232 if (!planeBoxOverlap(normal, d, maxbox: extents)) return Ps::IntFalse;
233
234 return Ps::IntTrue; // box and triangle overlaps
235 }
236 }
237
238#undef CROSS
239#undef DOT
240#undef FINDMINMAX
241#undef AXISTEST_X01
242#undef AXISTEST_X2
243#undef AXISTEST_Y02
244#undef AXISTEST_Y1
245#undef AXISTEST_Z12
246#undef AXISTEST_Z0
247
248}
249
250#endif
251
252

source code of qtquick3dphysics/src/3rdparty/PhysX/source/geomutils/include/GuIntersectionTriangleBoxRef.h