← Back to branch summary

~ubuntu-branches/debian/sid/ember/sid

« back to all changes in this revision

Viewing changes to src/components/ogre/ogreopcode/src/OgreOpcodeMath.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Michael Koch
  • Date: 2009-07-23 07:46:40 UTC
  • Revision ID: james.westby@ubuntu.com-20090723074640-wh0ukzis0kda36qv
Tags: upstream-0.5.6
Import upstream version 0.5.6

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/components/ogre/ogreopcode/src/OgreOpcodeMath.cpp
 
1
///////////////////////////////////////////////////////////////////////////////
 
2
///  @file OgreOpcodeMath.cpp
 
3
///  @brief Triangle Intersection routines
 
4
///
 
5
///  @author The OgreOpcode Team
 
6
///
 
7
///////////////////////////////////////////////////////////////////////////////
 
8
///
 
9
///  This file is part of OgreOpcode.
 
10
///
 
11
///  A lot of the code is based on the Nebula Opcode Collision module, see docs/Nebula_license.txt
 
12
///
 
13
///  OgreOpcode is free software; you can redistribute it and/or
 
14
///  modify it under the terms of the GNU Lesser General Public
 
15
///  License as published by the Free Software Foundation; either
 
16
///  version 2.1 of the License, or (at your option) any later version.
 
17
///
 
18
///  OgreOpcode is distributed in the hope that it will be useful,
 
19
///  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
20
///  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
21
///  Lesser General Public License for more details.
 
22
///
 
23
///  You should have received a copy of the GNU Lesser General Public
 
24
///  License along with OgreOpcode; if not, write to the Free Software
 
25
///  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
26
///
 
27
///////////////////////////////////////////////////////////////////////////////
 
28
 
 
29
#include "OgreOpcodeMath.h"
 
30
 
 
31
using namespace Ogre;
 
32
namespace OgreOpcode
 
