Hi, yet another question on SAT (sorry!).

What are some robust approaches to swept SAT collision detection in 3D. I have implemented the algorithm for this thanks to the help from many articles on this website, however, none of these articles address the problem of making the collision detection numerically robust.

While my current implmentation is able to successfully detect swept collisions, often the objects will interpenetrate thanks to floating point errors, thus causing the objects to become stuck. How can these floating point errors be adrressed?

Furthermore, none of the articles address the problem of collision resolution, for example, calculating the collision normal vector for a swept test so that objects can be slided along one another. How can my algorithm be modified such that this value can be returned?

This seems like a fairly common thing to want to do, why can I find no information for this on the internet, most articles I find consider non swept cases but my particular scenario requires continuous collision detection so this is not an option for me.

This has massively stumped me for weeks now, so any help is genuinely massively appreciated.

I will include the code for my swept intersection testing function below.

function testAxes(corners1, corners2, axes, velocity)
    local tFirst = 0
    local tLast = 100000
    local T
    local bestAxis
    for i, axis in pairs(axes) do
        if axis.Magnitude ~= 0 and tostring(axis) ~= "NAN, NAN, NAN" then
            local adists, bdists = {}, {};
            for i = 1, 8 do
                table.insert(adists, corners1[i]:Dot(axis));
                table.insert(bdists, corners2[i]:Dot(axis));
            end;
            local max0, min0 = math.max(unpack(adists)), math.min(unpack(adists));
            local max1, min1 = math.max(unpack(bdists)), math.min(unpack(bdists));

            local speed = axis:Dot(velocity)

            if max1 < min0 then
                if speed <= 0 then
                    return false, tFirst, tLast
                end
                T = (min0 - max1)/speed; 
                if T > tFirst then 
                    tFirst = T
                    bestAxis = axis
                end
                if tFirst > 1 then 
                    return false, tFirst, tLast
                end
                T = (max0 - min1) / speed; 
                if T < tLast then 
                    tLast = T
                end
                if tFirst > tLast then 
                    return false, tFirst, tLast
                end
            elseif max0 < min1 then
                if speed >= 0 then
                    return false, tFirst, tLast
                end
                T = (max0 - min1)/speed; 
                if T > tFirst then 
                    tFirst = T
                    bestAxis = -axis
                end
                if tFirst > 1 then 
                    return false, tFirst, tLast 
                end
                T = (min0 - max1) / speed;
                if T < tLast then 
                    tLast = T
                end
                if tFirst > tLast then 
                    return false, tFirst, tLast
                end
            else -- overlapping
                if speed > 0 then
                    T = (max0-min1)/speed; 
                    if T < tLast then tLast = T end
                    if tFirst > tLast then 
                        return false, tFirst, tLast
                    end
                elseif speed < 0 then
                    T = (min0 - max1)/speed; 
                    if T < tLast then tLast = T end
                    if tFirst > tLast then 
                        return false, tFirst, tLast
                    end
                end
            end
        end
    end
    return true, tFirst, tLast, bestAxis
end;

Hm, not sure I can give a good answer. Hopefully someone else can chime in. But I have implemented my own version of SAT in 3D in c++.

From the implementations I've seen, SAT returns a “minimum translation vector” (MTV), which gets your object out of collision. It is one of the axes that the algorithm projects to – in fact it is the axiss with the smallest overlap of the projections of the two objects. It is a vector pointing in the direction to get out of collision. If you have a moving object and a stationary object, and your detect collision, if you do `movObj.position += MTV` in theory you get out of the collision. But like you pointed out, due to floating point issues you can get stuck even with this vector. So what I did is something like `moveObj.position += MTV * 1.01f` which gives it a slight nudge past the imprecision of float.s How big that multiplier should be is just a guess, you can probably test a few values to find a good one (binary-search-like)(1,01 → 1.005 → 1.075 → etc)

Anyways this isn't really a great answer to your question but may help you figure out something that works? It isn't swept specific as that isn't necessarily how I implemented it.

my implementations: not optimized as I coded up the theory:
.h https://github.com/mattstone22133/Learning-OpenGL-CoreProfile/blob/master/LearningOpenGL_CoreProfile/LearningOpenGL_CoreProfile/new_src/Algorithms/SeparatingAxisTheorem/SATComponent.h
.cpp https://github.com/mattstone22133/Learning-OpenGL-CoreProfile/blob/master/LearningOpenGL_CoreProfile/LearningOpenGL_CoreProfile/new_src/Algorithms/SeparatingAxisTheorem/SATComponent.cpp

