Collision Detection

[Andy]

ZeroPaladn wrote:

I've just never used basic collision detection for my programs, i was taught to use whatdotcolour, and what is what i use to this day. i prefer to use what i allready know (even if it does suck) instead of learning something else, when they both serve the same purpose (depending on useage). one day ill learn normal collision detection, and this conversation would be pointless...

that is the dumbest justification you could've possibly gave. if that is your attitude, then we dont need your input. your job, as a student is to learn, and we are here to help you learn how to complete your tasks the most efficient way.

and cervantes, whatdotcolor is superior in every situation. i'd like to see your math detect collision in the situation you mentioned with convex polygons

[Cervantes]

Cervantes wrote:

and cervantes, whatdotcolor is superior in every situation. i'd like to see your math detect collision in the situation you mentioned with convex polygons

I doubt I could do it, but I believe it can be done. I'd like to see whatdotcolour do the collision detection in that situation. Or even in the situation using circles instead of convex polygons. And remember, maintaining a good execution speed is important here.

[blaster009]

God forbid you should be able to use decent looking pictures in your program with various different colours. I mean, thinking that far outside of the box would completely nullify whatdotcolour!

[[Gandalf]]

blaster009 wrote:

God forbid you should be able to use decent looking pictures in your program with various different colours. I mean, thinking that far outside of the box would completely nullify whatdotcolour!

Ah but it's you who are not thinking outside the box. What if there was a collision detection layer, underneath your colourful pictures, which you used whatdotcolour on? I'm sure there's tons of other tricky stuff that can be done with whatdotcolour.

[Cervantes]

[Gandalf] wrote:

Ah but it's you who are not thinking outside the box. What if there was a collision detection layer, underneath your colourful pictures, which you used whatdotcolour on?

Then you'd be doing far more drawing than necessary, and your code would be that much slower. Drawing is a hefty task.

[[Gandalf]]

Cervantes wrote:

Then you'd be doing far more drawing than necessary, and your code would be that much slower. Drawing is a hefty task.

The point is that using multi-coloured pictures doesn't "completely nullify" whatdotcolour. Indeed, using math is almost always faster and more flexible, but it's not the only way.

[Andy]

cervantes, i am not suggesting a pure whatdotcolor approach. more like a combined effort between wdc and math.

With whatdotcolour detection, you only need to traverse through the outer perimeter of the given shape. and when lines cross, you get a different colored pixel than you expect, thus signifying a collision. the perimeter of anyshape can be expressed as a first degree function, so your algorithm would be O(n), its really not that slow.

blaster009, no offence, but who the hell do you think you're talking to?

[vertozia]

I frankly understand the picture/rectangle collision. How is colour to picture collision performed.

e.g. I'm making a Mario game, Mario is a pic, the pipe is a color? How?

[Cervantes]

Did you read the whatdotcolour tutorial? That would be a good place to start.

[richcash]

More Advanced Collision Detection

To get the most out of this tutorial, you will need to understand the following :

if and for loop constructs
types
records
functions
circular collision detection
rectangular collision detection

Circle vs Rectangle

Assume that :
(x1, y1) is the lower left corner of the rectangle
(x2, y2) is the upper right corner of the rectangle
(x, y) is the center of the circle
r is the radius of the circle

The first way we can check if the circle and rectangle are intersecting is to check if any of the rectangle's four corners are inside of the circle. We already have two of the rectangle's corners (x1, y1) and (x2, y2). The other two corners will obviously be (x1, y2) and (x2, y1).
if (x1 - x)^2 + (y1 - y)^2 <= r^2 or (x1 - x)^2 + (y2 - y)^2 <= r^2 or (x2 - x)^2 + (y1 - y)^2 <= r^2 or (x2 - x)^2 + (y2 - y)^2 <= r^2
then we know we have a collision between the circle and the rectangle

But the circle and rectangle can intersect in such a way that none of the rectangle's corners are inside of the circle. Just imagine the circle on one of the rectangle's edges. First, let's think of this type of scenario happenning on one of the rectangle's horizontal edges. If this is the case, then either the highest point on the circle or the lowest point on the circle is inside of the rectangle. Similarly, for the vertical edges, the furthest left or furthest right point on the circle must be inside of the rectangle. So, we just check these four points to be in the rectangle. These four points on a circle are obvious :
highest : (x, y + r)
lowest : (x, y - r)
furthest right : (x + r, y)
furthest left : (x - r, y)

This is one long expression, and we can even pin it on to the last one using an or. But, to keep it neat, you might want to separate them. For example, I separated them in horizontal edge collisions and vertical edge collisions :

if x > x1 and x < x2 and (y + r > y1 and y + r < y2 or y - r > y1 and y - r < y2)
then there is an intersection
if y > y1 and y < y2 and (x + r > x1 and x + r < x2 or x - r > x1 and x - r < x2)
then there is an intersection

These cases above do not cover all intersections of a circle and a rectangle, though. Can you think of a scenario where none of the four corners of the rectangle are inside of the circle and the highest, lowest, furthest left, or furthest right points of the circle are not inside the rectangle?

