🔒 Locked

sweep sphere vs triangle edge 3D intersect - response

Started by dubplatecode Apr 22, 2010 at 2:06 PM 9 replies 5.4k views

Original Post

Apr 22, 2010 at 2:06 PM

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[Edited by - chris2001net on April 22, 2010 2:32:14 PM]

CPPNick

May 1, 2010 at 11:24 PM

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

oliii

May 2, 2010 at 6:29 AM

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;}

oliii

May 2, 2010 at 6:40 AM

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.

CPPNick

May 5, 2010 at 2:04 AM

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?

oliii

May 5, 2010 at 5:18 AM

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.

CPPNick

May 5, 2010 at 9:38 AM

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?

oliii

May 5, 2010 at 10:32 AM

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();

CPPNick

May 5, 2010 at 11:38 AM

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!

oliii

May 5, 2010 at 11:39 AM

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^2bool 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;}

CPPNick

May 5, 2010 at 6:52 PM

Hey..Thanks bro. I can't bare to look at this code right now though lol
tomorrow is another day XD

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.