#include <collision_surface_temp.h>
Inheritance diagram for NLPACS::CEdgeCollideNode:
Nevrax France
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 |
|
|
Definition at line 183 of file edge_collide.h.
00183 {ParallelEdges=0, StartOnEdge, StopOnEdge, TraverseEndPoint, EdgeNull, PointMoveProblemCount};
|
|
|
Definition at line 52 of file collision_surface_temp.h.
00053 {
00054 Next= 0xFFFFFFFF;
00055 }
|
|
||||||||||||
|
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().
|
|
|
return true if this oriented bbox collide this edge.
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 }
|
|
||||||||||||||||||||
|
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.
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 }
|
|
||||||||||||||||||||
|
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 }
|
|
||||||||||||||||
|
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:
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 }
|
|
|
Definition at line 190 of file edge_collide.h. Referenced by NLPACS::CEdgeCollide::make(), and NLPACS::CEdgeCollide::testCircleMove(). |
|
|
Definition at line 190 of file edge_collide.h. Referenced by NLPACS::CEdgeCollide::make(), and NLPACS::CEdgeCollide::testCircleMove(). |
|
|
Definition at line 191 of file edge_collide.h. Referenced by NLPACS::CEdgeCollide::make(), NLPACS::CEdgeCollide::testBBoxMove(), and NLPACS::CEdgeCollide::testCircleMove(). |
|
|
Definition at line 189 of file edge_collide.h. |
|
|
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(). |
|
|
Definition at line 189 of file edge_collide.h. Referenced by NLPACS::CEdgeCollide::make(), NLPACS::CEdgeCollide::testBBoxMove(), NLPACS::CEdgeCollide::testCircleMove(), and NLPACS::CGlobalRetriever::testMovementWithCollisionChains(). |
|
|
Definition at line 187 of file edge_collide.h. |
|
|
Definition at line 188 of file edge_collide.h. |
1.3.6