nevrax.org : docs

00001 
+00007 /* Copyright, 2001 Nevrax Ltd.
+00008  *
+00009  * This file is part of NEVRAX NEL.
+00010  * NEVRAX NEL is free software; you can redistribute it and/or modify
+00011  * it under the terms of the GNU General Public License as published by
+00012  * the Free Software Foundation; either version 2, or (at your option)
+00013  * any later version.
+00014 
+00015  * NEVRAX NEL is distributed in the hope that it will be useful, but
+00016  * WITHOUT ANY WARRANTY; without even the implied warranty of
+00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+00018  * General Public License for more details.
+00019 
+00020  * You should have received a copy of the GNU General Public License
+00021  * along with NEVRAX NEL; see the file COPYING. If not, write to the
+00022  * Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+00023  * MA 02111-1307, USA.
+00024  */
+00025 
+00026 #include "stdpacs.h"
+00027 
+00028 #include "pacs/edge_collide.h"
+00029 
+00030 using namespace NLMISC;
+00031 using namespace std;
+00032 
+00033 
+00034 
+00035 namespace NLPACS
+00036 {
+00037 
+00038 
+00039 static  const   float   EdgeCollideEpsilon= 1e-5f;
+00040 
+00041 
+00042 // ***************************************************************************
+00043 void            CEdgeCollide::make(const CVector2f &p0, const CVector2f &p1)
+00044 {
+00045         P0= p0;
+00046         P1= p1;
+00047         // translation axis of the edge.
+00048         Dir= P1-P0;
+00049         Dir.normalize();
+00050         A0= P0*Dir;
+00051         A1= P1*Dir;
+00052         // line equation.
+00053         Norm.x=  Dir.y;
+00054         Norm.y= -Dir.x;
+00055         C= - P0*Norm;
+00056 }
+00057 
+00058 
+00059 // ***************************************************************************
+00060 CRational64     CEdgeCollide::testPointMove(const CVector2f &start, const CVector2f &end, TPointMoveProblem &moveBug)
+00061 {
+00062         /*
+00063                 To have a correct test (with no float precision problem):
+00064                         - test first if there is collision beetween the 2 edges:
+00065                                 - test if first edge collide the other line.
+00066                                 - test if second edge collide the other line.
+00067                                 - if both true, yes, there is a collision.
+00068                         - compute time of collision.
+00069         */
+00070 
+00071 
+00072         // *this must be a correct edge.
+00073         if(P0==P1)
+00074         {
+00075                 moveBug= EdgeNull;
+00076                 return -1;
+00077         }
+00078 
+00079         // if no movement, no collision.
+00080         if(start==end)
+00081                 return 1;
+00082 
+00083         // NB those edges are snapped (1/256 for edgeCollide, and 1/1024 for start/end), so no float problem here.
+00084         // precision is 20 bits.
+00085         CVector2f       normEdge;
+00086         CVector2f       normMove;
+00087         CVector2f       deltaEdge;
+00088         CVector2f       deltaMove;
+00089 
+00090         // compute normal of the edge (not normalized, because no need, and for precision problem).
+00091         deltaEdge= P1-P0;
+00092         normEdge.x= -deltaEdge.y;
+00093         normEdge.y= deltaEdge.x;
+00094 
+00095         // compute normal of the movement (not normalized, because no need, and for precision problem).
+00096         deltaMove= end-start;
+00097         normMove.x= -deltaMove.y;
+00098         normMove.y= deltaMove.x;
+00099 
+00100         // distance from points of movment against edge line. Use double, because of multiplication.
+00101         // precision is now 43 bits.
+00102         double  moveD0= (double)normEdge.x*(double)(start.x-P0.x) + (double)normEdge.y*(double)(start.y-P0.y);
+00103         double  moveD1= (double)normEdge.x*(double)(end.x  -P0.x) + (double)normEdge.y*(double)(end.y  -P0.y);
+00104 
+00105         // distance from points of edge against movement line. Use double, because of multiplication.
+00106         // precision is now 43 bits.
+00107         double  edgeD0= (double)normMove.x*(double)(P0.x-start.x) + (double)normMove.y*(double)(P0.y-start.y);
+00108         double  edgeD1= (double)normMove.x*(double)(P1.x-start.x) + (double)normMove.y*(double)(P1.y-start.y);
+00109 
+00110 
+00111         // If both edges intersect lines (including endpoints), there is a collision, else none.
+00112         sint    sgnMove0, sgnMove1;
+00113         sgnMove0= fsgn(moveD0);
+00114         sgnMove1= fsgn(moveD1);
+00115 
+00116         // special case if the 2 edges lies on the same line.
+00117         if(sgnMove0==0 && sgnMove1==0)
+00118         {
+00119                 // must test if there is a collision. if yes, problem.
+00120                 // project all the points on the line of the edge.
+00121                 // Use double because of multiplication. precision is now 43 bits.
+00122                 double  moveA0= (double)deltaEdge.x*(double)(start.x-P0.x) + (double)deltaEdge.y*(double)(start.y-P0.y);
+00123                 double  moveA1= (double)deltaEdge.x*(double)(end.x  -P0.x) + (double)deltaEdge.y*(double)(end.y  -P0.y);
+00124                 double  edgeA0= 0;
+00125                 double  edgeA1= (double)deltaEdge.x*(double)deltaEdge.x + (double)deltaEdge.y*(double)deltaEdge.y;
+00126 
+00127                 // Test is there is intersection (endpoints included). if yes, return -1. else return 1 (no collision at all).
+00128                 if(moveA1>=edgeA0 && edgeA1>=moveA0)
+00129                 {
+00130                         moveBug= ParallelEdges;
+00131                         return -1;
+00132                 }
+00133                 else
+00134                         return 1;
+00135         }
+00136 
+00137         // if on same side of the line=> there is no collision.
+00138         if( sgnMove0==sgnMove1)
+00139                 return 1;
+00140 
+00141         // test edge against move line.
+00142         sint    sgnEdge0, sgnEdge1;
+00143         sgnEdge0= fsgn(edgeD0);
+00144         sgnEdge1= fsgn(edgeD1);
+00145 
+00146         // should not have this case, because tested before with (sgnMove==0 && sgnMove1==0).
+00147         nlassert(sgnEdge0!=0 || sgnEdge1!=0);
+00148 
+00149 
+00150         // if on same side of the line, no collision against this edge.
+00151         if( sgnEdge0==sgnEdge1 )
+00152                 return 1;
+00153 
+00154         // Here the edges intersect, but ensure that there is no limit problem.
+00155         if(sgnEdge0==0 || sgnEdge1==0)
+00156         {
+00157                 moveBug= TraverseEndPoint;
+00158                 return -1;
+00159         }
+00160         else if(sgnMove1==0)
+00161         {
+00162                 moveBug= StopOnEdge;
+00163                 return -1;
+00164         }
+00165         else if(sgnMove0==0)
+00166         {
+00167                 // this should not arrive.
+00168                 moveBug= StartOnEdge;
+00169                 return -1;
+00170         }
+00171 
+00172 
+00173         // Here, there is a normal collision, just compute it.
+00174         // Because of Division, there is a precision lost in double. So compute a CRational64.
+00175         // First, compute numerator and denominator in the highest precision. this is 1024*1024 because of prec multiplication.
+00176         double          numerator= (0-moveD0)*1024*1024;
+00177         double          denominator= (moveD1-moveD0)*1024*1024;
+00178         sint64          numeratorInt= (sint64)numerator;
+00179         sint64          denominatorInt= (sint64)denominator;
+00180 /*
+00181         nlassert(numerator == numeratorInt);
+00182         nlassert(denominator == denominatorInt);
+00183 */
+00184         if (numerator != numeratorInt)
+00185                 nlwarning("numerator(%f) != numeratorInt(%"NL_I64"d)", numerator, numeratorInt);
+00186         if (denominator != denominatorInt)
+00187                 nlwarning("denominator(%f) != denominatorInt(%"NL_I64"d)", denominator, denominatorInt);
+00188 
+00189         return CRational64(numeratorInt, denominatorInt);
+00190 }
+00191 
+00192 
+00193 // ***************************************************************************
+00194 static  inline float            testCirclePoint(const CVector2f &start, const CVector2f &delta, float radius, const CVector2f &point)
+00195 {
+00196         // factors of the qaudratic: at� + bt + c=0
+00197         float           a,b,c;
+00198         float           dta;
+00199         float           r0, r1, res;
+00200         CVector2f       relC, relV;
+00201 
+00202         // compute quadratic..
+00203         relC= start-point;
+00204         relV= delta;
+00205         a= relV.x*relV.x + relV.y*relV.y;               // a>=0.
+00206         b= 2* (relC.x*relV.x + relC.y*relV.y);
+00207         c= relC.x*relC.x + relC.y*relC.y - radius*radius;
+00208         // compute delta of the quadratic.
+00209         dta= b*b - 4*a*c;       // b�-4ac
+00210         if(dta>=0)
+00211         {
+00212                 dta= (float)sqrt(dta);
+00213                 r0= (-b -dta)/(2*a);
+00214                 r1= (-b +dta)/(2*a);
+00215                 // since a>0, r0<=r1.
+00216                 if(r0>r1)
+00217                         swap(r0,r1);
+00218                 // if r1 is negative, then we are out and go away from this point. OK.
+00219                 if(r1<=0)
+00220                 {
+00221                         res= 1;
+00222                 }
+00223                 // if r0 is positive, then we may collide this point.
+00224                 else if(r0>=0)
+00225                 {
+00226                         res= min(1.f, r0);
+00227                 }
+00228                 else    // r0<0 && r1>0. the point is already in the sphere!!
+00229                 {
+00230                         //nlinfo("COL: Point problem: %.2f, %.2f.  b=%.2f", r0, r1, b);
+00231                         // we allow the movement only if we go away from this point.
+00232                         // this is true if the derivative at t=0 is >=0 (because a>0).
+00233                         if(b>0)
+00234                                 res= 1; // go out.
+00235                         else
+00236                                 res=0;
+00237                 }
+00238         }
+00239         else
+00240         {
+00241                 // never hit this point along this movement.
+00242                 res= 1;
+00243         }
+00244 
+00245         return res;
+00246 }
+00247 
+00248 
+00249 // ***************************************************************************
+00250 float           CEdgeCollide::testCircleMove(const CVector2f &start, const CVector2f &delta, float radius, CVector2f &normal)
+00251 {
+00252         // distance from point to line.
+00253         double  dist= start*Norm + C;
+00254         // projection of speed on normal.
+00255         double  speed= delta*Norm;
+00256 
+00257         // test if the movement is against the line or not.
+00258         bool    sensPos= dist>0;
+00259         bool    sensSpeed= speed>0;
+00260 
+00261         // Does the point intersect the line?
+00262         dist= fabs(dist) - radius;
+00263         speed= fabs(speed);
+00264         if( dist > speed )
+00265                 return 1;
+00266 
+00267         // if not already in collision with the line, test when it collides.
+00268         // ===============================
+00269         if(dist>=0)
+00270         {
+00271                 // if signs are equals, same side of the line, so we allow the circle to leave the line.
+00272                 if(sensPos==sensSpeed )
+00273                         return 1;
+00274 
+00275                 // collide the line, at what time.
+00276                 double  t= dist/speed;
+00277 
+00278 
+00279                 // compute the collision position of the Circle on the edge.
+00280                 // this gives the center of the sphere at the collision point.
+00281                 CVector2d       proj= CVector2d(start) + CVector2d(delta)*t;
+00282                 // must add radius vector.
+00283                 proj+= Norm * (sensSpeed?radius:-radius);
+00284                 // compute projection on edge.
+00285                 double          aProj= proj*Dir;
+00286 
+00287                 // if on the interval of the edge.
+00288                 if( aProj>=A0 && aProj<=A1)
+00289                 {
+00290                         // collision occurs on interior of the edge. the normal to return is +- Norm.
+00291                         if(sensPos)     // if algebric distance of start position was >0.
+00292                                 normal= Norm;
+00293                         else
+00294                                 normal= -Norm;
+00295 
+00296                         // return time of collision.
+00297                         return (float)t;
+00298                 }
+00299         }
+00300         // else, must test if circle collide segment at t=0. if yes, return 0.
+00301         // ===============================
+00302         else
+00303         {
+00304                 // There is just need to test if projection of circle's center onto the line hit the segment.
+00305                 // This is not a good test to know if a circle intersect a segment, but other cases are
+00306                 // managed with test of endPoints of the segment after.
+00307                 float           aProj= start*Dir;
+00308 
+00309                 // if on the interval of the edge.
+00310                 if( aProj>=A0 && aProj<=A1)
+00311                 {
+00312                         // if signs are equals, same side of the line, so we allow the circle to leave the edge.
+00313                         /* Special case: do not allow to leave the edge if we are too much in the edge.
+00314                          It is important for CGlobalRetriever::testCollisionWithCollisionChains() because of the
+00315                          "SURFACEMOVE NOT DETECTED" Problem.
+00316                          Suppose we can walk on this chain SA/SB (separate Surface A/SurfaceB). Suppose we are near this edge, 
+00317                          and on Surface SA, and suppose there is an other chain SB/SC the circle collide with. If we 
+00318                          return 1 (no collision), SB/SC won't be detected (because only SA/?? chains will be tested) and 
+00319                          so the cylinder will penetrate SB/SC...
+00320                          This case arise at best if chains SA/SB and chain SB/SC do an angle of 45�
+00321 
+00322                          \todo yoyo: this is a Hack.
+00323                         */
+00324                         if(sensPos==sensSpeed && (-dist)<0.5*radius)
+00325                         {
+00326                                 return 1;
+00327                         }
+00328                         else
+00329                         {
+00330                                 // hit the interior of the edge, and sensPos!=sensSpeed. So must stop now!!
+00331                                 // collision occurs on interior of the edge. the normal to return is +- Norm.
+00332                                 if(sensPos)     // if algebric distance of start position was >0.
+00333                                         normal= Norm;
+00334                                 else
+00335                                         normal= -Norm;
+00336 
+00337                                 return 0;
+00338                         }
+00339                 }
+00340         }
+00341 
+00342         // In this case, the Circle do not hit the edge on the interior, but may hit on borders.
+00343         // ===============================
+00344         // Then, we must compute collision sphere-points.
+00345         float           tmin, ttmp;
+00346         // first point.
+00347         tmin= testCirclePoint(start, delta, radius, P0);
+00348         // second point.
+00349         ttmp= testCirclePoint(start, delta, radius, P1);
+00350         tmin= min(tmin, ttmp);
+00351 
+00352         // if collision occurs, compute normal of collision.
+00353         if(tmin<1)
+00354         {
+00355                 // to which point we collide?
+00356                 CVector2f       colPoint= tmin==ttmp? P1 : P0;
+00357                 // compute position of the entity at collision.
+00358                 CVector2f       colPos= start + delta*tmin;
+00359 
+00360                 // and so we have this normal (the perpendicular of the tangent at this point).
+00361                 normal= colPos - colPoint;
+00362                 normal.normalize();
+00363         }
+00364 
+00365         return tmin;
+00366 }
+00367 
+00368 
+00369 
+00370 // ***************************************************************************
+00371 bool            CEdgeCollide::testEdgeMove(const CVector2f &q0, const CVector2f &q1, const CVector2f &delta, float &tMin, float &tMax, bool &normalOnBox)
+00372 {
+00373         double  a,b,cv,cc,  d,e,f;
+00374         CVector2d       tmp;
+00375 
+00376         // compute D1 line equation of q0q1. bx - ay + c(t)=0, where c is function of time [0,1].
+00377         // ===========================
+00378         tmp= q1 - q0;           // NB: along time, the direction doesn't change.
+00379         // Divide by norm()�, so that  a projection on this edge is true if the proj is in interval [0,1].
+00380         tmp/= tmp.sqrnorm();
+00381         a= tmp.x;
+00382         b= tmp.y;
+00383         // c= - q0(t)*CVector2d(b,-a).  but since q0(t) is a function of time t (q0+delta*t), compute cv, and cc.
+00384         // so c= cv*t + cc.
+00385         cv= - CVector2d(b,-a)*delta;
+00386         cc= - CVector2d(b,-a)*q0;
+00387 
+00388         // compute D2 line equation of P0P1. ex - dy + f=0.
+00389         // ===========================
+00390         tmp= P1 - P0;
+00391         // Divide by norm()�, so that  a projection on this edge is true if the proj is in interval [0,1].
+00392         tmp/= tmp.sqrnorm();
+00393         d= tmp.x;
+00394         e= tmp.y;
+00395         f= - CVector2d(e,-d)*P0;
+00396 
+00397 
+00398         // Solve system.
+00399         // ===========================
+00400         /*
+00401                 Compute the intersection I of 2 lines across time.
+00402                 We have the system:
+00403                         bx - ay + c(t)=0
+00404                         ex - dy + f=0
+00405 
+00406                 which solve for:
+00407                         det= ae-bd      (0 <=> // lines)
+00408                         x(t)= (d*c(t) - fa) / det
+00409                         y(t)= (e*c(t) - fb) / det
+00410         */
+00411 
+00412         // determinant of matrix2x2.
+00413         double  det= a*e - b*d;
+00414         // if to near of 0. (take delta for reference of test).
+00415         if(det==0 || fabs(det)<delta.norm()*EdgeCollideEpsilon)
+00416                 return false;
+00417 
+00418         // intersection I(t)= pInt + vInt*t.
+00419         CVector2d               pInt, vInt;
+00420         pInt.x= ( d*cc - f*a ) / det;
+00421         pInt.y= ( e*cc - f*b ) / det;
+00422         vInt.x= ( d*cv ) / det;
+00423         vInt.y= ( e*cv ) / det;
+00424 
+00425 
+00426         // Project Intersection.
+00427         // ===========================
+00428         /*
+00429                 Now, we project x,y onto each line D1 and D2, which gives  u(t) and v(t), each one giving the parameter of 
+00430                 the parametric line function. When it is in [0,1], we are on the edge.
+00431 
+00432                 u(t)= (I(t)-q0(t)) * CVector2d(a,b)     = uc + uv*t
+00433                 v(t)= (I(t)-P0) * CVector2d(d,e)        = vc + vv*t
+00434         */
+00435         double  uc, uv;
+00436         double  vc, vv;
+00437         // NB: q0(t)= q0+delta*t
+00438         uc= (pInt-q0) * CVector2d(a,b);
+00439         uv= (vInt-delta) * CVector2d(a,b);
+00440         vc= (pInt-P0) * CVector2d(d,e);
+00441         vv= (vInt) * CVector2d(d,e);
+00442 
+00443 
+00444         // Compute intervals.
+00445         // ===========================
+00446         /*
+00447                 Now, for each edge, compute time interval where parameter is in [0,1]. If intervals overlap, there is a collision.
+00448         */
+00449         double  tu0, tu1, tv0, tv1;
+00450         // infinite interval.
+00451         bool    allU=false, allV=false;
+00452 
+00453         // compute time interval for u(t).
+00454         if(uv==0 || fabs(uv)<EdgeCollideEpsilon)
+00455         {
+00456                 // The intersection does not move along D1. Always projected on u(t)=uc. so if in [0,1], OK, else never collide.
+00457                 if(uc<0 || uc>1)
+00458                         return false;
+00459                 // else suppose "always valid".
+00460                 tu0 =tu1= 0;
+00461                 allU= true;
+00462         }
+00463         else
+00464         {
+00465                 tu0= (0-uc)/uv; // t for u(t)=0
+00466                 tu1= (1-uc)/uv; // t for u(t)=1
+00467         }
+00468 
+00469         // compute time interval for v(t).
+00470         if(vv==0 || fabs(vv)<EdgeCollideEpsilon)
+00471         {
+00472                 // The intersection does not move along D2. Always projected on v(t)=vc. so if in [0,1], OK, else never collide.
+00473                 if(vc<0 || vc>1)
+00474                         return false;
+00475                 // else suppose "always valid".
+00476                 tv0 =tv1= 0;
+00477                 allV= true;
+00478         }
+00479         else
+00480         {
+00481                 tv0= (0-vc)/vv; // t for v(t)=0
+00482                 tv1= (1-vc)/vv; // t for v(t)=1
+00483         }
+00484 
+00485 
+00486         // clip intervals.
+00487         // ===========================
+00488         // order time interval.
+00489         if(tu0>tu1)
+00490                 swap(tu0, tu1);         // now, [tu0, tu1] represent the time interval where line D2 hit the edge D1.
+00491         if(tv0>tv1)
+00492                 swap(tv0, tv1);         // now, [tv0, tv1] represent the time interval where line D1 hit the edge D2.
+00493 
+00494         normalOnBox= false;
+00495         if(!allU && !allV)
+00496         {
+00497                 // if intervals do not overlap, no collision.
+00498                 if(tu0>tv1 || tv0>tu1)
+00499                         return false;
+00500                 else
+00501                 {
+00502                         // compute intersection of intervals.
+00503                         tMin= (float)max(tu0, tv0);
+00504                         tMax= (float)min(tu1, tv1);
+00505                         // if collision of edgeCollide against the bbox.
+00506                         if(tv0>tu0)
+00507                                 normalOnBox= true;
+00508                 }
+00509         }
+00510         else if(allU)
+00511         {
+00512                 // intersection of Infinite and V interval.
+00513                 tMin= (float)tv0;
+00514                 tMax= (float)tv1;
+00515                 // if collision of edgeCollide against the bbox.
+00516                 normalOnBox= true;
+00517         }
+00518         else if(allV)
+00519         {
+00520                 // intersection of Infinite and U interval.
+00521                 tMin= (float)tu0;
+00522                 tMax= (float)tu1;
+00523         }
+00524         else
+00525         {
+00526                 // if allU && allV, this means delta is near 0, and so there is always collision.
+00527                 tMin= -1000;
+00528                 tMax= 1000;
+00529         }
+00530         
+00531         return true;
+00532 }
+00533 
+00534 
+00535 // ***************************************************************************
+00536 float           CEdgeCollide::testBBoxMove(const CVector2f &start, const CVector2f &delta, const CVector2f bbox[4], CVector2f &normal)
+00537 {
+00538         // distance from center to line.
+00539         float   dist= start*Norm + C;
+00540 
+00541         // test if the movement is against the line or not.
+00542         bool    sensPos= dist>0;
+00543         // if signs are equals, same side of the line, so we allow the circle to leave the line.
+00544         /*if(sensPos==sensSpeed)
+00545                 return 1;*/
+00546 
+00547 
+00548         // Else, do 4 test edge/edge, and return Tmin.
+00549         float   tMin, tMax;
+00550         bool    edgeCollided= false;
+00551         bool    normalOnBox= false;
+00552         CVector2f       boxNormal;
+00553         for(sint i=0;i<4;i++)
+00554         {
+00555                 float   t0, t1;
+00556                 bool    nob;
+00557                 CVector2f       a= bbox[i];
+00558                 CVector2f       b= bbox[(i+1)&3];
+00559 
+00560                 // test move against this edge.
+00561                 if(testEdgeMove(a, b, delta, t0, t1, nob))
+00562                 {
+00563                         if(edgeCollided)
+00564                         {
+00565                                 tMin= min(t0, tMin);
+00566                                 tMax= max(t1, tMax);
+00567                         }
+00568                         else
+00569                         {
+00570                                 edgeCollided= true;
+00571                                 tMin= t0;
+00572                                 tMax= t1;
+00573                         }
+00574 
+00575                         // get normal of box against we collide.
+00576                         if(tMin==t0)
+00577                         {
+00578                                 normalOnBox= nob;
+00579                                 if(nob)
+00580                                 {
+00581                                         CVector2f       dab;
+00582                                         // bbox must be CCW.
+00583                                         dab= b-a;
+00584                                         // the normal is computed so that the vector goes In the bbox.
+00585                                         boxNormal.x= -dab.y;
+00586                                         boxNormal.y= dab.x;
+00587                                 }
+00588                         }
+00589                 }
+00590         }
+00591 
+00592         // if collision occurs,and int the [0,1] interval...
+00593         if(edgeCollided && tMin<1 && tMax>0)
+00594         {
+00595                 // compute normal of collision.
+00596                 if(normalOnBox)
+00597                 {
+00598                         // assume collsion is an endpoint of the edge against the bbox.
+00599                         normal= boxNormal;
+00600                 }
+00601                 else
+00602                 {
+00603                         // assume collision occurs on interior of the edge. the normal to return is +- Norm.
+00604                         if(sensPos)     // if algebric distance of start position was >0.
+00605                                 normal= Norm;
+00606                         else
+00607                                 normal= -Norm;
+00608                 }
+00609 
+00610                 // compute time of collison.
+00611                 if(tMin>0)
+00612                         // return time of collision.
+00613                         return tMin;
+00614                 else
+00615                 {
+00616                         // The bbox is inside the edge, at t==0. test if it goes out or not.
+00617                         // accept only if we are much near the exit than the enter.
+00618                         /* NB: 0.2 is an empirical value "which works well". Normally, 1 is the good value, but because of the
+00619                                 "SURFACEMOVE NOT DETECTED" Problem (see testCircleMove()), we must be more restrictive.
+00620                         */
+00621                         if( tMax<0.2*(-tMin) )
+00622                                 return 1;
+00623                         else
+00624                                 return 0;
+00625                 }
+00626         }
+00627         else
+00628                 return 1;
+00629 
+00630 }
+00631 
+00632 
+00633 // ***************************************************************************
+00634 bool            CEdgeCollide::testBBoxCollide(const CVector2f bbox[4])
+00635 {
+00636         // clip the edge against the edge of the bbox.
+00637         CVector2f               p0= P0, p1= P1;
+00638 
+00639         for(sint i=0; i<4; i++)
+00640         {
+00641                 CVector2f       a= bbox[i];
+00642                 CVector2f       b= bbox[(i+1)&3];
+00643                 CVector2f       delta= b-a, norm;
+00644                 // sign is important. bbox is CCW. normal goes OUT the bbox.
+00645                 norm.x= delta.y;
+00646                 norm.y= -delta.x;
+00647 
+00648                 float   d0= (p0-a)*norm;
+00649                 float   d1= (p1-a)*norm;
+00650 
+00651                 // if boths points are out this plane, no collision.
+00652                 if( d0>0 && d1>0)
+00653                         return false;
+00654                 // if difference, must clip.
+00655                 if( d0>0 || d1>0)
+00656                 {
+00657                         CVector2f       intersect= p0 + (p1-p0)* ((0-d0)/(d1-d0));
+00658                         if(d1>0)
+00659                                 p1= intersect;
+00660                         else
+00661                                 p0= intersect;
+00662                 }
+00663         }
+00664 
+00665         // if a segment is still in the bbox, collision occurs.
+00666         return true;
+00667 }
+00668 
+00669 
+00670 
+00671 } // NLPACS
+
edge_collide.cpp
