Sign in to follow this  
zoner7

Collision detection with diagonal lines

Recommended Posts

So I have a rectangle that begins in a standard upright position with two vertical lines and two horizontal lines. As the program progresses, the rectangle may rotate in either direction, thus changing the angle with respect to the origin of the aforementioned lines When the lines are horizontal and vertical to the axes, I can simply test collisions between the x and y boundaries of the box. This is not possible once it begins rotating, since the lines are no longer parallel to any of the axes. But I still need to detect when an object collides with one of these lines. I was thinking that I could find the equation of the line and then simply test all of the x and y coordinates along this line. I would make a for loop.
[source lang=c++]
for (int x = 0; x < length of line; x++)
{
	y = mx + b;
	//store the x and the cooresponding y that the above equation produces.
	//Now I have all the points on the line
}
for every point on line
{
	if (collision == true)
	....do stuff



I suppose I could test every 5 coordinates or something like that to improve performance. The objects are big enough such that a collision will still be detected, and as long as the user cannot notice that the object is partially passing through the rectangle, I'm fine. Is this a decent approach? Thank you

Share this post


Link to post
Share on other sites
How are your objects represented? Circles? Rectangles? Points?

One trick you can do, is to keep track of the rectangle's rotation, then, when you want to see if a circle object or a point collides with the rectangle, you can apply a negative rotation to both the rectangle and object (circle/point) which should give you back vertical/horizontal lines for the rectangle that you can then test the object against.

Share this post


Link to post
Share on other sites
Quote:
Original post by zoner7
So I have a rectangle that begins in a standard upright position with two vertical lines and two horizontal lines. As the program progresses, the rectangle may rotate in either direction, thus changing the angle with respect to the origin of the aforementioned lines

When the lines are horizontal and vertical to the axes, I can simply test collisions between the x and y boundaries of the box. This is not possible once it begins rotating, since the lines are no longer parallel to any of the axes.

But I still need to detect when an object collides with one of these lines. I was thinking that I could find the equation of the line and then simply test all of the x and y coordinates along this line. I would make a for loop.

*** Source Snippet Removed ***

I suppose I could test every 5 coordinates or something like that to improve performance. The objects are big enough such that a collision will still be detected, and as long as the user cannot notice that the object is partially passing through the rectangle, I'm fine.

Is this a decent approach?

Thank you
Stepping along the lines in discrete intervals is not how this is normally done; it's messy and inaccurate, and may not even be faster than alternate approaches.

Also, the line form y = mx + b is problematic in that it cannot represent all lines uniformly, and so it's rarely used in game programming.

There are straightforward methods for detecting intersection between arbitrarily oriented shapes. One of the most commonly used methods is the SAT (separating axis test), which can be used to test for intersection between convex polytopes (which includes line segments and boxes, among other things).

Share this post


Link to post
Share on other sites
If your objects are geometric shapes you can use much better algorithms.


for example hittesting a line and circle. it finds the closest point on line to the center of circle and test if it is smaller than radius (based on this algorithm http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/)



int testCircleLine(float p1[2], //first point of line
float p2[2], //second point of line
float c[2], //center of circle
float r //radius of center
){



float v1[2], v2[2], t, temp, xdiff, ydiff;
float closest[2];

v1[0] = r[0] - p1[0]; //v1 = r - p1
v1[1] = r[1] - p1[1];

v2[0] = p2[0] - p1[0]; //v2 = Normal(p2 - p1)
v2[1] = p2[1] - p1[1];
temp = sqrt(v2[0]*v2[0] + v2[1]*v2[1]);
v2[0] /= temp;
v2[1] /= temp;

t = v1[0]*v2[0] + v1[1]*v2[1]; //dotproduct(v1, v2)

if(t < 0.0){
closest[0] = p1[0]; //if t is smaller than 0.0,
closest[1] = p1[1]; //closest point is at the left of first point
//use first point instead
}else if(t > 1.0){
closest[0] = p2[0]; //closest point is at the right side of second point
closest[1] = p2[1]; //use the second point
}else{
closest[0] = p1[0] + v2[0]*t; //find the closest point center of the circle
closest[1] = p1[1] + v2[1]*t;
}

xdiff = closest[0] - c[0];
ydiff = closest[1] - c[1];

if( sqrt(xdiff*xdiff + ydiff*ydiff) < r){
return 1;//if distance smaller than r return 1
}else{
return 0; //else return 0
}

}

Share this post


Link to post
Share on other sites
for testing two rectangle hits each other, here is another algorithm.

this one tests if two lines intersects. first it finds the intersection of two lines and after that check if this point is between input points


int test2lines(float p1[2], float p2[2], float q1[2],float q2[2]){

float m1, n1, m2, n2, xInt, yInt

//y = mx+ n << find m and n for both lines

float m1 = (p2[1] - p1[1])/(p2[0] - p1[0]);
float n1 = p1[1] - m1*p1[0];

float m2 = (q2[1] - q1[1])/(q2[0] - q1[0]);
float n2 = q1[1] - m2*q1[0];

if(m1 == m2) return 0; //if they are paralel no intersection


// m1x + n1 = m2x + n1 << find x

xInt = (n2 - n1)/(m1 - m2);
yInt = m1*xInt + n1; //then find y

//check if this point between p1-p2 and q1-q2
if(p1[0] < p2[0]){
if(xInt < p1[0] || xInt > p2[0]) return 0;
}else{
if(xInt > p1[0] || xInt < p2[0]) return 0;
}

if(p1[1] < p2[1]){
if(xInt < p1[1] || xInt > p2[1]) return 0;
}else{
if(xInt > p1[1] || xInt < p2[1]) return 0;
}


if(q1[0] < q2[0]){
if(xInt < q1[0] || xInt > q2[0]) return 0;
}else{
if(xInt > q1[0] || xInt < q2[0]) return 0;
}

if(p1[1] < q2[1]){
if(xInt < q1[1] || xInt > q2[1]) return 0;
}else{
if(xInt > q1[1] || xInt < q2[1]) return 0;
}

return 1;
}


I am note sure about last part but it should work

Share this post


Link to post
Share on other sites
What kind of objects needs to collide against the rotated rectangle?

Most collisions can be based on the basic point-to-line distance functions. For example, when you check if a point is inside your normal rectangle, you probably do something like the following:

if(x > leftx && x < rightx)
is inside on the x axis


This can be translated to the following, where you have two edges, the left and the right edge of the rectangle.

distance to left side = leftx - x
distance to right side = x - rightx
if(both distances < 0)
is inside on the x axis

This works by letting each edge have a 'front side', and a 'back side', where the distance is negative 'behind' the edge, and positive 'in front of' the edge, and we decide that the front side is pointing to the outside of the box. The same can be done for distance to the horizontal edges with the y-coordinate, so when the distance is negative to all edges, then a point is inside the box.

The same type of distance can be used for every line, not just horizontal and vertical lines. By using a representation for the line like in the image below, we can decide the distance to it.


To get a line like this, you need the end-points (x0,y0) and (x1,y1), which should be easy since I guess your box has 4 corner points. The way this works is that when starting at (x0,y0) and looking towards (x1,y1), the 'front side' of the line, with positive distance, is to the right of the line. So by switching order of the end-points you get that the other side of the line is the front.
When you have two end-points you can calculate the 'normal' (nx,ny). It is done in the following way:

nx = y0 - y1
ny = x1 - x0


This can also be used to get the actual distance from the line to a point. In the simple case of a vertical line and 'distance = x - x0', you get the distance as the number of pixels from the line to the point. In the case of the diagonal line you will always get a correct positive or negative distance, so you know the side, but if you want the actual distance you also need to 'normalize' the normal, like the following (requires floating point numbers):

nx = y0 - y1
ny = x1 - x0
length = sqrt(nx*nx + ny*ny)
nx /= length
ny /= length

Or just divide the distance by the length of the normal after the calculation.

Share this post


Link to post
Share on other sites
Quote:
Original post by shultays
If your objects are geometric shapes you can use much better algorithms.


for example hittesting a line and circle. it finds the closest point on line to the center of circle and test if it is smaller than radius (based on this algorithm http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/)


I actually really wanted to do this. I just wasn't sure how. I haven't yet taken the time to fiddle with the geometry on paper.

At the moment I have balls bouncing around a stationary rectangle. When a ball hits a wall, I want the rectangle to rotate. At the moment I have, I am testing the radius of the ball against the distance from the wall.

I want to clarify that the game is in 2-d

So the only difference between my code and your code is that the closest point on the rectangle with respect to the ball is unknown. Now I need to find this point.

I am going to read these posts a few times and post once I understand them.

also, I was wondering if I could simply rotate the entire game and then test how far the balls are from the x and y boundaries of the rectangle. Would this be a very expensive operation?

Correct?

Share this post


Link to post
Share on other sites
EDIT: Was having a serious brain fart. Figured it out

So I think I understand what's going on. The only question I have is how to do I find the vertices of the rectangle?

I know the initial coordinates of each vertex of the rectangle and the amount in radians that each vertex has rotated. I next need to use the knowledge of the angle of rotation to find how much each vertex has shifted. This new vertex can be used as the second point of the line that I'm looking for.

All I know is that they will lay along the boundary of some ellipse. (It isn't a circle because a rectangle is rotating, not a square.)

Ideas?

Thank you

[Edited by - zoner7 on July 23, 2009 10:21:59 PM]

Share this post


Link to post
Share on other sites
It's still a circle.
To rotate a point around the origin (counter clockwise when y increases downwards and x to the right) you do:

newx = x * cos(angle) + y * sin(angle)
newy = y * cos(angle) - x * sin(angle)


If you have an original point on the rectangle (x, y), rotating around the rectangle's center point (cx, cy), then you can get the new coordinates as follows:

newx = cx + (x - cx) * cos(angle) + (y - cy) * sin(angle)
newy = cy + (y - cy) * cos(angle) - (x - cx) * sin(angle)

Share this post


Link to post
Share on other sites
hmm... not quite sure if I did something different that your last post does. about your last post. I'm pretty positive that what I did is right.

Anyhow. I messed up somewhere along the way. The balls simply go right through the walls.

I think I did something wrong in my calculation of u. Unfortunately, I still haven't figured out how to use VS's debugger.

here is my code:

It looks long, but it simply repeats the same operation four times, once time for each line. I would really appreciate a little guidance. Thanks a ton.

By the way, the call of this function is inside a for loop that tests every ball.

[source lang = c++]
void PlayGameState::WallCollision (vector <Ball>:: iterator iter)
{
double u;
//Starting from the upper left vertice and going clockwise, ending at the lower left vertice.
//This finds the coordinates of each vertex based on the given rotation.

Vector2d vertice1 (radius * cos(rotationPos) + 200, radius * sin(rotationPos) + 220); //200 and 220 are the coorinates of the center of the box.

Vector2d vertice2 (radius * cos(rotationPos + PI) + 200, radius * sin(rotationPos + PI) + 220);

Vector2d vertice3 (radius * cos(rotationPos + 3/2 * PI) + 200, radius * sin(rotationPos + 3/2 * PI) + 220);

Vector2d vertice4 (radius * cos(rotationPos + 2 * PI) + 200, radius * sin(rotationPos + 2 * PI) + 220);

Vector2d testPoint;

// Find the closest point on every line to the ball (iter).
// Take dot product between position vector and relative velocity vector //

// which velocities reverse depends on the orientation of the wall.
// If rotationPos = 0, then we use the calculations we used for stationay collision testing.
// we will determine which wall is which by using vertices.
u = ( ((*iter).Pos().x - vertice1.x) * (vertice2.x - vertice1.x) + ((*iter).Pos().y - vertice1.y) * (vertice2.y - vertice1.y) ) / Distance(vertice1, vertice2);
if ( u < 1 && u > 0)
{
testPoint.x = vertice1.x + u * (vertice2.x - vertice1.x);
testPoint.y = vertice1.y + u * (vertice2.y - vertice1.y);

if ( Distance((*iter).Pos(), testPoint) <= 29 )
{
//1st and 2nd vertice means top wall... need to find orientation by looking at rotationPos

if (rotationPos != 0)
{
(*iter).Vel( - (*iter).Vel() );
}
else (*iter).Vel(Vector2d((*iter).Vel().x, -(*iter).Vel().y));

game.hge->Effect_Play(WallCollisionEffect);
CalculateRotation(iter);

//occasionally there is sticking. Under these circumstances,
//we want to move theq ball back into the rectangle to avoid infinite collision detection

(*iter).Pos(( (-(*iter).Vel()) * epsilon * 100000) + (*iter).OldPos());
}
}
u = ( ((*iter).Pos().x - vertice3.x) * (vertice4.x - vertice3.x) + ((*iter).Pos().y - vertice3.y) * (vertice4.y - vertice3.y) ) / Distance(vertice3, vertice4);
if ( u < 1 && u > 0)
{
testPoint.x = vertice3.x + u * (vertice4.x - vertice3.x);
testPoint.y = vertice3.y + u * (vertice4.y - vertice3.y);

if ( Distance((*iter).Pos(), testPoint) <= 29 )
{
//3rd and 4th vertices means bottom wall.

if (rotationPos != 0)
{
(*iter).Vel( - (*iter).Vel() );
}
else (*iter).Vel(Vector2d((*iter).Vel().x, -(*iter).Vel().y));

game.hge->Effect_Play(WallCollisionEffect);
CalculateRotation(iter);

//occasionally there is sticking. Under these circumstances,
//we want to move the ball back into the rectangle to avoid infinite collision detection

(*iter).Pos(( (-(*iter).Vel()) * epsilon * 100000) + (*iter).OldPos());
}
}

u = ( ((*iter).Pos().x - vertice2.x) * (vertice3.x - vertice2.x) + ((*iter).Pos().y - vertice2.y) * (vertice3.y - vertice2.y) ) / Distance(vertice2, vertice3);
if ( u < 1 && u > 0)
{
testPoint.x = vertice2.x + u * (vertice3.x - vertice2.x);
testPoint.y = vertice2.y + u * (vertice3.y - vertice2.y);

if ( Distance((*iter).Pos(), testPoint) <= 29 )
{
//2nd and 3rd vertices means right wall.

if (rotationPos != 0)
{
(*iter).Vel( - (*iter).Vel() );
}
else (*iter).Vel(Vector2d(-(*iter).Vel().x, (*iter).Vel().y));

game.hge->Effect_Play(WallCollisionEffect);
CalculateRotation(iter);

//occasionally there is sticking. Under these circumstances,
//we want to move the ball back into the rectangle to avoid infinite collision detection

(*iter).Pos(( (-(*iter).Vel()) * epsilon * 100000) + (*iter).OldPos());
}
}


u = ( ((*iter).Pos().x - vertice4.x) * (vertice1.x - vertice4.x) + ((*iter).Pos().y - vertice4.y) * (vertice1.y - vertice4.y) ) / Distance(vertice4, vertice1);
if ( u < 1 && u > 0)
{
testPoint.x = vertice4.x + u * (vertice1.x - vertice4.x);
testPoint.y = vertice4.y + u * (vertice1.y - vertice4.y);

if ( Distance((*iter).Pos(), testPoint) <= 29 )
{
//1st and 4th vertices means left wall.

if (rotationPos != 0)
{
(*iter).Vel( - (*iter).Vel() );
}
else (*iter).Vel(Vector2d(-(*iter).Vel().x, (*iter).Vel().y));

game.hge->Effect_Play(WallCollisionEffect);
CalculateRotation(iter);

//occasionally there is sticking. Under these circumstances,
//we want to move the ball back into the rectangle to avoid infinite collision detection

(*iter).Pos(( (-(*iter).Vel()) * epsilon * 100000) + (*iter).OldPos());
}
}
}






EDIT: changed the order of the vertex arguments in the distance formula. They were backwards. The program still does not work, however

Share this post


Link to post
Share on other sites
so I changed the calculation of the test points such that I'm using the formula you suggested above.

Note that vector2d is simply a class that holds both an x and y value. Pretty self-explanatory.

Now I'm told that vertex1 is undefined... along with every other vertex

[source lang=c++]

Vector2d vertex1 (200 + (vertice1.x - 200) * cos(rotationPos) + (vertice1.y - 220) * sin(rotationPos), 220 + (vertice1.x - 200) * cos(rotationPos) - (vertice1.y - 220) * sin(rotationPos)); //200 and 220 are the coorinates of the center of the box.


Share this post


Link to post
Share on other sites
alright. I part of it working. The vertices are now calculated properly, and the points perpendicular to the line where we test for a collision are calculated properly. Now I just need to get the collisions to actually occur in the correct places.

Share this post


Link to post
Share on other sites
So I now have a rectangle with a bunch of balls bouncing around inside of it. When the rectangle begins to rotate, collisions work decently...there are times when they seem to reverse velocities a couple pixels before a side of the rectangle, but that shouldn't be hard to fix. Sometimes, however, I have some serious sticking. I haven't quite figured that one out yet.

As the rectangle rotates farther and farther from its original point, the collisions become less and less accurate. The balls begin to change their velocity close to 50 pixels away from the actual sides of the rectangle.

Does anyone know what might be causing this anomaly?

Here is my code:

[source lang = c++]

void PlayGameState::FindWallCollision (vector <Ball>:: iterator iter)
{
Vector2d vertex1, vertex2, vertex3, vertex4, testPoint;
double u, distance;
//Starting from the upper left vertex and going clockwise, ending at the lower left vertex.
//This finds the coordinates of each vertex based on the given rotation.

// I considered this formula to calculate each vertex below. cx and cy are the anchor point of the rectangle.
// x and y are the original vertices (the corners) of the rectangle
// newx = cx + (x - cx) * cos(angle) + (y - cy) * sin(angle)
// newy = cy + (y - cy) * cos(angle) - (x - cx) * sin(angle)

vertex1.x = 200 + (55 - 200) * cos(-rotationPos) + (55 - 220) * sin(-rotationPos);//200 and 240 are the coorinates of the center of the box.
vertex1.y = 220 + (55 - 220) * cos(-rotationPos) - (55 - 200) * sin(-rotationPos);

vertex2.x = 200 + (455 - 200) * cos(-rotationPos) + (55 - 220) * sin(-rotationPos);
vertex2.y = 220 + (55 - 220) * cos(-rotationPos) - (455 - 200) * sin(-rotationPos);

vertex3.x = 200 + (455 - 200) * cos(-rotationPos) + (455 - 220) * sin(-rotationPos);
vertex3.y = 220 + (455 - 220) * cos(-rotationPos) - (455 - 200) * sin(-rotationPos);

vertex4.x = 200 + (55 - 200) * cos(-rotationPos) + (455 - 220) * sin(-rotationPos);
vertex4.y = 220 + (455 - 220) * cos(-rotationPos) - (55 - 200) * sin(-rotationPos);


// Find the closest point on every line to the ball (iter).
// Take dot product between position vector and relative velocity vector //

// which velocities reverse depends on the orientation of the wall.
// we will determine which wall is which by simply considering which two vertices were are examining.

//1st and 2nd vertex means top wall.

u = ( ( ( (*iter).Pos().x- vertex1.x ) * ( vertex2.x - vertex1.x ) ) +
( ( (*iter).Pos().y - vertex1.y ) * ( vertex2.y - vertex1.y ) ) ) /
( Distance (vertex1, vertex2) * Distance (vertex1, vertex2) );

if (u > 0.0f && u < 1.0f)
{
//The point on the side of the rectangle that we are testing that is closest to the ball.
//A line that connects these two points would intersect perpendicularly the line between the two vertices we are testing.

testPoint.x = vertex1.x + u * (vertex2.x - vertex1.x);
testPoint.y = vertex1.y + u * (vertex2.y - vertex1.y);

//find the distance between the ball and the wall
distance = Distance((*iter).Pos(), testPoint);

//if the distance is greater than the radius of the ball, a collision occurs
if ( distance <= 29 * (*iter).GetMass() + epsilon)
{

//The rectangle is rotated based on the momentum of the ball.
CalculateRotation(iter);

//occasionally there is sticking. Under these circumstances,
//we want to teleport (a very very small distance) the ball back into the rectangle to avoid the detection of a collision over and over.

(*iter).Pos(( (-(*iter).Vel()) * epsilon * 100000) + (*iter).OldPos());

//the velocitiy of the ball is changed.
(*iter).Vel(Vector2d((*iter).Vel().x, -(*iter).Vel().y));

game.hge->Effect_Play(WallCollisionEffect);

}
}

//note that this operation is repeated 4 times, once for each line of the rectangle.



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