Register
Handmade Hero»Forums»Code»SAT Collision detection and response
66 posts
SAT Collision detection and response
1 week, 5 days ago Edited by C_Worm on June 22, 2020, 12:35 p.m. Reason: Initial post
Hey I managed to implement the serparated axis theorem(SAT), however im finding it very hard to understand how to extract the so called "minimum translation vector" so that the colliding polygons can be separated.

Any advice on how to implement this would be appreciated.

Here's my Collision function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
struct CollisionInfo
{
    bool collision;
    V2f minVec;
};


CollisionInfo Collision_Entity_SAT(Entity e1, Entity e2)
{
    CollisionInfo result = {};
    
    // get normal of both sides
    V2f normal1 = Normal_V2f(e1.pTop, e1.pRight);
    V2f normal2 = Normal_V2f(e1.pTop, e1.pLeft);
    
    float dp1[4] = {};
    float dp2[4] = {};
    float dp3[4] = {};
    float dp4[4] = {};
  
    // get dotproduct of each entities corner against both normals
    
    dp2[0] = DotProduct_V2f(normal1, e1.pTop);
    dp2[1] = DotProduct_V2f(normal1, e1.pLeft);
    dp2[2] = DotProduct_V2f(normal1, e1.pRight);
    dp2[3] = DotProduct_V2f(normal1, e1.pBottom);
    
    dp1[0] = DotProduct_V2f(normal1, e2.pTop);
    dp1[1] = DotProduct_V2f(normal1, e2.pLeft);
    dp1[2] = DotProduct_V2f(normal1, e2.pRight);
    dp1[3] = DotProduct_V2f(normal1, e2.pBottom);
    
    dp4[0] = DotProduct_V2f(normal2, e1.pTop);
    dp4[1] = DotProduct_V2f(normal2, e1.pLeft);
    dp4[2] = DotProduct_V2f(normal2, e1.pRight);
    dp4[3] = DotProduct_V2f(normal2, e1.pBottom);
    
    dp3[0] = DotProduct_V2f(normal2, e2.pTop);
    dp3[1] = DotProduct_V2f(normal2, e2.pLeft);
    dp3[2] = DotProduct_V2f(normal2, e2.pRight);
    dp3[3] = DotProduct_V2f(normal2, e2.pBottom);
    
    float max_dp1 = Max_f(dp1, sizeof(dp1) / sizeof(float));
    float min_dp1 = Min_f(dp1, sizeof(dp1) / sizeof(float));
    
    float max_dp2 = Max_f(dp2, sizeof(dp2) / sizeof(float));
    float min_dp2 = Min_f(dp2, sizeof(dp2) / sizeof(float));
    
    float max_dp3 = Max_f(dp3, sizeof(dp3) / sizeof(float));
    float min_dp3 = Min_f(dp3, sizeof(dp3) / sizeof(float));
    
    float max_dp4 = Max_f(dp4, sizeof(dp4) / sizeof(float));
    float min_dp4 = Min_f(dp4, sizeof(dp4) / sizeof(float));
    
    V2f minVec = {};
    
    if(max_dp1 > min_dp2 &&
       min_dp1 < max_dp2 &&
       max_dp3 > min_dp4 &&
       min_dp3 < max_dp4)
    {
        result.collision = true;
  
    }
    else
    {
        result.collision = false;

    }
    
    return result;
    
}
18 posts
SAT Collision detection and response
1 week, 2 days ago
Note: I hesitated to reply to this because its been quite a while since I implemented SAT (or any collision detection/response/physics for that matter) so take this with your favourite amount of salt, its basically an educated guess based on what I remember and can reason out. I happily defer to anybody who is more confident on this topic. Hopefully this helps though :)

When using SAT you have a collection of axes that you're projecting your polygons onto and checking if there are any on which they don't overlap. If they overlap on all axes then the polygons themselves overlap. However as part of this calculation, you already compute (or can easily compute) the *distance* by which they overlap on each axis. The axis with the lowest such distance is the one in which the polygons are conceptually "the closest to being separated".

If you move the polygons apart on that axis then you will have an axis along which they are now separated and therefore can be sure that you have resolved the collision! As to whether this is the *minimum* translation to separate them, I suspect so based on the hand-waving line of reasoning that if you followed this procedure for any axis you could always separate the polygons by moving them some distance but since we picked the axis along which the polygons overlap the least, we know that the distance we need to move them is minimal among all the axes we're checking.

So now we have an axis and a distance to move in order to separate our polygons. You may want to just move one of them the full distance, you may want to move them both half the distance (but in opposite directions). It depends on the objects and the behaviour you're looking for. This is definitely not something I have researched/implemented myself but I believe you tend to run into problems with this sort of thing when you have two or more pairs of objects you're checking for collisions between, where in resolving one intersection you create another (imagine a ball moving into the corner where two walls meet, or getting squashed between two rectangles getting closer together). You'll need some more involved machinery to resolve that with any amount of reliability.

Also note that you're only checking two axes, which is sufficient only if your objects are all axis-aligned rectangles. If you ever rotate anything you'll need to check the other 2 normals as well. :)
66 posts
SAT Collision detection and response
1 week, 1 day ago
Thanks, nice to "hear" your voice on this!