Sometimes the expanding polytype algorithm takes a long time to
terminate, e.g. in situations like this:
.-.
: +-:-+
'-' |
| |
+---+
The issue here is that the EPA adds vertices very close to each other,
which makes the separation distance change very slowly. If this is the
case, consider the current separation distance as approximately correct
and continue.
support(A,B, 1,0) returns 0,0 when A and B are touching in a vertex of
both A and B AND this vertex is on the right of A's center (in direction
(1,0)), e.g. this situation:
.---.
.-.| B |
: A x---'
'-'
Then: support(A,B, 1,0) = A:support(1,0) - B:support(-1,0) = x - x = 0
Since CircleShape:support(dx,dy) normalizes dx,dy this will result in a
division by 0 error in the subsequent execution of the GJK algorithm.
An early out with result 'not colliding' (in accordance to the other
edge cases) prevents this error.
Collecting collisions and then reporting leads to confusing behavior
when a previous collision callback resolved the collision, e.g.
platforms in jump in runs pushing the player upwards when standing on
two platforms at the same time.
Shape must have at least two functions:
- shape:bbox()
must return an axis aligned bounding box of the shape
- shape:collidesWith(other)
must return false, ... if the two shapes do not collide
must return true, sx, sy if the two shapes collide, where sx,sy is the
separation vector from from shape to other.
Convex shapes can use the supplied GJK algorithm. In that case the shape
must implement shape:support(dx,dy) which returns the point of the shape
that lies furthest in the direction of dx,dy.
The Gilbert–Johnson–Keerthi collision detection algorithm is
significantly faster than collision detection using the separating axis
theorem. GJK can only determine whether two shapes collide, but not the
penetration vector. The expanding polytype algorithm can use information
from GJK to quickly find the required vector.
Shapes were not inserted into the spatial hash when not moved. Shapes
set to passive directly after creation would not be in the hash,
resulting in no collision reports.
Spatialhash drawing updated to the new cell indexing method.
Polygon triangulation bug:
In some cases Kongs triangulation algorithm produces triangles
with collinear points. The Polygon constructor removes one of
these and throws an error because there are not enough vertices.
Checking if the current points in a triangulation step are
collinear and discarding those triangles fixes the problem.
Class-commons lets you use any supporting class system as
backend for HC.
Add SpatialHash:draw() for debug purposes.
