NLPACS::CEdgeCollideNode Class Reference

#include <collision_surface_temp.h>

Inheritance diagram for NLPACS::CEdgeCollideNode:

NLPACS::CEdgeCollide

Detailed Description

Temp collision data used during tryMove().
Author:
Lionel Berenguier

Nevrax France

Date:
2001

Definition at line 45 of file collision_surface_temp.h.

Public Types

enum  TPointMoveProblem {
  ParallelEdges = 0, StartOnEdge, StopOnEdge, TraverseEndPoint,
  EdgeNull, PointMoveProblemCount
}

Public Member Functions

 CEdgeCollideNode ()
void make (const CVector2f &p0, const CVector2f &p1)
bool testBBoxCollide (const CVector2f bbox[4])
float testBBoxMove (const CVector2f &start, const CVector2f &delta, const CVector2f bbox[4], CVector2f &normal)
float testCircleMove (const CVector2f &start, const CVector2f &delta, float radius, CVector2f &normal)
CRational64 testPointMove (const CVector2f &start, const CVector2f &end, TPointMoveProblem &moveBug)

Data Fields

float A0
float A1
float C
CVector2f Dir
uint32 Next
 Next edgeCollideNode in the CCollisionSurfaceTemp allocator. 0xFFFFFFFF if none.

CVector2f Norm
CVector2f P0
CVector2f P1


Member Enumeration Documentation

enum NLPACS::CEdgeCollide::TPointMoveProblem [inherited]
 

Enumeration values:
ParallelEdges 
StartOnEdge 
StopOnEdge 
TraverseEndPoint 
EdgeNull 
PointMoveProblemCount 

Definition at line 183 of file edge_collide.h.


Constructor & Destructor Documentation

NLPACS::CEdgeCollideNode::CEdgeCollideNode  )  [inline]
 

Definition at line 52 of file collision_surface_temp.h.

00053         {
00054                 Next= 0xFFFFFFFF;
00055         }


Member Function Documentation

void NLPACS::CEdgeCollide::make const CVector2f p0,
const CVector2f p1
[inherited]
 

Definition at line 43 of file edge_collide.cpp.

References NLPACS::CEdgeCollide::A0, NLPACS::CEdgeCollide::A1, NLPACS::CEdgeCollide::C, NLPACS::CEdgeCollide::Norm, NLMISC::CVector2f::normalize(), NLMISC::CVector2f::x, and NLMISC::CVector2f::y.

Referenced by NLPACS::CLocalRetriever::testCollision(), and NLPACS::CRetrieverInstance::testExteriorCollision().

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 }

bool NLPACS::CEdgeCollide::testBBoxCollide const CVector2f  bbox[4]  )  [inherited]
 

return true if this oriented bbox collide this edge.

Parameters:
bbox 4 points of the bbox, in CCW.
Returns:
true if collision occurs.

Definition at line 657 of file edge_collide.cpp.

References sint, NLMISC::CVector2f::x, and NLMISC::CVector2f::y.

Referenced by NLPACS::CGlobalRetriever::testRotCollisionWithCollisionChains().

00658 {
00659         // clip the edge against the edge of the bbox.
00660         CVector2f               p0= P0, p1= P1;
00661 
00662         for(sint i=0; i<4; i++)
00663         {
00664                 CVector2f       a= bbox[i];
00665                 CVector2f       b= bbox[(i+1)&3];
00666                 CVector2f       delta= b-a, norm;
00667                 // sign is important. bbox is CCW. normal goes OUT the bbox.
00668                 norm.x= delta.y;
00669                 norm.y= -delta.x;
00670 
00671                 float   d0= (p0-a)*norm;
00672                 float   d1= (p1-a)*norm;
00673 
00674                 // if boths points are out this plane, no collision.
00675                 if( d0>0 && d1>0)
00676                         return false;
00677                 // if difference, must clip.
00678                 if( d0>0 || d1>0)
00679                 {
00680                         CVector2f       intersect= p0 + (p1-p0)* ((0-d0)/(d1-d0));
00681                         if(d1>0)
00682                                 p1= intersect;
00683                         else
00684                                 p0= intersect;
00685                 }
00686         }
00687 
00688         // if a segment is still in the bbox, collision occurs.
00689         return true;
00690 }

float NLPACS::CEdgeCollide::testBBoxMove const CVector2f start,
const CVector2f delta,
const CVector2f  bbox[4],
CVector2f normal
[inherited]
 