33
{
 
34
        namespace Details
 
35
        {
 
36
#define SMALL_EPSILON 0.000001f
 
37
 
 
38
#define FABS(x) (fabsf(x))        /* implement as is fastest on your machine */
 
39
 
 
40
                /* if USE_EPSILON_TEST is true then we do a check: 
 
41
                if |dv|<SMALL_EPSILON then dv=0.0;
 
42
                else no check is done (which is less robust)
 
43
                */
 
44
#define USE_EPSILON_TEST TRUE  
 
45
 
 
46
                /* some macros */
 
47
 
 
48
                /* sort so that a<=b */
 
49
#define SORT(a,b)       \
 
50
        if(a>b)    \
 
51
                {          \
 
52
                float c; \
 
53
                c=a;     \
 
54
                a=b;     \
 
55
                b=c;     \
 
56
        }
 
57
 
 
58
                /* this edge to edge test is based on Franlin Antonio's gem:
 
59
                "Faster Line Segment Intersection", in Graphics Gems III,
 
60
                pp. 199-202 */ 
 
61
#define EDGE_EDGE_TEST(V0,U0,U1)                      \
 
62
        Bx=U0[i0]-U1[i0];                                   \
 
63
        By=U0[i1]-U1[i1];                                   \
 
64
        Cx=V0[i0]-U0[i0];                                   \
 
65
        Cy=V0[i1]-U0[i1];                                   \
 
66
        f=Ay*Bx-Ax*By;                                      \
 
67
        d=By*Cx-Bx*Cy;                                      \
 
68
        if((f>0 && d>=0 && d<=f) || (f<0 && d<=0 && d>=f))  \
 
69
                {                                                   \
 
70
                e=Ax*Cy-Ay*Cx;                                    \
 
71
                if(f>0)                                           \
 
72
                {                                                 \
 
73
                if(e>=0 && e<=f) return true;                   \
 
74
        }                                                 \
 
75
        else                                              \
 
76
                {                                                 \
 
77
                if(e<=0 && e>=f) return true;                   \
 
78
        }                                                 \
 
79
        }                                
 
80
 
 
81
#define EDGE_AGAINST_TRI_EDGES(V0,V1,U0,U1,U2) \
 
82
                {                                              \
 
83
                float Ax,Ay,Bx,By,Cx,Cy,e,d,f;               \
 
84
                Ax=V1[i0]-V0[i0];                            \
 
85
                Ay=V1[i1]-V0[i1];                            \
 
86
                /* test edge U0,U1 against V0,V1 */          \
 
87
                EDGE_EDGE_TEST(V0,U0,U1);                    \
 
88
                /* test edge U1,U2 against V0,V1 */          \
 
89
                EDGE_EDGE_TEST(V0,U1,U2);                    \
 
90
                /* test edge U2,U1 against V0,V1 */          \
 
91
                EDGE_EDGE_TEST(V0,U2,U0);                    \
 
92
        }
 
93
 
 
94
#define POINT_IN_TRI(V0,U0,U1,U2)           \
 
95
                {                                           \
 
96
                float a,b,c,d0,d1,d2;                     \
 
97
                /* is T1 completly inside T2? */          \
 
98
                /* check if V0 is inside tri(U0,U1,U2) */ \
 
99
                a=U1[i1]-U0[i1];                          \
 
100
                b=-(U1[i0]-U0[i0]);                       \
 
101
                c=-a*U0[i0]-b*U0[i1];                     \
 
102
                d0=a*V0[i0]+b*V0[i1]+c;                   \
 
103
                \
 
104
                a=U2[i1]-U1[i1];                          \
 
105
                b=-(U2[i0]-U1[i0]);                       \
 
106
                c=-a*U1[i0]-b*U1[i1];                     \
 
107
                d1=a*V0[i0]+b*V0[i1]+c;                   \
 
108
                \
 
109
                a=U0[i1]-U2[i1];                          \
 
110
                b=-(U0[i0]-U2[i0]);                       \
 
111
                c=-a*U2[i0]-b*U2[i1];                     \
 
112
                d2=a*V0[i0]+b*V0[i1]+c;                   \
 
113
                if(d0*d1>0.0)                             \
 
114
                {                                         \
 
115
                if(d0*d2>0.0) return true;              \
 
116
        }                                         \
 
117
        }
 
118
 
 
119
                static bool coplanar_tri_tri(const Vector3& N, const Vector3 tri1[3],
 
120
                        const Vector3 tri2[3])
 
121
                {
 
122
                        float A[3];
 
123
                        short i0,i1;
 
124
                        /* first project onto an axis-aligned plane, that maximizes the area */
 
125
                        /* of the triangles, compute indices: i0,i1. */
 
126
                        A[0]=fabs(N[0]);
 
127
                        A[1]=fabs(N[1]);
 
128
                        A[2]=fabs(N[2]);
 
129
                        if(A[0]>A[1])
 
130
                        {
 
131
                                if(A[0]>A[2])  
 
132
                                {
 
133
                                        i0=1;      /* A[0] is greatest */
 
134
                                        i1=2;
 
135
                                }
 
136
                                else
 
137
                                {
 
138
                                        i0=0;      /* A[2] is greatest */
 
139
                                        i1=1;
 
140
                                }
 
141
                        }
 
142
                        else   /* A[0]<=A[1] */
 
143
                        {
 
144
                                if(A[2]>A[1])
 
145
                                {
 
146
                                        i0=0;      /* A[2] is greatest */
 
147
                                        i1=1;                                           
 
148
                                }
 
149
                                else
 
150
                                {
 
151
                                        i0=0;      /* A[1] is greatest */
 
152
                                        i1=2;
 
153
                                }
 
154
                        }               
 
155
 
 
156
                        /* test all edges of triangle 1 against the edges of triangle 2 */
 
157
                        EDGE_AGAINST_TRI_EDGES(tri1[0],tri1[1],tri2[0],tri2[1],tri2[2]);
 
158
                        EDGE_AGAINST_TRI_EDGES(tri1[1],tri1[2],tri2[0],tri2[1],tri2[2]);
 
159
                        EDGE_AGAINST_TRI_EDGES(tri1[2],tri1[0],tri2[0],tri2[1],tri2[2]);
 
160
 
 
161
                        /* finally, test if tri1 is totally contained in tri2 or vice versa */
 
162
                        POINT_IN_TRI(tri1[0],tri2[0],tri2[1],tri2[2]);
 
163
                        POINT_IN_TRI(tri2[0],tri1[0],tri1[1],tri1[2]);
 
164
 
 
165
                        return false;
 
166
                }
 
167
 
 
168
#define NEWCOMPUTE_INTERVALS(VV0,VV1,VV2,D0,D1,D2,D0D1,D0D2,A,B,C,X0,X1) \
 
169
                { \
 
170
                if(D0D1>0.0f) \
 
171
                { \
 
172
                /* here we know that D0D2<=0.0 */ \
 
173
                /* that is D0, D1 are on the same side, D2 on the other or on the plane */ \
 
174
                A=VV2; B=(VV0-VV2)*D2; C=(VV1-VV2)*D2; X0=D2-D0; X1=D2-D1; \
 
175
                } \
 
176
        else if(D0D2>0.0f)\
 
177
                { \
 
178
                /* here we know that d0d1<=0.0 */ \
 
179
                A=VV1; B=(VV0-VV1)*D1; C=(VV2-VV1)*D1; X0=D1-D0; X1=D1-D2; \
 
180
                } \
 
181
        else if(D1*D2>0.0f || D0!=0.0f) \
 
182
                { \
 
183
                /* here we know that d0d1<=0.0 or that D0!=0.0 */ \
 
184
                A=VV0; B=(VV1-VV0)*D0; C=(VV2-VV0)*D0; X0=D0-D1; X1=D0-D2; \
 
185
                } \
 
186
        else if(D1!=0.0f) \
 
187
                { \
 
188
                A=VV1; B=(VV0-VV1)*D1; C=(VV2-VV1)*D1; X0=D1-D0; X1=D1-D2; \
 
189
                } \
 
190
        else if(D2!=0.0f) \
 
191
                { \
 
192
                A=VV2; B=(VV0-VV2)*D2; C=(VV1-VV2)*D2; X0=D2-D0; X1=D2-D1; \
 
193
                } \
 
194
        else \
 
195
                { \
 
196
                /* triangles are coplanar */ \
 
197
                return coplanar_tri_tri(N1,tri1,tri2); \
 
198
                } \
 
199
                }
 
200
 
 
201
                /**
 
202
                * Tests if two triangles intersect (without divisions)
 
203
                *
 
204
                * @param tri1 Vertices of triangle 1
 
205
                * @param tri2 Vertices of triangle 2
 
206
                * @return true if the triangles intersect, otherwise false
 
207
                *
 
208
                */
 
209
 
 
210
                bool Intersect3::triangleTriangle(const Vector3 tri1[3],
 
211
                        const Vector3 tri2[3])
 
212
                {
 
213
                        Vector3 E1,E2;
 
214
                        Vector3 N1,N2;
 
215
                        float d1,d2;
 
216
                        float du0,du1,du2,dv0,dv1,dv2;
 
217
                        Vector3 D;
 
218
                        float isect1[2], isect2[2];
 
219
                        float du0du1,du0du2,dv0dv1,dv0dv2;
 
220
                        short index;
 
221
                        float vp0,vp1,vp2;
 
222
                        float up0,up1,up2;
 
223
                        float bb,cc,max;
 
224
                        float a,b,c,x0,x1;
 
225
                        float d,e,f,y0,y1;
 
226
                        float xx,yy,xxyy,tmp;
 
227
 
 
228
                        /* compute plane equation of triangle(tri1) */
 
229
                        E1 = tri1[1] - tri1[0];
 
230
                        E2 = tri1[2] - tri1[0];
 
231
                        N1 = E1.crossProduct(E2);
 
232
                        d1=-(N1.dotProduct(tri1[0]));
 
233
                        /* plane equation 1: N1.X+d1=0 */
 
234
 
 
235
                        /* put tri2 into plane equation 1 to compute signed distances to the plane*/
 
236
                        du0=(N1.dotProduct(tri2[0]))+d1;
 
237
                        du1=(N1.dotProduct(tri2[1]))+d1;
 
238
                        du2=(N1.dotProduct(tri2[2]))+d1;
 
239
 
 
240
                        /* coplanarity robustness check */
 
241
#if USE_EPSILON_TEST==TRUE
 
242
                        if(FABS(du0)<SMALL_EPSILON) du0=0.0;
 
243
                        if(FABS(du1)<SMALL_EPSILON) du1=0.0;
 
244
                        if(FABS(du2)<SMALL_EPSILON) du2=0.0;
 
245
#endif
 
246
                        du0du1=du0*du1;
 
247
                        du0du2=du0*du2;
 
248
 
 
249
                        if(du0du1>0.0f && du0du2>0.0f) /* same sign on all of them + not equal 0 ? */
 
250
                                return 0;                    /* no intersection occurs */
 
251
 
 
252
                        /* compute plane of triangle (tri2) */
 
253
                        E1 = tri2[1] - tri2[0];
 
254
                        E2 = tri2[2] - tri2[0];
 
255
                        N2 = E1.crossProduct(E2);
 
256
                        d2=-(N2.dotProduct(tri2[0]));
 
257
                        /* plane equation 2: N2.X+d2=0 */
 
258
 
 
259
                        /* put tri1 into plane equation 2 */
 
260
                        dv0=(N2.dotProduct(tri1[0]))+d2;
 
261
                        dv1=(N2.dotProduct(tri1[1]))+d2;
 
262
                        dv2=(N2.dotProduct(tri1[2]))+d2;
 
263
 
 
264
#if USE_EPSILON_TEST==TRUE
 
265
                        if(FABS(dv0)<SMALL_EPSILON) dv0=0.0;
 
266
                        if(FABS(dv1)<SMALL_EPSILON) dv1=0.0;
 
267
                        if(FABS(dv2)<SMALL_EPSILON) dv2=0.0;
 
268
#endif
 
269
 
 
270
                        dv0dv1=dv0*dv1;
 
271
                        dv0dv2=dv0*dv2;
 
272
 
 
273
                        if(dv0dv1>0.0f && dv0dv2>0.0f) /* same sign on all of them + not equal 0 ? */
 
274
                                return 0;                    /* no intersection occurs */
 
275
 
 
276
                        /* compute direction of intersection line */
 
277
                        D = N1.crossProduct(N2);
 
278
 
 
279
                        /* compute and index to the largest component of D */
 
280
                        max=(float)FABS(D[0]);
 
281
                        index=0;
 
282
                        bb=(float)FABS(D[1]);
 
283
                        cc=(float)FABS(D[2]);
 
284
                        if(bb>max) max=bb,index=1;
 
285
                        if(cc>max) max=cc,index=2;
 
286
 
 
287
                        /* this is the simplified projection onto L*/
 
288
                        vp0=tri1[0][index];
 
289
                        vp1=tri1[1][index];
 
290
                        vp2=tri1[2][index];
 
291
 
 
292
                        up0=tri2[0][index];
 
293
                        up1=tri2[1][index];
 
294
                        up2=tri2[2][index];
 
295
 
 
296
                        /* compute interval for triangle 1 */
 
297
                        NEWCOMPUTE_INTERVALS(vp0,vp1,vp2,dv0,dv1,dv2,dv0dv1,dv0dv2,a,b,c,x0,x1);
 
298
 
 
299
                        /* compute interval for triangle 2 */
 
300
                        NEWCOMPUTE_INTERVALS(up0,up1,up2,du0,du1,du2,du0du1,du0du2,d,e,f,y0,y1);
 
301
 
 
302
                        xx=x0*x1;
 
303
                        yy=y0*y1;
 
304
                        xxyy=xx*yy;
 
305
 
 
306
                        tmp=a*xxyy;
 
307
                        isect1[0]=tmp+b*x1*yy;
 
308
                        isect1[1]=tmp+c*x0*yy;
 
309
 
 
310
                        tmp=d*xxyy;
 
311
                        isect2[0]=tmp+e*xx*y1;
 
312
                        isect2[1]=tmp+f*xx*y0;
 
313
 
 
314
                        SORT(isect1[0],isect1[1]);
 
315
                        SORT(isect2[0],isect2[1]);
 
316
 
 
317
                        if(isect1[1]<isect2[0] || isect2[1]<isect1[0]) return false;
 
318
                        return true;
 
319
                }
 
320
 
 
321
                /* sort so that a<=b */
 
322
#define SORT2(a,b,smallest)       \
 
323
        if(a>b)       \
 
324
                {             \
 
325
                float c;    \
 
326
                c=a;        \
 
327
                a=b;        \
 
328
                b=c;        \
 
329
                smallest=1; \
 
330
                }             \
 
331
        else smallest=0;
 
332
 
 
333
 
 
334
                static inline void isect2(const Vector3 tri[3],float VV0,float VV1,float VV2,
 
335
                        float D0,float D1,float D2,float *isect0,float *isect1,Vector3 isectline[2])
 
336
                {
 
337
                        float tmp=D0/(D0-D1);          
 
338
                        Vector3 diff;
 
339
                        *isect0=VV0+(VV1-VV0)*tmp;         
 
340
                        diff = tri[1] - tri[0];              
 
341
                        diff = diff * tmp;               
 
342
                        isectline[0] = diff + tri[0];        
 
343
                        tmp=D0/(D0-D2);                    
 
344
                        *isect1=VV0+(VV2-VV0)*tmp;          
 
345
                        diff = tri[2] - tri[0];                   
 
346
                        diff = diff * tmp;                 
 
347
                        isectline[1] = tri[0] + diff;          
 
348
                }
 
349
 
 
350
 
 
351
                static inline bool compute_intervals_isectline(const Vector3 tri[3],
 
352
                        float VV0,float VV1,float VV2,float D0,float D1,float D2,
 
353
                        float D0D1,float D0D2,float *isect0,float *isect1,
 
354
                        Vector3 isectline[2])
 
355
                {
 
356
                        if(D0D1>0.0f)                                        
 
357
                        {                                                    
 
358
                                /* here we know that D0D2<=0.0 */                  
 
359
                                /* that is D0, D1 are on the same side, D2 on the other or on the plane */
 
360
                                Vector3 newTri[3] = {tri[2], tri[0], tri[1]};
 
361
                                isect2(newTri,VV2,VV0,VV1,D2,D0,D1,isect0,isect1,isectline);
 
362
                        } 
 
363
                        else if(D0D2>0.0f)                                   
 
364
                        {   
 
365
                                Vector3 newTri[3] = {tri[1], tri[0], tri[2]};
 
366
                                /* here we know that d0d1<=0.0 */             
 
367
                                isect2(newTri,VV1,VV0,VV2,D1,D0,D2,isect0,isect1,isectline);
 
368
                        }                                                  
 
369
                        else if(D1*D2>0.0f || D0!=0.0f)   
 
370
                        {        
 
371
                                Vector3 newTri[3] = {tri[0], tri[1], tri[2]};
 
372
                                /* here we know that d0d1<=0.0 or that D0!=0.0 */
 
373
                                isect2(newTri,VV0,VV1,VV2,D0,D1,D2,isect0,isect1,isectline);   
 
374
                        }                                                  
 
375
                        else if(D1!=0.0f)                                  
 
376
                        {             
 
377
                                Vector3 newTri[3] = {tri[1], tri[0], tri[2]};
 
378
                                isect2(newTri,VV1,VV0,VV2,D1,D0,D2,isect0,isect1,isectline); 
 
379
                        }                                         
 
380
                        else if(D2!=0.0f)                                  
 
381
                        {                  
 
382
                                Vector3 newTri[3] = {tri[2], tri[0], tri[1]};
 
383
                                isect2(newTri,VV2,VV0,VV1,D2,D0,D1,isect0,isect1,isectline);     
 
384
                        }                                                 
 
385
                        else                                               
 
386
                        {                                                   
 
387
                                /* triangles are coplanar */    
 
388
                                return 1;
 
389
                        }
 
390
                        return 0;
 
391
                }
 
392
 
 
393
#define COMPUTE_INTERVALS_ISECTLINE(VERT0,VERT1,VERT2,VV0,VV1,VV2,D0,D1,D2,D0D1,D0D2,isect0,isect1,isectpoint0,isectpoint1) \
 
394
        if(D0D1>0.0f)                                         \
 
395
                {                                                     \
 
396
                /* here we know that D0D2<=0.0 */                   \
 
397
                /* that is D0, D1 are on the same side, D2 on the other or on the plane */ \
 
398
                isect2(VERT2,VERT0,VERT1,VV2,VV0,VV1,D2,D0,D1,&isect0,&isect1,isectpoint0,isectpoint1);          \
 
399
                }                                                     
 
400
#if 0
 
401
        else if(D0D2>0.0f)                                    \
 
402
        {                                                     \
 
403
        /* here we know that d0d1<=0.0 */                   \
 
404
        isect2(VERT1,VERT0,VERT2,VV1,VV0,VV2,D1,D0,D2,&isect0,&isect1,isectpoint0,isectpoint1);          \
 
405
        }                                                     \
 
406
        else if(D1*D2>0.0f || D0!=0.0f)                       \
 
407
        {                                                     \
 
408
        /* here we know that d0d1<=0.0 or that D0!=0.0 */   \
 
409
        isect2(VERT0,VERT1,VERT2,VV0,VV1,VV2,D0,D1,D2,&isect0,&isect1,isectpoint0,isectpoint1);          \
 
410
        }                                                     \
 
411
        else if(D1!=0.0f)                                     \
 
412
        {                                                     \
 
413
        isect2(VERT1,VERT0,VERT2,VV1,VV0,VV2,D1,D0,D2,&isect0,&isect1,isectpoint0,isectpoint1);          \
 
414
        }                                                     \
 
415
        else if(D2!=0.0f)                                     \
 
416
        {                                                     \
 
417
        isect2(VERT2,VERT0,VERT1,VV2,VV0,VV1,D2,D0,D1,&isect0,&isect1,isectpoint0,isectpoint1);          \
 
418
        }                                                     \
 
419
        else                                                  \
 
420
        {                                                     \
 
421
        /* triangles are coplanar */                        \
 
422
        coplanar=1;                                         \
 
423
        return coplanar_tri_tri(N1,V0,V1,V2,U0,U1,U2);      \
 
424
        }
 
425
#endif
 
426
 
 
427
        /**
 
428
        * Tests if two triangles intersect and compute the line of intersection
 
429
        * (if they are not coplanar).
 
430
        *
 
431
        * @param tri1 Vertices of triangle 1
 
432
        * @param tri2 Vertices of triangle 2
 
433
        * @param[out] isectline The line segment where they intersect
 
434
        * @param[out] coplanar Returns whether the triangles are coplanar
 
435
        * @return true if the triangles intersect, otherwise false
 
436
        *
 
437
        */
 
438
 
 
439
        bool Intersect3::triangleTriangle(const Vector3 tri1[3],
 
440
                const Vector3 tri2[3],
 
441
                Segment3& isectline, bool& coplanar)
 
442
        {
 
443
                Vector3 E1,E2;
 
444
                Vector3 N1,N2;
 
445
                float d1,d2;
 
446
                float du0,du1,du2,dv0,dv1,dv2;
 
447
                Vector3 D;
 
448
                float isect1[2] = {0,0}, isect2[2] = {0,0};
 
449
                Vector3 isectpointA[2];
 
450
                Vector3 isectpointB[2];
 
451
                float du0du1,du0du2,dv0dv1,dv0dv2;
 
452
                short index;
 
453
                float vp0,vp1,vp2;
 
454
                float up0,up1,up2;
 
455
                float b,c,max;
 
456
                int smallest1,smallest2;
 
457
 
 
458
                /* compute plane equation of triangle(tri1) */
 
459
                E1 = tri1[1] - tri1[0];
 
460
                E2 = tri1[2] - tri1[0];
 
461
                N1 = E1.crossProduct(E2);
 
462
                d1 =-(N1.dotProduct(tri1[0]));
 
463
                /* plane equation 1: N1.X+d1=0 */
 
464
 
 
465
                /* put tri2 into plane equation 1 to compute signed distances to the plane*/
 
466
                du0=(N1.dotProduct(tri2[0]))+d1;
 
467
                du1=(N1.dotProduct(tri2[1]))+d1;
 
468
                du2=(N1.dotProduct(tri2[2]))+d1;
 
469
 
 
470
                /* coplanarity robustness check */
 
471
#if USE_EPSILON_TEST==TRUE
 
472
                if(fabs(du0)<SMALL_EPSILON) du0=0.0;
 
473
                if(fabs(du1)<SMALL_EPSILON) du1=0.0;
 
474
                if(fabs(du2)<SMALL_EPSILON) du2=0.0;
 
475
#endif
 
476
                du0du1=du0*du1;
 
477
                du0du2=du0*du2;
 
478
 
 
479
                if(du0du1>0.0f && du0du2>0.0f) /* same sign on all of them + not equal 0 ? */
 
480
                        return 0;                    /* no intersection occurs */
 
481
 
 
482
                /* compute plane of triangle (tri2) */
 
483
                E1 = tri2[1] - tri2[0];
 
484
                E2 = tri2[2] - tri2[0];
 
485
                N2 = E1.crossProduct(E2);
 
486
                d2=-(N2.dotProduct(tri2[0]));
 
487
                /* plane equation 2: N2.X+d2=0 */
 
488
 
 
489
                /* put tri1 into plane equation 2 */
 
490
                dv0=(N2.dotProduct(tri1[0]))+d2;
 
491
                dv1=(N2.dotProduct(tri1[1]))+d2;
 
492
                dv2=(N2.dotProduct(tri1[2]))+d2;
 
493
 
 
494
#if USE_EPSILON_TEST==TRUE
 
495
                if(fabs(dv0)<SMALL_EPSILON) dv0=0.0;
 
496
                if(fabs(dv1)<SMALL_EPSILON) dv1=0.0;
 
497
                if(fabs(dv2)<SMALL_EPSILON) dv2=0.0;
 
498
#endif
 
499
 
 
500
                dv0dv1=dv0*dv1;
 
501
                dv0dv2=dv0*dv2;
 
502
 
 
503
                if(dv0dv1>0.0f && dv0dv2>0.0f) /* same sign on all of them + not equal 0 ? */
 
504
                        return 0;                    /* no intersection occurs */
 
505
 
 
506
                /* compute direction of intersection line */
 
507
                D = N1.crossProduct(N2);
 
508
 
 
509
                /* compute and index to the largest component of D */
 
510
                max=fabs(D[0]);
 
511
                index=0;
 
512
                b=fabs(D[1]);
 
513
                c=fabs(D[2]);
 
514
                if(b>max) max=b,index=1;
 
515
                if(c>max) max=c,index=2;
 
516
 
 
517
                /* this is the simplified projection onto L*/
 
518
                vp0=tri1[0][index];
 
519
                vp1=tri1[1][index];
 
520
                vp2=tri1[2][index];
 
521
 
 
522
                up0=tri2[0][index];
 
523
                up1=tri2[1][index];
 
524
                up2=tri2[2][index];
 
525
 
 
526
                /* compute interval for triangle 1 */
 
527
                coplanar=compute_intervals_isectline(tri1,vp0,vp1,vp2,dv0,dv1,dv2,
 
528
                        dv0dv1,dv0dv2,&isect1[0],&isect1[1],isectpointA);
 
529
                if(coplanar) return coplanar_tri_tri(N1, tri1, tri2);     
 
530
 
 
531
 
 
532
                /* compute interval for triangle 2 */
 
533
                compute_intervals_isectline(tri2,up0,up1,up2,du0,du1,du2,
 
534
                        du0du1,du0du2,&isect2[0],&isect2[1],isectpointB);
 
535
 
 
536
                SORT2(isect1[0],isect1[1],smallest1);
 
537
                SORT2(isect2[0],isect2[1],smallest2);
 
538
 
 
539
                if(isect1[1]<isect2[0] || isect2[1]<isect1[0]) return 0;
 
540
 
 
541
                /* at this point, we know that the triangles intersect */
 
542
 
 
543
                if(isect2[0]<isect1[0])
 
544
                {
 
545
                        if(smallest1==0) { isectline.setStart(isectpointA[0]); }
 
546
                        else { isectline.setStart(isectpointA[1]); }
 
547
 
 
548
                        if(isect2[1]<isect1[1])
 
549
                        {
 
550
                                if(smallest2==0) { isectline.setEnd(isectpointB[1]); }
 
551
                                else { isectline.setEnd(isectpointB[0]); }
 
552
                        }
 
553
                        else
 
554
                        {
 
555
                                if(smallest1==0) { isectline.setEnd(isectpointA[1]); }
 
556
                                else { isectline.setEnd(isectpointA[0]); }
 
557
                        }
 
558
                }
 
559
                else
 
560
                {
 
561
                        if(smallest2==0) { isectline.setStart(isectpointB[0]); }
 
562
                        else { isectline.setStart(isectpointB[1]); }
 
563
 
 
564
                        if(isect2[1]>isect1[1])
 
565
                        {
 
566
                                if(smallest1==0) { isectline.setEnd(isectpointA[1]); }
 
567
                                else { isectline.setEnd(isectpointA[0]); }      
 
568
                        }
 
569
                        else
 
570
                        {
 
571
                                if(smallest2==0) { isectline.setEnd(isectpointB[1]); }
 
572
                                else { isectline.setEnd(isectpointB[0]); } 
 
573
                        }
 
574
                }
 
575
                return true;
 
576
        }
 
577
 
 
578
                bool powerOf2(unsigned int i)
 
579
                {
 
580
                        Ogre::String binary = decimalToBinary(i);
 
581
                        int counter = 0;
 
582
                        for( int index = 0; index < static_cast<int>(binary.size()); ++index )
 
583
                                if( binary[index] == '1' ) ++counter;
 
584
 
 
585
                        if( counter > 1 ) return false;
 
586
                        else return true;
 
587
                }
 
588
 
 
589
                Ogre::String decimalToBinary(unsigned int i)
 
590
                {
 
591
                        Ogre::String binary = "";
 
592
                        Ogre::String temp = "";
 
593
 
 
594
                        do{
 
595
                                temp += (i % 2) + '0';
 
596
                                i = i / 2;
 
597
                        }while( i > 0 );
 
598
 
 
599
                        for( int counter = static_cast<int>(temp.size()); counter > 0; --counter )
 
600
                                binary += temp[counter];
 
601
 
 
602
                        return binary;
 
603
                }
 
604
 
 
605
        }
 
606
}