Hi, curious reader. Today I want to initiate you to secrets of collision detection in games. I'll tell how to predict time of impact (TOI) of two objects. One way to easily do it – is to use swept Separating Axis Theorem (swept SAT or continuous SAT).
First of all I want to talk about notations in this article.
Vector I'll write as small bold latin letter (for example, a). Objects I'll write as big latin letters (like A or B). Scalars – like everywhere )).
Also I assume that you know what is normal, how to normalize vector and what is dot product is.
Ok, continue. You may ask, why we need to know TOI at all!? The best way to understand – is to imagine bullet that flies through paper.
As you can see – collision can be skipped easily, and this is not good.
I'll notice that if your game not operates such big velocities then you can use usual discrete SAT. This method can detect penetration of objects into each other and can push that objects back till they not touching. I won't accent on that method. The best resource I know – it's famous tutorialA. But I'll put my five cents about it then I'll discuss swept SAT.
Actually, what that SAT is? I'll tell how I see it. It's simple enough – if you can find such axis that projections of two objects on that axis doesn't overlap than this objects not intersects.
Here you can see that number of such axes can be infinite. And axes a and b is good for us and axis c not – here projections overlaps. So which axis should we choose? We choose axis that perpendicular to object's edge – it's axis a on the picture. Smart reader surely notes that for SAT method both objects should be convex, i.e. angle between neighboring edges should be lower than 180 degrees.
For example, here we can see that objects does not intersects but despite axis I took projection will overlap.
Ok, now we should understand how to arrange object data to use it efficiently.
Here you can see that I declare vertices from object center clockwise.
Now we hold almost everything to start a party! But before a couple more variables. Knowing object's center positions we get distance d between them – it's just difference between object's positions. Remember this value – we'll need it later. Next, we need remove one velocity – object B velocity. We'll get velocity of object A relative to B. This velocity vr is difference between va and vb.
And now the algorithm.
Now I'll take a survey on each item and show it on example.
1-st and 2-nd item is simple – just look at the picture.
3-rd and 4-th items we'll examine in detail. Projection – is just dot product. So we need to project to normal each vertex of each object. And on the way we should keep min and max value for each object. This four values (minA, maxA, minB, maxB) – is objects projections. To find correct projection points of object B relative to object A we need also project distance d between objects and add this value to minB and maxB.
No we should find distances between closest and farthest projections points. There's small nuance – if normal n and distance d look in one direction, than distance between closest projections points is E = minB – maxA. And distance between farthest projections points – is L = maxB – minA.
But if we'll reverse normal than we’ll see that E = minA – maxB, L = maxA – minB. But it's more suitable to store this values as E = maxB – minA, L = minB – maxA (later I'll divide them on velocity projection this will help to get correct values).
So, we should take into account normal direction and change it or later interchange values tEnter and tLeave (I took latter approach).
Item 5. Having distance and speed we can find a time which object will spend to pass that distance. As you remember from school physics t = s / v. So tEnter = E / v – it's time when projections will meet and tLeave = L / v – it's time when projections will leave. Remember that tEnter shold be always smaller than tLeave. And if you get wrong (when normal looks in another way – see above) you should interchange values.
Item 6. Having a bunch of tEnter and tLeave we should take greatest of tEnter and the least of tLeave. That makes sense if you look on the picture.
As you can see – tEnter that we get when project on blue normal is smaller than tEnter that we get when project on red normal (you can print picture and measure with ruler distances between projections and velocity projection and divide them - I specially carry out projections in lower right corner :-)). But it's clearly seen that square and triangle will meet exactly on red side – that when tEnter greater.
Curious reader may ask – why we need tLeave at all??? Firstly, it can be useful for animation (for example when bullet hits the wall and you need to show dust from walls other side). Secondly, if on any axis you get that tEnter is greater that tLeave then that means that there's no collision at all and you can break loop (I'm really tired to draw pictures – do it yourself if you don't believe :-)).
Now let's investigate a couple of examples for better understanding. Here's a picture.
And here's values we got:
Iterate over axis of red object (A – red object, B – blue object, position of A is (300, 300), position of B is (450, 250)).
Now iterate over axes of blue object (and change objects hierarchy - now A is blue object and B - red).
So we got max tEnter = 0.51 and min tLeave = 2.38.
One more example (objects and positions the same - only velocities changed).
Here we can see that intervals not overlaps - on second iteration we got that max tEnter is greater that min tLeave. This means that where will no collision.
Almost done. Now one more picture for better understanding.
Black lines - it's projection axes. Red lines - it's intervals from tEnter to tLeave. If we take all this intervals and look at the - we should see - values we're triying to find it's overlapping interval of all red lines (as you can see it's greatest of tEnter and the least of tLeave).
Here's small demo that demonstrates swept SAT - you can drag objects, you can rotate objects by dragging blue squares, you can change velocities by dragging green squares.
That's all.
First of all I want to talk about notations in this article.
Vector I'll write as small bold latin letter (for example, a). Objects I'll write as big latin letters (like A or B). Scalars – like everywhere )).
Also I assume that you know what is normal, how to normalize vector and what is dot product is.
Ok, continue. You may ask, why we need to know TOI at all!? The best way to understand – is to imagine bullet that flies through paper.
As you can see – collision can be skipped easily, and this is not good.
I'll notice that if your game not operates such big velocities then you can use usual discrete SAT. This method can detect penetration of objects into each other and can push that objects back till they not touching. I won't accent on that method. The best resource I know – it's famous tutorialA. But I'll put my five cents about it then I'll discuss swept SAT.
Actually, what that SAT is? I'll tell how I see it. It's simple enough – if you can find such axis that projections of two objects on that axis doesn't overlap than this objects not intersects.
Here you can see that number of such axes can be infinite. And axes a and b is good for us and axis c not – here projections overlaps. So which axis should we choose? We choose axis that perpendicular to object's edge – it's axis a on the picture. Smart reader surely notes that for SAT method both objects should be convex, i.e. angle between neighboring edges should be lower than 180 degrees.
For example, here we can see that objects does not intersects but despite axis I took projection will overlap.
Ok, now we should understand how to arrange object data to use it efficiently.
Here you can see that I declare vertices from object center clockwise.
Now we hold almost everything to start a party! But before a couple more variables. Knowing object's center positions we get distance d between them – it's just difference between object's positions. Remember this value – we'll need it later. Next, we need remove one velocity – object B velocity. We'll get velocity of object A relative to B. This velocity vr is difference between va and vb.
And now the algorithm.
- Get object's edge.
- Build normal for that edge.
- Project distance and velocity on that normal. Also project vertices and find projections of both objects.
- Find closest and farthest coordinates on projection and get distances between that coordinates.
- Divide that distances on velocity projection. And get tEnter – time when objects will meet and tLeave – time when objects will diverge.
- Do 1-5 item for every edge of every object. Having bunch tEnter and tLeave we need to take maximum of tEnter and minimum of tLeave. This values is what we search for.
Note: for swept SAT it's not necessary to normalize normal. But I'll do it in examples to operate small values.
Now I'll take a survey on each item and show it on example.
1-st and 2-nd item is simple – just look at the picture.
3-rd and 4-th items we'll examine in detail. Projection – is just dot product. So we need to project to normal each vertex of each object. And on the way we should keep min and max value for each object. This four values (minA, maxA, minB, maxB) – is objects projections. To find correct projection points of object B relative to object A we need also project distance d between objects and add this value to minB and maxB.
Note: for usual discrete SAT this four values is enough – if minB is greater than maxA at least on one axis – that objects surely not intersects. But if on every axis minB smaller than maxA – than we keep axis with minimum projection overlapping. This axis is collision normal and this overlapped interval – is distance by which we should move objects apart (along normal) to prevent intersection.
No we should find distances between closest and farthest projections points. There's small nuance – if normal n and distance d look in one direction, than distance between closest projections points is E = minB – maxA. And distance between farthest projections points – is L = maxB – minA.
But if we'll reverse normal than we’ll see that E = minA – maxB, L = maxA – minB. But it's more suitable to store this values as E = maxB – minA, L = minB – maxA (later I'll divide them on velocity projection this will help to get correct values).
So, we should take into account normal direction and change it or later interchange values tEnter and tLeave (I took latter approach).
Item 5. Having distance and speed we can find a time which object will spend to pass that distance. As you remember from school physics t = s / v. So tEnter = E / v – it's time when projections will meet and tLeave = L / v – it's time when projections will leave. Remember that tEnter shold be always smaller than tLeave. And if you get wrong (when normal looks in another way – see above) you should interchange values.
Note: tEnter and tLeave can be less than 0 or greater than 1. First case means that projections already met on moment of check. Second case means that projections won't meet in that frame.
Item 6. Having a bunch of tEnter and tLeave we should take greatest of tEnter and the least of tLeave. That makes sense if you look on the picture.
As you can see – tEnter that we get when project on blue normal is smaller than tEnter that we get when project on red normal (you can print picture and measure with ruler distances between projections and velocity projection and divide them - I specially carry out projections in lower right corner :-)). But it's clearly seen that square and triangle will meet exactly on red side – that when tEnter greater.
Curious reader may ask – why we need tLeave at all??? Firstly, it can be useful for animation (for example when bullet hits the wall and you need to show dust from walls other side). Secondly, if on any axis you get that tEnter is greater that tLeave then that means that there's no collision at all and you can break loop (I'm really tired to draw pictures – do it yourself if you don't believe :-)).
Now let's investigate a couple of examples for better understanding. Here's a picture.
Iterate over axis of red object (A – red object, B – blue object, position of A is (300, 300), position of B is (450, 250)).
normal: x: -0.86, y: -0.51
minA: -72.03 , maxA: 30.9 , minB: -154.35 , maxB: -37.73, velocity projection: -73.74
minB - maxA: -185.22 , maxB - minA: 34.3
tEnter: 2.51 , tLeave: -0.47 (tEnter should be smaller than tLeave, so interchange them)
tEnter: -0.47 , tLeave: 2.51
**************
normal: x: 0.86, y: -0.51
minA: -72.03 , maxA: 30.9 , minB: 89.18 , maxB: 205.8, velocity projection: 114.9
minB - maxA: 58.31 , maxB - minA: 277.83
tEnter: 0.51 , tLeave: 2.42
**************
normal: x: 0, y: 1
minA: -60 , maxA: 40 , minB: -110 , maxB: 10, velocity projection: -40
minB - maxA: -150 , maxB - minA: 70
tEnter: 3.75 , tLeave: -1.75 (tEnter should be smaller than tLeave, so interchange them)
tEnter: -1.75 , tLeave: 3.75
Now iterate over axes of blue object (and change objects hierarchy - now A is blue object and B - red).
normal: x: -1, y: 0
minA: -60 , maxA: 40 , minB: 90 , maxB: 210
minB - maxA: 50 , maxB - minA: 270
velocity projection: 110
tEnter: 0.45 , tLeave: 2.45
**************
normal: x: 0.51, y: -0.86
minA: -72.03, maxA: 30.87 , minB: -185.22 , maxB: -68.6, velocity projection: -90.89
minB - maxA: -216.09 , maxB - minA: 3.43
tEnter: 2.38 , t1: -0.04 (tEnter should be smaller than tLeave, so interchange them)
tEnter: -0.04 , tLeave: 2.38
**************
normal: x: 0.51, y: 0.86
minA: -72.03, maxA: 30.87 , minB: -85.75 , maxB: 30.87, velocity projection: -22.29
minB - maxA: -116.62 , maxB - minA: 102.9
tEnter: 5.23 , tLeave: -4.62 (tEnter should be smaller than tLeave, so interchange them)
tEnter: -4.62 , tLeave: 5.23
So we got max tEnter = 0.51 and min tLeave = 2.38.
One more example (objects and positions the same - only velocities changed).
normal: x: -0.86, y: -0.51
minA: -72.03, maxA: 30.87 , minB: -154.35 , maxB: -37.73, velocity projection: -42.87
minB - maxA: -185.22 , maxB - minA: 34.3
tEnter: 4.32 , tLeave: -0.8 (tEnter should be smaller than tLeave, so interchange them)
tEnter: -0.8 , tLeave: 4.32
**************
normal: x: 0.86, y: -0.51
minA: -72.03 , maxA: 30.87 , minB: 89.18 , maxB: 205.8, velocity projection: -8.57
minB - maxA: 58.31 , maxB - minA: 277.83
tEnter: -6.8 , tLeave: -32.4 (tEnter should be smaller than tLeave, so interchange them)
tEnter: -32.4 , tLeave: -6.8
Here we can see that intervals not overlaps - on second iteration we got that max tEnter is greater that min tLeave. This means that where will no collision.
Almost done. Now one more picture for better understanding.
Black lines - it's projection axes. Red lines - it's intervals from tEnter to tLeave. If we take all this intervals and look at the - we should see - values we're triying to find it's overlapping interval of all red lines (as you can see it's greatest of tEnter and the least of tLeave).
Here's small demo that demonstrates swept SAT - you can drag objects, you can rotate objects by dragging blue squares, you can change velocities by dragging green squares.
That's all.
Комментариев нет:
Отправить комментарий