Imagine a circle and a square with the same center and the square's corners sticking out of the circle. If this is happening, then the center of the circle must be inside of the rectangle, so we can check for that last condition.
if x > x1 and x < x2 and y > y1 and y < y2
then the rectangle and circle are intersecting

So, we have created four expressions (that can all be combined into one expression using or if we really want to). If any of these expressions are true, then there is an intersection. If none of them are true, then there is no collision between the rectangle and the circle.

code:

View.Set ("offscreenonly") var x1, y1, x2, y2, x, y, b, r : int x1 := 100 y1 := 100 x2 := 200 y2 := 200 r := 60 fcn circleRectangle (x, y, r, x1, y1, x2, y2 : real) : boolean     if x > x1 and x < x2 and (y + r > y1 and y + r < y2 or y - r > y1 and y - r < y2) then         result true     end if     if y > y1 and y < y2 and (x + r > x1 and x + r < x2 or x - r > x1 and x - r < x2) then         result true     end if     if (x1 - x) ** 2 + (y1 - y) ** 2 <= r ** 2 or (x1 - x) ** 2 + (y2 - y) ** 2 <= r ** 2 or (x2 - x) ** 2 + (y1 - y) ** 2 <= r ** 2 or (x2 - x) ** 2 + (y2 - y) ** 2 <= r ** 2 then         result true     end if     result x > x1 and x < x2 and y > y1 and y < y2 end circleRectangle loop     Mouse.Where (x, y, b)     Draw.Box (x1, y1, x2, y2, black)     Draw.Oval (x, y, r, r, blue)     put circleRectangle (x, y, r, x1, y1, x2, y2)     View.Update     delay (10)     cls end loop

Point on Ellipse

The formula for a point (x, y) on an ellipse is :
((e.x - x)/rx)^2 + ((e.y - y)/ry)^2 = 1
where (e.x, e.y) is the center of the ellipse

e.rx is the x-radius (the distance from the center to the outside of the ellipse along the x-axis)

e.ry is the y-radius (the distance from the center to the outside of the ellipse along the y-axis)

Let's write the expression for determining if a point (x, y) is inside of a circle :
(c.x - x)^2 + (c.y - y)^2 <= r^2
this can be rewritten as :
((c.x - x)/r)^2 + ((c.y - y)/r)^2 <= 1
Do you see the similarity to the ellipse equation? It just so happens that for the ellipse, the expression is similar to the circle one except it uses the x-radius and y-radius :

((e.x - x)/rx)^2 + ((e.y - y)/ry)^2 <= 1
If the above expression evaluates to true, then the point is on or inside the ellipse. Otherwise, the point is outside of the ellipse.

Go here to find out about the derivation of the ellipse formula and more information about the ellipse.

code:

View.Set ("offscreenonly") type ellipse :     record         x, y, rx, ry : real         clr : int     end record var e : ellipse var x, y, button : int e.x := 100 e.y := 100 e.rx := 85 e.ry := 32 e.clr := green fcn pointEllipse (e : ellipse, x, y : real) : boolean     result ((e.x - x) / e.rx) ** 2 + ((e.y - y) / e.ry) ** 2 <= 1 end pointEllipse loop     Mouse.Where (x, y, button)     Draw.Oval (round (e.x), round (e.y), round (e.rx), round (e.ry), e.clr)     put pointEllipse (e, x, y)     View.Update     delay (10)     cls end loop

Math Review : Finding the point of intersection of two lines

The equation of a line is :
y = mx + b OR

where m is the slope and b is the y-intercept
y - y0 = m * (x - x0)

where m is the slope and (x0, y0) is a known point on the line

Suppose we are given two points on two different lines and we want to find the point of intersection of these two lines
(x1, y1) and (x2, y2) are on the first line
(x3, y3) and (x4, y4) are on the second line

then, we have to first find the slopes of both lines so we can write the equation of each line :
m1 = (y2 - y1) / (x2 - x1) slope of the first line
m2 = (y4 - y3) / (x4 - x3) slope of the second line

Now, we write the equations of both lines :
y - y1 = m1 * (x - x1)
y - y3 = m2 * (x - x3)

To solve for the point of intersection, we solve for x and y in this system of equations.
y = m1*x - m1*x1 + y1
y = m2*x - m1*x3 + y3

m1*x - m1*x1 + y1 = m2*x - m2*x3 + y3
m1*x - m2*x = -m2*x3 + y3 + m1*x1 - y1
(m1 - m2) * x = -m2*x3 + y3 + m1*x1 - y1

x = (-m2*x3 + y3 + m1*x1 - y1) / (m1 - m2)
y = m1*(x - x1) + y1 <-we substitute x which we computed above into this equation to get y

And (x, y) will be the point of intersection.

Line Segment vs. Line Segment

Lines extend infinitely (have an infinite length), while line segments have two endpoints and a finite length. When dealing with graphics, line segments are usually more relevant. Any two non-parallel lines are intersecting, but this can not be said for line segments.

Suppose the first line segment has endpoints (x1, y1) and (x2, y2).
Suppose the second line segment has endpoints (x3, y3) and (x4, y4).

To determine whether or not two line segments are intersecting, we first treat them as lines. We find the slope of each line and calculate the intersection point.

