craftyjs/Crafty — pull request #835 by starwed (2014-11-17 23:10:23+00:00)
Title: Fix _SAT algorithm, optimize Crafty.polygon

Our current implementation of the SAT (Separating Axis Theorem) algorithm is both a bit slow and somewhat incorrect.

To improve the speed, this patch changes the behavior of Crafty.polygon to store points as a single flat array, rather than an array of smaller arrays. This is a breaking change -- code that interacts with this (e.g. by creating collision regions) will have to be modified. I'm pretty sure it's worth it, though. Doing some jsperf tests indicates that dealing with a single array is much faster.

This patch also prevents the creation of temporary objects within each step of the SAT algorithm, which also increases the speed a bit.

The algorithm also seemed somewhat incorrect; it calculated the minimal overlap for each edge of each polygon, but never actually did anything with the first result. This doesn't matter when dealing with simple rectangles, which is probably why this went unnoticed til now.

I added some tests to make sure our _SAT behavior isn't broken in the future.