Better collision checking

[eliskleen]

Run a more sophisticated collision detection when SAP says there is a collision

[v-olin]

Couldn't figure out why colliders can be colliding without any reflection, but here are some things I've noticed:

We do a bubble sort on edge lists every frame

In physicsmanager line 400 we have this code:

if (!traverse_edge_list) { ... } else {
    bubblesort();
    traverse();
}

the problem here is that traverse_edge_list will always be true, so the else-case will run every time. Because these variables are never set to false

bool traverse_edge_list_x{ true };
bool traverse_edge_list_y{ true };
bool traverse_edge_list_z{ true };

We might swap but not flip?

In Ulf's slides on collision detection he says "flip the bits in the matrix when the sort order changes", but we may change sort order without flipping in physicsmanager line 420

if (!traverse_edge_list) {
    for (...) {
        for (...) {
            if (edge_list[j + 1].val < edge_list[j].val) {

                if (edge_list[j + 1].is_b != edge_list[j].is_b) {
                    /*
                     do stuff
                    */

                    // here we flip bits
                    overlap_matrix[a][b] = overlap_matrix[a][b] == 0 ? 1 : 0;
                }

                // here we change the order
                auto tmp = edge_list[j];
                edge_list[j] = edge_list[j + 1];
                edge_list[j + 1] = tmp;
            }
        }
    }

I don't know if this is intentional but @eliskleen and @fatonhoti knows more about this, it just seemed weird

[eliskleen]

We don't do bubble sort on every frame

In findOverlaps where we do the bubble sort we set the traverse_edge_list to false. And that variable is a reference to the correct variable for the current axis.

else {
  BubbleSort(axis);
  TraverseEdgeList(axis);
  traverse_edge_list = false;
}

We might swap but not flip, and this is correct.

Ulf also says "if(swap(e,s) or swap(s,e)) -> flip bit" which means that we should only flip the bit in the matrix when we swap a start and a beginning of an interval in the edge list.