## 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
D0NM
Party member
Posts: 245
Joined: Mon Feb 08, 2016 10:35 am
Contact:

### a super fast AABB collision detection ( Minkowski Sums )

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

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

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

----
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.
LÖVE & Lua Video Lessons in Russian / Видео уроки по LÖVE и Lua

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

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

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.

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

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

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.
LÖVE & Lua Video Lessons in Russian / Видео уроки по LÖVE и Lua

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

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

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

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

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

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
LÖVE & Lua Video Lessons in Russian / Видео уроки по LÖVE и Lua

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

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

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.

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

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

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.

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

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

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.

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

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

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 )

Code: Select all

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

### Who is online

Users browsing this forum: No registered users and 61 guests