[Optimization] Rotating Convex Polygons

[camelCase]

I just implemented a collider system for a crude Android game engine (for educational purposes) and it works. I use the Separating Axis Theorem (SAT) to detect collisions and calculate the minimum translation vector.

I know that SAT only works for convex polygons and that's why I have two classes:
ConvexPolygon
Collider

Class ConvexPolygon's constructor: [ljass]ConvexPolygon (Vector2[] points)[/ljass]
Class Collider's constructor: [ljass]Collider(ConvexPolygon convexPolygon)[/ljass]

So, ConvexPolygon ensures that the points form a convex polygon (duh) and Collider takes advantage of that safety and implements SAT (pre-computes the axes, too).

I have a method [ljass]ConvexPolygon rotate(float radian, Vector2 center)[/ljass] that returns a new instance of ConvexPolygon that's the original polygon rotated by 'radian' around 'center'. So, this method allocates a new array of Vector2 and fills it up, calling cos() and sin() for each point.

So, every time my game object rotates, I have to rotate its collider accordingly, too. And the way I do this is.. [ljass]m_Collider = new Collider(m_Collider.getConvexPolygon().rotate(radian, center));[/ljass]

Which means..
If I rotate my game object by an arbitrary angle every frame (meaning I can't pre-compute the polygons..) I'll have to:
allocate a new array of Vector2
Call cos() and sin() for each point
Pre-compute the axes of the rotated convex polygon for SAT

It doesn't affect my frame rate and I know that this isn't really an OMGWTFMEGAHUGE drain on the CPU but seeing that kind of memory allocation and sin() and cos() calls EVERY FRAME really irks me =/

There might not be a better way to do this if my rotations are going to be arbitrary but I thought I might get some suggestions.

 

[Accname]

Why do you need to create a new instance? Why dont you simply change the values?

 

[s3rius]

Can't you re-use the Collider object and prevent a new array allocation by just overwriting the old one?

And cos/sin can be precomputed and stored in an array or lookup table.

Depending on how frequent collisions are, you can omit the creation of a collider object unless one is actually needed.
E.g. you create the collider only on collision. To actually check for collisions a simple axis-aligned bounding box will suffice (or sometimes a circle is better, especially for polygons this could be true).

If that is too time consuming (= you have too many collisions happening in one frame) you do a very broad collision prediction and determine whether the polygon might actually collide with something in the near future. This way you can start creating colliders a few frames before the collision actually happens.
But that's probably overkill.

 

[camelCase]

Yeah, I could change the values and over-write the old one. I have no idea what I was thinking =/
Oh, yeah, I can't believe I forgot about look-up tables! God-send!

I know that AABBs and circles are great, I've used them up to this point but my game objects have to get rotated and that just ruins AABBs and leaves me with circles which aren't always the best approximation for shapes..
I kinda' like that create colliders a few moments before collision but probably won't be using it xD

 

[s3rius]

Well, "ruin" is a harsh word
Depending on how your polygons look like it might be more or less performant. If most polygons at least somewhat resemble a round-ish shape then AABBs are still great. Even if their shape bad for AABBs, it'll still be better to test for a simple intersection test before testing for polygon intersection.
And considering you re-calculate all polygon points on rotation, it's sheepishly easy to construct the AABB.

At least if your polygons usually consist of many points I'd try it out.. for science! It's 10 minutes of work for a potentially nice performance improvement.

 

[camelCase]

You make a very good point. I think I will use AABBs as the second test xD
01) Quadtree
02) AABB
03) SAT

Sounds good.

Also, I just implemented a look-up table of cos() and sin() values. It has an accuracy of up to 0.5 degrees which would normally require 720 + 720 floats. However, my implementation only uses 361 floats xD

I realized I only needed 720/2 + 1 floats for cos() because, well, the value bounces around from -1 ~ 1. And I didn't need anymore floats for sin() because sin(theta) = cos(Tau/4 - theta).

So, my implementation uses 1/4th the floats a straightforward implementation would xD

However, when I just plugged the look-up table into the code and tested, the polygon would rotate and keep its shape, however, it would start shifting about because of the loss in precision..

So, I had to create a new "ConvexPolygon" class:
01) ConvexPolygonSource
02) ConvexPolygon
03) Collider

One creates an instance of ConvexPolygonSource(float[] points) which does all error checks and whatnot and creates an instance of ConvexPolygon(ConvexPolygonSource src) using the source created.

So, whenever a rotation needs to be done, the array in ConvexPolygon is updated using the "untainted" values in ConvexPolygonSource (which is immutable).