a super fast AABB collision detection ( Minkowski Sums )

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
D0NM
Party member
Posts: 245
Joined: Mon Feb 08, 2016 10:35 am
Location: Zabuyaki
Contact:

a super fast AABB collision detection ( Minkowski Sums )

Post by D0NM » Wed Sep 18, 2019 10:56 am

Yo! Has anyone tried to implement this to resolve collisions yet?
I found a rather nice & fast algorithm Minkowski Sums . It has been used in RiverCityRansomUnderground game.

I translated it into Lua. Now testing
Upd: I've hecked up the vectors stuff.... :halloween:

Code: Select all

function MinkowskiCheckCollision(ax, ay, aw, ah, bx, by, bw, bh)
    local mt = ay - by - bh
    local mb = ay + ah - by
    local ml = ax - bx - bw
    local mr = ax + aw - bx
    local px, py = 0, 0
    if (mr >= 0 and ml <= 0 and mt >= 0 and mb <= 0) then
        local min = -100000
        if (math.abs(ml) < min) then
            min = math.abs(ml)
            --penetration = glm(ml, 0)
            px = ml
        end
        if (math.abs(mr) < min) then
            min = math.abs(mr)
            --penetration = glm(mr, 0)
            px = mr
        end
        if (math.abs(mt) < min) then
            min = math.abs(mt)
            --penetration = glm(0, mt)
            py = mt
        end
        if (math.abs(mb) < min) then
            min = math.abs(mb)
            --penetration = glm(0, mb)
            py = mb
        end

        return true, px, py
    end
    return false, px, py
end


http://spaderthomas.com/post/2018/08/25/minkowski/

Image

(there is a source code as well https://blog.hamaluik.ca/posts/simple-a ... ifference/ )

I'm migrating from the Bump and HC collision detection libs. (they are a bottle neck in my project. they take ~40% of CPU)
So this stuff might be a bingo. :joker:

----
Off-topic: Also found Differ - A Separating Axis Theorom collision library for haxe
https://github.com/snowkit/differ
Last edited by D0NM on Wed Sep 18, 2019 11:55 am, edited 2 times in total.
Our LÖVE Gamedev blog Zabuyaki (an open source retro beat 'em up game). Twitter: @Zabuyaki.
:joker: LÖVE & Lua Video Lessons in Russian / Видео уроки по LÖVE и Lua :joker:

User avatar
raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

Re: a super fast AABB collision detection ( Minkowski Sums )

Post by raidho36 » Wed Sep 18, 2019 11:25 am

Seems like a roundabout way to do regular AABB collision testing. Instead of testing coordinates against each other directly, it computes differential between coordinates and tests all of them against zero.

User avatar
D0NM
Party member
Posts: 245
Joined: Mon Feb 08, 2016 10:35 am
Location: Zabuyaki
Contact:

Re: a super fast AABB collision detection ( Minkowski Sums )

Post by D0NM » Wed Sep 18, 2019 11:47 am

raidho36 wrote:
Wed Sep 18, 2019 11:25 am
Seems like a roundabout way to do regular AABB collision testing. Instead of testing coordinates against each other directly, it computes differential between coordinates and tests all of them against zero.
the pros is it returns the PENETRATION vector (like HC Collider does).
It helps u resolving a collision with 1 line of code.
Our LÖVE Gamedev blog Zabuyaki (an open source retro beat 'em up game). Twitter: @Zabuyaki.
:joker: LÖVE & Lua Video Lessons in Russian / Видео уроки по LÖVE и Lua :joker:

User avatar
pgimeno
Party member
Posts: 2484
Joined: Sun Oct 18, 2015 2:58 pm

Re: a super fast AABB collision detection ( Minkowski Sums )

Post by pgimeno » Wed Sep 18, 2019 1:07 pm

Bump uses the closely related Minkowski difference method, both to detect and to resolve collisions.

User avatar
D0NM
Party member
Posts: 245
Joined: Mon Feb 08, 2016 10:35 am
Location: Zabuyaki
Contact:

Re: a super fast AABB collision detection ( Minkowski Sums )

Post by D0NM » Wed Sep 18, 2019 3:07 pm

pgimeno wrote:
Wed Sep 18, 2019 1:07 pm
Bump uses the closely related Minkowski difference method, both to detect and to resolve collisions.
Yep. I used it. It was nice. Now I'm switching to my own simple functions.

I even recorded 3 long video lessons on how to use Bump. https://youtu.be/caK_BBMum0k
Our LÖVE Gamedev blog Zabuyaki (an open source retro beat 'em up game). Twitter: @Zabuyaki.
:joker: LÖVE & Lua Video Lessons in Russian / Видео уроки по LÖVE и Lua :joker:

User avatar
raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

Re: a super fast AABB collision detection ( Minkowski Sums )

Post by raidho36 » Wed Sep 18, 2019 9:21 pm

D0NM wrote:
Wed Sep 18, 2019 11:47 am
the pros is it returns the PENETRATION vector (like HC Collider does).
It helps u resolving a collision with 1 line of code.
It computes this vector in the same fashion as regular AABB collision routine would. As I said, it's the same old method but with 1 extra step.

User avatar
pgimeno
Party member
Posts: 2484
Joined: Sun Oct 18, 2015 2:58 pm

Re: a super fast AABB collision detection ( Minkowski Sums )

Post by pgimeno » Wed Sep 18, 2019 11:09 pm

The Minkowski difference reduces rectangle-rectangle interaction to point-rectangle interaction, which IMO is easier to process and reason through. It helps, for example, with swept collision checking, as you only have to check a line segment against each box, rather than a moving box.

User avatar
raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

Re: a super fast AABB collision detection ( Minkowski Sums )

Post by raidho36 » Wed Sep 18, 2019 11:51 pm

pgimeno wrote:
Wed Sep 18, 2019 11:09 pm
The Minkowski difference reduces rectangle-rectangle interaction to point-rectangle interaction, which IMO is easier to process and reason through. It helps, for example, with swept collision checking, as you only have to check a line segment against each box, rather than a moving box.
My point was that if you compare them line for line, it's basically the same code as plain old AABB implementations, with an additional operation slapped on top.

User avatar
ivan
Party member
Posts: 1703
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: a super fast AABB collision detection ( Minkowski Sums )

Post by ivan » Thu Sep 19, 2019 6:21 am

I'm migrating from the Bump and HC collision detection libs. (they are a bottle neck in my project. they take ~40% of CPU)
Physics and collisions are almost never a bottleneck in my games, 99% of the time it's love.draw or when I'm blatantly misusing another library.
So this stuff might be a bingo.
No offense but bump and HC are already very well optimized. Also, bump does sweeping collisions which is much more complicated.
As for separating two overlapping AABBs that's fairly easy and could be made faster than your example - as I show in the following tutorial:
https://2dengine.com/?p=collisions#Detection

Regarding Differ or the separating axis algorithm or SAT, that's used for general purpose non-axis aligned shapes.

Collision detection and response is a complicated topic and it takes a lot of work to make something better than the existing libs out there. :) That's why I use and recommend Box2D aka love.physics.

monolifed
Party member
Posts: 146
Joined: Sat Feb 06, 2016 9:42 pm

Re: a super fast AABB collision detection ( Minkowski Sums )

Post by monolifed » Thu Sep 19, 2019 10:45 am

Code: Select all

I come up with something smart but it is already implemented and optimized
:o

Post Reply

Who is online

Users browsing this forum: No registered users and 64 guests