Quote:

struct Box{public:	Box()	: m_centre(Vector(0, 0, 0))	, m_halfsize(Vector(0, 0, 0))	, m_color(0x00000000)	{		m_orientation[0] = Vector(0, 0, 0);		m_orientation[1] = Vector(0, 0, 0);		m_orientation[2] = Vector(0, 0, 0);	}	Box(const Vector& centre, const Vector& halfsize, const Vector* orientation, unsigned int color)	: m_centre(centre)	, m_halfsize(halfsize)	, m_color(color)	{		m_orientation[0] = orientation[0];		m_orientation[1] = orientation[1];		m_orientation[2] = orientation[2];	}	void render()	{		RenderBox(m_centre, m_halfsize, m_orientation, m_color, 0xffffffff);	}	// Separation Axis Theorem interface.	virtual int SAT_FaceCount() const { return 3; }	virtual const Vector& SAT_FaceNormal(int index) const { return m_orientation[index]; }	virtual int SAT_EdgeCount() const { return 3; }	virtual const Vector& SAT_EdgeDir(int index) const { return m_orientation[index]; }	virtual void SAT_Project(const Vector& axis, float& min, float& max) const	{		float rx = fabs(axis * m_orientation[0]) * m_halfsize[0];		float ry = fabs(axis * m_orientation[1]) * m_halfsize[1];		float rz = fabs(axis * m_orientation[2]) * m_halfsize[2];				float c  = m_centre * axis;		float r  = rx + ry + rz;		min = c - r;		max = c + r;	}	void place(const Vector& position)	{		m_centre = position;	}public:	unsigned int m_color;	Vector		 m_centre;	Vector		 m_halfsize;	Vector		 m_orientation[3];};struct SAT{public:	//----------------------------------------------------------------------------------------------------	// test collision and intersection along a direction.	// axis : the direction along which test for collision	// a, b : the two collision boxes.	// vel : relative velocity of box a against box b	// mtd, mtd2, intersecting : current state of our separation vector.	// Nenter, Nleave, tenter, tleave, colliding : current state of when and where the two boxes collide along vector 'vel'.	//----------------------------------------------------------------------------------------------------	static bool TestAxis(	const Vector& axis, const Box& a, const Box& b, const Vector& vel, // axis and box info							Vector& mtd, float& mtd2,	bool& intersecting, // intersection info							Vector& Nenter, Vector& Nleave, float& tenter, float& tleave, bool& colliding) // collision info	{		// intervals along axis		float mina, maxa;		float minb, maxb;		a.SAT_Project(axis, mina, maxa);		b.SAT_Project(axis, minb, maxb);		// calculate the two possible overlap ranges.		// either we overlap on the left or right sides.		float d0 = (maxb - mina); // 'left' side		float d1 = (maxa - minb); // 'right' side		float v  = (axis * vel);  // project velocity on axis for swept tests		// test intersections		intersecting &= TestAxis_Intersection(axis, d0, d1, mtd, mtd2);		// test collisions		colliding &= TestAxis_Collision(axis, d0, d1, v, Nenter, Nleave, tenter, tleave);				// we should be either intersecting or colliding		return (intersecting || colliding);	}	static bool TestAxis_Intersection(	const Vector& axis, float d0, float d1, 										Vector& mtd, float& mtd2)	{		// the axis length squared		float axis_length_squared = axis * axis;				// axis is degenerate. ignore.		if(axis_length_squared < 1.0E-8f)			return true;				// intervals do not overlap. no intersection.		if(d0 < 0.0f || d1 < 0.0f)			return false;				// find out if we overlap on the 'right' or 'left' of the object.		float overlap = (d0 < d1)? d0 : -d1;		// the mtd vector for that axis		Vector sep = axis * (overlap / axis_length_squared);		// the mtd vector length squared.		float sep_length_squared = (sep * sep);		// if that vector is smaller than our computed MTD (or the mtd hasn't been computed yet)		// use that vector as our current mtd.		if(sep_length_squared < mtd2 || mtd2 < 0.0f)		{			mtd2 = sep_length_squared;			mtd  = sep;		}		return true;	}	// SAT collision along an axis. t_enter and t_leave represent the first time of collision, and the time 	// when the objects stop intersecting.	static bool TestAxis_Collision(	const Vector& axis, float d0, float d1, float v, 									Vector& Nenter, Vector& Nleave, float& tenter, float& tleave)	{		// velocity perpendicular to axis or axis degenerate or velocity too small. ignore test.		if(fabs(v) < 1.0E-8f) 			return true;		Vector N0 = axis;		Vector N1 = -axis;		float t0 = d0 / v;  // estimated time of collision to the 'left' side		float t1 =-d1 / v;  // estimated time of collision to the 'right' side		// sort values on axis so we have a valid swept interval.		if(t0 > t1) 		{			float ttemp = t0;			t0 = t1;			t1 = ttemp;			Vector Ntemp = N0;			N0 = N1;			N1 = Ntemp;		}				// swept interval outside our range.		if(t1 < 0.0f) // || t0 > 1.0f)			return false;				// first swept test. 		if(tenter > tleave)		{			tenter = t0;			tleave = t1;			Nenter = N0;			Nleave = N1;			return true;		}		// collision missed.		if(t0 > tleave || t1 < tenter)			return false;		// minimise the collision interval		if (t0 > tenter)		{			tenter = t0;			Nenter = N0;		}		if (t1 < tleave)		{			tleave = t1;			Nleave = N1;		}		// colliding.		return true;	}	static bool TestBoxes(	const Box& a, const Vector& va, 							const Box& b, const Vector& vb, 							Vector& mtd, Vector& ncoll, float& tcoll, 							bool& colliding, bool& intersecting)	{		intersecting = true;		colliding = true;		mtd = Vector(0, 0, 0);		ncoll = Vector(0, 0, 0);		tcoll = 0.0f;		// initialise to impossible values.		float mtd2 = -1.0f;		float t_enter = 1.0f;		float t_leave = 0.0f;		// the normals of the faces when we first collide, and when the two objects stop intersecting along the velocity vector.		Vector n_enter;		Vector n_leave;		// relative velocity of the boxes.		Vector vel = (va - vb);		// test a face dirs		for(int i = 0; i < a.SAT_FaceCount(); i ++)		{			if(!TestAxis(a.SAT_FaceNormal(i), 						 a, b, vel, 						 mtd, mtd2, intersecting, 						 n_enter, n_leave, t_enter, t_leave, colliding))			{				return false;			}		}		// test b face dirs		for(int i = 0; i < b.SAT_FaceCount(); i ++)		{			if(!TestAxis(b.SAT_FaceNormal(i), 						 a, b, vel, 						 mtd, mtd2, intersecting, 						 n_enter, n_leave, t_enter, t_leave, colliding))			{				return false;			}		}		// test edges cross dirs			for(int i = 0; i < a.SAT_EdgeCount(); i ++)		{			const Vector& a_edge = a.SAT_EdgeDir(i);			for(int j = 0; j < b.SAT_EdgeCount(); j ++)			{				const Vector& b_edge = b.SAT_EdgeDir(j);				Vector axis = a_edge ^ b_edge;				if(!TestAxis(axis, 							 a, b, vel, 							 mtd, mtd2, intersecting, 							 n_enter, n_leave, t_enter, t_leave, colliding))				{					return false;				}			}		}		// no intersections were ever tested.		if(mtd2 < 0.0f) intersecting = false;		// no collision were ever tested.		if(t_enter > t_leave) colliding = false;		// intersection failed. reset mtd to 0.		if(!intersecting)		{			mtd = Vector(0, 0, 0);		}		// we have collided. setup collision params.		if(colliding)		{			tcoll = t_enter;			ncoll = n_enter;			ncoll.Normalise();		}		// no collision reported (box could have the same velocity).		// in that case, use the mtd as normal of collision.		else		{			if(intersecting)			{				ncoll = mtd;				ncoll.Normalise();			}		}		// return intersection or collision.		return (colliding || intersecting);	}};

Quote:

struct Box{public:	Box()	: m_centre(Vector(0, 0, 0))	, m_halfsize(Vector(0, 0, 0))	, m_color(0x00000000)	{		m_orientation[0] = Vector(0, 0, 0);		m_orientation[1] = Vector(0, 0, 0);		m_orientation[2] = Vector(0, 0, 0);	}	Box(const Vector& centre, const Vector& halfsize, const Vector* orientation, unsigned int color)	: m_centre(centre)	, m_halfsize(halfsize)	, m_color(color)	{		m_orientation[0] = orientation[0];		m_orientation[1] = orientation[1];		m_orientation[2] = orientation[2];	}	void render()	{		RenderBox(m_centre, m_halfsize, m_orientation, m_color, 0xffffffff);	}	// Separation Axis Theorem interface.	virtual int SAT_FaceCount() const { return 3; }	virtual const Vector& SAT_FaceNormal(int index) const { return m_orientation[index]; }	virtual int SAT_EdgeCount() const { return 3; }	virtual const Vector& SAT_EdgeDir(int index) const { return m_orientation[index]; }	virtual void SAT_Project(const Vector& axis, float& min, float& max) const	{		float rx = fabs(axis * m_orientation[0]) * m_halfsize[0];		float ry = fabs(axis * m_orientation[1]) * m_halfsize[1];		float rz = fabs(axis * m_orientation[2]) * m_halfsize[2];				float c  = m_centre * axis;		float r  = rx + ry + rz;		min = c - r;		max = c + r;	}	void place(const Vector& position)	{		m_centre = position;	}public:	unsigned int m_color;	Vector		 m_centre;	Vector		 m_halfsize;	Vector		 m_orientation[3];};struct SAT{public:	//----------------------------------------------------------------------------------------------------	// test collision and intersection along a direction.	// axis : the direction along which test for collision	// a, b : the two collision boxes.	// vel : relative velocity of box a against box b	// mtd, mtd2, intersecting : current state of our separation vector.	// Nenter, Nleave, tenter, tleave, colliding : current state of when and where the two boxes collide along vector 'vel'.	//----------------------------------------------------------------------------------------------------	static bool TestAxis(	const Vector& axis, const Box& a, const Box& b, const Vector& vel, // axis and box info							Vector& mtd, float& mtd2,	bool& intersecting, // intersection info							Vector& Nenter, Vector& Nleave, float& tenter, float& tleave, bool& colliding) // collision info	{		// intervals along axis		float mina, maxa;		float minb, maxb;		a.SAT_Project(axis, mina, maxa);		b.SAT_Project(axis, minb, maxb);		// calculate the two possible overlap ranges.		// either we overlap on the left or right sides.		float d0 = (maxb - mina); // 'left' side		float d1 = (maxa - minb); // 'right' side		float v  = (axis * vel);  // project velocity on axis for swept tests		// test intersections		intersecting &= TestAxis_Intersection(axis, d0, d1, mtd, mtd2);		// test collisions		colliding &= TestAxis_Collision(axis, d0, d1, v, Nenter, Nleave, tenter, tleave);				// we should be either intersecting or colliding		return (intersecting || colliding);	}	static bool TestAxis_Intersection(	const Vector& axis, float d0, float d1, 										Vector& mtd, float& mtd2)	{		// the axis length squared		float axis_length_squared = axis * axis;				// axis is degenerate. ignore.		if(axis_length_squared < 1.0E-8f)			return true;				// intervals do not overlap. no intersection.		if(d0 < 0.0f || d1 < 0.0f)			return false;				// find out if we overlap on the 'right' or 'left' of the object.		float overlap = (d0 < d1)? d0 : -d1;		// the mtd vector for that axis		Vector sep = axis * (overlap / axis_length_squared);		// the mtd vector length squared.		float sep_length_squared = (sep * sep);		// if that vector is smaller than our computed MTD (or the mtd hasn't been computed yet)		// use that vector as our current mtd.		if(sep_length_squared < mtd2 || mtd2 < 0.0f)		{			mtd2 = sep_length_squared;			mtd  = sep;		}		return true;	}	// SAT collision along an axis. t_enter and t_leave represent the first time of collision, and the time 	// when the objects stop intersecting.	static bool TestAxis_Collision(	const Vector& axis, float d0, float d1, float v, 									Vector& Nenter, Vector& Nleave, float& tenter, float& tleave)	{		// velocity perpendicular to axis or axis degenerate or velocity too small. ignore test.		if(fabs(v) < 1.0E-8f) 			return true;		Vector N0 = axis;		Vector N1 = -axis;		float t0 = d0 / v;  // estimated time of collision to the 'left' side		float t1 =-d1 / v;  // estimated time of collision to the 'right' side		// sort values on axis so we have a valid swept interval.		if(t0 > t1) 		{			float ttemp = t0;			t0 = t1;			t1 = ttemp;			Vector Ntemp = N0;			N0 = N1;			N1 = Ntemp;		}				// swept interval outside our range.		if(t1 < 0.0f) // || t0 > 1.0f)			return false;				// first swept test. 		if(tenter > tleave)		{			tenter = t0;			tleave = t1;			Nenter = N0;			Nleave = N1;			return true;		}		// collision missed.		if(t0 > tleave || t1 < tenter)			return false;		// minimise the collision interval		if (t0 > tenter)		{			tenter = t0;			Nenter = N0;		}		if (t1 < tleave)		{			tleave = t1;			Nleave = N1;		}		// colliding.		return true;	}	static bool TestBoxes(	const Box& a, const Vector& va, 							const Box& b, const Vector& vb, 							Vector& mtd, Vector& ncoll, float& tcoll, 							bool& colliding, bool& intersecting)	{		intersecting = true;		colliding = true;		mtd = Vector(0, 0, 0);		ncoll = Vector(0, 0, 0);		tcoll = 0.0f;		// initialise to impossible values.		float mtd2 = -1.0f;		float t_enter = 1.0f;		float t_leave = 0.0f;		// the normals of the faces when we first collide, and when the two objects stop intersecting along the velocity vector.		Vector n_enter;		Vector n_leave;		// relative velocity of the boxes.		Vector vel = (va - vb);		// test a face dirs		for(int i = 0; i < a.SAT_FaceCount(); i ++)		{			if(!TestAxis(a.SAT_FaceNormal(i), 						 a, b, vel, 						 mtd, mtd2, intersecting, 						 n_enter, n_leave, t_enter, t_leave, colliding))			{				return false;			}		}		// test b face dirs		for(int i = 0; i < b.SAT_FaceCount(); i ++)		{			if(!TestAxis(b.SAT_FaceNormal(i), 						 a, b, vel, 						 mtd, mtd2, intersecting, 						 n_enter, n_leave, t_enter, t_leave, colliding))			{				return false;			}		}		// test edges cross dirs			for(int i = 0; i < a.SAT_EdgeCount(); i ++)		{			const Vector& a_edge = a.SAT_EdgeDir(i);			for(int j = 0; j < b.SAT_EdgeCount(); j ++)			{				const Vector& b_edge = b.SAT_EdgeDir(j);				Vector axis = a_edge ^ b_edge;				if(!TestAxis(axis, 							 a, b, vel, 							 mtd, mtd2, intersecting, 							 n_enter, n_leave, t_enter, t_leave, colliding))				{					return false;				}			}		}		// no intersections were ever tested.		if(mtd2 < 0.0f) intersecting = false;		// no collision were ever tested.		if(t_enter > t_leave) colliding = false;		// intersection failed. reset mtd to 0.		if(!intersecting)		{			mtd = Vector(0, 0, 0);		}		// we have collided. setup collision params.		if(colliding)		{			tcoll = t_enter;			ncoll = n_enter;			ncoll.Normalise();		}		// no collision reported (box could have the same velocity).		// in that case, use the mtd as normal of collision.		else		{			if(intersecting)			{				ncoll = mtd;				ncoll.Normalise();			}		}		// return intersection or collision.		return (colliding || intersecting);	}};