# Polar Collision Module

#### magic

##### Active Member
3rd Party Module Dev
3rd Party Tool Dev
This is a collision detection module that I created long time ago. The idea come from a question post by someone at stackoverflow.com answer by @Blindman67 about the idea of having fast but almost pixel perfect collision using Polar coordinate.
https://stackoverflow.com/questions...detection-of-two-partially-transparent-images

The concept:

Fast almost pixel perfect collision can be achieved by defining the shape of each sprite with a set of polar coordinated. Each coordinate describes the distance from the center (the center is arbitrary but must be inside the sprite) and direction from the center of the furthest most pixel from the center along that direction. The number of coordinates (n) is determined by the circumference of the outermost pixel.

Base on the answer by @Blindman67 ,I code this CX module here: https://github.com/zomagic/cerberus_magic/tree/master/polarcollision/modules_ext/magic
Feel free to optimize it

Last edited:

#### magic

##### Active Member
3rd Party Module Dev
3rd Party Tool Dev
I tough the the concept is interesting (semi/almost pixel perfect collision). So I coded into CX. Try to see how fast it do the job.

#### MikeHart

Interesting concept for sure. With your examples, I get a lot of collisions where none should appear or opposite. Is there a function where it renders the collision shape for debugging purposes?

And I understood, that it is also creating sprites to draw the images, right?

#### Rich

##### Well-Known Member
CX Code Contributor
3rd Party Module Dev
Tutorial Author
3rd Party Tool Dev
I really like optimisations like this.
Cant wait to have a look when i get home

#### magic

##### Active Member
3rd Party Module Dev
3rd Party Tool Dev
I get a lot of collisions where none should appear or opposite
Its not accurate but faster than doing pixel perfect collisions. It suitable for fast game where player can barely discern a pixel.

Good thing is.. it can support transform (scale and rotation) and animated image

Is there a function where it renders the collision
No. But probably can create a sprite during CreatePolarData() for the purpose of debugging.

#### SLotman

##### Active Member
3rd Party Module Dev
I once wrote a routine to test if a point was inside a polygon. But it didn't handle scaling or rotation.

Does this generate the polygon automatically from an image? And it handles real time scaling/rotating? If so, this is very interesting, and can have many applications indeed

#### magic

##### Active Member
3rd Party Module Dev
3rd Party Tool Dev
Does this generate the polygon automatically from an image?
No. Its generate polar coordinates from the image automatically. It do that in function CreatePolarData(). This function only call once but must be done inside OnRender() due to using ReadPixel(). The function task is to get polar data of all image (every frames if animation) and store in array.

It is actually an array of distance (from center).

And it handles real time scaling/rotating?
Yes.

This is how collision is check:
1. First it check normal box collide
2. If true then do a polar checking
a. get distance of both image from centre

b. get which polar coordinate to be use (after consider rotation of image above)

b. Then get average distances to be use

c. Finally add both distance (cyan+magenta) and compare with real distance(yellow)
If more meaning a collision

To be able to consider scaling, it just multiply polar length with current scale.

#### SLotman

##### Active Member
3rd Party Module Dev
Well, in those images you can see there is a collision and it isn't registered... maybe instead of comparing distances/real distance would be better to just do a line intersection and see where they hit each other and then compare it to the lines 'distance'?

To get the intersection point seems really easy: http://www.pdas.com/lineint.html

#### SLotman

##### Active Member
3rd Party Module Dev
If I'm not mistaken, I think that code on that page would translate to something like this:

Cerberus X:
``````Global LineIntersectionX:Float
Global LineIntersectionY:Float

Function LinesIntersectionPoint:Bool(x1:Int, y1:Int, x2:Int, y2:Int, x3:Int, y3:Int, x4:Int, y4:Int)

Local a1:Int, a2:Int, b1:Int, b2:Int, c1:Int, c2:Int ' Coefficients of line eqns.
Local denom:Int

a1 = y2-y1
b1 = x1-x2
c1 = x2*y1 - x1*y2  '{ a1*x + b1*y + c1 = 0 is line 1 }
a2 = y4-y3
b2 = x3-x4
c2 = x4*y3 - x3*y4  '{ a2*x + b2*y + c2 = 0 is line 2 }

denom = a1*b2 - a2*b1
If denom = 0 Then Return False

LineIntersectionX = (b1*c2 - b2*c1) / denom
LineIntersectionY = (a2*c1 - a1*c2) / denom
End Function``````

So what am I thinking? Get 2 lines, one from each image. Get the intersection point between those. Get distance from intersection point to center of image 1. Get distance of the line from image 1. If distance_line <= distance_intersection, we have a colision.

#### magic

##### Active Member
3rd Party Module Dev
3rd Party Tool Dev
Well, in those images you can see there is a collision and it isn't registered

Yes, I am aware of this problem from the beginning.

This method produce good and fast solution on scenario A and B

On case C it fail to recognize a collide. May be we can improve by do a line intersection checking like you suggested
We can check only few line that 90 degree facing the other sprite.

In the above image show only 4 set of line to be test.