m1 = (y2 - y1) / (x2 - x1)
m2 = (y4 - y3) / (x4 - x3)
intX = (-m2 * x3 + y3 + m1 * x1 - y1) / (m1 - m2)
intY = (m1 * (intX - x1) + y1)

Now we have the intersection point (intX, intY) of the two lines, but remember, we have line segments. So, we check if this point of intersection is on BOTH line segments. If it is, then the line segments are intersecting. If it's not on one or both of the line segments, then there is no intersection.

To check if this point is on the line segment, we just check if its x-coordinates are between the x coordinates of the endpoints of the first and second line. We do the same with its y coordinate. After some logic, it can be shortened to :
intX >= max (min (x1, x2), min (x3, x4)) and intX <= min (max (x1, x2), max (x3, x4)) and
intY >= max (min (y1, y2), min (y3, y4)) and intY <= min (max (y1, y2), max (y3, y4))

if the above expression is true, then the line segments are intersecting.

code:

View.Set ("offscreenonly") var x1, y1, x2, y2, x3, y3, x4, y4, angle : real var x, y, button : int angle := 90 x1 := 100 y1 := 100 x2 := 200 y2 := 200 fcn lineLine (x1, y1, x2, y2, x3, y3, x4, y4 : real) : boolean     var m1 := (y2 - y1) / (x2 - x1 + 1e-5)     var m2 := (y4 - y3) / (x4 - x3 + 1e-5)     var intX := round ((-m2 * x3 + y3 + m1 * x1 - y1) / (m1 - m2))     var intY := round ((m1 * (intX - x1) + y1))     result intX >= max (min (x1, x2), min (x3, x4)) and intX <= min (max (x1, x2), max (x3, x4)) and         intY >= max (min (y1, y2), min (y3, y4)) and intY <= min (max (y1, y2), max (y3, y4)) end lineLine loop     Mouse.Where (x, y, button)     x3 := x     y3 := y     if button = 1 then         angle += 1     end if     x4 := x + 70 * cosd (angle)     y4 := y + 70 * sind (angle)     Draw.Line (round (x1), round (y1), round (x2), round (y2), blue)     Draw.Line (round (x3), round (y3), round (x4), round (y4), red)     put lineLine (x1, y1, x2, y2, x3, y3, x4, y4)     View.Update     delay (10)     cls end loop

Line Segment vs. Circle

We know by know that if the distance from the line to the center of the circle is less than the radius of the circle, then the line segment must be intersecting with the circle. But, we can do even better, the closest point on this line segment to the center of the circle must be inside the circle for an intersection to occur. So now the problem becomes finding the point on the line segment that is the closest to the center of the circle.

Let :
(x, y) be the center of the circle
r be the radius of the circle
(x1, y1) and (x2, y2) be the endpoints of the line segment

Now, first let's treat the line segment as a line and find the point on the line closest to the center of the circle. We'll call the line (l).
For this, we assume the geometric property that the shortest path from a point to a line is the path perpendicular to the line.
Assuming this, we now have a second line and we know its slope will be perpendicular to the original line (l) and it will go through the center of the circle. We find the intersection point of the original line (l) and the new perpendicular line.

m = (y2 - y1) / (x2 - x1)
M = -1 / m
X = (m * x1 - y1 - M * x + y) / (m - M)
Y = m * (X - x1) + y1
where m is the slope of the original line (l)

M is the slope of the new perpendicular line

(X, Y) is the point of intersection between the two lines

Now we have the point on the line that is the shortest distance away from the center of the circle. But wait, we have a line segment to start with, so we have to check if this point of intersection is actually even on our line segment.

if X >= min (x1, x2) and X <= max (x1, x2) and Y >= min (y1, y2) and Y <= max (y1, y2)
then the point of intersection is on the line segment. Now, we check if this point is inside the circle using circular collision.
(px - X) ** 2 + (py - Y) ** 2 <= r ** 2
If that expression is true then the closest point on the line segment is inside of the circle and there is an intersection between the line segment and the circle.

But what if the point of intersection was not on our line segment (the first if statement evaluated to false)? Then we conclude that the closest point on the line segment to the center of the circle must be one of the endpoints (whichever one is closer).

Since our general circular collision compares if the distance squared is less than or equal to the radius squared, we can check which distance from endpoint to center squared is less and then see if it less than or equal to the radius squared.
min ((px - x1) ** 2 + (py - y1) ** 2, (px - x2) ** 2 + (py - y2) ** 2) <= r ** 2
If the above expression evaluates to true, then you have an intersection between the circle and the line segment. If it evaluates to false, then there is no intersection.

Bringing our two conditions together, we get pseudocode like this :
if X >= min (x1, x2) and X <= max (x1, x2) and Y >= min (y1, y2) and Y <= max (y1, y2) then

result (x - X) ** 2 + (y - Y) ** 2 <= r ** 2
else

result min ((x - x1) ** 2 + (y - y1) ** 2, (x - x2) ** 2 + (y - y2) ** 2) <= r ** 2

code:

