Basic 3d collision detection question involving lines and spheres...
Author
Hi, I'm trying to come up with an idea for really basic collision detection between 3d objects. By basic I basically mean spherical collision detection, eg checking the distances.
I've just thought of this idea where say you find the largest distance from an object's vertex to its centre, the radius for the spherical collision detection.
So say you got objects of all sizes, you would pick the largest radius out of the lot.
Then you would create a line for each object between its last position and its next position.
You would then divide each of the (x1,y1,z1)-(x2,y2,z2) points of each line by the largest radius eg: int(x1/radius),int(y1/radius),int(z1/radius) etc.
And basically just find if any of the lines intersect, if they do, you have a basic collision.
Does this sound feasible to anyone?
Thanks
That method won't work. The following diagram demonstrates why. Objects 'o' and 'x' will obviosly collide, but the directional lines don't intersect.
^ | x | x x o x x o o x x o o x o o | o | v
Author
Quote:Original post by Dave Hunt
That method won't work. The following diagram demonstrates why. Objects 'o' and 'x' will obviosly collide, but the directional lines don't intersect.^ | x | x x o x x o o x x o o x o o | o | v
hmmm say that diagram is before dividing by radius.
Then after they would be on the same line...
hmm, but the basic of sphere collision is u find the distance between the 2 objects centers & u compare it to the value u get by adding the 2 sphere radiuses together. so why complicate life.
Collision detection between two spheres travelling in a straight line is not particularly complicated. Say you have two spheres with radii r1 and r2 respectively. Your first sphere is at position P1 and moving with velocity V1 whilst your second sphere is at position P2 and moving with velocity V2. At any time t your first sphere is at P1 + tV1 and your second sphere is at P2 + tV2. To find the length of a vector you use:
d = √(x² + y² + z²).
In vector terms this is written:
d = |A|
and is equivalent to:
d = √(A.A)
where A is the vector in question. To find a collision between two spheres you want to find the point where the distance between their centers is equal to the sum of their radii:
|(P1 + tV1) - (P2 + tV2)| = r1 + r2
This can be rearranged to:
|(P1 - P2) + t(V1 - V2)| = r1 + r2
By using:
|A| = √(A.A)
we can rewrite this as:
√(((P1 - P2) + t(V1 - V2)).((P1 - P2) + t(V1 - V2))) = r1 + r2
Squaring both sides gives:
((P1 - P2) + t(V1 - V2)).((P1 - P2) + t(V1 - V2)) = (r1 + r2)²
This can then be rearranged to:
(P1 - P2).(P1 - P2) + 2t(P1 - P2).(V1 - V2) + t²(V1 - V2).(V1 - V2) = (r1 + r2)²
which is a simple quadratic equation in t. Rearranging it into at² + bt + c = 0 form gives:
(V1 - V2).(V1 - V2)t² + 2(P1 - P2).(V1 - V2)t + (P1 - P2).(P1 - P2) - (r1 + r2)² = 0
We can now use the standard quadratic equation:
t = (-b ± √(b² - 4ac)) / 2a
Which drops out to:
t = (-2(P1 - P2).(V1 - V2) ± √(4((P1 - P2).(V1 - V2))² - 4(V1 - V2).(V1 - V2)((P1 - P2).(P1 - P2) - (r1 + r2)²))) / 2(V1 - V2).(V1 - V2)
This gives two solutions for t, the next time of collision. These two solutions are the time when the two spheres make contact and the time when the two spheres cease to make contact, assuming that they continued travelling through each other. Either or both of these solutions may be negative, or a solution may not exist (if the root term b² - 4ac is negative).
Here's some example code demonstrating how to implement and use this equation:
Enigma
d = √(x² + y² + z²).
In vector terms this is written:
d = |A|
and is equivalent to:
d = √(A.A)
where A is the vector in question. To find a collision between two spheres you want to find the point where the distance between their centers is equal to the sum of their radii:
|(P1 + tV1) - (P2 + tV2)| = r1 + r2
This can be rearranged to:
|(P1 - P2) + t(V1 - V2)| = r1 + r2
By using:
|A| = √(A.A)
we can rewrite this as:
√(((P1 - P2) + t(V1 - V2)).((P1 - P2) + t(V1 - V2))) = r1 + r2
Squaring both sides gives:
((P1 - P2) + t(V1 - V2)).((P1 - P2) + t(V1 - V2)) = (r1 + r2)²
This can then be rearranged to:
(P1 - P2).(P1 - P2) + 2t(P1 - P2).(V1 - V2) + t²(V1 - V2).(V1 - V2) = (r1 + r2)²
which is a simple quadratic equation in t. Rearranging it into at² + bt + c = 0 form gives:
(V1 - V2).(V1 - V2)t² + 2(P1 - P2).(V1 - V2)t + (P1 - P2).(P1 - P2) - (r1 + r2)² = 0
We can now use the standard quadratic equation:
t = (-b ± √(b² - 4ac)) / 2a
Which drops out to:
t = (-2(P1 - P2).(V1 - V2) ± √(4((P1 - P2).(V1 - V2))² - 4(V1 - V2).(V1 - V2)((P1 - P2).(P1 - P2) - (r1 + r2)²))) / 2(V1 - V2).(V1 - V2)
This gives two solutions for t, the next time of collision. These two solutions are the time when the two spheres make contact and the time when the two spheres cease to make contact, assuming that they continued travelling through each other. Either or both of these solutions may be negative, or a solution may not exist (if the root term b² - 4ac is negative).
Here's some example code demonstrating how to implement and use this equation:
#include <algorithm>#include <cmath>#include <ctime>#include <vector>#include <boost/bind.hpp>#include <GL/glut.h>// basic three dimensional vector classclass Vector{ public: explicit Vector(); explicit Vector(float x, float y, float z); float dot(Vector const & vector) const; Vector & operator+=(Vector const & vector); Vector & operator-=(Vector const & vector); Vector & operator*=(float scalar); Vector & operator/=(float scalar); float x_; float y_; float z_;};Vector::Vector() : x_(0), y_(0), z_(0){}Vector::Vector(float x, float y, float z) : x_(x), y_(y), z_(z){}float Vector::dot(Vector const & vector) const{ return (x_ * vector.x_) + (y_ * vector.y_) + (z_ * vector.z_);}Vector & Vector::operator+=(Vector const & vector){ x_ += vector.x_; y_ += vector.y_; z_ += vector.z_; return *this;}Vector & Vector::operator-=(Vector const & vector){ x_ -= vector.x_; y_ -= vector.y_; z_ -= vector.z_; return *this;}Vector & Vector::operator*=(float scalar){ x_ *= scalar; y_ *= scalar; z_ *= scalar; return *this;}Vector & Vector::operator/=(float scalar){ x_ /= scalar; y_ /= scalar; z_ /= scalar; return *this;}Vector operator+(Vector lhs, Vector const & rhs){ return (lhs += rhs);}Vector operator-(Vector lhs, Vector const & rhs){ return (lhs -= rhs);}Vector operator*(Vector lhs, float rhs){ return (lhs *= rhs);}Vector operator*(float lhs, Vector rhs){ return (rhs *= lhs);}Vector operator/(Vector lhs, float rhs){ return (lhs /= rhs);}Vector operator/(float lhs, Vector rhs){ return (rhs /= lhs);}void glTranslatef(Vector const & vector){ glTranslatef(vector.x_, vector.y_, vector.z_);}// main collision detection functionbool collides(Vector const & object1Start, Vector const & object2Start, Vector const & object1End, Vector const & object2End, float object1Radius, float object2Radius){ // collisionRadiusSquared = (r1 + r2)² float collisionRadius = object1Radius + object2Radius; float collisionRadiusSquared = collisionRadius * collisionRadius; // startPositionDifference = P1 - P2 Vector startPositionDifference = object1Start - object2Start; // directionDifference = V1 - V2 Vector directionDifference = (object1End - object1Start) - (object2End - object2Start); // startPositionDifferenceDotSelf = (P1 - P2).(P1 - P2) float startPositionDifferenceDotSelf = startPositionDifference.dot(startPositionDifference); // directionDifferenceDotSelf = (V1 - V2).(V1 - V2) float directionDifferenceDotSelf = directionDifference.dot(directionDifference); // handle the case where the spheres are travelling along parallel paths are identical speed if (directionDifferenceDotSelf == 0) { // if they are already colliding then they will remain colliding if (startPositionDifferenceDotSelf <= collisionRadiusSquared) { return true; } // otherwise they are not colliding return false; } // startPositionDifferenceDotDirectionDifference = (P1 - P2).(V1 - V2) float startPositionDifferenceDotDirectionDifference = startPositionDifference.dot(directionDifference); // rootTerm = b² - 4ac float rootTerm = (startPositionDifferenceDotDirectionDifference * startPositionDifferenceDotDirectionDifference) - (directionDifferenceDotSelf * (startPositionDifferenceDotSelf - collisionRadiusSquared)); // can't take the square root of a negative number - no solutions so not colliding if (rootTerm < 0) { return false; } // find the two solutions float root = std::sqrt(rootTerm); float t1 = (-startPositionDifferenceDotDirectionDifference + root) / directionDifferenceDotSelf; float t2 = (-startPositionDifferenceDotDirectionDifference - root) / directionDifferenceDotSelf; // if one solution is in the past and the other is in the future then we are currently colliding return (t1 < 0 && t2 >= 0) || (t1 >= 0 && t2 < 0);};void reshape(int width, int height){ if (height == 0) { height = 1; } glMatrixMode(GL_PROJECTION); glLoadIdentity(); glViewport(0,0,width,height); gluPerspective(45.0f,(GLfloat)width/(GLfloat)height,10.0f,200.0f); glMatrixMode(GL_MODELVIEW); glLoadIdentity();}// generate a random number in the range [min, max]float random(float min, float max){ return ((std::rand() * (max - min)) / RAND_MAX) + min;}class Sphere{ public: Sphere(); void clearCollisions(); void collide(float time, Sphere & sphere); void render() const; void update(float time); private: Vector position_; Vector velocity_; float radius_; bool colliding_;};// generate a random sphereSphere::Sphere() : position_(Vector(random(-20, 20), random(-20, 20), random(-20, 20))), velocity_(Vector(random(-10, 10), random(-10, 10), random(-10, 10))), radius_(random(1, 5)), colliding_(false){}void Sphere::clearCollisions(){ colliding_ = false;}// check if this sphere collides with the given spherevoid Sphere::collide(float time, Sphere & sphere){ if (collides(position_, sphere.position_, position_ + (velocity_ * time), sphere.position_ + (sphere.velocity_ * time), radius_, sphere.radius_)) { colliding_ = true; sphere.colliding_ = true; }}void Sphere::render() const{ if (colliding_) { glColor3f(1, 0, 0); } else { glColor3f(1, 1, 1); } glPushMatrix(); glTranslatef(position_); glutSolidSphere(radius_, 16, 16); glPopMatrix();}// update the sphere. Wrap it around if it moves too far.void Sphere::update(float time){ position_ += (velocity_ * time); if (position_.x_ < -40) { position_.x_ += 80; } if (position_.y_ < -40) { position_.y_ += 80; } if (position_.z_ < -40) { position_.z_ += 80; } if (position_.x_ > 40) { position_.x_ -= 80; } if (position_.y_ > 40) { position_.y_ -= 80; } if (position_.z_ > 40) { position_.z_ -= 80; }}std::vector< Sphere > spheres;float time;// check if the subject collides with any of the spheres in the range [first, last)template < typename ForwardIterator >void checkCollisions(ForwardIterator subject, ForwardIterator first, ForwardIterator last, float deltaTime){ std::for_each(first, last, boost::bind(Sphere::collide, subject, deltaTime, _1));}// for each sphere check if it collides with any other spheretemplate < typename ForwardIterator >void checkCollisions(ForwardIterator first, ForwardIterator last, float deltaTime){ if (first == last) { return; } ForwardIterator subject = first; ++first; while (first != last) { checkCollisions(subject, first, last, deltaTime); ++first; ++subject; }}void display(){ glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT | GL_STENCIL_BUFFER_BIT); glLoadIdentity(); glTranslatef(0, 0, -160); float currentTime = std::clock(); float deltaTime = (currentTime - time) / 1000.0f; std::for_each(spheres.begin(), spheres.end(), boost::bind(Sphere::clearCollisions, _1)); checkCollisions(spheres.begin(), spheres.end(), deltaTime); std::for_each(spheres.begin(), spheres.end(), boost::bind(Sphere::update, _1, deltaTime)); glEnable(GL_LIGHTING); std::for_each(spheres.begin(), spheres.end(), boost::bind(Sphere::render, _1)); glDisable(GL_LIGHTING); glColor3f(1, 1, 1); // render an 80 by 80 by 80 box that our spheres inhabit glBegin(GL_LINES); glVertex3f(-40, -40, -40); glVertex3f(40, -40, -40); glVertex3f(40, -40, -40); glVertex3f(40, 40, -40); glVertex3f(40, 40, -40); glVertex3f(-40, 40, -40); glVertex3f(-40, 40, -40); glVertex3f(-40, -40, -40); glVertex3f(-40, -40, 40); glVertex3f(40, -40, 40); glVertex3f(40, -40, 40); glVertex3f(40, 40, 40); glVertex3f(40, 40, 40); glVertex3f(-40, 40, 40); glVertex3f(-40, 40, 40); glVertex3f(-40, -40, 40); glVertex3f(-40, -40, -40); glVertex3f(-40, -40, 40); glVertex3f(40, -40, -40); glVertex3f(40, -40, 40); glVertex3f(40, 40, -40); glVertex3f(40, 40, 40); glVertex3f(-40, 40, -40); glVertex3f(-40, 40, 40); glEnd(); time = currentTime; glutSwapBuffers();}int main(int argc, char** argv){ glutInit(&argc, argv); glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGBA); glutInitWindowPosition(0, 0); glutInitWindowSize(800,600); glutCreateWindow("Collision Detection Test"); glutReshapeFunc(reshape); glutDisplayFunc(display); glutIdleFunc(display); time = std::clock(); for (unsigned int sphere = 0; sphere < 64; ++sphere) { spheres.push_back(Sphere()); } glEnable(GL_LIGHT0); glEnable(GL_COLOR_MATERIAL); glEnable(GL_DEPTH_TEST); glutMainLoop(); return 0;}Enigma
Author
Quote:Original post by ZeRaW
hmm, but the basic of sphere collision is u find the distance between the 2 objects centers & u compare it to the value u get by adding the 2 sphere radiuses together. so why complicate life.
because the main reason Im doing this is to find the first collision of all the objects while in that current loop, so I then do a another loop within the main loop and play out all the collisions that would occur during the main loop, basically stepping thru the collisions and responses until i can goto the next main loop and all the objects are in the right place, eg basically i split one main loop into a bunch of chunks.
I haven't totally worked this idea out yet,
thanks Enigma, im having a look at your stuff now..
Quote:Original post by johnnyBravo
hmmm say that diagram is before dividing by radius.
Then after they would be on the same line...
No. Dividing by the radius only scales the lines. It doesn't change their direction. For example:
Line 1: (2,2)-(2,6)Line 2: (4,4)-(4,0)Radius: 2After division:Line 1: (1,1)-(1,3)Line 2: (2,2)-(2,0)Those lines don't intersect.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
