After the entities have been moved to their new positions, non-penetration constraints may be violated. Therefore, we check for each rock whether it collides with the player, the terrain or any of the other rocks and resolve it. Because only pairwise collisions are considered and to ensure stability, this loop is repeated until no collisions occur anymore. We do however, allow the simulation to stop after a maximum number of resolution steps. This coincides with our design choice of prioritizing performance over accuracy.

There are many options for collision detection between convex polygons, such as the Gilbert-Johnnson-Keerthi algorithm (GJK), Minkowski Portal Refinement (MPR) and different variations of the separating axis theorem (SAT). For the sake of simplicity and efficiency, we chose an SAT based approach. The SAT states that two convex polygons do not collide if and only if there exists a separating axis. If a separating axis exists, a separating axis can be found that is parallel to one of the polygons' edges. The figure below demonstrates this with an example. Our implementation of the SAT roughly follows the algorithms outlined by Wheeler. Separating axes are found by projecting all vertices of both polygons on all edge normals. If a separating axis is found, the algorithm instantly returns. Otherwise, if none of the edges constitutes a separating axis, the edge with the smallest overlap of the projections is returned. This edge is called the reference edge and the corresponding polygon is called reference polygon. The other polygon is the incident polygon.

Figure: On the left, the separating axis is $s$. On the right, no separating axis exists, the algorithm returns the reference edge $e$, which has the smallest collision depth $\Delta$.

We take measures to increase the performance of our collision detection routines. When a separating axis to another polygon is found, its index is stored in a map accessed by a polygon ID. When those two polygons are checked for collisions the next time, the detection algorithm starts with this edge as there is a high probability that it is a separating axis again and the algorithm can return early. This concept is called warm starting.

Moreover, we use swept axis-aligned bounding boxes (swept AABBs). The rather expensive SAT algorithm is not executed when the swept AABBs do not collide. In addition to increasing performance, the use of swept AABBs also increases accuracy. If a potential collision is signalled by the AABB check, the last simulation step is substepped if the rocks are `fast`, i.e. the following holds for the two velocities $\vec{v_1} = \vec{P_1}/m_1$ and $\vec{v_2} = \vec{P_2}/m_2$: $$ \left|\vec{v_1}\right| + \left|\vec{v_2}\right| > \frac{minPolySize}{2\delta t} $$ We approximate continuous collision detection by using a small but constant $\delta t' < \delta t$ for substepping. In order to ensure efficient access, the swept AABB is calculated and stored during positioning. Furthermore, to allow local substepping via interpolation, the last position $\vec{x}^{t-1}$ and rotation angle $\theta^{t-1}$ are kept as attributes.

Figure: Swept AABBs increase accuracy. Potential collisions can be detected even if the objects are not currently colliding.

By itself, the SAT only works for convex polygons. However, our terrain is obviously concave. To handle this with our existing collision detection architecture, we triangulate the terrain using the poly2tri library's constrained Delaunay triangulation. Using triangles, all the collision detection methods above work as is. Still, one important aspect to consider is the retrieval of the relevant parts $T_{cd}$ of the terrain and how to create a polygon as input for poly2tri from the line representation of the terrain.

In order to achieve this, we first compare the swept axis aligned bounding box $AABB_e$ of the entity with the axis aligned bounding boxes $AABB_{t_{i}}$ of the terrain sections $T_{i, cd}$. Here, we filter out the sections $T_{min, cd}$ and $T_{max, cd}$ as the first and last terrain sections $T_{i, cd}$ for which $AABB_{t_{i}}$ overlaps with $AABB_e$. Then, we create a new polyline $Pl_{T,e}$ by combining all sections from $T_{min, cd}$ to $T_{max, cd}$ along the terrain:

$$Pl_{T,e} = (T_{min, cd}, T_{min + 1, cd}, \dots, T_{max - 1, cd}, T_{max, cd})$$

After that, we combine the hitboxes $AABB_e$ of the entity and $AABB_{PL_{T,e}}$ of the created polyline into a merged $AABB_{e, PL_{T,e}}$ that includes both of them and has an additional tolerance to each side. Then, we project the first and last point of $Pl_{T,e}$ outwards onto $AABB_{e, PL_{T,e}}$ and add those points $p_{min}$ and $p_{max}$ to the start and end of $Pl_{T,e}$. As a last step, we close the modified Polyline to a polygon $P_{T,e}$ by adding the corners $c_{min}, c_{min+1}, \dots, c_{max}$ of $AABB_{e, PL_{T,e}}$ in between $p_{max}$ and $p_{min}$ in clockwise order.

$$P_{T,e} = (p_{min}, T_{min, cd}, T_{min + 1, cd}, \dots, T_{max, cd}, p_{max}, c_{min}, c_{min + 1} \dots, c_{max})$$

The process of creating such a polygon for both normal terrain and in case of overhangs is illustrated in the following figure.