View.Set ("offscreenonly") var x, y, button, x1, y1, x2, y2, r : int x1 := 100 y1 := 100 x2 := 100 y2 := 200 r := 25 fcn circleLine (px, py, r, x1, y1, x2, y2 : real) : boolean     var m := (y2 - y1) / (x2 - x1 + 1e-8)     var M := -1 / m     var X := (m * x1 - y1 - M * px + py) / (m - M)     var Y := m * (X - x1) + y1     if round (X) >= min (x1, x2) and round (X) <= max (x1, x2)             and round (Y) >= min (y1, y2) and round (Y) <= max (y1, y2) then         result (px - X) ** 2 + (py - Y) ** 2 <= r ** 2     else         result min ((px - x1) ** 2 + (py - y1) ** 2, (px - x2) ** 2 + (py - y2) ** 2) <= r ** 2     end if end circleLine loop     Mouse.Where (x, y, button)     put circleLine (x, y, r, x1, y1, x2, y2)     Draw.Line (x1, y1, x2, y2, black)     Draw.Oval (x, y, r, r, blue)     View.Update     delay (30)     cls end loop

Similar Ellipse vs Similar Ellipse

Well, if you use the circle again, let's write the expression that determines whether or not two circles are intersecting :
(c1.x - c2.x)^2 + (c1.y - c2.y)^2 <= (c1.r + c2.r)^2 OR
(c1.x - c2.x)^2 / (c1.r + c2.r)^2 + (c1.y - c2.y)/r)^2 / (c1.r + c2.r)^2 <= 1

Well, if we plug in the sum of the ellipses' x-radii for the first r and the sum of the ellipses' y-radii for the second r, then we have :
(e1.x - e2.x) ** 2 / (e1.rx + e2.rx) ** 2 + (e1.y - e2.y) ** 2 / (e1.ry + e2.ry) ** 2 <= 1

Unfortunately, that does not work for all ellipses. It only works for what I call similar ellipses (probably not the right mathematical term!). When I say the ellipses are similar, I mean that their x and y radii are proportional. So,
e1.rx / e1.ry = e2.rx / e2.ry

For example, if an ellipse has an x-radius of 25 and a y-radius of 40, then a similar ellipse might have an x-radius of 50 and a y-radius of 80.

I have yet to attempt to geometrically prove this, but the reason has something to do with the point of intersection of similar ellipses always being on the vector joining the two centers of the ellipses. So, if the expression we declared above is true, then the similar ellipses intersect. If that expression is false, then there is no collision.

code:

View.Set ("offscreenonly") type ellipse :     record         x, y, rx, ry, clr : int     end record var e1, e2 : ellipse var x, y, b : int e1.x := 100 e1.y := 100 e1.rx := 90 e1.ry := 50 e1.clr := red e2.rx := 45 e2.ry := 25 e2.clr := blue fcn ellipseEllipse (e1, e2 : ellipse) : boolean     result ((e2.x - e1.x) / (e1.rx + e2.rx)) ** 2 + ((e2.y - e1.y) / (e1.ry + e2.ry)) ** 2 <= 1 end ellipseEllipse loop     Mouse.Where (x, y, b)     e2.x := x     e2.y := y     Draw.Oval (e1.x, e1.y, e1.rx, e1.ry, e1.clr)     Draw.Oval (e2.x, e2.y, e2.rx, e2.ry, e2.clr)     put ellipseEllipse (e1, e2)     View.Update     delay (15)     cls end loop

Math Lesson : Determining which side of a vector a point is on (left or right?)

If you have a vector in 2 dimensions v with a tip of (x1, y1) and a tail of (x2, y2) and a point p (x, y), and you want to determine if the point is to the left or to the right of the vector, you use a cross product.

First, we construct two new vectors. One will go from the point p to the tail (start) of the vector, and the other will go from the point p to the tip (end) of the vector.
The first vector (tail to point) :
(x - x1, y - y1, 0)
The second vector (tip to point) :
(x - x2, y - y2, 0)
Note that the z component of the vectors will be 0 because we're dealing in 2 dimensions.

