This topic is 3456 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'm writting code to test sweep sphere to triangle collision. I'm stuck on the sphere to edge response. I have (T) time along the sweep sphere path for the shortest distance to triangle edge, and distance to the edge at that point. I cant figure out how to find the path point where the sphere first intersected the edge line segment. Uploaded with ImageShack.us Trigonometry works ok but it fails when the lines are nearly parallel, see picture. Whats happening is the closest distance is found between two lines, but the collision point is before this point. if( edge_collision_found ) { float rr = radiussquare - closestdistance; //trigonomentry to figure out how far back the sphere needs to move float dd = sphere_velocity.length(); rr/= dd; rr = sqrtf(rr); T -= rr; T *= sphere_velocity.lengthsqrt(); if(firstcollision <-1.f || T<firstcollision) { first_collision_time = T; } } any suggestions? thanks [Edited by - chris2001net on April 22, 2010 2:32:14 PM]

Share on other sites
Funny you ask this question, because I am stuck at the same part. One thing I was thinking of differently though was this line:

float rr = radiussquare - closestdistance;

since A^2 + B^2 = C^2, and
closest distance should be a perpendicular line segment between the two lines, and the distance between t on the direction vector and the closest point on the edge should be radius^2, then we only have to solve for the third edge of the triangle. Then we subtract that third edge from the vector between the origin of the direction vector and the point where the two segments are closest, and that is the spheres collision position..does that sound right?

X^2 + closest_distance_vector^2 = radius^2

solve for X

then construct a vector from the origin of the direction vector to the point on the direction vector where the segs are closest.

finally subtract (X*normalized_direction) from that vector to get the spheres collided position.

I don't see any reason why this wouldn't work..but I don't think it would be nearly as fast as it could be...anywho, let me know what you think

Share on other sites
say you have a sphere (p, v, r) and you want to collision against edge (a, b).

The usual process is to find the times of intersect of ray (p, v) against the infinite cylinder (a, b, r).

a point q is on the cylinder surface if

((q - a) x (b - a))^2 = r^2 * ((b - a).(b - a))

So that's quite similar to a test of a sphere against a ray, which boils down to solving a quadratic equation.

Vector vxd = v.cross_product(b - a);
Vector pxd = (p - c).cross_product(b - a);

float a = vxd.dot_product(vxd);
float b = 2.0f * vxd.dot_product(pxd);
float c = pxd.dot_product(pxd) - (r*r) * (b - a).dot_product(b - a);

float d2 = b*b - (4.0f * a * c);
if(d2 < 0.0f) return false;

float d = sqrt(d2);
float t0 = (-b - d) / (2.0f * a);
float t1 = (-b + d) / (2.0f * a);

if(t0 > t1) swap(t0, t1);

t0 and t1 are the times the ray enters and exits the cylinder.

The position of the sphere at the first time of collision is then

p_enter = p + v * t0;

Now you check where that point is with respect to the edge start and end positions.

If that point is in front of 'a', then it means that the sphere will be tested against the vertex 'a'.

If that point is behind of 'b', then it means that the sphere will be tested against the vertex 'b'.

Else, the point is in between 'a' and 'b', and the cylinder collision will be the edge collision.

You can do that check like this.

float t = (p_enter - a).dot_product(b - a) / (b - a).dot_product(b - a);

if(t < 0.0f)
{
// you've hit the cylinder in front of 'a'.
// test against vertex 'a'.
}
else if(t > 1.of)
{
// you've hit the cylinder behind of 'b'.
// test against vertex 'b'.
}
else
{
// you've hit the cylinder between 'a' and 'b'.
t_collision = t0;
}

Share on other sites
I'm still a little confused. What I understand of the theory so far is this:

1. Form a cylinder from the path of the sphere
2. Find the intersections of the ray(triangle's edge) with the cylinder
3. Check if the intersections are beyond the end points of the triangle's edge to decide which vertex, if any, to colide with.
4. If both intersections are between the triangle edge ray's endpoints, then the sphere has to be tested against the edge itself.

This is where I am having trouble now. How do I find where the sphere hit the edge? I know you probably have it in your explanation, but I am just not seeing it for some reason. I can't use the Collision with the Cylinder can I? then what happens if the sphere hits the line dead on?

Share on other sites
Nope, it's the reverse process.

1) Form a cylinder from the edge points, and the radius of the sphere.
2) form a ray from the sphere path.
3) find intersections of ray and cylinder.
4) check if first intersection is beyond the end points of the triangle's edge to decide which vertex, if any, to colide with.
5) If first intersections is between the triangle edge ray's endpoints, then the sphere has to be tested against the edge itself.

