This was meant to be published before the RNG one, but apparently UA-cam orders videos by when they were first made public rather than when they were first uploaded. Sorry for the duplicate notifications!
1:43 and 3:39 : Correction : AABB is frequently used for non-rectangles, and for rotated rectangles. The idea is to wrap each polygon -- regardless of what it is or how it is rotated -- with a rectangle suitable for this kind of check. It's an optimization over the naive approach of using each polygon's natural/real boundaries, because it's very fast to determine this wrapping -- this "axis-aligned bounding box". Additionally, as such, it can an is used as a "middle" phase -- it's not necessarily something one uses instead of SAT, but can be used alongside SAT as a quick check after the broad phase and before SAT, since SAT is so heavy. Some sources even classify AABB as a broad phase technique. I hope this info helps you and your viewers.
Sorry it took me so long to respond! I guess when I said AABB only worked on non-rotated rectangles, I meant that the hitboxes _themselves_ had to match these criteria, but it can still be used on non-rectangles or rotated objects. I added this to the description as a clarification, since I probably should've done a better job of communicating it. Regardless, the bit about AABB being narrow phase was incorrect, so I added that to the description as a correction. If anything else is wrong, feel free to let me know. Thanks for your help :)
That’s useful! Thinking about writing my own simple physics engine instead of using box2d and was wondering about the best approach on detecting collisions 3 phases like this would work perfect 🙂
Re: SAT I don't get the "parallel" and "angle" part. The last time I implemented SAT, I had to get the edge normal(the axis), project each vertex to the normal to get the min and max edges then test that with the other polygon whether both min-max overlap. If there is a separating axis, get out of the test early since only one separating axis is needed to determin if they are not colliding.
This is very interesting, but there is a question of how to predict the collision, since in a lot of cases finding out that the objects overlap is too late, because you might never want them to intersect at any point in time. Does that mean you have to run the check at every frame??? It is one thing to calculate detection in a static frame and I guess a whole different beast, to calculate this dynamically with thousands of objects moving on the screen.... :D
maybe it isn't what you aim to do, but I absolutely LOVE videos like this but that get into every detail in it's implemetantion, 3blue1brown does that but in math and some other channels do that but in computer sience, I hoped this video would provide me that but sadly is just an overview I wanted to say this so you know that there is, at least, someone that would want that
does anyone know how to implement section 4 I’ve been trying to find out how but I can’t find any sources, and when I tried implementing it myself it worked but had problems, please 😭😭💀
For SAT you want to determine all the vertices of the polygons that you want to collide (assuming you’re doing polygon v polygon collisions). You then need to get the “separation axes” of the polygons. To get the separation axis you need to take all the edges of the polygons and get the normal of them. Getting the edges is just taking two of the vertices and subtracting their positions. for example we have a triangle made up of 3 vertices. We then loop through all the vertices and in the loop we take the vertices[index] and vertices[index mod len(vertices)] and subtract them. We then need to normalize those edges. The edges tell use the direction of the edges from the start to the end. We need to get the direction facing away from the edge. (Ex: we have a vertical wall like | and the direction facing away is
Here is some code written in lua that uses SAT to determine if two convex polygons are colliding: function polygonVPolygon(p1, p2) --Separating Axis Theorem here --get the axes local axes = {} --list of axes for i=1, #p1 do local edge = vectorSubtr(p1[i], p1[i%#p1 + 1]) --note that in lua the first index in a list is 1. In languages like python you would do (i + 1)%len(p1) axes[#axes + 1] = vectorNormal(edge) end for i=2, #p2 do local edge = vectorSubtr(p2[i], p2[i%#p2 + 1]) axes[#axes + 1] = vectorNormal(edge) end --We have all the axes. We now need to project the polygons local function projectPolygon(vertices, axis) local max = vectorDot(vertices[1], axis) local min = max for i=2, #vertices do local vertex = vertices[i] local projectedOntoAxis = vectorDot(vertex, axis) if projectedOntoAxis > max then max = projectedOntoAxis end if projectedOntoAxis < min then min = projectedOntoAxis end end return max, min end for _, axis in pairs(axes) do local p1max, p1min = projectPolygon(p1, axis) local p2max, p2min = projectPolygon(p2, axis) if p1min > p2max or p2min > p1max then --not colliding return false end end return true end --vector functions function vectorAdd(v1, v2) return {v1[1] + v2[1], v1[2] + v2[2]} end function vectorSubtr(v1, v2) return {v1[1] - v2[1], v1[2] - v2[2]} end function vectorMult(v, s) return {v[1] * s, v[2] * s} end function vectorNormal(v) local len = length(v) return {-v[2]/len, v[1]/len} end function vectorDot(v1, v2) return v1[1] * v2[1] + v1[2] * v2[2] end function length(v) return math.sqrt(v[1]^2 + v[2]^2) end Keep in mind that this code assumes that polygons are made up of a list of vertices list this {{x, y}, {x,y}, {x,y}}
I personally used GameMaker as a language to start with, but you unfortunately can't get a free license for it anymore. I would then say Python (+ the Pygame library) is a good way to start nowadays :)
While SAT is fast, it is still inefficient to run it all the time. Many modern physics engine use both, drawing an AABB and if those collide, using SAT to check if they are actually colliding.
This was meant to be published before the RNG one, but apparently UA-cam orders videos by when they were first made public rather than when they were first uploaded. Sorry for the duplicate notifications!
1:43 and 3:39 : Correction : AABB is frequently used for non-rectangles, and for rotated rectangles. The idea is to wrap each polygon -- regardless of what it is or how it is rotated -- with a rectangle suitable for this kind of check. It's an optimization over the naive approach of using each polygon's natural/real boundaries, because it's very fast to determine this wrapping -- this "axis-aligned bounding box". Additionally, as such, it can an is used as a "middle" phase -- it's not necessarily something one uses instead of SAT, but can be used alongside SAT as a quick check after the broad phase and before SAT, since SAT is so heavy. Some sources even classify AABB as a broad phase technique. I hope this info helps you and your viewers.
Sorry it took me so long to respond!
I guess when I said AABB only worked on non-rotated rectangles, I meant that the hitboxes _themselves_ had to match these criteria, but it can still be used on non-rectangles or rotated objects. I added this to the description as a clarification, since I probably should've done a better job of communicating it. Regardless, the bit about AABB being narrow phase was incorrect, so I added that to the description as a correction. If anything else is wrong, feel free to let me know. Thanks for your help :)
That’s useful!
Thinking about writing my own simple physics engine instead of using box2d and was wondering about the best approach on detecting collisions
3 phases like this would work perfect 🙂
This video is so high quality and informative. It's a shame it has so few likes and views.
You're animations and explanations are really well done, thanks for making this video.
This is an incredible video, everything from the animation to the explanation! You deserve so much more attention. 🎉
your humble disclaimer made me subscribe you even before starting the video
Ive seen one of your videos from a long time ago, amd you have improved alot
Re: SAT
I don't get the "parallel" and "angle" part.
The last time I implemented SAT, I had to get the edge normal(the axis), project each vertex to the normal to get the min and max edges then test that with the other polygon whether both min-max overlap.
If there is a separating axis, get out of the test early since only one separating axis is needed to determin if they are not colliding.
This is very interesting, but there is a question of how to predict the collision, since in a lot of cases finding out that the objects overlap is too late, because you might never want them to intersect at any point in time. Does that mean you have to run the check at every frame??? It is one thing to calculate detection in a static frame and I guess a whole different beast, to calculate this dynamically with thousands of objects moving on the screen.... :D
Great and informative video! I loved it
i feel cool rn, i called it in the previous video comments
maybe it isn't what you aim to do, but I absolutely LOVE videos like this but that get into every detail in it's implemetantion, 3blue1brown does that but in math and some other channels do that but in computer sience, I hoped this video would provide me that but sadly is just an overview
I wanted to say this so you know that there is, at least, someone that would want that
"however, i'm an idiot" i let out a chuckle, maybe two :)
4:07 when Marco Pixle goes 3D
R tX on!
THANK YOU DUDE
Bro’s becoming RGME
how do i know what is the point where i have to apply the impulse though?
does anyone know how to implement section 4 I’ve been trying to find out how but I can’t find any sources, and when I tried implementing it myself it worked but had problems, please 😭😭💀
For SAT you want to determine all the vertices of the polygons that you want to collide (assuming you’re doing polygon v polygon collisions). You then need to get the “separation axes” of the polygons. To get the separation axis you need to take all the edges of the polygons and get the normal of them. Getting the edges is just taking two of the vertices and subtracting their positions.
for example we have a triangle made up of 3 vertices. We then loop through all the vertices and in the loop we take the vertices[index] and vertices[index mod len(vertices)] and subtract them.
We then need to normalize those edges. The edges tell use the direction of the edges from the start to the end. We need to get the direction facing away from the edge. (Ex: we have a vertical wall like | and the direction facing away is
Here is some code written in lua that uses SAT to determine if two convex polygons are colliding:
function polygonVPolygon(p1, p2) --Separating Axis Theorem here
--get the axes
local axes = {} --list of axes
for i=1, #p1 do
local edge = vectorSubtr(p1[i], p1[i%#p1 + 1])
--note that in lua the first index in a list is 1. In languages like python you would do (i + 1)%len(p1)
axes[#axes + 1] = vectorNormal(edge)
end
for i=2, #p2 do
local edge = vectorSubtr(p2[i], p2[i%#p2 + 1])
axes[#axes + 1] = vectorNormal(edge)
end
--We have all the axes. We now need to project the polygons
local function projectPolygon(vertices, axis)
local max = vectorDot(vertices[1], axis)
local min = max
for i=2, #vertices do
local vertex = vertices[i]
local projectedOntoAxis = vectorDot(vertex, axis)
if projectedOntoAxis > max then
max = projectedOntoAxis
end
if projectedOntoAxis < min then
min = projectedOntoAxis
end
end
return max, min
end
for _, axis in pairs(axes) do
local p1max, p1min = projectPolygon(p1, axis)
local p2max, p2min = projectPolygon(p2, axis)
if p1min > p2max or p2min > p1max then --not colliding
return false
end
end
return true
end
--vector functions
function vectorAdd(v1, v2)
return {v1[1] + v2[1], v1[2] + v2[2]}
end
function vectorSubtr(v1, v2)
return {v1[1] - v2[1], v1[2] - v2[2]}
end
function vectorMult(v, s)
return {v[1] * s, v[2] * s}
end
function vectorNormal(v)
local len = length(v)
return {-v[2]/len, v[1]/len}
end
function vectorDot(v1, v2)
return v1[1] * v2[1] + v1[2] * v2[2]
end
function length(v)
return math.sqrt(v[1]^2 + v[2]^2)
end
Keep in mind that this code assumes that polygons are made up of a list of vertices list this {{x, y}, {x,y}, {x,y}}
I wonder which language is good for this when you want to start
I personally used GameMaker as a language to start with, but you unfortunately can't get a free license for it anymore. I would then say Python (+ the Pygame library) is a good way to start nowadays :)
Use english this is america
how do u make ur animations?
But how much more heavy it is to use the movable axis one?, i know that aabb is fast, but how faster is it compared to the second one?
While SAT is fast, it is still inefficient to run it all the time. Many modern physics engine use both, drawing an AABB and if those collide, using SAT to check if they are actually colliding.
@@aidenshi5178 so switching dynamically is more efficient that only having SAT? Huh, interesting.
@@Cyberlong Basically you use a faster, but less accurate method (AABB) do see if they might collide, and then you run a more accurate test (SAT)
@@aidenshi5178 ohh, i get it now, thanks!
No problem :)
The HEX
e
true...
im not early but im 11th
hi
hummm
those aren't parallel!