Now, if the point p is to the right of the original vector v, then the cross product of our two constructed vectors will be pointing out of the screen (if you know the right-hand rule, you can confirm this). If the point p is to the left, the cross product will be going into the screen. Well, if the cross product is coming out of the screen, then the z-component will be negative; and if the cross product is going into the screen then the z-component will be positive. (Note, if the point is right on the line, then the two constructed vectors' cross product would obviously be 0.)

So, we just have to check the sign of the z-component of the cross product. The z-component of the cross product can be computed like this :
(y - y1) * (x2 - x1) - (x - x1) * (y2 - y1)

So, if the sign of the above calculation is negative, then the point is to the right of the vector. If the sign is positive, then the point is to the left of the vector. If the above calculation is 0, then the point is on the vector.

Point in Convex Polygon

Let's say the array that represents the convex polygon's x coordinates is px and the array that represents the convex polygon's y coordinates is py. Let's call our point we are testing p (x, y).

In order to use the Draw.Polygon procedure, you must have your coordinates in your arrays in order. Well, since we're dealing with a convex polygon, the points must go in a clockwise or counter-clockwise direction. Now, imagine each edge of the polygon as a vector so that the polygon creates either a clockwise or counter-clockwise path. If your path is clockwise, then all points inside of the polygon are to the right of each edge vector. If your path is counterclockwise, then all points inside the polygon are to the left of each edge vector. All points outside of the polygon are to the left of some edge vectors and to the right of others regardless if the path is clockwise or counter-clockwise.

Now, all we do is check if our point p is to the right of all the edges of the polygon or to the left of all the edges of our polygon using the method learned in the above section.

for each edge of the polygon

z-com = (y - y1) * (x2 - x1) - (x - x1) * (y2 - y1)
where (x1, y1) is the start point (tail) of the edge vector and (x2, y2) is the ending point (tip) of the edge vector.

We check if all the z-components are the same sign (or 0; if we include a point on the polygon as inside). If all of the z-components are the same sign then the point is inside of the polygon. If at least one of them is not the same sign, then the point is outside of the convex polygon.

code:

View.Set ("offscreenonly") var px : array 1 .. 8 of int := init (100, 80, 80, 100, 120, 140, 140, 120) var py : array 1 .. 8 of int := init (100, 120, 140, 160, 160, 140, 120, 100) var x, y, button : int fcn pointPolygon (px, py : array 1 .. * of int, x, y : real) : boolean     var n := upper (px)     var z : array 1 .. n of real     for i : 1 .. n - 1         z (i) := (y - py (i)) * (px (i + 1) - px (i)) - (x - px (i)) * (py (i + 1) - py (i))     end for     z (n) := (y - py (n)) * (px (1) - px (n)) - (x - px (n)) * (py (1) - py (n))     for i : 2 .. n         if sign (z (i)) not= sign (z (1)) and sign (z (i)) not= 0 then             result false         end if     end for     result true end pointPolygon loop     Mouse.Where (x, y, button)     Draw.Polygon (px, py, 8, blue)     put pointPolygon (px, py, x, y)     View.Update     delay (10)     cls end loop

Math Lesson : Projecting a point onto a line going through the origin

If we want to project a point p (x, y) onto a line going through (0, 0) called v(vX, vY), we can use this formula :

proj.x = [(x * vx + y * vy) / (vx **2 + vy ** 2)] * vx
proj.y = [(x * vx + y * vy) / (vx **2 + vy ** 2)] * vy
Note that what's in the square brackets is the same for both proj.x and proj.y, and can be said as the dot product of the position vector of the point p with the vector v, divided by v dot v.

Convex Polygon vs. Convex Polygon

If two polygons are not intersecting, there is always a line (with infinite length) that can be drawn between them. In fact, a line can be drawn between the polygons will actually be parallel to one edge of one of the polygons. If they are intersecting, then no such line can be drawn.

So, how do we test if a line parallel to one of the 2 polygons' edges will be able to separate the polygons? Well, let's start with the first edge of the first polygon. We take a line perpendicular to this and, for simplicity, let's have this line going through (0, 0). This line will act as an axis. If we project both polygons onto this axis and the projections of the polygons are not overlapping, then the first edge of the first polygon has a line parallel to it that can separate the polygons. Simply put, there is no intersection between the polygons.

We do this for every edge of both polygons. The instant that the projections of both polygons onto a perpendicular axis are not overlapping, then we know we have no collision between the two convex polygons. If the projections overlap on every perpendicular to every edge of both polygons, then there is an intersection between the polygons.

We have one more problem which you may or may have not figured out. What is meant by projecting a polygon onto a line (axis)? By this, I just mean project every point of the polygon onto the axis and join them with a line.

So, in psuedocode :
for each edge of the polygon

find perpendicular axis going through (0, 0)

project polygon 1 onto this axis

project polygon 2 onto this axis

check if the two projection lines are overlapping

code:

View.Set ("offscreenonly") var x1 : array 1 .. 6 of int := init (100, 70, 100, 130, 160, 130) var y1 : array 1 .. 6 of int := init (100, 130, 160, 160, 130, 100) var a : array 1 .. 8 of int := init (0, -30, -30, 0, 30, 60, 60, 30) var b : array 1 .. 8 of int := init (0, 30, 60, 90, 90, 60, 30, 0) var x2, y2 : array 1 .. upper (a) of int var x, y, button : int fcn Min (arr : array 1 .. *, 1 .. * of real, n : int) : real     var minimum := arr (n, 1)     for i : 2 .. upper (arr, 2)         if arr (n, i) < minimum then             minimum := arr (n, i)         end if     end for     result minimum end Min fcn Max (arr : array 1 .. *, 1 .. * of real, n : int) : real     var maximum := arr (n, 1)     for i : 2 .. upper (arr, 2)         if arr (n, i) > maximum then             maximum := arr (n, i)         end if     end for     result maximum end Max fcn polygonPolygon (x1, y1, x2, y2 : array 1 .. * of int) : boolean     var X11 : array 1 .. upper (x1), 1 .. upper (x1) of real     var X12 : array 1 .. upper (x1), 1 .. upper (x2) of real     var X21 : array 1 .. upper (x2), 1 .. upper (x1) of real     var X22 : array 1 .. upper (x2), 1 .. upper (x2) of real     for i : 1 .. upper (x1)         var nx1, ny1 : real         if i = upper (x1) then             nx1 := -1 / (x1 (1) - x1 (upper (x1)) + 1e-8)             ny1 := -1 / (y1 (1) - y1 (upper (y1)) + 1e-8)         else             nx1 := -1 / (x1 (i + 1) - x1 (i) + 1e-8)             ny1 := -1 / (y1 (i + 1) - y1 (i) + 1e-8)         end if         for j : 1 .. upper (x1)             X11 (i, j) := ((x1 (j) * nx1 + y1 (j) * ny1) / (nx1 ** 2 + ny1 ** 2)) * nx1         end for         for j : 1 .. upper (x2)             X12 (i, j) := ((x2 (j) * nx1 + y2 (j) * ny1) / (nx1 ** 2 + ny1 ** 2)) * nx1         end for     end for     for i : 1 .. upper (x1)         if Max (X11, i) < Min (X12, i) or Max (X12, i) < Min (X11, i) then             result false         end if     end for     for i : 1 .. upper (x2)         var nx, ny : real         if i = upper (x2) then             nx := -1 / (x2 (1) - x2 (upper (x2)) + 1e-8)             ny := -1 / (y2 (1) - y2 (upper (y2)) + 1e-8)         else             nx := -1 / (x2 (i + 1) - x2 (i) + 1e-8)             ny := -1 / (y2 (i + 1) - y2 (i) + 1e-8)         end if         for j : 1 .. upper (x1)             X21 (i, j) := ((x1 (j) * nx + y1 (j) * ny) / (nx ** 2 + ny ** 2)) * nx         end for         for j : 1 .. upper (x2)             X22 (i, j) := ((x2 (j) * nx + y2 (j) * ny) / (nx ** 2 + ny ** 2)) * nx         end for     end for     for i : 1 .. upper (x2)         if Max (X21, i) <= Min (X22, i) or Max (X22, i) <= Min (X21, i) then             result false         end if     end for     result true end polygonPolygon loop     Mouse.Where (x, y, button)     for i : 1 .. upper (a)         x2 (i) := a (i) + x         y2 (i) := b (i) + y     end for     Draw.Polygon (x1, y1, upper (x1), red)     Draw.Polygon (x2, y2, upper (x2), blue)     put polygonPolygon (x1, y1, x2, y2)     View.Update     delay (10)     cls end loop

[richcash]

I would like to apologize to anyone who has been waiting for this tutorial. I was supposed to do it in January and forgot all about it!

I've been working on the second part of my collision detection tutorial for about a week now. I think I've gotten quite far with it. I have a tendancy to overexplain things, so in this tutorial I tried to keep it straight to the point.

This is a work in progress. I plan on fixing up the format, adding 2 or 3 more sections, and I might still edit the polygon stuff if anyone doesn't get what I'm saying. I'm also still debating over whether or not to keep some of the math stuff in separate sections. I also forgot to provide a link to zylum's very excellent tutorial on time-based collision.

Any comments or suggestions for impovements are appreciated. If anyone wants anything else included, I'll see if I can do it.

[Clayton]

This is excellent! Until I get a look at it, I'll start off with a good +100 bits. Suggestions to come. =)

[zylum]

wow that looks like a lot of work. and it looks like you covered a lot of topics. so far i have read from the bottom (convex polygon) up to similar elipses and it looks pretty solid so far!

+Karma and 300 bits for the hard work

if you manage to get elipse vs elipse to work for any arbitrary elipses i will add an additional 500 bits

[richcash]

Whoa, thanks to both of you for the bits+karma!!

zylum wrote:

if you manage to get elipse vs elipse to work for any arbitrary elipses

hmm... I shall try my best to get a solution. Hopefully it won't mean computing the discriminant of some quartic every frame (which would be far too costly).



Edit :

My tutorial wrote:

(c.x - x)^2 + (c.y - y)^2 <= r^2 OR
((c.x - x)/r)^2 + ((c.y - y)/r)^2 <= 1

The above is in the Similar Ellipse vs. Similar Ellipse section as the collision detection expression for two circles. This should obviously be :

(c1.x - c2.x)^2 + (c1.y - c2.y)^2 <= (c1.r + c2.r)^2 OR
(c1.x - c2.x)^2 / (c1.r + c2.r)^2 + (c1.y - c2.y)/r)^2 / (c1.r + c2.r)^2 <= 1
where c1 and c2 are two circles each with :
(x, y) as the center
r as the radius