In a way, the sphere radius is 'transferred' from the sphere to the edge, turning the edge into a cylinder, while the sphere is turned into a point.

If you know how to check when a sphere hits a vertex, then you'll know how to check if a sphere hits an infinite line, because the equations are virtually the same.

sphere(c, r) equation. 'p' is on sphere surface if : (p - c)^2 = r^2

cylinder(c, d, r) equation (d is the direction of the cylinder, normalised, c is a point on the centre of the cylinder). 'p' is on cylinder surface if : ((p - c) x d)^2 = r^2.

Share on other sites
Eureka! it makes sense, but for step 5, do I actually have to test again? Shouldn't the first intersection with the cylinder be the sphere's center at time of collision with the edge?

edit- wait!. I think I get it. I need to find the spot on the surface of the sphere to compute the normal of the sliding plane right?

Share on other sites
yes on both counts.

Once you found the time the sphere hits the edge, you use the point of contact at the time of intersection, and check if it is near a vertex, or on the edge itself.

If on the edge, the normal will be the the line shooting from the sphere centre to the point on the edge closest to the sphere centre.

Vector p_edge = a + (b - a) * t;
ncoll = (p_enter - p_edge);
ncoll.normalise();

Share on other sites
ok. I'm still a little foggy about the quadratic formula stuff, but I'm gonna start coding anyways. I think I can figure it out. Thanks for the help!

Share on other sites
here's the code if you're interested.

class Vector
{
public:
float x, y, z;

Vector(){}
Vector(float a, float b, float c) : x(a), y(b), z(c){}
Vector(const Vector& other) : x(other.x), y(other.y), z(other.z){}

Vector& operator += (const Vector& other) { x += other.x; y += other.y; z += other.z; return *this; }
Vector& operator -= (const Vector& other) { x -= other.x; y -= other.y; z -= other.z; return *this; }
Vector& operator *= (const float scalar) { x *= scalar; y *= scalar; z *= scalar; return *this; }
Vector& operator /= (const float scalar) { float inv = (1.0f / scalar); return (*this) *= inv; }

Vector operator + (const Vector& other) const { Vector temp(*this); return temp += other; }
Vector operator - (const Vector& other) const { Vector temp(*this); return temp -= other; }
Vector operator * (const float scalar) const { Vector temp(*this); return temp *= scalar; }
Vector operator / (const float scalar) const { Vector temp(*this); return temp /= scalar; }

Vector cross_product(const Vector& other) const { Vector temp(y*other.z-z*other.y, z*other.x-x*other.z, x*other.y-y*other.x); return temp; }
float dot_product(const Vector& other) const { return x*other.x + y*other.y + z*other.z; }

float length_squared() const { return (*this).dot_product(*this); }
float length() const { return sqrt(length_squared()); }
float normalise() { float l = length(); if(l > 1.0E-8f) (*this) /= l; return l; }

friend Vector operator * (float scalar, const Vector& v) { return v * scalar; }
};

// quadratic : a* t^2 + b*t + c = 0.
// d = b^2 - 4*a*c
// t0 = (-b - sqrt(d)) / (2 * a)
// t1 = (-b + sqrt(d)) / (2 * a)
bool solveQuadratic(float a, float b, float c, float& t0, float& t1)
{
float d2 = b*b - 4 * a * c;
if(d2 < 0.0f) return false;
float d = sqrt(d2);
t0 = (-b - d) / (2 * a);
t1 = (-b + d) / (2 * a);
if(t0 > t1) { float temp(t0); t0 = t1; t1 = temp; }
if(t1 < 0.0f || t0 > 1.0f) return false;
return true;
}

// ray (p, v)
// sphere (c, r)
// quadratic : ((p - c) + v * t)^2 = r^2
bool intersectRaySphere(const Vector& ray_origin,
const Vector& ray_direction,
const Vector& sphere_origin,
float& t_enter,
float& t_exit)
{
Vector p(ray_origin - sphere_origin);
float v2 = ray_direction.dot_product(ray_direction);
float p2 = p.dot_product(p);
float pv = p.dot_product(ray_direction);

float a = v2;
float b = pv * 2.0f;
float c = p2 - r2;

// ray direction very small.
if(a < 1.0E-8f)
{
// no intersection
if (c > 0.0f) return false;

// intersection
t_enter = t_exit = 0.0f;
return true;
}

return solveQuadratic(a, b, c, t_enter, t_exit);
}

