Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Collision Detection
Index -> Programming, Turing -> Turing Tutorials
Goto page Previous  1, 2, 3  Next
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Andy




PostPosted: Thu Oct 19, 2006 2:59 am   Post subject: (No subject)

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
Sponsor
Sponsor
Sponsor
sponsor
Cervantes




PostPosted: Thu Oct 19, 2006 9:00 am   Post subject: (No subject)

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




PostPosted: Sat Oct 28, 2006 6:44 pm   Post subject: (No subject)

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]




PostPosted: Sat Oct 28, 2006 6:52 pm   Post subject: (No subject)

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




PostPosted: Sat Oct 28, 2006 10:51 pm   Post subject: (No subject)

[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]




PostPosted: Sat Oct 28, 2006 11:09 pm   Post subject: (No subject)

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




PostPosted: Sun Oct 29, 2006 4:55 am   Post subject: (No subject)

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




PostPosted: Fri Dec 29, 2006 12:06 am   Post subject: (No subject)

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?
Sponsor
Sponsor
Sponsor
sponsor
Cervantes




PostPosted: Fri Dec 29, 2006 5:27 pm   Post subject: (No subject)

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




PostPosted: Fri Mar 16, 2007 9:40 pm   Post subject: Re: Collision Detection

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




PostPosted: Fri Mar 16, 2007 9:53 pm   Post subject: Re: Collision Detection

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




PostPosted: Fri Mar 16, 2007 11:37 pm   Post subject: Re: Collision Detection

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




PostPosted: Fri Mar 16, 2007 11:40 pm   Post subject: RE:Collision Detection

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 Smile

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




PostPosted: Sat Mar 17, 2007 2:29 am   Post subject: Re: Collision Detection

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

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




PostPosted: Thu Mar 22, 2007 4:14 pm   Post subject: Re: Collision Detection

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
Display posts from previous:   
   Index -> Programming, Turing -> Turing Tutorials
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 2 of 3  [ 36 Posts ]
Goto page Previous  1, 2, 3  Next
Jump to:   


Style:  
Search: