Ideas? Collision detection during rotation

Java 2D
#1

Hi,

I would really appreciate any help and ideas from all you Java gods with regards to the following 2D problem:

  1. How do I detect AND recover from a collision between arbitrary polygons (convex or concave with more than 3 vertices) in 2D rotating and moving directionally at different speeds?

I was thinking of checking each line segment generated from each BEFORE MOVING vertex of polygon A to the AFTER MOVING vertex, against all the edges of the polygon B. The process is then repeated for polygon B “moving” in the opposite direction. Very brute-force I know, but at least it solves the speed problem with collision detection.

I’ve linked a pic to illustrate: http://www.imagedump.com/index.cgi?pick=get&tp=49876&poll_id=0&warned=y

In the picture, the red line segments generated from the movement are checked against the blue edges of the green polygon. The red circles represent the point of intersections.

  1. To detect collision during DIRECTION MOVEMENT at arbitrary speeds, i find the before and after coordinates and use the above algorithm. To correct the movement, I find the point of intersection with the least displacement from the original vertex and translate the polygon there instead.

  2. To detect collision during ROTATION at arbitrary speeds, i would use the exact same process, with the exception that line segments are now rotation arcs.

My big and ugly problem is that I can’t find a neat and (somewhat) efficient algorithm to compute the angle I must “un-rotate” to get the correct displacement. Since I’m hardly a mathematician, the algorithm I have, in a word, sucks.

Can anyone help with the algorithm? Is this even a good way to get around the problem? :-/

Thanks.

#2

Interesting problem, try not to corss post tho.

Kev

#3