// ray (p, v)
// cylinder (c, d, r)
// quadratic : ((p - c) x d + (v x d) * t)^2 = r^2 * (d.d)
bool intersectRayCylinder( const Vector& ray_origin,
const Vector& ray_direction,
const Vector& cylinder_origin,
const Vector& cylinder_direction,
float& t_enter,
float& t_exit)
{
Vector pxd = (ray_origin - cylinder_origin).cross_product(cylinder_direction);
Vector vxd = ray_direction.cross_product(cylinder_direction);
float d2 = cylinder_direction.dot_product(cylinder_direction);
float v2 = vxd.dot_product(vxd);
float p2 = pxd.dot_product(pxd);
float pv = pxd.dot_product(vxd);

float a = v2;
float b = pv * 2.0f;
float c = p2 - (r2 * d2);

// ray direction parallel to cylinder.
if(a < 1.0E-8f)
{
// no intersection
if (c > 0.0f) return false;

// intersection
t_enter = t_exit = 0.0f;
return true;
}

return solveQuadratic(a, b, c, t_enter, t_exit);
}

bool CollideSphereEdge( const Vector& sphere_centre,
const Vector& sphere_velocity,
const Vector& edge_start,
const Vector& edge_end,
Vector& collision_point, // point of collision on edge
Vector& collision_normal, // normal of collision
float& collision_depth, // depth of intersection in case the sphere is embedded in edge
float& collision_time) // time of collisoin. 0.0f if sphere intersects edge already.
{
// edge dir (not normalised)
Vector edge_dir(edge_end - edge_start);

// chech against infinite cylinder.
float t_enter, t_exit;
if(!intersectRayCylinder( sphere_centre,
sphere_velocity,
edge_start,
edge_dir,
t_enter,
t_exit))
{
// missed cylinder -> missed edge
return false;
}

// time of collision (the time we first hit the edge).
float t_collision = t_enter;

// intersecting. reset to 0.0f.
if(t_collision < 0.0f) t_collision = 0.0f;

// sphere centre position at time of collision.
Vector sphere_collision = sphere_centre + sphere_velocity * t_collision;

// which side of the edge the sphere is.
float u = (sphere_collision - edge_start).dot_product(edge_dir) / edge_dir.dot_product(edge_dir);

// point on the edge collided by the sphere
Vector edge_collision;

// sphere position before edge start. test against edge start vertex.
if(u < 0.0f)
{
// test against start vertex.
if(!intersectRaySphere( sphere_centre,
sphere_velocity,
edge_start,
t_enter,
t_exit))
{
// missed vertex -> missed edge.
return false;
}

// new time of collision
t_collision = t_enter;
if(t_collision < 0.0f) t_collision = 0.0f;

// re-compute the sphere position at new time of collision.
sphere_collision = sphere_centre + sphere_velocity * t_collision;

// point on edge is start point.
edge_collision = edge_start;
}
// sphere position after edge end. test against edge end vertex.
else if (u > 1.0f)
{
if(!intersectRaySphere( sphere_centre,
sphere_velocity,
edge_end,
t_enter,
t_exit))
{
// missed vertex -> missed edge.
return false;
}

// new time of collision
t_collision = t_enter;
if(t_collision < 0.0f) t_collision = 0.0f;

// re-compute the sphere position at new time of collision.
sphere_collision = sphere_centre + sphere_velocity * t_collision;

// point on edge is end point.
edge_collision = edge_end;
}
else
{
// point of collision on the edge.
edge_collision = edge_start + edge_dir * u;
}

collision_point = edge_collision; // collision point on edge.
collision_time = t_collision; // time of collision.
collision_normal = (sphere_collision - edge_collision); // normal of collision.
float d = collision_normal.normalise(); // disatnce of the sphere position and point of collision
collision_depth = (d < sphere_radius)? (sphere_radius- d) : 0.0f; // intersection depth, if intersecting.
return true;
}

• Game Developer Survey We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 15
• 21
• 26
• 11