xmin   xmax                                  xmin       xmax          |      |          ymax                                            |      |          --------------         ymax +---------+          |      |                                      |         |          |      |       +                    =         |         |          |      |                                      |         |          |      |          --------------         ymin +---------+          |      |          ymin          |      |

//-------------------------------------------------// box : [xmin, xmax, ymin, ymax]// particle : start point : A, end point : B//-------------------------------------------------//-------------------------------------------------// Here, we have a collision//-------------------------------------------------                  |       |      A   |       |       \  |       |        \ |       |         \|xenter |          *       |          |\ yenter                ------+-*-----+--------    <-----          |  \    |                  | [xenter, xexit] and [yenter, yexit]           |   \yexit                 | intersect.    ------+----*--+--------    <-----          |     \ |          |      \|          |       * xexit          |       |\              |       | \              |       |  \              |       |   B    //-------------------------------------------------// Here, it's a miss//-------------------------------------------------          |       |                   A  |       |                    \ |       |                     \|       |          *xenter |                      |\      |                      | \     |                      |  \    |                      |   \   |                      |    \  |                      |     \ |                      |      \|                      |       *xexit        <-------              |       |\                    |          |       | \                   | intervals [xenter, xexit] and  ymax     |       |  \ yenter   <-------  [yenter, yexit] do not intersect. ---------+-------+---*----------                    |       |    \                    |       |     \            ymin     |       |      \ yexit           ---------+-------+-------*------                     |       |        \                     |       |         B                   xmin    xmax

               // box [min, max]      // segment [a, b]  // intersections[enter, exit]bool SlabIntersection(flot bmin, float bmax, float a, float b, float& tenter, float& texit){    float denom = (smax - smin);    if (fabs(denom) < 1.0E-8f)    {        return (bmin < tmax && bmax > tmin);    }    float t0 = (bmin - smin) / denom;    float t1 = (bmax - smin) / denom;    if(t0 > t1)     {        swapf(t0, t1);    }    if (t0 > texit || t1 < tenter}    {        return false;    }    tenter = max(tenter, t0);    texit  = min(texit , t1);    return true;} bool SegmentABBoxIntersect(CBox Box, CSegment Seg, float& t){    float tenter = 0.0f, texit = 1.0f;        if (!SlabIntersection(Box.Min.x, Box.Max.x, Seg.A.x, Seg.B.x, tenter, texit))    {        return false;    }    if (!SlabIntersection(Box.Min.y, Box.Max.y, Seg.A.y, Seg.B.y, tenter, texit))    {        return false;    }    t = tenter;    return true;}

