aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/ode-0.9/GIMPACT/src/gim_tri_tri_overlap.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/ode-0.9/GIMPACT/src/gim_tri_tri_overlap.cpp')
-rw-r--r--libraries/ode-0.9/GIMPACT/src/gim_tri_tri_overlap.cpp251
1 files changed, 251 insertions, 0 deletions
diff --git a/libraries/ode-0.9/GIMPACT/src/gim_tri_tri_overlap.cpp b/libraries/ode-0.9/GIMPACT/src/gim_tri_tri_overlap.cpp
new file mode 100644
index 0000000..5b4e08d
--- /dev/null
+++ b/libraries/ode-0.9/GIMPACT/src/gim_tri_tri_overlap.cpp
@@ -0,0 +1,251 @@
1
2/*
3-----------------------------------------------------------------------------
4This source file is part of GIMPACT Library.
5
6For the latest info, see http://gimpact.sourceforge.net/
7
8Copyright (c) 2006 Francisco Leon. C.C. 80087371.
9email: projectileman@yahoo.com
10
11 This library is free software; you can redistribute it and/or
12 modify it under the terms of EITHER:
13 (1) The GNU Lesser General Public License as published by the Free
14 Software Foundation; either version 2.1 of the License, or (at
15 your option) any later version. The text of the GNU Lesser
16 General Public License is included with this library in the
17 file GIMPACT-LICENSE-LGPL.TXT.
18 (2) The BSD-style license that is included with this library in
19 the file GIMPACT-LICENSE-BSD.TXT.
20
21 This library is distributed in the hope that it will be useful,
22 but WITHOUT ANY WARRANTY; without even the implied warranty of
23 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
24 GIMPACT-LICENSE-LGPL.TXT and GIMPACT-LICENSE-BSD.TXT for more details.
25
26-----------------------------------------------------------------------------
27*/
28
29#include "GIMPACT/gim_trimesh.h"
30
31
32#define FABS(x) (float(fabs(x))) /* implement as is fastest on your machine */
33
34/* some macros */
35
36#define CLASSIFY_TRIPOINTS_BY_FACE(v1,v2,v3,faceplane,out_of_face)\
37{ \
38 _distances[0] = DISTANCE_PLANE_POINT(faceplane,v1);\
39 _distances[1] = _distances[0] * DISTANCE_PLANE_POINT(faceplane,v2);\
40 _distances[2] = _distances[0] * DISTANCE_PLANE_POINT(faceplane,v3); \
41 if(_distances[1]>0.0f && _distances[2]>0.0f)\
42 {\
43 out_of_face = 1;\
44 }\
45 else\
46 {\
47 out_of_face = 0;\
48 }\
49}\
50
51/* sort so that a<=b */
52#define SORT(a,b) \
53 if(a>b) \
54 { \
55 float c; \
56 c=a; \
57 a=b; \
58 b=c; \
59 }
60
61
62/* this edge to edge test is based on Franlin Antonio's gem:
63 "Faster Line Segment Intersection", in Graphics Gems III,
64 pp. 199-202 */
65#define EDGE_EDGE_TEST(V0,U0,U1) \
66 Bx=U0[i0]-U1[i0]; \
67 By=U0[i1]-U1[i1]; \
68 Cx=V0[i0]-U0[i0]; \
69 Cy=V0[i1]-U0[i1]; \
70 f=Ay*Bx-Ax*By; \
71 d=By*Cx-Bx*Cy; \
72 if((f>0 && d>=0 && d<=f) || (f<0 && d<=0 && d>=f)) \
73 { \
74 e=Ax*Cy-Ay*Cx; \
75 if(f>0) \
76 { \
77 if(e>=0 && e<=f) return 1; \
78 } \
79 else \
80 { \
81 if(e<=0 && e>=f) return 1; \
82 } \
83 }
84
85#define EDGE_AGAINST_TRI_EDGES(V0,V1,U0,U1,U2) \
86{ \
87 float Ax,Ay,Bx,By,Cx,Cy,e,d,f; \
88 Ax=V1[i0]-V0[i0]; \
89 Ay=V1[i1]-V0[i1]; \
90 /* test edge U0,U1 against V0,V1 */ \
91 EDGE_EDGE_TEST(V0,U0,U1); \
92 /* test edge U1,U2 against V0,V1 */ \
93 EDGE_EDGE_TEST(V0,U1,U2); \
94 /* test edge U2,U1 against V0,V1 */ \
95 EDGE_EDGE_TEST(V0,U2,U0); \
96}
97
98#define POINT_IN_TRI(V0,U0,U1,U2) \
99{ \
100 float a,b,c,d0,d1,d2; \
101 /* is T1 completly inside T2? */ \
102 /* check if V0 is inside tri(U0,U1,U2) */ \
103 a=U1[i1]-U0[i1]; \
104 b=-(U1[i0]-U0[i0]); \
105 c=-a*U0[i0]-b*U0[i1]; \
106 d0=a*V0[i0]+b*V0[i1]+c; \
107 \
108 a=U2[i1]-U1[i1]; \
109 b=-(U2[i0]-U1[i0]); \
110 c=-a*U1[i0]-b*U1[i1]; \
111 d1=a*V0[i0]+b*V0[i1]+c; \
112 \
113 a=U0[i1]-U2[i1]; \
114 b=-(U0[i0]-U2[i0]); \
115 c=-a*U2[i0]-b*U2[i1]; \
116 d2=a*V0[i0]+b*V0[i1]+c; \
117 if(d0*d1>0.0) \
118 { \
119 if(d0*d2>0.0) return 1; \
120 } \
121}
122
123int coplanar_tri_tri(GIM_TRIANGLE_DATA *tri1,
124 GIM_TRIANGLE_DATA *tri2)
125{
126 short i0,i1;
127 /* first project onto an axis-aligned plane, that maximizes the area */
128 /* of the triangles, compute indices: i0,i1. */
129 PLANE_MINOR_AXES(tri1->m_planes.m_planes[0], i0, i1);
130
131 /* test all edges of triangle 1 against the edges of triangle 2 */
132 EDGE_AGAINST_TRI_EDGES(tri1->m_vertices[0],tri1->m_vertices[1],tri2->m_vertices[0],tri2->m_vertices[1],tri2->m_vertices[2]);
133 EDGE_AGAINST_TRI_EDGES(tri1->m_vertices[1],tri1->m_vertices[2],tri2->m_vertices[0],tri2->m_vertices[1],tri2->m_vertices[2]);
134 EDGE_AGAINST_TRI_EDGES(tri1->m_vertices[2],tri1->m_vertices[0],tri2->m_vertices[0],tri2->m_vertices[1],tri2->m_vertices[2]);
135
136 /* finally, test if tri1 is totally contained in tri2 or vice versa */
137 POINT_IN_HULL(tri1->m_vertices[0],(&tri2->m_planes.m_planes[1]),3,i0);
138 if(i0==0) return 1;
139
140 POINT_IN_HULL(tri2->m_vertices[0],(&tri1->m_planes.m_planes[1]),3,i0);
141 if(i0==0) return 1;
142
143 return 0;
144}
145
146
147
148#define NEWCOMPUTE_INTERVALS(VV0,VV1,VV2,D0,D1,D2,D0D1,D0D2,A,B,C,X0,X1) \
149{ \
150 if(D0D1>0.0f) \
151 { \
152 /* here we know that D0D2<=0.0 */ \
153 /* that is D0, D1 are on the same side, D2 on the other or on the plane */ \
154 A=VV2; B=(VV0-VV2)*D2; C=(VV1-VV2)*D2; X0=D2-D0; X1=D2-D1; \
155 } \
156 else if(D0D2>0.0f)\
157 { \
158 /* here we know that d0d1<=0.0 */ \
159 A=VV1; B=(VV0-VV1)*D1; C=(VV2-VV1)*D1; X0=D1-D0; X1=D1-D2; \
160 } \
161 else if(D1*D2>0.0f || D0!=0.0f) \
162 { \
163 /* here we know that d0d1<=0.0 or that D0!=0.0 */ \
164 A=VV0; B=(VV1-VV0)*D0; C=(VV2-VV0)*D0; X0=D0-D1; X1=D0-D2; \
165 } \
166 else if(D1!=0.0f) \
167 { \
168 A=VV1; B=(VV0-VV1)*D1; C=(VV2-VV1)*D1; X0=D1-D0; X1=D1-D2; \
169 } \
170 else if(D2!=0.0f) \
171 { \
172 A=VV2; B=(VV0-VV2)*D2; C=(VV1-VV2)*D2; X0=D2-D0; X1=D2-D1; \
173 } \
174 else \
175 { \
176 /* triangles are coplanar */ \
177 return coplanar_tri_tri(tri1,tri2); \
178 } \
179}\
180
181
182
183int gim_triangle_triangle_overlap(
184 GIM_TRIANGLE_DATA *tri1,
185 GIM_TRIANGLE_DATA *tri2)
186{
187 vec3f _distances;
188 char out_of_face;
189 CLASSIFY_TRIPOINTS_BY_FACE(tri1->m_vertices[0],tri1->m_vertices[1],tri1->m_vertices[2],tri2->m_planes.m_planes[0],out_of_face);
190 if(out_of_face==1) return 0;
191
192 CLASSIFY_TRIPOINTS_BY_FACE(tri2->m_vertices[0],tri2->m_vertices[1],tri2->m_vertices[2],tri1->m_planes.m_planes[0],out_of_face);
193 if(out_of_face==1) return 0;
194
195
196 float du0=0,du1=0,du2=0,dv0=0,dv1=0,dv2=0;
197 float D[3];
198 float isect1[2], isect2[2];
199 float du0du1=0,du0du2=0,dv0dv1=0,dv0dv2=0;
200 short index;
201 float vp0,vp1,vp2;
202 float up0,up1,up2;
203 float bb,cc,max;
204
205 /* compute direction of intersection line */
206 VEC_CROSS(D,tri1->m_planes.m_planes[0],tri2->m_planes.m_planes[0]);
207
208 /* compute and index to the largest component of D */
209 max=(float)FABS(D[0]);
210 index=0;
211 bb=(float)FABS(D[1]);
212 cc=(float)FABS(D[2]);
213 if(bb>max) max=bb,index=1;
214 if(cc>max) max=cc,index=2;
215
216 /* this is the simplified projection onto L*/
217 vp0= tri1->m_vertices[0][index];
218 vp1= tri1->m_vertices[1][index];
219 vp2= tri1->m_vertices[2][index];
220
221 up0= tri2->m_vertices[0][index];
222 up1= tri2->m_vertices[1][index];
223 up2= tri2->m_vertices[2][index];
224
225 /* compute interval for triangle 1 */
226 float a,b,c,x0,x1;
227 NEWCOMPUTE_INTERVALS(vp0,vp1,vp2,dv0,dv1,dv2,dv0dv1,dv0dv2,a,b,c,x0,x1);
228
229 /* compute interval for triangle 2 */
230 float d,e,f,y0,y1;
231 NEWCOMPUTE_INTERVALS(up0,up1,up2,du0,du1,du2,du0du1,du0du2,d,e,f,y0,y1);
232
233 float xx,yy,xxyy,tmp;
234 xx=x0*x1;
235 yy=y0*y1;
236 xxyy=xx*yy;
237
238 tmp=a*xxyy;
239 isect1[0]=tmp+b*x1*yy;
240 isect1[1]=tmp+c*x0*yy;
241
242 tmp=d*xxyy;
243 isect2[0]=tmp+e*xx*y1;
244 isect2[1]=tmp+f*xx*y0;
245
246 SORT(isect1[0],isect1[1]);
247 SORT(isect2[0],isect2[1]);
248
249 if(isect1[1]<isect2[0] || isect2[1]<isect1[0]) return 0;
250 return 1;
251}
generated by cgit v1.1 at 2025-02-24 21:57:06 +0000