The code is a bit more complicated though. Worth 1/2 hour. This is lifted from the 2D polygon test, and not tested.
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); }};
NOTE : the operator '*' between two vectors is a dot product.
NOTE : the operator '^' between two vectors is a cross product.
[Edited by - oliii on June 24, 2009 4:30:11 AM]