bool AABBoxAABBoxIntersect(CBox A, CBox B, float& t){    Vector Bextent = (B.Max - B.Min) * 0.5f;    Vector Bcentre = (B.Max + B.Min) * 0.5f;    Vector Vrel    = (B.Displacement - A.Displacement);    // static box, which is box A, expanded by box B's size    CBox C(A.Min, A.Max);    C.Min -= Bextent;    C.Max += Bextent;    // segment, which is box B, shrunk to a point, and with relative     // dispalcement (B.disp - A.disp).    CSegment S(BCentre, Bcentre + Vrel);        retrun SegmentABBoxIntersect(C, S, t);}

bool PolyPolyIntersect(const CPoly& A, const CPoly& B, float& t){     float tenter = 0.0f, texit = 1.0f;     //-------------------------------------------------------------------------            // Test SAT of polygon (A)     //-------------------------------------------------------------------------            for(int i = 0; i < A.NumEdges; i ++)     {         Vector Axis(-A.Edge.y, A.Edge.x);         if (!SlabAxisIntersect(Axis, A, B, tenter, texit))         {              return false;         }     }     //-------------------------------------------------------------------------            // Test SAT of polygon (B)     //-------------------------------------------------------------------------            for(int i = 0; i < B.NumEdges; i ++)     {         Vector Axis(-B.Edge.y, B.Edge.x);         if (!SlabAxisIntersect(Axis, A, B, tenter, texit))         {              return false;         }     }       t = tenter;     return true;}SlabAxisIntersect(const Vector& Axis, const CPoly& A, const CPoly& B, float& tenter, float& texit){     //------------------------------------------------------------     // relative displacement.     // or you can also work with velocities,      // except, you ned to initialise texit to the frame timestep, instead     // of 1.0f.     // This is doing Avel - Bvel, since (A) is the one we consider for a      // particle.     //------------------------------------------------------------     Vector Vrel = A.Displacement - B.Displacement;     float v = Vrel.DotProduct(Axis); // the projected velocity along the axis.     // calculate the polygon slabs     float amin, amax;     float bmin, bmax;     //-------------------------------------------------------------------------            // the two 'slabs' along the axis of separation     // that is, the min and max of the polys, when projected along the axis     //-------------------------------------------------------------------------            A.FindSlab(Axis, amin, amax);     B.FindSlab(Axis, bmin, bmax);     //-------------------------------------------------------------------------            // convert the two slabs into a single particle-slab system.     // like switching from a AABBox-AABBox to a particle-AABBox algorithm.     //-------------------------------------------------------------------------            acen = (amax + amin) * 0.5f;     aext = (amax - amin) * 0.5f;      // the expanded slab     bmin -= aext;     bmax += aext;              // the slab reduced to a single particle     float start = acen;     float end   = acen + v;     //-------------------------------------------------------------------------            // do the simple particle-slab intersection             //-------------------------------------------------------------------------            return SlabIntersection(bmin, bmax, start, end, tenter, texit);}

     for(int i = 0; i < Poly.NumEdges; i ++)     {         Vector Axis(-Poly.Edge.y, Poly.Edge.x);         if (!SlabAxisIntersect(Axis, Poly, Sphere, tenter, texit))         {              return false;         }     }     for(int i = 0; i < Poly.NumVertices; i ++)     {         Vector Axis(Poly.Vertex - Sphere.Centre);         if (!SlabAxisIntersect(Axis, Poly, Sphere, tenter, texit))         {              return false;         }     }

//-------------------------------------------------------------------------------// Sphere Triangle Collision Routine :// -----------------------------------// Triangle : Vertices		: V[3] (assuming counter clockwise vertex ordering (CCW))//            Normal		: N    (assuming right-handed system (and also CCW), and normalised)// Sphere   : Position		: P//            Displacement	: D//            Radius		: r//            Radius Squared: r2//// Constraints		: Time Bound		: tmax//                    DoubleSidedTest	: bDoubleSided// Collision Result : PointOfContact	: Pcoll//                    NormalOfCOntact	: Ncoll//                    TimeOfCollision	: tcoll//					  MTD (intersection): Dcoll// // Warning : Due to FP innacuracies, Dcoll should not be used in case of a collision.//           Dcoll, really, is for intersections only (it represents the MTD in that case).//-------------------------------------------------------------------------------//// Algorithm : // -----------// // 1) find Pplane, tplane : Point of collision of sphere on Triangle plane, //    and time of collision on plane// 2) Find features collidable. // 3) test collision with each features.// 4) keep the earliest.//-------------------------------------------------------------------------------bool SphereTriangleCollide(	const Vector* V, const Vector& N,							// triangle							const Vector& P, const Vector& D, float r, float r2,		// sphere							float tmax, bool double_sided_tests,						// max time, and if we are doing double sided tests							Vector& Pcoll, Vector& Ncoll, Vector& Dcoll, float& tcoll)  // intersection params{	// signed distance of sphere centre to plane	float dist_to_plane = (P - V[0]) * N;		// impact velocity	float dn = D * N;		// plane - sphere collision parameters	float tplane;	Vector Pplane;		// is the sphere cut by plane	bool sphere_cut_by_plane = false;		// is the sphere centre back-facing the plane	bool sphere_back_facing = (dist_to_plane < -r);		// the plane offset for time of collision	float plane_offset = (sphere_back_facing)? -r : r;	// sphere behind the plane, and no double sided test	if (sphere_back_facing && !double_sided_tests)	{		return false;	}	//-----------------------------------------------------------	// sphere cut by the triangle plane	//-----------------------------------------------------------	if(fabs(dist_to_plane) < r)	{		sphere_cut_by_plane = true;		tplane = 0.0f;		Pplane = P - dist_to_plane * N;	}	//-----------------------------------------------------------	// Sphere outside the triangle plane	//-----------------------------------------------------------	else	{		// Sphere not mivong, and not in plane. no collision		if(fabs(dn) < 1.0E-8f)		{			return false;		}				// Sphere is moving		// time of intersection with the plane		tplane = (plane_offset - dist_to_plane) / dn;		// time of collision out of bounds.		if (tplane < 0.0f || tplane > tmax)			return false;		// point of collision on plane at time of impact.		Pplane = P + D * tplane - (plane_offset * N);	}	// sphere too far away from plane	if (tplane < 0.0f || tplane > tmax)	{		return false;	}	//-----------------------------------------------------------	// Test edge collisions one by one	//-----------------------------------------------------------	// Is the sphere found outside the triangle?	bool outside_of_triangle = false;	// have we collided with an edge?	bool collided = false;		int i = 2;	int ip1 = 0;	for(; ip1 < 3; i = ip1, ip1++)	{		// edge direction		Vector E = V[ip1] - V;				// edge length squared		float e2 = E * E;		// edge normal (perpendicular to edge, and triangle plane)		Vector En = E ^ N;		// relative position to edge start.		Vector H = Pplane - V;		// distance of P to edge plane		float hn = H * En;		// Found the point outside the edge		// Need to test against the edge		if (hn > 0.0f)		{			outside_of_triangle = true;			// distance of P along the edge			float he = (H * E);			//-------------------------------------------------------------------			// test collision with the first vertex of the edge			//-------------------------------------------------------------------			if(he < 0.0f)			{				// relative position f sphere centre				H = P - V;				// do a vertex-sphere collision time calculation				// find root of second order equation [P + D.t - Vi]^2 - r^2 = 0				float a = (D * D);				float b = 2.0f * (D * H);				float c = (H * H) - r2;				float d = b*b - 4 * a * c;				// missed the vertex. edge does not collide				if (d < 0.0f)				{					continue;				}				// possible intersection.				// calculate the times of collision				d = sqrt(d);								float t0 = (-b - d) / (2.0f * a);				float t1 = (-b + d) / (2.0f * a);				// sort the times of collision				if(t0 > t1)				{					float t= t0; 					t0 = t1;					t1 = t;				}				// vertex is too far away				// go to next edge				if (t0 > tmax || t1 < 0.0f)				{					continue;				}								// found the sphere embedded in the vertex				if(t0 <= 0.0f)				{					// report a sphere-vertex collision					float dist = H.Normalise();					tcoll = 0.0f;					Pcoll = V;					Ncoll = H;					Dcoll = (r - dist) * Ncoll;										// no need to continue further					collided = true;					break;				}								// move sphere to time of collision, and calculate the 				// relative positon from vertex				H += D * t0;								// distance to vertex at time of collision				float dist = H.Normalise();								tmax  = t0; // our new maximum time of collision found				tcoll = t0;				Pcoll = V;				Ncoll = H;				Dcoll = (r - dist) * Ncoll; // hopefully, 0.				// continue teh search, in case 				// another collision is closer.				collided = true;				continue;			}			//-------------------------------------------------------------------			// Test collsion with the end vertex			//-------------------------------------------------------------------			else if (he > e2)			{				// no need to test the end vertex. This will be done on the next edge				// as a start vertex collision.				// a end vertex is always a start vertex of another edge				/// due to the inherent edge loop in a closed polygon.				continue;			}			//-------------------------------------------------------------------			// Test collsion with the edge itself			//-------------------------------------------------------------------			else			{				// relative position f sphere centre				H = P - V;				// do a vertex-sphere collision time calculation				// find root of second order equation [(P + D.t - Vi) x E]^2 - r^2 = 0				Vector DxE = D ^ E;				Vector HxE = H ^ E;				float a = DxE * DxE;				float b = 2.0f * (DxE * HxE);				float c = (HxE * HxE) - r2 * e2;				float d = b*b - 4 * a * c;				// missed the vertex. edge does not collide				if (d < 0.0f)				{					continue;				}				// possible intersection.				// calculate the times of collision				d = sqrt(d);								float t0 = (-b - d) / (2.0f * a);				float t1 = (-b + d) / (2.0f * a);				// sort the times of collision				if(t0 > t1)				{					float t = t0; 					t0 = t1;					t1 = t;				}				// vertex is too far away				if (t0 > tmax || t1 < 0.0f)				{					continue;				}								// found the sphere embedded in the vertex				if(t0 < 0.0f)				{					// H is now perpendicular to edge direction					H -= E * (he / e2);					// report a sphere-vertex collision					float dist = H.Normalise();					tcoll = 0.0f;					Pcoll = V;					Ncoll = H;					Dcoll = (r - dist) * Ncoll;										// no need to continue further					collided = true;					break;				}				// found a collision				// move sphere to time of collision, and calculate the 				// relative positon from vertex				H += D * t0;						// H is now perpendicular to edge direction				H -= E * (he / e2);				// distance to vertex at time of collision				float dist = H.Normalise();								tmax  = t0; // our new maximum time of collision found				tcoll = t0;				Ncoll = H;				Pcoll = V + E * (he / e2);				Dcoll = (r - dist) * Ncoll; // hopefully, 0.				// continue teh search, in case 				// another collision is closer.				collided = true;				continue;			}		}	}	// deemed outside the triangle	if(outside_of_triangle)	{		// no edge-vertex collision found, maybe.		return collided;	}	// sphere inside triangle. 	// report a plane collision	tcoll = tplane;	Pcoll = Pplane;	Ncoll = (sphere_back_facing)? -N : N;	Dcoll = (sphere_cut_by_plane)? N * (plane_offset - dist_to_plane) : Vector(0, 0, 0);	collided = true;	return collided;}