return 1 either if the bbox moves away from the line, or no collision occurs. Else return a [0,1[ interval. If collision occurs (ie return<1), return in "normal" the normal of the collision. It may be normal of edge (+-), or normal against a point of the edge.

Parameters:
bbox 4 points of the bbox at start. start must be the barycentre of those points.

Definition at line 559 of file edge_collide.cpp.

References NLPACS::CEdgeCollide::C, min, NLPACS::CEdgeCollide::Norm, sint, NLPACS::CEdgeCollide::testEdgeMove(), NLMISC::CVector2f::x, and NLMISC::CVector2f::y.

Referenced by NLPACS::CGlobalRetriever::testCollisionWithCollisionChains().

00560 {
00561         // distance from center to line.
00562         float   dist= start*Norm + C;
00563 
00564         // test if the movement is against the line or not.
00565         bool    sensPos= dist>0;
00566         // if signs are equals, same side of the line, so we allow the circle to leave the line.
00567         /*if(sensPos==sensSpeed)
00568                 return 1;*/
00569 
00570 
00571         // Else, do 4 test edge/edge, and return Tmin.
00572         float   tMin, tMax;
00573         bool    edgeCollided= false;
00574         bool    normalOnBox= false;
00575         CVector2f       boxNormal;
00576         for(sint i=0;i<4;i++)
00577         {
00578                 float   t0, t1;
00579                 bool    nob;
00580                 CVector2f       a= bbox[i];
00581                 CVector2f       b= bbox[(i+1)&3];
00582 
00583                 // test move against this edge.
00584                 if(testEdgeMove(a, b, delta, t0, t1, nob))
00585                 {
00586                         if(edgeCollided)
00587                         {
00588                                 tMin= min(t0, tMin);
00589                                 tMax= max(t1, tMax);
00590                         }
00591                         else
00592                         {
00593                                 edgeCollided= true;
00594                                 tMin= t0;
00595                                 tMax= t1;
00596                         }
00597 
00598                         // get normal of box against we collide.
00599                         if(tMin==t0)
00600                         {
00601                                 normalOnBox= nob;
00602                                 if(nob)
00603                                 {
00604                                         CVector2f       dab;
00605                                         // bbox must be CCW.
00606                                         dab= b-a;
00607                                         // the normal is computed so that the vector goes In the bbox.
00608                                         boxNormal.x= -dab.y;
00609                                         boxNormal.y= dab.x;
00610                                 }
00611                         }
00612                 }
00613         }
00614 
00615         // if collision occurs,and int the [0,1] interval...
00616         if(edgeCollided && tMin<1 && tMax>0)
00617         {
00618                 // compute normal of collision.
00619                 if(normalOnBox)
00620                 {
00621                         // assume collsion is an endpoint of the edge against the bbox.
00622                         normal= boxNormal;
00623                 }
00624                 else
00625                 {
00626                         // assume collision occurs on interior of the edge. the normal to return is +- Norm.
00627                         if(sensPos)     // if algebric distance of start position was >0.
00628                                 normal= Norm;
00629                         else
00630                                 normal= -Norm;
00631                 }
00632 
00633                 // compute time of collison.
00634                 if(tMin>0)
00635                         // return time of collision.
00636                         return tMin;
00637                 else
00638                 {
00639                         // The bbox is inside the edge, at t==0. test if it goes out or not.
00640                         // accept only if we are much near the exit than the enter.
00641                         /* NB: 0.2 is an empirical value "which works well". Normally, 1 is the good value, but because of the
00642                                 "SURFACEMOVE NOT DETECTED" Problem (see testCircleMove()), we must be more restrictive.
00643                         */
00644                         if( tMax<0.2*(-tMin) )
00645                                 return 1;
00646                         else
00647                                 return 0;
00648                 }
00649         }
00650         else
00651                 return 1;
00652 
00653 }

float NLPACS::CEdgeCollide::testCircleMove const CVector2f start,
const CVector2f delta,
float  radius,
CVector2f normal
[inherited]
 

return 1 either if the circle moves away from the line, or no collision occurs. Else return a [0,1[ interval. If collision occurs (ie return<1), return in "normal" the normal of the collision. It may be normal of edge (+-), or normal against a point of the edge.

Definition at line 265 of file edge_collide.cpp.

References NLPACS::CEdgeCollide::A0, NLPACS::CEdgeCollide::A1, NLPACS::CEdgeCollide::C, NLMISC::CVector2f::isNull(), min, NLPACS::CEdgeCollide::Norm, NLMISC::CVector2f::normalize(), t, and NLPACS::testCirclePoint().

Referenced by NLPACS::CGlobalRetriever::testCollisionWithCollisionChains().

00266 {
00267         // If the movement is NULL, return 1 (no collision!)
00268         if(     delta.isNull() )
00269                 return 1;
00270 
00271         // distance from point to line.
00272         double  dist= start*Norm + C;
00273         // projection of speed on normal.
00274         double  speed= delta*Norm;
00275 
00276         // test if the movement is against the line or not.
00277         bool    sensPos= dist>0;
00278         bool    sensSpeed= speed>0;
00279 
00280         // Does the point intersect the line?
00281         dist= fabs(dist) - radius;
00282         speed= fabs(speed);
00283         if( dist > speed )
00284                 return 1;
00285 
00286         // if not already in collision with the line, test when it collides.
00287         // ===============================
00288         if(dist>=0)
00289         {
00290                 // if signs are equals, same side of the line, so we allow the circle to leave the line.
00291                 if(sensPos==sensSpeed )
00292                         return 1;
00293 
00294                 // if speed is 0, it means that movement is parralel to the line => never collide.
00295                 if(speed==0)
00296                         return 1;
00297 
00298                 // collide the line, at what time.
00299                 double  t= dist/speed;
00300 
00301 
00302                 // compute the collision position of the Circle on the edge.
00303                 // this gives the center of the sphere at the collision point.
00304                 CVector2d       proj= CVector2d(start) + CVector2d(delta)*t;
00305                 // must add radius vector.
00306                 proj+= Norm * (sensSpeed?radius:-radius);
00307                 // compute projection on edge.
00308                 double          aProj= proj*Dir;
00309 
00310                 // if on the interval of the edge.
00311                 if( aProj>=A0 && aProj<=A1)
00312                 {
00313                         // collision occurs on interior of the edge. the normal to return is +- Norm.
00314                         if(sensPos)     // if algebric distance of start position was >0.
00315                                 normal= Norm;
00316                         else
00317                                 normal= -Norm;
00318 
00319                         // return time of collision.
00320                         return (float)t;
00321                 }
00322         }
00323         // else, must test if circle collide segment at t=0. if yes, return 0.
00324         // ===============================
00325         else
00326         {
00327                 // There is just need to test if projection of circle's center onto the line hit the segment.
00328                 // This is not a good test to know if a circle intersect a segment, but other cases are
00329                 // managed with test of endPoints of the segment after.
00330                 float           aProj= start*Dir;
00331 
00332                 // if on the interval of the edge.
00333                 if( aProj>=A0 && aProj<=A1)
00334                 {
00335                         // if signs are equals, same side of the line, so we allow the circle to leave the edge.
00336                         /* Special case: do not allow to leave the edge if we are too much in the edge.
00337                          It is important for CGlobalRetriever::testCollisionWithCollisionChains() because of the
00338                          "SURFACEMOVE NOT DETECTED" Problem.
00339                          Suppose we can walk on this chain SA/SB (separate Surface A/SurfaceB). Suppose we are near this edge, 
00340                          and on Surface SA, and suppose there is an other chain SB/SC the circle collide with. If we 
00341                          return 1 (no collision), SB/SC won't be detected (because only SA/?? chains will be tested) and 
00342                          so the cylinder will penetrate SB/SC...
00343                          This case arise at best if chains SA/SB and chain SB/SC do an angle of 45deg
00344 
00345                          \todo yoyo: this is a Hack.
00346                         */
00347                         if(sensPos==sensSpeed && (-dist)<0.5*radius)
00348                         {
00349                                 return 1;
00350                         }
00351                         else
00352                         {
00353                                 // hit the interior of the edge, and sensPos!=sensSpeed. So must stop now!!
00354                                 // collision occurs on interior of the edge. the normal to return is +- Norm.
00355                                 if(sensPos)     // if algebric distance of start position was >0.
00356                                         normal= Norm;
00357                                 else
00358                                         normal= -Norm;
00359 
00360                                 return 0;
00361                         }
00362                 }
00363         }
00364 
00365         // In this case, the Circle do not hit the edge on the interior, but may hit on borders.
00366         // ===============================
00367         // Then, we must compute collision sphere-points.
00368         float           tmin, ttmp;
00369         // first point.
00370         tmin= testCirclePoint(start, delta, radius, P0);
00371         // second point.
00372         ttmp= testCirclePoint(start, delta, radius, P1);
00373         tmin= min(tmin, ttmp);
00374 
00375         // if collision occurs, compute normal of collision.
00376         if(tmin<1)
00377         {
00378                 // to which point we collide?
00379                 CVector2f       colPoint= tmin==ttmp? P1 : P0;
00380                 // compute position of the entity at collision.
00381                 CVector2f       colPos= start + delta*tmin;
00382 
00383                 // and so we have this normal (the perpendicular of the tangent at this point).
00384                 normal= colPos - colPoint;
00385                 normal.normalize();
00386         }
00387 
00388         return tmin;
00389 }

CRational64 NLPACS::CEdgeCollide::testPointMove const CVector2f start,
const CVector2f end,
TPointMoveProblem moveBug
[inherited]
 

return 1 either if no collision occurs. Else return a [0,1[ interval. return -1 if precision problem (see below). This method is used by CGlobalRetriever::doMove(). UnManageables cases arise when:

  • the movement start/stop on a edge (dist==0). In this case, don't know on what surface we arrive (before or after).
  • the movement is // to the edge and collide with it. same problem than stop on an edge.
  • the movement traverse the edge on an endpoint. In this case, there is 2+ edges sharing the point, and result is undefined. On thoses cases, moveBug is filled, and -1 is returned.

Definition at line 60 of file edge_collide.cpp.

References NLPACS::CEdgeCollide::EdgeNull, NLMISC::fsgn(), NL_I64, nlassert, nlwarning, NLPACS::CEdgeCollide::ParallelEdges, sint, sint64, NLPACS::CEdgeCollide::StartOnEdge, NLPACS::CEdgeCollide::StopOnEdge, NLPACS::CEdgeCollide::TraverseEndPoint, NLMISC::CVector2f::x, and NLMISC::CVector2f::y.

Referenced by NLPACS::CGlobalRetriever::testMovementWithCollisionChains().

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 }


Field Documentation

float NLPACS::CEdgeCollide::A0 [inherited]
 

Definition at line 190 of file edge_collide.h.

Referenced by NLPACS::CEdgeCollide::make(), and NLPACS::CEdgeCollide::testCircleMove().

float NLPACS::CEdgeCollide::A1 [inherited]
 

Definition at line 190 of file edge_collide.h.

Referenced by NLPACS::CEdgeCollide::make(), and NLPACS::CEdgeCollide::testCircleMove().

float NLPACS::CEdgeCollide::C [inherited]
 

Definition at line 191 of file edge_collide.h.

Referenced by NLPACS::CEdgeCollide::make(), NLPACS::CEdgeCollide::testBBoxMove(), and NLPACS::CEdgeCollide::testCircleMove().

CVector2f NLPACS::CEdgeCollide::Dir [inherited]
 

Definition at line 189 of file edge_collide.h.

uint32 NLPACS::CEdgeCollideNode::Next
 

Next edgeCollideNode in the CCollisionSurfaceTemp allocator. 0xFFFFFFFF if none.

Definition at line 49 of file collision_surface_temp.h.

Referenced by NLPACS::CLocalRetriever::testCollision(), NLPACS::CGlobalRetriever::testCollisionWithCollisionChains(), NLPACS::CRetrieverInstance::testExteriorCollision(), NLPACS::CGlobalRetriever::testMovementWithCollisionChains(), and NLPACS::CGlobalRetriever::testRotCollisionWithCollisionChains().

CVector2f NLPACS::CEdgeCollide::Norm [inherited]
 

Definition at line 189 of file edge_collide.h.

Referenced by NLPACS::CEdgeCollide::make(), NLPACS::CEdgeCollide::testBBoxMove(), NLPACS::CEdgeCollide::testCircleMove(), and NLPACS::CGlobalRetriever::testMovementWithCollisionChains().

CVector2f NLPACS::CEdgeCollide::P0 [inherited]
 

Definition at line 187 of file edge_collide.h.

CVector2f NLPACS::CEdgeCollide::P1 [inherited]
 

Definition at line 188 of file edge_collide.h.


The documentation for this class was generated from the following file:
Generated on Tue Mar 16 14:12:32 2004 for NeL by doxygen 1.3.6