# Sphere and rectangle collision, adjusting for intersection

## Recommended Posts

simotix    142
I am currently doing a sphere to rectangle collision in which case I can find if it has collision, no collision or resting contact. While finding the resting contact I have to get the intersection depth. However, if how can I adjust the spheres position so that way it is no longer intersecting? I tried to scurry the internet, however, I just do not see much on the topic. Here is my currently implementation.
	D3DXMATRIX mTransform = *pCollisionRectangle->GetTransform();
D3DXMATRIX mInverseTransform;
D3DXMatrixInverse(&mInverseTransform, NULL, &mTransform);

D3DXVECTOR4 vLocalPoint4;
D3DXVECTOR3 vLocalPoint;
D3DXVec3Transform(&vLocalPoint4, &pCollisionSphere->GetOrigin(), &mInverseTransform);
vLocalPoint = D3DXVECTOR3(vLocalPoint4.x, vLocalPoint4.y, vLocalPoint4.z);
clamp(vLocalPoint.x, -pCollisionRectangle->GetExtents().x, pCollisionRectangle->GetExtents().x);
clamp(vLocalPoint.y, -pCollisionRectangle->GetExtents().y, pCollisionRectangle->GetExtents().y);
vLocalPoint.z = 0;

D3DXVECTOR4 vClosest4;
D3DXVec3Transform(&vClosest4, &vLocalPoint, &mTransform);
D3DXVECTOR3 vClosest(vClosest4.x, vClosest4.y, vClosest4.z);

D3DXVECTOR3 vDelta = pCollisionSphere->GetOrigin() - vClosest;

float dist = D3DXVec3Dot(&vDelta, &vDelta);

return NO_COLLISION;

float d = sqrt(dist);

D3DXVECTOR3 vCollisionNormal = vDelta / d;
float fIntersectionDepth = (pCollisionSphere->GetRadius() - d);

if(fIntersectionDepth == 0.0f)
return RESTING_CONTACT;

return HAS_COLLISION;


##### Share on other sites
haegarr    7372
"is no longer intersecting" is not a detailed description of what you want.

The simplest correction would be to shift the sphere's origin along what you've called the collision normal, because the intersection depth is given for that direction:
pCollisionSphere->GetOrigin() += vCollisionNormal * fIntersectionDepth

However, that makes the correction without taking any history into account. What I mean is that if the collision occured due to a motion of the (e.g.) sphere, then repelling the sphere in an arbitrary direction and amount (here arbitrary w.r.t. the motion) may look unnaturally. In this case the sphere seems to suddenly stick with the plane as soon as the collision occurs. This may or may not what you want. So you have to do the collision correction w.r.t. the "physical" effect that you've in mind, but we don't know what that is ...

##### Share on other sites
simotix    142
Quote:
 Original post by haegarrHowever, that makes the correction without taking any history into account. What I mean is that if the collision occured due to a motion of the (e.g.) sphere, then repelling the sphere in an arbitrary direction and amount (here arbitrary w.r.t. the motion) may look unnaturally. In this case the sphere seems to suddenly stick with the plane as soon as the collision occurs. This may or may not what you want. So you have to do the collision correction w.r.t. the "physical" effect that you've in mind, but we don't know what that is ...

The sphere would be in motion, so I am not sure if my initial collision detection would have to change also. I know that the collision detection being a sphere/plane and a in motion sphere/plane is a little bit different. What would be the most natural looking way to adjust for intersection?

##### Share on other sites
oliii    2196
1) find point on box surface closest to the sphere centre.
2) if point outside sphere, no collision.
3) else reflect against normal (point - sphere.centre); That's your collision plane.

##### Share on other sites
Eric_Brown    127
I've recently composed a little tutorial on how to sweep a sphere against a polygon.

##### Share on other sites
simotix    142
Quote:
 Original post by oliii1) find point on box surface closest to the sphere centre.2) if point outside sphere, no collision.3) else reflect against normal (point - sphere.centre); That's your collision plane.

Maybe I worded my question wrong.

I know how to detect collision with a sphere and rectangle, but if the sphere and rectangle are colliding and the sphere is inside the rectangle, I am not sure what is the proper way to adjust the sphere so it is no longer intersecting it.