Whoops, sorry. :-[

Any ideas though? How would you guys implement collision detection and response for rotating polygons?

#4

There are a lot of assumptions that will simplify this.
One is that this happens in one frame time - so you know the maximum traveling that each polygon will do.

So step your simulation by one full frame time and if it results in collisions, try again by stepping only half a frame time.

Use successive approximations, divide and conquer algorithm - After only a small number of iterations you will find the point ‘just’ before the collision.

You can get better accuracy by computing a few steps per frame in the first place… just in case things move so far in a single step as to path completely through each other… but you can solve that as a separate problem (e.g. computing the intersections of line segments like you wrote).
Also don’t use real arcs for the rotation case - use piece-wise linear “arcs”… that is basically the same as only doing linear movements but with finer steps.

#5

This algorithm doesn’t have to be particularly fast, because you can immediately discard pairs when you determine that their bounding radii do not intersect. In other words, perform a very cheap circle-circle collision detection first, and then in the few instances where they do actually intersect, perform the full polygon collision detection (which I don’t know how to do off the top of my head but isn’t there a Java2D API for this?)

Cas :slight_smile:

#6

[quote] in the few instances where they do actually intersect, perform the full polygon collision detection (which I don’t know how to do off the top of my head but isn’t there a Java2D API for this?)
[/quote]
If I remember right, the AWT Polygon class only has tests for poly-point and poly-rectangle. :frowning:

#7

First of all, I would like to thank you guys for your contributions. :slight_smile:

This is what the algorithm would probably look like after giving it a little thought:

class MyPolygon
{
…

/*

  • Rotates all the vertices of this polygon and checks

  • for collision with another polygon.

  • If there is a collision, rotate to the point just

  • before collison.
    */
    void rotateAndRecover(int angleSpeed, MyPolygon anotherPolygon)
    {
    Store the current coordinates of all the vertices…

    // Check for rotation collisions with the other polygon
    // and get the value for the least angular
    // displacement
    int rotateAngle1 = checkForRotationCollision(anotherPolygon);

    // Do the same, except get the anotherPolygon to
    // simulate a rotation instead. This will ensure that
    // we do not miss a collision
    int rotateAngle2 = anotherPolygon.checkForRotationCollision(this);

    // Now get the lowest returned rotation angle and
    // see if it is less
    // than angleSpeed (meaning a collision has occured)
    int toRotate;
    if(rotateAngle1 < rotateAngle2)
    toRotate = rotateAngle1;
    else
    toRotate = unrotateAngle2;

    // Rotate by the corrected angle if a collision
    // has occured
    if(toRotate < angleSpeed)
    this.rotate(toRotate);
    else
    this.rotate(angleSpeed);

}

int checkForRotationCollision(MyPolygon anotherPolygon)
{
// Note that number of vertices = number of edges
for(int i=0; i<this.numVertices; i++)
{
Get coords for Before_Rotate_Vertex[i]…
for(int j=0; j<anotherPolygon.numVertices; j++)
{
Get edge[j] from anotherPolygon…
Get circle[i] formed by a 360deg rotation of Before_Rotate_Vertex[i] with a radius r…
Calculate points of intersection with edge[j] and circle[i]
Calculate angular displacements from Before_Rotate_Vertex[i] to the points of intersection.
Store the value of the lowest angular displacement seen so far
}
}
return lowest angular displacement seen so far
}

Looks like complexity O(2nm) approximately for this rotation collision check… Opinions please?

#8

[quote]There are a lot of assumptions that will simplify this.
One is that this happens in one frame time - so you know the maximum traveling that each polygon will do.

So step your simulation by one full frame time and if it results in collisions, try again by stepping only half a frame time.

Use successive approximations, divide and conquer algorithm - After only a small number of iterations you will find the point ‘just’ before the collision.

You can get better accuracy by computing a few steps per frame in the first place… just in case things move so far in a single step as to path completely through each other… but you can solve that as a separate problem (e.g. computing the intersections of line segments like you wrote).
Also don’t use real arcs for the rotation case - use piece-wise linear “arcs”… that is basically the same as only doing linear movements but with finer steps.
[/quote]
Each iteration/approximation is O(n*m) to test for collisions. Therefore with a large number of iterations (in the case with a large displacement per frame for instance), this might prove too expensive to implement.

#9

[quote]This algorithm doesn’t have to be particularly fast, because you can immediately discard pairs when you determine that their bounding radii do not intersect. In other words, perform a very cheap circle-circle collision detection first, and then in the few instances where they do actually intersect, perform the full polygon collision detection (which I don’t know how to do off the top of my head but isn’t there a Java2D API for this?)

Cas :slight_smile:
[/quote]
Yes, I would probably implement bounding circle before resorting to more expensive tests. The Shapes/Polygon class in the API only allow for testing if a point is contained within the Shape.

#10

Area does provide limited capability (though im quite sure it would be incredibly slow)


if(!(new Area(polygon1).intersect(new Area(polygon2)).isEmpty())
{
//collision
}
#11

[quote]Each iteration/approximation is O(n*m) to test for collisions. Therefore with a large number of iterations (in the case with a large displacement per frame for instance), this might prove too expensive to implement.
[/quote]
Ah, but you will only need to iterate again in the case where there IS an intersection/collision on the first iteration.

You can also implement other techniques to partition the work. Instead of simply using a bounding box or circle per polygon, you could have a hierarchy of ‘sectors’ and only compare to objects that are in the same sector. It’s basically the same kind of stuff that is done in 3D to avoid rendering polygons that aren’t in the view frustum. If there are groups of polygons that can’t possibly be close enough to collide you can eliminate them all in one operation by choosing not to iterate through a particular list while looking for collisions.

#12

I see what you mean… This is probably how I would implement such a scheme:

  1. To ensure that a collision is detected when a polygon moves at arbitrary speeds, I would use the line-segment intersection method which I previously mentioned. This is O(2nm).

  2. If a collision is detected, I approximate the midpoint of the collision and repeat the collision algorithm, this time using the midpoint towards the original vertex. Else, I repeat the collision algorithm towards the displaced vertex. In other words, a bit like binary search.

At best, the algorithm I would implement is O(2nm), at the case where no collisions are detected. At worst, it’s O(2logpn*m). Do correct me if I’m mistaken however. :stuck_out_tongue:

Thanks.

#13

Have you looked up AABB’s?

#14

You’ve got the idea, but you can reduce your m*n with clever partitioning of your objects. e.g. if they are ordered in some way or arranged in fancier data structures you will be able to eliminate checking for collisions with multiple objects with a single comparison. Something along the lines of object X is on the left half of the screen so I don’t need to check for collisions with any objects that are on the right half o the screen. That’s just the general idea.
So when you update an objects position you can move it around in some other data structure that has the objects spatially sorted.

#15

For each polygon, pick a central point and then sort the points of the polygon by angular position around that central point. Now use the lines from the centre out through those points to divide the polygon up into lots of slices (this is most obvious where each line only cuts the polygon once, but it works with the more complex case too).

Assuming your polygons are rigid the above calculation need only be done once (and will require about n log n time for each n point polygon).

Now to find the intersection, draw the line between the two centres and find the slice of each polygon containing this line (o(log(n)+log(m)). Work slice by slice comparing looking for intersections in much the same way as a merge sort (you have to proceed in both clockwise and anticlockwise directions from the initial position) until no possibility of intersection remains. This should not take more than about o(n+m) time.

Note that you do NOT need to use any trig functions to sort by polar order (although it might be easier if your maths is poor).

I think this approach should work, but I haven’t checked it out in detail.

There is book by Joseph O’Rourke called “Computational Geometry in C” which might be useful when considering this sort of work.

#16

Agreed. I might try that to see how it measures up instead.

Sounds interesting but I’m having trouble understanding your explanation.

Could you elaborate further or direct me to a source which describes this algorithm in greater detail please?

O(n+m) does sound very nice though. :slight_smile:

#17

You should also look into the algorithm detailed in “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein.

It is a general-purpose method for finding the intersecting pairs in a field of n arbitrary line segments, and it runs in O( n log n ) time, although I’m sure there’s a hefty constant factor attached to that.