Freakman Edit: I've added that in there for you, any other changes, just post here and I'll add them in.

Unfortunately, I can't edit my above post.

[richcash]

I think I have finally found a solution to zylum's challenge!! My function works for any 2 ellipses that can be drawn uses Turing's Draw.Oval command (have their major and minor axes on the x and y axes and can be defined using rx and ry).

((x-x1)/a)^2 + ((y-y1)/b)^2 = 1
((x-x2)/c)^2 + ((y-y2)/d)^2 = 1
The intersection of two ellipses results in a quartic with 4 roots (2 real, 2 complex; 4 real; or 4 complex). So, someone plugged in the above two equations and found that quartic for me using Maple (algebra software). Here is the resulting ugly quartic :

Quote:

(c^4*b^4+a^4*d^4-2*c^2*b^2*a^2*d^2)*x^4

+(4*c^2*b^2*
a^2*d^2*x2+4*c^2*b^2*x1*a^2*d^2-4*a^4*d^4*x2-4*c^4*b^4*x1)*x^3

+(6*a^4*d^
4*x2^2-2*c^2*b^2*a^2*d^2*x2^2+2*c^2*a^4*d^2*y2^2-2*c^4*b^4*a^2+2*c^4*b^2
*a^2*y1^2-4*c^4*y2*a^2*y1*b^2+2*c^4*b^2*a^2*d^2+6*c^4*b^4*x1^2+2*c^2*a^4
*y1^2*d^2-2*c^2*b^2*x1^2*a^2*d^2+2*c^2*a^4*d^2*b^2-4*c^2*y2*a^4*y1*d^2-2
*c^2*a^4*d^4+2*c^4*b^2*a^2*y2^2-8*c^2*b^2*x1*a^2*d^2*x2)*x^2