##### Share on other sites
jyk    2094
Quote:
 I know how to detect collision with a sphere and rectangle, but if the sphere and rectangle are colliding and the sphere is inside the rectangle, I am not sure what is the proper way to adjust the sphere so it is no longer intersecting it.
Quote:
 Original post by haegarrThe simplest correction would be to shift the sphere's origin along what you've called the collision normal, because the intersection depth is given for that direction:pCollisionSphere->GetOrigin() += vCollisionNormal * fIntersectionDepth
Like haegarr said, this may not always give the desired results (depending on the circumstances), but geometrically speaking, it will resolve the intersection in the most direct way possible, if that's what you're looking for.

##### Share on other sites
simotix    142
Not entirely, just in case for the strange reason that it is not actually in resting contact but the intersection depth is zero (very rare, but it could happen). Plus if the sphere is approaching the rectangle on the x axis (rectangle is 90 x rotated), it would pop above the rectangle rather then move back on the x.

I am trying to put together a solution that is a mix between mine and Eric_Brown's. However, I am not sure if that is more of a hack

##### Share on other sites
simotix    142
Well I just tested implementing browns tutorial with my code, and I must have messed something up to say the least. In fact, I am not even sure if hacking his code into mine is suppose to be the correct formular. Here is what I came up with, P4 will be (-1.#, -1.#, -1.#) the first time there is collision (and the sphere is intersecting the rectangle).

// If there is no collision, will in intersect?	D3DXVECTOR3 P1 = pRigidBodySphere->GetOrigin() - (vCollisionNormal * pRigidBodySphere->GetRadius());	float s = d - (D3DXVec3Dot(&P1, &vCollisionNormal));	D3DXVECTOR3 P2 = P1 + (pRigidBodySphere->GetVelocity() * s);	D3DXVECTOR3 P3;	// Calculate the nearest point	{		float t = (D3DXVec3Dot(&vCollisionNormal, &P2) - d) / D3DXVec3Dot(&vCollisionNormal, &vCollisionNormal);		P3 = P2 - (t * vCollisionNormal);	}		float sweep = D3DXVec3Dot(&(P3 - pRigidBodySphere->GetOrigin()), &pRigidBodySphere->GetVelocity())*2 -	4 * (D3DXVec3Dot(&pRigidBodySphere->GetVelocity(), &pRigidBodySphere->GetVelocity())) *	D3DXVec3Dot(&(P3 + pRigidBodySphere->GetOrigin()), &(P3 - pRigidBodySphere->GetOrigin())) - (pRigidBodySphere->GetRadius()*2);	float t = (sqrt(sweep) - D3DXVec3Dot(&(2 * (P3-pRigidBodySphere->GetOrigin())), &pRigidBodySphere->GetVelocity())) / D3DXVec3Dot(&(2*pRigidBodySphere->GetVelocity()), &pRigidBodySphere->GetVelocity());	D3DXVECTOR3 P4 = P3 - (pRigidBodySphere->GetVelocity() *t);

##### Share on other sites
jyk    2094
Quote:
 Well I just tested implementing browns tutorial with my code, and I must have messed something up to say the least.
We were just discussing in another thread that the method described in that tutorial is not actually correct (see the thread here for further details).

##### Share on other sites
simotix    142
I read that thread and then also the collision.pdf that was linked to it. However, I am still unsure what I should do for a moving sphere and rectangle collision. Those collisions seem to be just for sphere/sphere and ellipsoid collisions. Surely there is a more optimal one for a sphere/triangle. Does anyone know of one?

##### Share on other sites
jyk    2094
Quote:
 Original post by simotixI read that thread and then also the collision.pdf that was linked to it. However, I am still unsure what I should do for a moving sphere and rectangle collision. Those collisions seem to be just for sphere/sphere and ellipsoid collisions. Surely there is a more optimal one for a sphere/triangle. Does anyone know of one?
The .pdf covers sphere-vs.-triangle collision. Also, check the thread again (some additional information regarding sphere-triangle intersection has been added).

##### Share on other sites
simotix    142
I have read that, however, is there no more optimized technique rather then just doing two triangle checks?

##### Share on other sites
jyk    2094
Quote:
 I have read that, however, is there no more optimized technique rather then just doing two triangle checks?
You mean specifically for a swept sphere vs. rectangle test? If so, sure, it can be optimized. It's basically the same principle: you raytrace the CSO of the rectangle and the sphere, which can be thought of as being comprised of two rectangles, four (finite) cylinders, and four spheres, more or less. An optimized version of the algorithm will most likely test against the rectangles first, then, based on the results of this test, determine what other features need to be tested against, etc., etc. Implementing all of this correctly and robustly can be kind of a pain, but it's doable.

##### Share on other sites
Dave Eberly    1173
Quote:
 Original post by simotixI have read that, however, is there no more optimized technique rather then just doing two triangle checks?

Make a minor modification to the algorithm and identify closest features based on the Voronoi region of the rectangle within its plane. In fact, the implementation is slightly easier for the rectangle, because you can take advantage of the fact that you have two pairs of parallel edges. The clipping of the projected line of centers is simpler for the rectangle than for the triangle.

##### Share on other sites
simotix    142
I am still looking into this issue, I was reading real time collision detection to learn other in motion collision detect techniques. I was able understand the moving sphere to plane collision just fine. As a result, i took my knowledge of sphere to rectangle collision and moving sphere to plane collision, than tried to apply it together in what I thought would make logical sense.

What I basically did was just calculate the distance different than I would for moving sphere to plane collision. I calculated the distance as I would for a sphere/rectangle collision. The problem is it is still wrong. Does anyone have any suggestions on what I should do?

D3DXMATRIX mTransform = *rectangle->GetTransform();	D3DXMATRIX mInverseTransform;	D3DXMatrixInverse(&mInverseTransform, NULL, &mTransform);	D3DXVECTOR4 vLocalPoint4;	D3DXVECTOR3 vLocalPoint; 	D3DXVec3Transform(&vLocalPoint4, &sphere->GetOrigin(), &mInverseTransform);	vLocalPoint = D3DXVECTOR3(vLocalPoint4.x, vLocalPoint4.y, vLocalPoint4.z);	clamp(vLocalPoint.x, -rectangle->GetExtents().x, rectangle->GetExtents().x);	clamp(vLocalPoint.y, -rectangle->GetExtents().y, rectangle->GetExtents().y);	vLocalPoint.z = 0;	D3DXVECTOR4 vClosest4;	D3DXVec3Transform(&vClosest4, &vLocalPoint, &mTransform);	D3DXVECTOR3 vClosest(vClosest4.x, vClosest4.y, vClosest4.z);	D3DXVECTOR3 vDelta = sphere->GetOrigin() - vClosest;	float distance = D3DXVec3Dot(&vDelta, &vDelta);	if(abs(distance) <= sphere->GetRadius())	{		// There was collision	}	float movement = D3DXVec3Dot(&rectangle->GetNormal(), &sphere->GetVelocity());	if(movement == 0.0f)	{		// There is resting contact	}	if(movement * distance > 0.0f) 	{		// Moving away	}	else	{		// Will collide ... in time		float t = (sphere->GetRadius() - distance) / movement;		float r;		if(distance > 0.0f)			r = sphere->GetRadius();		else			r = -sphere->GetRadius();		D3DXVECTOR3 intersectionPoint = sphere->GetOrigin() + t * sphere->GetVelocity() - r * rectangle->GetNormal();

##### Share on other sites
jyk    2094
Quote:
 Original post by simotixI am still looking into this issue, I was reading real time collision detection to learn other in motion collision detect techniques. I was able understand the moving sphere to plane collision just fine. As a result, i took my knowledge of sphere to rectangle collision and moving sphere to plane collision, than tried to apply it together in what I thought would make logical sense. What I basically did was just calculate the distance different than I would for moving sphere to plane collision. I calculated the distance as I would for a sphere/rectangle collision. The problem is it is still wrong. Does anyone have any suggestions on what I should do?*** Source Snippet Removed ***
Unfortunately, it's not as easy as what you've posted there.

To intersect a moving sphere with a rectangle in 3-d, there's a certain amount of work that has to be done - you really can't just tweak the discrete test and hope to get reasonable results.

I'd recommend reading the thread linked to previously again. That thread is on the topic of sphere-vs.-triangle intersection, but a swept sphere-vs.-rectangle test can be implemented in a similar way.

Note that these sorts of tests can be tricky to implement. May I ask what you need it for? Perhaps there are other, more practical solutions to whatever problem you're trying to solve.

##### Share on other sites
simotix    142
Quote:
 Original post by jykTo intersect a moving sphere with a rectangle in 3-d, there's a certain amount of work that has to be done - you really can't just tweak the discrete test and hope to get reasonable results.I'd recommend reading the thread linked to previously again. That thread is on the topic of sphere-vs.-triangle intersection, but a swept sphere-vs.-rectangle test can be implemented in a similar way. Note that these sorts of tests can be tricky to implement. May I ask what you need it for? Perhaps there are other, more practical solutions to whatever problem you're trying to solve.

I will read the sphere vs triangle intersection again and see if I could get a good grasp of it.

The reason I want to test a moving sphere against a wall is because I want to set up a room and have balls be thrown against the wall. It is not going to be a simple box room, but there will be ledges in the room also, so I can not just use planes.

Also the rectangle is not moving. Only the sphere is moving.

[Edited by - simotix on April 2, 2010 1:38:24 AM]

##### Share on other sites
simotix    142
Could someone be more specific? I have researched the static collisions of sphere with a rectangle and sphere with a triangle. I then looked at how a moving sphere to rectangle is calculated. I just do not see how a moving sphere to triangle calculation can be translated to moving sphere to rectangle. Could someone explain the collision steps for a moving sphere to rectangle?

##### Share on other sites
jyk    2094
Quote:
 Could someone explain the collision steps for a moving sphere to rectangle?
Well, let's see. (Long post coming up, I think...)

Suggestion number one: use an existing physics library. If this is for learning purposes and the main point is to implement the collision detection yourself, then this probably isn't an option. If the goal is just to get a simulation up and running though, using an existing physics solution will probably be much faster than trying to implement it yourself.

Suggestion number two: stick with the discrete test, and make sure that the per-update displacement for the sphere is small enough to prevent tunneling and other unwanted effects. The discrete test is much easier to implement than the continuous test, so this approach would probably be much easier. (Plus, it sounds like you've already got the discrete test implemented, or nearly so.)

Ok, if you're still here...

The first thing to realize is that there's a limit to how simple the continuous test can be made. In other words, it's complex enough that it doesn't necessarily break down easily into simple 'step by step' directions.

The other thread that we've been discussing includes pretty much all the info you need in one form or another. There were some points made in that thread that I didn't fully understand (as evidenced by my responses there), but I'll go ahead and provide the best answer I can here.

There are several different ways to conceptualize the test, and several different ways to implement it. I find at useful, at least for illustrative purposes, to look at the test as what I refer to (perhaps incorrectly?) as a 'CSO raytrace'. This approach may not be to everyone's taste, but personally, I've found it useful.

Consider the Minkowski sum of a rectangle and a sphere. This is the shape swept out by sweeping the sphere center over the surface of the rectangle; you can also think of it as the set of all points for which the distance from the point to the rectangle is <= the sphere radius. Dave Eberly refers to this shape as a 'lozenge' in his materials, which should give you a sense of the type of shape we're talking about.

If we take the line segment representing the motion of the sphere center over the time step and intersect it with this lozenge, we can use the information returned to infer some things about the intersection (if any) between the sphere and the rectangle. If the segment and lozenge don't intersect, neither do the sphere and the rectangle. If the segment intersects the lozenge at some valid value of t, then the sphere and rectangle intersect, and t gives us the first time of intersection. And so on.

The segment-lozenge test can be implemented fairly easily if you already have segment intersection tests available for boxes, spheres, cylinders, and/or capsules. In short, you simply intersect the segment against all of the (overlapping) features of the lozenge, and look for (e.g.) the minimum value of t. This isn't very efficient, but might suffice if the number of narrow-phase tests you anticipate performing per update is small.

If greater efficiency is needed, the segment-lozenge test can be optimized considerably by first determining (via analysis of the relative configuration of the two shapes) which features must be tested against. This process is described in some of Dave's materials, although I'm not sure if there's an implementation for this particular test available on the website (I looked, but didn't see one).

There are other ways of conceptualizing and implementing the test as well. You could sweep the sphere against the various features of the rectangle (edges, etc.) and look for the first intersection, if any (note that the individual sweep tests are similar to the individual raycasts in the CSO test). Or you could follow the method described in Dave's references, where the segment is clipped to the Voronoi regions of the rectangle and quadratics are solved on a per-region basis in order to determine the points of intersection. Or, you could implement a generic continuous GJK test (I haven't done this myself, but I get the impression that it's non-trivial).

If you need more information, you might need to ask questions that are more specific. That is, rather than simply requesting more detail, explain what you've tried, what aspect of the test you're uncertain about, and/or what sort of problems you've run into with your implementation.

##### Share on other sites
simotix    142
Well what I am trying right now is taking what I have learned from http://www.peroxide.dk/papers/collision/collision.pdf and then applying that to a rectangle rather than a triangle. however, instead of doing something like

if (checkPointInTriangle(planeIntersectionPoint,p1,p2,p3))

I would do something like

if (checkPointInRectangle(planeIntersectionPoint,p1,p2,p3,p4))

Then I would extend the edge collision tests, that way I could do

// P4
b = 2.0*(velocity.dot(base-p4));
c = (p4-base).squaredLength() - 1.0;
if (getLowestRoot(a,b,c, t, &newT)) {
t = newT;
foundCollison = true;
collisionPoint = p4;

and then later the p3 -> p4 , p4 -> p1 tests. This would logically make sense to start with for me, howevr, maybe this just just a hack. The obvious slow way to do this would be to do two of these triangle checks, then as an optimization combine the two checks. I believe that if I combine the two checks I would get something like this.

##### Share on other sites
simotix    142
The one thing that I did find puzzling is that in http://www.peroxide.dk/papers/collision/collision.pdf they never use the sphere's radius when doing the any of the collision checks, only with the resolution. Why is this?

##### Share on other sites
oliii    2196
look like he is scaling the triangle by the inverse of the sphere radius. I think it comes from having to transform the triangle when you do a ellipsoid / triangle test, as opposed to a sphere / triangle test.

you'll have to replace

Quote:
 t0=(-1.0-signedDistToTrianglePlane)/normalDotVelocity;t1=( 1.0-signedDistToTrianglePlane)/normalDotVelocity;

by

Quote:
 t0=(-radius-signedDistToTrianglePlane)/normalDotVelocity;t1=( radius-signedDistToTrianglePlane)/normalDotVelocity;

and all the

Quote:
 b = 2.0*(velocity.dot(base-p1));c = (p1-base).squaredLength() - 1.0;if (getLowestRoot(a,b,c, t, &newT)) {t = newT;

by

Quote:
 b = 2.0*(velocity.dot(base-p1));c = (p1-base).squaredLength() - (radius*radius);if (getLowestRoot(a,b,c, t, &newT)) {t = newT;

... and maybe some others I missed.

##### Share on other sites
simotix    142
Alright, I have spent the last few weeks on that collision.pdf, trying to understand everything to implement it. However, is there no better explanation then trying to hack together a sphere to two triangle collision?

##### Share on other sites
simotix    142
I am reporting that I never have collision, even when I know my sphere in the triangle, I fear it may have something to do with this checkPointInTriangle test, with how I set some of my variables due to not using collision package.

Sphere:
Position = (1.5, 0.0, 0.0) ... (1.5, -0.11712570, 0.0) to be exact
Velocity = (0.0, -8.0, 0.0) ... (0.0 -8.0350113, 0.0) to be exact

Triangle:
Position = (0.0, 0.0, 0.0)
Vertex One = (4.0, 0.0, 4.0)
Vertex Two = (0.0, 0.0, 0.0)
Vertex Three = (4.0, 0.0, 0.0)
Normal = (0.0, 1.0, 0.0)

I drew the picture, and disabled my physics engine just to make sure, and there sphere is colliding with the triangle.

So basically the code will not return true, even though the sphere is in the triangle. Note that it is not detecting that it is embedded in the plane earlier also (!embeddedInPlane is true).

D3DXVECTOR3 planeIntersectionPoint = basePoint - triangleNormal + t0 * sphereVelocity;if (checkPointInTriangle(planeIntersectionPoint, p1,p2,p3))

basePoint = Sphere Position (1.5, 0.0, 0.0)
triangleNormal = (0.0, 1.0, 0.0)
t0 = 0
sphereVelocity = (0.0, -8.0, 0.0)

planeIntersectionPoint = (1.5, -1.1256210, 0)

Now, without even checking I can tell this point is not in the triangle as the triangle lays flat on the y axis. This leads me to believe that I am either defining my basePoint wrong (basePoint should be the same as a the sphere origin, right?) or my triangles normal (which should be (0, 1, 0) right?)