3 * 2004-10-27 Stephane Popinet: changed float to double
6 /********************************************************/
7 /* AABB-triangle overlap test code */
8 /* by Tomas Akenine-Möller */
9 /* Function: int triBoxOverlap(float boxcenter[3], */
10 /* float boxhalfsize[3],float triverts[3][3]); */
12 /* 2001-03-05: released the code in its first version */
13 /* 2001-06-18: changed the order of the tests, faster */
15 /* Acknowledgement: Many thanks to Pierre Terdiman for */
16 /* suggestions and discussions on how to optimize code. */
17 /* Thanks to David Hunt for finding a ">="-bug! */
18 /********************************************************/
26 #define CROSS(dest,v1,v2) \
27 dest[0]=v1[1]*v2[2]-v1[2]*v2[1]; \
28 dest[1]=v1[2]*v2[0]-v1[0]*v2[2]; \
29 dest[2]=v1[0]*v2[1]-v1[1]*v2[0];
31 #define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
33 #define SUB(dest,v1,v2) \
34 dest[0]=v1[0]-v2[0]; \
35 dest[1]=v1[1]-v2[1]; \
38 #define FINDMINMAX(x0,x1,x2,min,max) \
45 int planeBoxOverlap(double normal
[3], double vert
[3], double maxbox
[3]) // -NJMP-
48 double vmin
[3],vmax
[3],v
;
54 vmin
[q
]=-maxbox
[q
] - v
; // -NJMP-
55 vmax
[q
]= maxbox
[q
] - v
; // -NJMP-
59 vmin
[q
]= maxbox
[q
] - v
; // -NJMP-
60 vmax
[q
]=-maxbox
[q
] - v
; // -NJMP-
63 if(DOT(normal
,vmin
)>0.0f
) return 0; // -NJMP-
64 if(DOT(normal
,vmax
)>=0.0f
) return 1; // -NJMP-
70 /*======================== X-tests ========================*/
71 #define AXISTEST_X01(a, b, fa, fb) \
72 p0 = a*v0[Y] - b*v0[Z]; \
73 p2 = a*v2[Y] - b*v2[Z]; \
74 if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
75 rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z]; \
76 if(min>rad || max<-rad) return 0;
78 #define AXISTEST_X2(a, b, fa, fb) \
79 p0 = a*v0[Y] - b*v0[Z]; \
80 p1 = a*v1[Y] - b*v1[Z]; \
81 if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
82 rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z]; \
83 if(min>rad || max<-rad) return 0;
85 /*======================== Y-tests ========================*/
86 #define AXISTEST_Y02(a, b, fa, fb) \
87 p0 = -a*v0[X] + b*v0[Z]; \
88 p2 = -a*v2[X] + b*v2[Z]; \
89 if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} \
90 rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z]; \
91 if(min>rad || max<-rad) return 0;
93 #define AXISTEST_Y1(a, b, fa, fb) \
94 p0 = -a*v0[X] + b*v0[Z]; \
95 p1 = -a*v1[X] + b*v1[Z]; \
96 if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
97 rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z]; \
98 if(min>rad || max<-rad) return 0;
100 /*======================== Z-tests ========================*/
102 #define AXISTEST_Z12(a, b, fa, fb) \
103 p1 = a*v1[X] - b*v1[Y]; \
104 p2 = a*v2[X] - b*v2[Y]; \
105 if(p2<p1) {min=p2; max=p1;} else {min=p1; max=p2;} \
106 rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y]; \
107 if(min>rad || max<-rad) return 0;
109 #define AXISTEST_Z0(a, b, fa, fb) \
110 p0 = a*v0[X] - b*v0[Y]; \
111 p1 = a*v1[X] - b*v1[Y]; \
112 if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} \
113 rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y]; \
114 if(min>rad || max<-rad) return 0;
116 int triBoxOverlap(double boxcenter
[3],double boxhalfsize
[3],double triverts
[3][3])
119 /* use separating axis theorem to test overlap between triangle and box */
120 /* need to test for overlap in these directions: */
121 /* 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle */
122 /* we do not even need to test these) */
123 /* 2) normal of the triangle */
124 /* 3) crossproduct(edge from tri, {x,y,z}-directin) */
125 /* this gives 3x3=9 more tests */
126 double v0
[3],v1
[3],v2
[3];
128 double min
,max
,p0
,p1
,p2
,rad
,fex
,fey
,fez
; // -NJMP- "d" local variable removed
129 double normal
[3],e0
[3],e1
[3],e2
[3];
131 /* This is the fastest branch on Sun */
132 /* move everything so that the boxcenter is in (0,0,0) */
133 SUB(v0
,triverts
[0],boxcenter
);
134 SUB(v1
,triverts
[1],boxcenter
);
135 SUB(v2
,triverts
[2],boxcenter
);
137 /* compute triangle edges */
138 SUB(e0
,v1
,v0
); /* tri edge 0 */
139 SUB(e1
,v2
,v1
); /* tri edge 1 */
140 SUB(e2
,v0
,v2
); /* tri edge 2 */
143 /* test the 9 tests first (this was faster) */
147 AXISTEST_X01(e0
[Z
], e0
[Y
], fez
, fey
);
148 AXISTEST_Y02(e0
[Z
], e0
[X
], fez
, fex
);
149 AXISTEST_Z12(e0
[Y
], e0
[X
], fey
, fex
);
154 AXISTEST_X01(e1
[Z
], e1
[Y
], fez
, fey
);
155 AXISTEST_Y02(e1
[Z
], e1
[X
], fez
, fex
);
156 AXISTEST_Z0(e1
[Y
], e1
[X
], fey
, fex
);
161 AXISTEST_X2(e2
[Z
], e2
[Y
], fez
, fey
);
162 AXISTEST_Y1(e2
[Z
], e2
[X
], fez
, fex
);
163 AXISTEST_Z12(e2
[Y
], e2
[X
], fey
, fex
);
166 /* first test overlap in the {x,y,z}-directions */
167 /* find min, max of the triangle each direction, and test for overlap in */
168 /* that direction -- this is equivalent to testing a minimal AABB around */
169 /* the triangle against the AABB */
171 /* test in X-direction */
172 FINDMINMAX(v0
[X
],v1
[X
],v2
[X
],min
,max
);
173 if(min
>boxhalfsize
[X
] || max
<-boxhalfsize
[X
]) return 0;
175 /* test in Y-direction */
176 FINDMINMAX(v0
[Y
],v1
[Y
],v2
[Y
],min
,max
);
177 if(min
>boxhalfsize
[Y
] || max
<-boxhalfsize
[Y
]) return 0;
179 /* test in Z-direction */
180 FINDMINMAX(v0
[Z
],v1
[Z
],v2
[Z
],min
,max
);
181 if(min
>boxhalfsize
[Z
] || max
<-boxhalfsize
[Z
]) return 0;
184 /* test if the box intersects the plane of the triangle */
185 /* compute plane equation of triangle: normal*x+d=0 */
187 // -NJMP- (line removed here)
188 if(!planeBoxOverlap(normal
,v0
,boxhalfsize
)) return 0; // -NJMP-
190 return 1; /* box and triangle overlaps */