Sign in to follow this  
chris2001net

sweep sphere vs triangle edge 3D intersect - response

Recommended Posts

chris2001net    215
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 this post


Link to post
Share on other sites
CPPNick    100
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 this post


Link to post
Share on other sites
oliii    2196
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 this post


Link to post
Share on other sites
oliii    2196
if you use a 'closest point' approach, you'll need an iterative solution. It's quite complicated in itself, and since you can solve the equation relatively easily, it's probably overkill.

Share this post


Link to post
Share on other sites
CPPNick    100
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 this post


Link to post
Share on other sites
oliii    2196
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 this post


Link to post
Share on other sites
CPPNick    100
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 this post


Link to post
Share on other sites
oliii    2196
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 this post


Link to post
Share on other sites
CPPNick    100
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 this post


Link to post
Share on other sites
oliii    2196
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,
const float sphere_radius,
float& t_enter,
float& t_exit)
{
Vector p(ray_origin - sphere_origin);
float r2 = (sphere_radius * sphere_radius);
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,
const float cylinder_radius,
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 r2 = (cylinder_radius * cylinder_radius);
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 float sphere_radius,
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,
sphere_radius,
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,
sphere_radius,
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,
sphere_radius,
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;
}


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this