Sabbatical Log: November 4th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Fun Saturday nights lead to somewhat less fun Sunday mornings. Still going to try and make some progress on the collision detection problem, but definitely not firing on all cylinders.

I’ve managed to get most of a collision detection algorithm implemented, at least to the point of determining which polygons will collide and at what times.

The gist is:

• Only work over convex polygons (I’ll handle this shortcoming later)
• For each pair of polygons…
  • Treat the first polygon as stationary and increase or decrease the velocity of the second polygon so the same “relative motion” is happening
  • For each line segment in their polygon, determine it’s normal
    • For a line running along the vector (x,y) the normal is (-y, x)
  • Keep any normal that isn’t parallel to a normal I’ve already found
    • Two lines are parallel if their cross product is 0
  • Project each polygon in the pair onto each normal, producing two line segments per normal
    • This is just taking the dot product between the normal and the start and end point of each line segment, and keeping the min and max over the whole polygon.
  • Take those line segments, and determine if the one corresponding to the second polygon (the only one moving) is moving towards the other line segment
    • If not, they will never collide on that axis
    • If so, the distance divided by its velocity (projected onto the same axis) is the time to collision
  • The minimum time of collision on all axises, if any, is the time these two polygons will collide

I’ve now got both the time and the point of collision working. I’ve decided what I’m going to consider the point of collision is point halfway between the closest vertices and/or line segments of the involved polygons.

This boils down to:

• I’m given two polygons that are “colliding”
• For both polygons
  • Enumerate one of their vertices and the others line segments
  • Determine the the closest point on the line segment to the vertex (I based my math on this article)
  • If there is no closest point, move on
  • Measure the distance between the found point and the vertex
  • Take all the vertices (and their paired points) with the smallest distance
    • There may be multiple!
• If you have no vertices/points, then repeat the above but instead of measuring between vertices and line segments, compare only vertices
• Average each set of points you found (one set is from the first polygon, one from the other) to create new points
  • Most of the time you’ll only have one, but if you’re in the case where two line segments are parallel and going to collide you’ll have more
• The point of collision is the point halfway between these two average points

I’ve got some tests for these two separate algorithms covering collisions between different sized square, triangles, octagons, and pentagons. I have yet to stick the two system together into a generic “detect and resolve collisions”-pass, but I’m getting close.

Whelp, sticking them together revealed a real logic error. The algorithm I’ve implemented is reasoning about single axises, so I’m getting phantom collisions whenever two shapes overlap on a normal.

I’ve got some ideas on a fix, which I’ll get to exploring tomorrow.

Continue onto November 5th