Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Thanks for that. I think I didn't explain the issue I was having properly, though, so I'll try again.
Here's an illustration:
The top image is the “usual” case: the player is collinear to an edge, but not quite on it, so there's no problems - they'll intersect a different edge of the triangle if need be, so no clipping needs to happen. The bottom image is showing my current problem: The player is /exactly/ on the edge, so the intersection test fails as expected (and I'd want an intersection at p2→p3)… but the intersection test against the p2→p3 edge fails (wherever that may be), because the movement might be passing /just/ outside the p2→p3 edge (ie. enough that testing p1→p2 is detected as collinear, but p2→p3 is detected as not being intersected).
So I guess it's more of a “corner case” than an edge case, sorry for the confusion. Here's a small video of what's happening if it helps explain things better:
I got you right from the beginning. Your problem is what i have assumed.
I'm assuming the player is not allowed to leave the navmesh, thus proposing to track the player on it so he can't get off, as shown in the gif. He would get stuck on the top right shared vertex of either of the two triangles visible on the top right of the image. One of these triangles would be the ‘current’. But he could move back freely. That's what you want, i guess?
Btw, my drawings are not top down but from the side. So the triangles become thick lines. I guess this could cause soem confusion.
Here's the ‘current triangle’ drawn on top of yours:
The player would be not allowed to cross any of it's two boundary edges. Only the 3rd. internal edge can be crossed, making the neighbor the current triangle. I think it's robust because no line - line intersection is needed.
Yes, that's the behaviour I'm trying to aim for. I just can't work out what you were trying to explain earlier, sorry.
I understand the “extrusion” of the edges along their normals, but I'm not understanding it in this context. I'm guessing that the edge with the normal arrow (bottom image) is a real edge in the geometry? So if I'm understanding correctly, then in the ambiguous cases of being exactly on an edge, I should test which triangle I'm “really” on via the standard signed area equation thing? And if the triangle I'm “most” on is outside the navmesh, then I should clip to the closest point (using something like this), correct?
– Edit after seeing your additions: Ok, now the pictures make more sense… but to be honest, I think I'm even more confused now. I'll try and think on it for a bit to see if it clicks.
Aikku said: I understand the “extrusion” of the edges along their normals, but I'm not understanding it in this context.
I see how that's confusing. And it's not even that important, but rather about the next special case problem you might encounter if the tracked triangle idea shows some promise.
The concept of voronoi regions is useful to find the closest point on convex polygon from a given point outside that polygon. (Or convex polyhedra in 3D). I'll illustrate that:
If your point is in the orange region, it is closest to the red edge. If it's in the green region, closest to green edge. But if it is in the blue region, it's closest to the blue vertex, not to any edge.
If the point is inside the polygon, we only need to find the closest edge.
So we can use this to project any point to the boundary of the polygon (or surface of a polyhedra), ensuring the projection takes the shortest distance to minimize energy. Useful for things like resolving collisions.
Now imagine the drawing shows a top down view of a doom level, and the polygon represents walls. But the player is an ant and can walk on the walls. He's outside the walls, and he may be in the blue voronoi region of the blue vertex. And the blue vertex is actually a vertical edge. It only looks like a vertex due to our top down view. And the player is walking upwards, parallel to that edge. In this case you could not easily tell if the player is on the red or green wall polygon, using this standard test. But we need to map to a polygon, on an edge, since we want to track polygons. That's why i have proposed an alternative test, which is the same as the signed area test you already use. If the player is exactly in the edge it should not matter which polygon we pick and we can just keep the old one. If the player is on one side of that edge, we pick the polygon accordingly.
So i guess it's not that much of a problem. Sorry about the confusion.
This is a great resource about such geometrical intersection and closest distance problems of various primitive shapes, see Dist* and Intr* functions:
Ah, ok! That makes much more sense now. So if I'm understanding correctly, you're proposing:
Don't trace the movement by crossing the edges of each polygon - there /will/ be nasty corner cases that are more painful to resolve than they're really worth.
Instead, test to see if the new point is inside the current polygon using the signed area test. If it's inside, great.
If the test says the player is outside the current polygon, choose the “closest” edge that was crossed (ie. the one with the smallest negative “signed area”). If it can be crossed, set the player polygon to the one opposite that edge and continue testing.
If the closest edge can't be crossed, then set the player position to the intersection point on that edge, project the movement vector, and try again.
If so, then I'm curious about that last point, since it brings me back to the exact same problem of the intersection calculation failing in weird corner cases (like in the video I showed earlier, with two edges resulting in negative signed area when out of bounds). Though I guess it might end up working: since I'd be testing all edges for their signed area anyway, then as long as at least one of those edges can intersect on the infinite line of p0→p1 it should work out (ie. check for collinearity and reject that edge, but then if I don't enforce that s and t are in the range 0.0~1.0 like in the StackExchange answer I linked, then the other edge will snap the player inside the polygon).
Thanks for that link, btw - I've bookmarked it for further reference.
Alright, that seems to have worked. I still sometimes get an intersection that puts me out of bounds (seems to be an accuracy issue this time), but I can now fail that case more gracefully by just aborting the movement altogether instead of actually going out of bounds. Not ideal, but maybe I'll be able to sort it out properly some day.
Aikku said: Don't trace the movement by crossing the edges of each polygon - there /will/ be nasty corner cases that are more painful to resolve than they're really worth.
I would want to keep the tracing, using the proposed stuff only to deal with failure cases.
Aikku said: If the closest edge can't be crossed, then set the player position to the intersection point on that edge, project the movement vector, and try again.
There is no need to calculate intersections. If the player is on a boundary edge and moves parallel to that edge (our problem case), you let him move but afterwards project him to the closest point on the edge (which is the same as projection to the closest point on the triangle containing the edge. The math is robust here. The only failure case would be zero edge lengths.
I would want to keep the tracing, using the proposed stuff only to deal with failure cases.
I think we're agreeing on the same thing here, but not understanding each other maybe?
I'm still tracing the movement, but in the previous code, I'd been intersecting on every edge I crossed, kind of like this:
The blue arrows represent calculating the line/edge intersection point and setting the player position to it, then reducing the magnitude of the move vector by the amount of distance moved from the last position to the intersection point.
The new version of the code just figures out which edges needs to be crossed to reach the target point, and keeps tracing which polygon I'm on until I reach the target or hit a wall. The only drawback is that I can now only compensate for the slope of one polygon, so the movement might “miss some slopes”, but that's not a big issue. Kinda like this (side-view):
There is no need to calculate intersections. If the player is on a boundary edge and moves parallel to that edge (our problem case), you let him move but afterwards project him to the closest point on the edge (which is the same as projection to the closest point on the triangle containing the edge.
I'm not sure I'm understanding this part. This is what I'm doing at the moment:
(red line = move vector, orange line = projected move vector, blue line = edge to use for intersection)
The top part is the “usual case”, where I can set the player position to the intersection point and project the remaining move vector. The bottom part is when I'm walking towards a corner: If it tries to intersect the bottom edge, it'll fail because of collinearity, so then it'll try the side edge and set the player position to the intersection point (which should be almost exactly the corner vertex) and try to project the remaining movement… but the projected move would put the player out of bounds, so it just stops moving.
That last part where it stops the movement when the remaining movement would put me out of bounds is what's causing my current corner case, where the player stops moving, even though they could potentially keep moving:
The player tries to move slight outside the polygon, so I intersect at the corner vertex, but then the projection would put me out of bounds, so the player stops moving.
Aikku said: The player tries to move slight outside the polygon, so I intersect at the corner vertex, but then the projection would put me out of bounds, so the player stops moving.
In this case you can't calc intersection with the edge collinear to movement, but you can do it for the edge which actually matters for crossing triangles:
Not sure about the logic, but maybe something like:
If player and movement is collinear to boundary edge, snap movement to the edge, ensuring he can't cross the boundary.
After that, ignore the snapped edge from the triangle edges to test for crossings using intersection tests. So you only intersect the two other edges.
After that, ignore the snapped edge from the triangle edges to test for crossings using intersection tests. So you only intersect the two other edges.
Ah right, I'd been doing that in the old code but didn't think to try it in the new one.
Either way, though, I figured out the actual problem: When I'm projecting the remaining move vector on the edge vector, I'm calling a specialized routine I wrote for vector projection (to project vector a on vector b) that starts by normalizing vector b… but in this case, I forgot to scale up the edge vector by the fixed-point precision, so it was detecting it as 0-length and set the projected move vector to {0,0,0}. Scaling the edge vector up fixed the problem (though I really should allow small vectors for normalization, so I'll try and fix the root cause).
