Hey guys,
Around episode 50 Casey implements line segment intersection collisions for axis aligned rectangles.
His implementation consists of this TestWall function:
And this iteration loop which tests the four edges and updates the tMin variable when collisions are found:
Later on, on episodes 90 and 91 Casey implements rendering of rotated and scaled rectangles and he mentions that we could use that to enhance the collision detection.
In his implementation, Casey tests each pixel to see if it is inside a rotated rectangle:
My question is, how to adapt the first two functions to use these better edge tests and find the appropriate tMin value?
Around episode 50 Casey implements line segment intersection collisions for axis aligned rectangles.
His implementation consists of this TestWall function:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | internal bool32 TestWall(real32 WallX, real32 RelX, real32 RelY, real32 PlayerDeltaX, real32 PlayerDeltaY, real32 *tMin, real32 MinY, real32 MaxY) { bool32 Hit = false; real32 tEpsilon = 0.00001f; if(PlayerDeltaX != 0.0f) { real32 tResult = (WallX - RelX) / PlayerDeltaX; real32 Y = RelY + tResult*PlayerDeltaY; if((tResult >= 0.0f) && (*tMin > tResult)) { if((Y >= MinY) && (Y <= MaxY)) { *tMin = Maximum(0.0f, tResult - tEpsilon); Hit = true; } } } return(Hit); } |
And this iteration loop which tests the four edges and updates the tMin variable when collisions are found:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | real32 tRemaining = 1.0f; for(uint32 Iteration = 0; (Iteration < 4) && (tRemaining > 0.0f); ++Iteration) { real32 tMin = 1.0f; v2 WallNormal = {}; Assert((MaxTileX - MinTileX) < 32); Assert((MaxTileY - MinTileY) < 32); for(uint32 AbsTileY = MinTileY; AbsTileY <= MaxTileY; ++AbsTileY) { for(uint32 AbsTileX = MinTileX; AbsTileX <= MaxTileX; ++AbsTileX) { tile_map_position TestTileP = CenteredTilePoint(AbsTileX, AbsTileY, AbsTileZ); uint32 TileValue = GetTileValue(TileMap, TestTileP); if(!IsTileValueEmpty(TileValue)) { real32 DiameterW = TileMap->TileSideInMeters + Entity->Width; real32 DiameterH = TileMap->TileSideInMeters + Entity->Height; v2 MinCorner = -0.5f*v2{DiameterW, DiameterH}; v2 MaxCorner = 0.5f*v2{DiameterW, DiameterH}; tile_map_difference RelOldPlayerP = Subtract(TileMap, &Entity->P, &TestTileP); v2 Rel = RelOldPlayerP.dXY; if(TestWall(MinCorner.X, Rel.X, Rel.Y, PlayerDelta.X, PlayerDelta.Y, &tMin, MinCorner.Y, MaxCorner.Y)) { WallNormal = v2{-1, 0}; } if(TestWall(MaxCorner.X, Rel.X, Rel.Y, PlayerDelta.X, PlayerDelta.Y, &tMin, MinCorner.Y, MaxCorner.Y)) { WallNormal = v2{1, 0}; } if(TestWall(MinCorner.Y, Rel.Y, Rel.X, PlayerDelta.Y, PlayerDelta.X, &tMin, MinCorner.X, MaxCorner.X)) { WallNormal = v2{0, -1}; } if(TestWall(MaxCorner.Y, Rel.Y, Rel.X, PlayerDelta.Y, PlayerDelta.X, &tMin, MinCorner.X, MaxCorner.X)) { WallNormal = v2{0, 1}; } } } } Entity->P = Offset(TileMap, Entity->P, tMin*PlayerDelta); Entity->dP = Entity->dP - 1*Inner(Entity->dP, WallNormal)*WallNormal; PlayerDelta = PlayerDelta - 1*Inner(PlayerDelta, WallNormal)*WallNormal; tRemaining -= tMin*tRemaining; } |
Later on, on episodes 90 and 91 Casey implements rendering of rotated and scaled rectangles and he mentions that we could use that to enhance the collision detection.
In his implementation, Casey tests each pixel to see if it is inside a rotated rectangle:
1 2 3 4 5 6 7 8 9 10 11 12 | real32 Edge0 = Inner(PixelP - Origin, -Perp(XAxis)); real32 Edge1 = Inner(PixelP - (Origin + XAxis), -Perp(YAxis)); real32 Edge2 = Inner(PixelP - (Origin + XAxis + YAxis), Perp(XAxis)); real32 Edge3 = Inner(PixelP - (Origin + YAxis), Perp(YAxis)); if((Edge0 < 0) && (Edge1 < 0) && (Edge2 < 0) && (Edge3 < 0)) { *Pixel = Color32; } |
My question is, how to adapt the first two functions to use these better edge tests and find the appropriate tMin value?
Edited by Rafael
on
Reason: Initial post
I don't know exactly what Casey meant, but I think the idea is to use the inner products to determine if there is a collision, and only if there is one, try to compute the intersection. I'm not sure that it would be faster, and the result would have the same precision since the line intersection algorithm would stay the same.
If you're trying to get some general collision code, you can look at the Separating Axis Theorem (SAT) or Gilbert Johnson Keerthi (GJK) + Expanding Polytope Algorithm (EPA).
In this thread there is an implementation of SAT and there are a few posts in these forums about GJK and EPA.
If you're trying to get some general collision code, you can look at the Separating Axis Theorem (SAT) or Gilbert Johnson Keerthi (GJK) + Expanding Polytope Algorithm (EPA).
In this thread there is an implementation of SAT and there are a few posts in these forums about GJK and EPA.
mrmixer
I don't know exactly what Casey meant, but I think the idea is to use the inner products to determine if there is a collision, and only if there is one, try to compute the intersection.
So if I understand you correctly,
Those inner product edge tests can only tell if a point is inside a rectangle but not produce the intersection point of a line segment and one of the edges? I just want to confirm that.
mrmixer
If you're trying to get some general collision code, you can look at the Separating Axis Theorem (SAT) or Gilbert Johnson Keerthi (GJK) + Expanding Polytope Algorithm (EPA).
Thanks a lot for I enjoyed the SAT link the most! I got a little implementation of it and it does more than I was hoping for this little game so I think I'm happy with that algorithm for now. On a later project I shall experiment with GJK + EPA as that seemed as more work but fun too.
Many thanks.
Grid
Those inner product edge tests can only tell if a point is inside a rectangle but not produce the intersection point of a line segment and one of the edges?
Yes. In this case the inner product (also called dot product) is used to tell on which side of a line a point is.
- If you do the dot product of two vectors, the resulting scalar tells you if the two vectors point in the same general direction:
--- if the value is positive they are pointing in the same general direction
--- if the value is negative they are pointing in opposite general direction
--- if the value is 0 they are perpendicular.
- If you take an edge of a polygon and computes the normal of that edge; than if you do a dot product of the normal with a segment that goes from a point on the segment (one of the vertices of the edge for example) to the test point P, you can find on which side of the segment P is.
- If you do that for all the edges of a convex polygon you can determine if the point is inside the polygon.
But that doesn't provide other information (as far as I know).
mrmixer
- If you do the dot product of two vectors, the resulting scalar tells you if the two vectors point in the same general direction:
--- if the value is positive they are pointing in the same general direction
--- if the value is negative they are pointing in opposite general direction
--- if the value is 0 they are perpendicular.
Thanks for the detailed explanation, that is very useful.
About the SAT collision detection,
The algorithm itself seems to be working fine but I'm having some trouble figuring out how to use it properly to adjust the position and velocity of entities when they bump into each other.
My reasoning so far has been:
1 - Apply equations of motion (v1=v0+a*t, s1=s0+v0*t+0.5f*a*t^2) to simulated entity
2 - Test entity's new position against all other entities one at a time (this produces the mtv)
3 - If mtv is in same general direction of simulated entity's velocity, then invert mtv and add it to entitys position
otherwise, if mtv is in opposite general direction of the entitys velocity, then just add mtv to entitys position
4 - If mtv vector has x component, then zero sim entity's velocity in x axis, do the same for the y direction
By doing these steps, entities will no longer stay overlapping, and they will -mostly- be pushed away towards the direction you would expect them to, but some fairly obvious problems still occur:
- If moving too fast, an entity can go directly through obstacles
- Even if they don't go completely though when moving fast, if they get far enough into an obstacle then they are pushed to the wrong side of it.
- Entities can't glide slopes nicely, since step 4 will zero their velocity so they glide downward slopes very slowly
That said,
I'm wondering if you know of some proven method that might be better than the hacks I put together.
Thanks!
Edited by Rafael
on
There isn't a single solution, as the solution mostly depends on the specific thing you're trying to do, and solving only that will, most likely, work better than solve "general physics collisions".
A common way to solve that is to do multiple small steps (with fixed timestep) for the physics simulation per frame. Using a fixed timestep is important to make the physics simulation do the exact same thing every times it runs with the same inputs.
Instead of setting the velocity to 0, you need to change the direction of the entity into the direction of the slope, and probably remove a bit of the velocity (how much you went into the obstacle). If I remember correctly the axis returned by SAT is the normal of the edge of the collider, so you can use the perpendicular of that axis as the direction. You'll need to figure out on which side of that axis you need to go (probably use the dot product of the veloctity with the axis to find out).
I would like to say that I never did that, so it might be completely wrong.
This is probably OK at first, but if you got a lot of entities, or shapes with a lot of edges it will most likely take a lot of time. If you run into that, you can do a "broad phase" where you do a simple test to see if a collision is possible and create a smaller list of entities pairs that could collide. The simple test is for example "entities that are more than 1 meter apart can't collide", or testing axis aligned bounding boxes.
Grid
- If moving too fast, an entity can go directly through obstacles
- Even if they don't go completely though when moving fast, if they get far enough into an obstacle then they are pushed to the wrong side of it.
A common way to solve that is to do multiple small steps (with fixed timestep) for the physics simulation per frame. Using a fixed timestep is important to make the physics simulation do the exact same thing every times it runs with the same inputs.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | while ( game_running ) { r32 delta_time = ...; r32 physics_timestep = 0.005f; /* Balance this value for "correctness" vs "performance". */ r32 p_dt = 0; while ( p_dt + physics_timestep < delta_time ) { simulate( physics_timestep, ... ); p_dt += physics_timestep; } /* Note that at this point p_dt is less than delta_time. So there is delta_time - p_dt time left to simulate. You can do another step with that time but it will change the predictability of the fixed timestep. You can simulate it in the next frame, ignore it, do something else. I don't really know about that. */ } |
Grid
- Entities can't glide slopes nicely, since step 4 will zero their velocity so they glide downward slopes very slowly
Instead of setting the velocity to 0, you need to change the direction of the entity into the direction of the slope, and probably remove a bit of the velocity (how much you went into the obstacle). If I remember correctly the axis returned by SAT is the normal of the edge of the collider, so you can use the perpendicular of that axis as the direction. You'll need to figure out on which side of that axis you need to go (probably use the dot product of the veloctity with the axis to find out).
I would like to say that I never did that, so it might be completely wrong.
Grid
2 - Test entity's new position against all other entities one at a time (this produces the mtv)
This is probably OK at first, but if you got a lot of entities, or shapes with a lot of edges it will most likely take a lot of time. If you run into that, you can do a "broad phase" where you do a simple test to see if a collision is possible and create a smaller list of entities pairs that could collide. The simple test is for example "entities that are more than 1 meter apart can't collide", or testing axis aligned bounding boxes.
Edited by Simon Anciaux
on
Reason: typo
mrmixer
Instead of setting the velocity to 0, you need to change the direction of the entity into the direction of the slope, and probably remove a bit of the velocity (how much you went into the obstacle).
You'll need to figure out on which side of that axis you need to go (probably use the dot product of the velocity with the axis to find out).
I have done that and it seems good enough so far.
later on I might as well experiment with some more elaborate physics calculations.
mrmixer
This is probably OK at first, but if you got a lot of entities, or shapes with a lot of edges it will most likely take a lot of time. If you run into that, you can do a "broad phase" where you do a simple test to see if a collision is possible and create a smaller list of entities pairs that could collide. The simple test is for example "entities that are more than 1 meter apart can't collide", or testing axis aligned bounding boxes.
Once I have more of a game to work with I will do that.
Thanks for all the tips and explanations,
Cheers!