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;

@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.

@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.

@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.