In the .cpp, if you look at Shape::CollisionTest you can see my implementation of a moving and stationary object. The 3rd parameter to the function is an “out” param, it is a MTV.

my unit tests I created using that above code, sliding worked for me:
https://imgur.com/a/c2KVdoJ

@mattstone2728 First, thank you so much for taking the time to write a reply. However, the algorithm above relates to a discrete test rather than a swept collision test and as such is not applicable for me. Unfortunately I need to my collision detection to be continuous.

No idea what you're doing, but floating point rounding errors are fundamental. They are caused by having only a finite number of bits to represent an infinite number of values. As a result, any floating point calculation is an approximation, since in most cases, the real exact answer cannot be represented in the number of available bits of a floating point number.

EDIT: It is like ⅓ written as decimal floating point number 0.33333.. . No matter how many “3” digits you write you never have enough to represent the true exact value, but at some point you run out of paper, and you thus have to live with an approximated value rather than the true value.

@Alberth Yep indeed, thanks for the response. I was hoping for an answer targeted to approaches that can mitigate the negative effect of these errors in relation to the swept SAT collision test with minimal loss in precision of the collision detction. I'm not really sure what the best approach to deal with these floating point errors is in context to this problem.

Just curious, but do you have a go-to resource for “swept SAT” so I can reason about how it is different from discrete. For my tests I do a few collision passes over all my objects using discrete test for each pair. Everything I've done is assigned to cells so there's only every a few pairs at a time.

@mattstone2728 Sure, so the best resource I've found that explains it well is this document (page 6).

The accepted answer on this post also has good information.

There's also a few posts on this website that can be found by searching ‘swept SAT’ (although the links above are most helpful).

The swept test determines the time of collision of an object moving along some velocity vector. This is useful because it stops tunnelling, so makes it impossible for a collision to be missed like it could be in the discrete test if an object were moving very fast. Basically, you move the object each time by (tFirst*velocity) where tFirst is the first time of intersection, bringing the object right up to the point of collision. However, floating point errors on tFirst mean that the object could slightly interpenetrate causing it to get stuck.

If you want CCD and computing intermediate positions where objects touch and slide, you should probably aim to make both slight interpenetration and slight loss of contact due to floating point imprecisions harmless: unless you constrain object shapes and movement directions, exact contact between two objects happens with probability zero and is an annoying special-case.

Can you explain why interpenetration is a problem?

Looking at your code, it seems you are processing arbitrary axes instead of the direction of the relative velocity of the objects plus two perpendicular directions: it's correct for axis-aligned boxes, which touch on planes that are perpendicular to an axis, but not for generic convex bodies.

Even for axis-aligned boxes, there's no interesting displacement direction to compute: the object is moving with its velocity until it collides, so it should simply move by velocity * some appropriate time interval, and then start to bounce or slide.

You are computing the only axis that determines collision time, not the best one; with edge on edge or vertex on vertex collisions there can be more axes that give the same collision time, but they are redundant.

@LorenzoGatti Okay, thank you for the response. If it's ok with you, I'd like to show you my working out for the code above so you can perhaps point a problem in my method and I can explain better what the intended behaviour of the code is. As far as I can tell I think my code is working for any convex object, I can say from testing that it looks like it's working? The below example runs through the working out for two oriented rectanges A and B in 2D space.

Is the above method not what my program is doing, I essentially loop through each `axis` in `axes` and calculate tFirst? I actually only need this to work for 3D OBBs, so in my case the `axes` variable contains the 15 possible separating axes.

Anyhow, you mentioned that I should modify the program such that interpenentration is ‘harmless’. The reason why it is a problem in my current implementation is because if the projections overlap then the minimum time returned will always be 0 meaning that the object will become stuck (since we advance the object by velocity*tFirst). Maybe you can further advise on how to make interpenetration harmless?

Hopefully this explains better the problem I have, thank you for your help so far.

Your 2D diagram is a good starting point for demonstrating some incorrect separation logic. As drawn, objects A and B don't intersect because they are separated along the shown axis, even if they overlap on the perpendicular axis (the bottom vertex of B is below the top vertices of A).

Now imagine B further right, with the rightmost vertex slightly right of min0: A and B now overlap on both axes, but they still do not intersect; B can still go a little right and/or down before its bottom right edge collides with the top left vertex of A.

The two objects would definitely intersect if their projections overlapped on all axes and B were an axis aligned box like A.

In practice, an algorithm that reports some false collisions cheaply can be a useful broad-phase first pass even if not suitable for CCD; there are exact and more expensive options for the small set of potentially colliding objects pairs.