+(-4*c^4*b^2
*x1*a^2*d^2+4*c^4*b^4*x1*a^2+4*c^2*b^2*x1*a^2*d^2*x2^2+8*c^4*y2*a^2*y1*b
^2*x1-4*c^2*a^4*d^2*x2*y2^2-4*c^2*a^4*d^2*x2*y1^2-4*a^4*d^4*x2^3-4*c^4*b
^2*x1*a^2*y1^2+4*c^2*b^2*x1^2*a^2*d^2*x2-4*c^4*b^4*x1^3-4*c^4*b^2*x1*a^2
*y2^2+4*c^2*a^4*d^4*x2+8*c^2*y2*a^4*y1*d^2*x2-4*c^2*a^4*d^2*x2*b^2)*x

+a^4*c^4*y2^4+a^4*d^4*x2^4+a^4*c^4*d^4+c^4*b^4*x1^4+c^4*a^4*y1^4+c^4*a^4
*b^4-2*c^4*b^4*x1^2*a^2-2*c^4*a^4*y1^2*b^2-2*c^4*a^4*y1^2*d^2+6*c^4*a^4*
y1^2*y2^2-2*c^4*a^4*b^2*d^2-2*c^4*a^4*b^2*y2^2-2*a^4*c^2*d^4*x2^2-2*a^4*
c^4*d^2*y2^2-4*c^4*y2*a^4*y1^3-4*c^4*y2^3*a^4*y1+2*c^4*b^2*x1^2*a^2*y1^2
+2*c^4*b^2*x1^2*a^2*d^2-2*c^2*b^2*x1^2*a^2*d^2*x2^2+2*c^4*b^2*x1^2*a^2*y
2^2+2*c^2*a^4*y1^2*d^2*x2^2+2*c^2*a^4*b^2*d^2*x2^2+2*c^2*a^4*d^2*x2^2*y2
^2-4*c^4*y2*a^2*y1*b^2*x1^2+4*c^4*y2*a^4*y1*b^2+4*c^4*y2*a^4*y1*d^2-4*c^
2*y2*a^4*y1*d^2*x2^2

That is awful, but it's still manageable. I calculated the coeffiecents and the constant at the end of the quartic and then calculated the discriminant. If the discriminant is less than 0, then there are two complex and two real roots. But we still have to find out whether or not when the discriminant is above 0 if the ellipses are intersecting in 4 points or in 0 points. For this you can try to see what I'm doing in my commented code.

Basically, if one ellipse has its right and left ends on separate sides of the other ellipse's center, then they are intersecting in 4 points or in none. So you have to move the ellipse to a point where a new discriminant will be less than 0 if the original position of the ellipse had 4 intersection points. I can't explain anymore than that without going into all of the details.

Because there are so many calculations going on in the computing of the coefficients, constant, and discriminant, any roundoff errors will be magnified. You'll notice that for really skinny ellipses, the accuracy is completely lost. I might write this in java to verify that it is only because of a roundoff error. To minimize the number of these errors, I use the collision expression for similar ellipse - similar ellipse (because although this function doesn't aways return true when it's supposed to, it will never return true when it's not supposed to. Therefore it can't make the collision detection worse).

I'll write a tutorial section on this soon, but until then here's my code. Enjoy!

Turing:

