#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. |