# Problem with sphere/triangle collisions

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

## Recommended Posts

So I've implemented the "sweping sphere" according to this paper. But it's weird, because it doesnt work for some edges/vertices. Right now I try to get it to work for the vertex (0,0,0). I have a right triangle and if I try to move into the left lowest corner, I move a bit "into" the triangle... the same goes for the lower edge, I can go through it with the top of the spere. But for some other edges, it works perfectly, the collisions are water-tight. So the collision is detected somewhat "late", like here here and here I dont know what it could be. Here is the important code in C# (I use the DirectX classes for Vectors). I use a sphere of radius 1, everything according the to article above.
// Solve the quadratic at^2+bt+c = 0 and check for vali roots, i.e. that are between 0 and max.
public bool LowestRoot(float a, float b, float c, float max, ref float root) {
if (b * b - 4.0f * a * c < 0.0f)
return false;
float r1, r2;
r1 = (-b - (float)Math.Sqrt(b * b - 4 * a * c))/(2*a);
r2 = (-b + (float)Math.Sqrt(b * b - 4 * a * c)) / (2 * a);

if (r1 > r2)
{
float temp = r1;
r1 = r2; r2 = temp;
}

if (r1 > 0 && r1 < max)
{
root = r1;
return true;
}
else if (r2 > 0 && r2 < max)
{
root = r2;
return true;
}

return false;
}

public bool LineVertexIntersection(Line line, Vector3 vertex, ref float t)
{
float A = Vector3.LengthSq(line.v);
float B = 2.0f * Vector3.Dot(line.v, line.p - vertex);
float C = Vector3.LengthSq(vertex - line.p) - 1.0f;
float root = 0;

if(LowestRoot(A,B,C, t, main, ref root)) {
t = root;
return true;
}

return false;
}


I call the function above for my moving sphere, and you can see the result in the images. When I collision is detected, I choose not to move the sphere, so there's no way it should look like that if the collision detection worked properly [Edited by - zurekx on June 25, 2008 10:43:34 AM]

##### Share on other sites
Back-tracing the ray from the closest point will fail sometimes. The problem is that a few iterations are required for it to work.

something like this.

//-----------------------------------------------------------------------------// test collision of a ball [m_position, m_velocity, m_radius] against // a axis aligned box [centre, halfsize].// --------------------------------------------------// This algo is iterative, and will work in a way like GJK works// 1) let {p} = {m_position}.// 2) find closest point {pcoll} on box to {p}.// 3) if that point within radius distance, then we have a collision// 4) else, compute the plane normal, {normal} = [{p} - {pcoll}].normalised().// 5) find time {t} of collision with the plane [{pcoll}, {normal}].// 6) if {t} > {tmax}, or point {m_position} back-facing the plane, no collision, we missed.// 7) move {p} to time of collision : {p} = {m_position} + {m_velocity} * {t}.// 8) go to 2).//-----------------------------------------------------------------------------bool Ball::collide(const Vector& centre, const Vector& halfsize, float& tcoll, Vector& pcoll, float tmax) const{	// search time	float t = 0.0f;	// search position. 	// we will advance the ball forward	// and refine the collision plane	Vector p = m_position;	// radius, plus some extra to terminate the collision iteration.	float r2 = ((m_radius + 0.01f) * (m_radius + 0.01f));	int iter = 0;		while (1)	{		iter++;		if(iter == 2) printf("iter: %d", iter);		else if(iter > 2) printf(", %d", iter);		// find the closest point on box from our search position.		bool inside;		pcoll = closestPointOnBox(p, centre, halfsize, inside);				// position inside the box.  		// extreme case when the ball gets inside a brick.		if(inside)		{			if(iter >= 2) printf("\n");			tcoll = t;			return true;		}		// check to see if that point can be our 		// final collison point		Vector delta = (p - pcoll);				// see if the point is inside our radius (plus extra).		float d2 = (delta.dotProduct(delta));				// yup, so we have collision		if(d2 < r2)		{			// we have an intersection.			if(iter >= 2) printf("\n");			tcoll = t;			return true;		}		// compute the normal of the plane of collision		Vector n = delta;		n /= sqrt(d2);		// find time of collision with that plane		float denom = (m_velocity * n);		float numer = ((m_position - pcoll).dotProduct(n));				// condition when the search becomes invalid		// (the ball misses the object).		if(denom > -1.0E-8f || numer < 0.0f) 		{			if(iter >= 2) printf("\n");			return false;		}					// find time of collision between 		// ball and the new collision plane		t = (m_radius - numer) / denom;				// intersection with that plane if invalid		if(t > tmax || t < 0.0f) 		{			if(iter >= 2) printf("\n");			return false;		}		// move search position forward.		p = m_position + m_velocity * t;	}}

In short, the algo they use would be doing one iteration of that routine. It needs a few more for edges and vertices.

the closestPointonBox() can be replaced with the ClosestPointOnTriangle() for testing against triangles.

However, dont use that code yet, It's still prototype. But in short, I believe the algo in that paper isn't 100%.

The root solving isn;t the problem, the problem is using the closest point as the opint of collision.

##### Share on other sites
Thanks for the reply! I dont really understand what you mean, could you explain it a little bit more? What back-tracing are you talking about? I only have one single triangle.. shouldnt I be able to detect whether or not Im colliding with e vertex? I just have a single vertex right now.

##### Share on other sites
It's the way the compute the collision point by using a ray fired from the closest point on the triangle, and using the opposite direction of the ray, and finding the intersection with the sphere.

For a single vertex, the algo you have should work. But as I said, it will not work 100% with the edges.

##### Share on other sites
Let me clearify things a little :) All I want to do (right now, Im debugging) is to check collision between the moving sphere and the single vertex (0,0,0), I ignore the triangle and the edges and all that. So I move the sphere around with the keyboard. For each frame, I compute the line between the old and new position, and I want to know if the sphere, somewhere along this line, intersects the vertex. I mean, that should work right? But for some reason, it gives the wrong answer for some vertices, which is weird.

Edit: feel like i should kill myself. Had some old code from my old intersection-code which only worked for a point..when drawing the sphere, I added 0.5 to the y-coordinate so it would "stand" on the ground. So my collision code is correct, I just rendered the sphere at the wrong place. Sorry!

##### Share on other sites
I saw nothing wrong with the code.

##### Share on other sites

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