View.Set ("offscreenonly") var x1, y1, rx1, ry1, x2, y2, rx2, ry2, x, y, button : int x1 := 100 y1 := 100 rx1 := 50 ry1 := 180 rx2 := 200 ry2 := 40 %(X1, Y1) and (X2, Y2) are centers of ellipses %a and c are x-radii of each ellipse; b and d are y-radii of each ellipse fcn ellipseEllipse (X1, Y1, a, b, X2, Y2, c, d : real) : boolean     var x1, y1, x2, y2 : real     x1 := X1     x2 := X2     y1 := Y1     y2 := Y2 for i : 1 .. 2 %rectangular collision among the ellipses' rectangles first     if x1 + a < x2 - c or x1 - a > x2 + c or y1 + b < y2 - d or y1 - b > y2 + d then         result false     end if %if the original discriminant failed, check if it was because there 4 real intersection %points among the two ellipses by moving one so that it will ensure to have two intersection %points if it previously had 4, and still have 0 if it previously had 0     if x2 - c < x1 and x2 + c > x1 and i = 2 then         x2 := x1 + c     end if     if x1 - a < x2 and x1 + a > x2 and i = 2 then         x1 := x2 + a     end if %the constant at the end of the quartic var a0 :=a**4*c**4*y2**4+a**4*d**4*x2**4+a**4*c**4*d**4+c**4*b**4*x1**4+c**4*a**4*y1**4+c**4*a**4 *b**4-2*c**4*b**4*x1**2*a**2-2*c**4*a**4*y1**2*b**2-2*c**4*a**4*y1**2*d**2+6*c**4*a**4* y1**2*y2**2-2*c**4*a**4*b**2*d**2-2*c**4*a**4*b**2*y2**2-2*a**4*c**2*d**4*x2**2-2*a**4* c**4*d**2*y2**2-4*c**4*y2*a**4*y1**3-4*c**4*y2**3*a**4*y1+2*c**4*b**2*x1**2*a**2*y1**2 +2*c**4*b**2*x1**2*a**2*d**2-2*c**2*b**2*x1**2*a**2*d**2*x2**2+2*c**4*b**2*x1**2*a**2*y2 **2+2*c**2*a**4*y1**2*d**2*x2**2+2*c**2*a**4*b**2*d**2*x2**2+2*c**2*a**4*d**2*x2**2*y2 **2-4*c**4*y2*a**2*y1*b**2*x1**2+4*c**4*y2*a**4*y1*b**2+4*c**4*y2*a**4*y1*d**2-4*c** 2*y2*a**4*y1*d**2*x2**2 %the coefficient of the x^4 term in the quartic var a4 := c**4*b**4+a**4*d**4-2*c**2*b**2*a**2*d**2 %the coefficient of the x^3 term var a3 := 4*c**2*b**2* a**2*d**2*x2+4*c**2*b**2*x1*a**2*d**2-4*a**4*d**4*x2-4*c**4*b**4*x1 %the coefficient of the x^2 term var a2 := 6*a**4*d** 4*x2**2-2*c**2*b**2*a**2*d**2*x2**2+2*c**2*a**4*d**2*y2**2-2*c**4*b**4*a**2+2*c**4*b**2 *a**2*y1**2-4*c**4*y2*a**2*y1*b**2+2*c**4*b**2*a**2*d**2+6*c**4*b**4*x1**2+2*c**2*a**4 *y1**2*d**2-2*c**2*b**2*x1**2*a**2*d**2+2*c**2*a**4*d**2*b**2-4*c**2*y2*a**4*y1*d**2-2 *c**2*a**4*d**4+2*c**4*b**2*a**2*y2**2-8*c**2*b**2*x1*a**2*d**2*x2 %the coefficient of the x term var a1 := -4*c**4*b**2 *x1*a**2*d**2+4*c**4*b**4*x1*a**2+4*c**2*b**2*x1*a**2*d**2*x2**2+8*c**4*y2*a**2*y1*b **2*x1-4*c**2*a**4*d**2*x2*y2**2-4*c**2*a**4*d**2*x2*y1**2-4*a**4*d**4*x2**3-4*c**4*b **2*x1*a**2*y1**2+4*c**2*b**2*x1**2*a**2*d**2*x2-4*c**4*b**4*x1**3-4*c**4*b**2*x1*a**2 *y2**2+4*c**2*a**4*d**4*x2+8*c**2*y2*a**4*y1*d**2*x2-4*c**2*a**4*d**2*x2*b**2 %the discriminant of the quartic; will be negative if there are exactly two roots var D := ((a1*a2*a3)**2 - 4*(a1*a3)**3 - 4*a1**2*a2**3*a4 + 18*a1**3*a2*a3*a4 - 27*a1**4*a4**2 + 256*(a0*a4)**3) + a0*(-4*a2**3*a3**2 + 18*a1*a2*a3**3 + 16*a2**4*a4 - 80*a1*a2**2*a3*a4 - 6*a1**2*a3**2*a4 + 144 * a1**2 * a2 * a4**2) + a0**2*(-27*a3**4 + 144*a2*a3**2*a4 - 128*(a2*a4)**2 - 192*a1*a3*a4**2) %check if the discriminant is less than 0 %also check for trivial intersections that the discriminant may not pick up %due to rounding errors using the similar ellipse - similar ellipse expression     if D < 0 or ((x2 - x1) / (a + c)) ** 2 + ((y2 - y1) / (b + d)) ** 2 <= 1 then         result true     elsif i = 2 then         result D < 0 or ((x2 - x1) / (a + c)) ** 2 + ((y2 - y1) / (b + d)) ** 2 <= 1     end if end for end ellipseEllipse loop     Mouse.Where (x, y, button)     x2 := x     y2 := y     Draw.Oval (x1, y1, rx1, ry1, blue)     Draw.Oval (x2, y2, rx2, ry2, red)     put ellipseEllipse (x1, y1, rx1, ry1, x2, y2, rx2, ry2)     View.Update     delay (20)     cls end loop