Hi, hopefully I've got the right forum for this question. I'm more of a DSP maths person, so 3D maths isn't something I'm all that familiar with. Please bear with me if I'm missing obvious things.

I'm working on a project that uses a pre-rendered background of a 3D space, combined with a 3D mesh that a player can move on. The implementation of the walkmesh I'm using is very simple, as I don't need anything complicated, and works exclusively on the xz plane (z = forward/back), with the final y position just being calculated once movement has finished. I can't just use an off-the-shelf library, because this is running on a very limited platform, on which I don't think I've seen any open-source tools for this (Nintendo GBA).

Implementation notes:

• Every entity gets assigned to a triangle in the walk mesh when spawned.
• To traverse the mesh, I take in the entity's current world position + associated triangle, and a walk vector (eg. {0,0,1} = Move 1.0 units along the triangle's yz plane).

Implementation steps:

1. Project the move vector onto the triangle's plane (ie. vDisplace = vWalk - (vWalk.TriNormal)*TriNormal) and displace the current entity position by vDisplace. This is to make it appear as though the entity is traversing that distance on the mesh rather than just the world axes.
2. Do a simple edge test against all sides of the current triangle to se if the new position lies outside the current triangle.
3. If the new position is inside the triangle, then everything's fine; exit by going to step 7.
4. If the new position is outside the triangle, then use the result of the edge tests to clip to the triangle's edges (eg. if the point is outside v1v2, clip against v1v2, and so on for v2v3 and v3v1).
5. Subtract the movement to the clipped position from the original intended movement (vWalk *= 1.0 - Length(vNewPos-vOldPos)/Length(vWalk)).
6. Use the edge tests combined with the triangle's edge connectivity to determine a new triangle to traverse to (eg. if v1v2 was crossed and a triangle exists across it, then select that). If a triangle exists, then restart at step 1 using that triangle and the current position + walk vectors.
7. Either we hit a dead-end edge, or the entity is inside the current triangle (came here from step 4). Either way, store the current y position and finish.

While this seems to be working fine, there's two things I want to add:

• Say an entity is moving by vWalk={0.7,0,0.7}, but is colliding with a wall on the x axis. Using the current system, the entity just gets "stuck" because it collides with a wall in the current direction and gets clipped. I would like to see instead a 'slide' against a wall. I've tried setting vWalk = vEdge * Length(vWalk)/Length(vEdge), but this seems to glitch out (probably from some precision issues, to be honest; all the maths needs to be done using fixed-point integers), and there's issues regarding which direction I'm moving in relative to the edge direction, anyway (ie. whether I used v1-v2 or v2-v1).
• While point collisions are a good place to start, ideally I'd have a sphere collision against edges (or rather, a circle collision, since I'm only actually referencing the xz planes). I really have no idea where to start on this, though.

A major point about the implementation is that it can't just use wild expressions everywhere, due to lack of CPU resources (eg. dot products are great, cross products are ok, but square roots and divisions should be as rare as possible; it's to the point where I'm calculating Sqrt[a/b] as 1/Sqrt[b/a] because I have fast routines for approximate reciprocals and approximate inverse square roots, which are faster than calculating divisions and square roots directly).

Does anyone know of any resources I could read up on to help with what I'm trying to do? From the looks of things, walkmesh implementations are mostly a thing of the past, with basically everything now just using physics engines directly, so I've been having a really hard time finding anything, and built my current implementation mostly based on intuition, with occasional maths-related searches.

Aikku said:
While this seems to be working fine

There might be special cases worth to investigate:

In this case, hitting a vertex exactly, and being colinear with an edge after that, you can't tell on which of the triangles you are, which might cause problems about robustness. I did the same algorithm you have described to trace on the surface of a 3D mesh, and iirc there was a need to handle those corner cases somehow, but it was not too bad.

Aikku said:
I would like to see instead a 'slide' against a wall.

You would just calculate the intersection with the edge, project the clipped movement vector to the edge to get a new start point and target (red arrow). Continue with that until the whole desired distance of travel is done, or you get stuck at corner with no way to proceed in the desired direction:

I guess that's what you have tried. It should work, but you may need to recurse multiple times, and since you're now walking on edges you are much more constrained, so the corner cases as mentioned above are more likely to show up. Precision always is an issue here, even with floating point numbers. The solution is usually to work out logic robust for all special cases.

Aikku said:
it's to the point where I'm calculating Sqrt[a/b] as 1/Sqrt[b/a] because I have fast routines for approximate reciprocals and approximate inverse square roots, which are faster than calculating divisions and square roots directly).

Look up tables might be another option. I have used them with fixed point math on ARM, at least for trig iirc.

A big optimization could be to use polygons instead triangles, since this may remove more than half of your edges. But eventually stick at triangles until it works 100% robust before you do this.

Aikku said:
Does anyone know of any resources I could read up on to help with what I'm trying to do?

No, but it sounds you're on a good track on your own. Just set up problem cases empirically so you can debug them specifically, i would say.

Edit: Maybe you can search for ‘navmesh’ instead walkmesh? That's still the same thing and widely used, just for AI.

Aikku said:
or rather, a circle collision

Consider to shrink the mesh inwards instead, so you could tackle this with pre-processing.

Cheers for the reply and the illustrations to help! (and sorry in advance for lack of good formatting; having issues with it on my browser for some reason)

> hitting a vertex exactly, and being colinear with an edge after that, you can't tell on which of the triangles you are

I guess that's technically possible, but the way I'm checking to see if I've crossed an edge is just a… side equation? Signed area equation? Not sure exactly what it's called, but defined as: v1x*(v2z - v3z) + v2x*(v3z - v1z) + v3x*(v1z - v2z). But the point is, if I'm /exactly/ on an edge (or criss-crossing between edges if precision is bad enough), shouldn't the above equation return a value “close enough” to 0 that I can stay on either edge without issue, as long as I use a threshold? What kinds of bad things could happen?

> You would just calculate the intersection with the edge, project the clipped movement vector to the edge to get a new start point and target (red arrow)

Ah ok, so there isn't really a special way to deal with it side from just “project the vector”. Good to know. I'll see if I can track down what causes the glitching, then.

> Look up tables might be another option

Yeah, my reciprocal and inverse square root approximations are table-based, up to the log2 of x (or half log2 for the inverse square root). I figure that I should probably get it mostly working with somewhat cleaner maths first before seeing if lookup tables are an improvement here.

> A big optimization could be to use polygons instead triangles

While that might've been an interesting option, I stuck with triangles for two reasons: 1) There is exactly one plane for a triangle, versus N-2 planes for an arbitrary polygon, which would make calculating the y values are bit weirder, and 2) The way I'm storing the data is using a heavily-compacted format that stores the three vertex indices in 10 bits each, plus the connected triangles of each edge using 11 bits each; trying to make this suit arbitrary polygons would be pretty much impossible without offset tables, and trying to use quads would need re-engineering of the format, as well as having to add special handling for “degenerate” cases.

> Maybe you can search for ‘navmesh’ instead walkmesh?

Omg cheers for that! I'd been trying “terrain mesh”, “walk mesh”, and other variations but nothing helped. Hell, “walkmesh” gives me probably 99% results related to Neverwinter…

> Consider to shrink the mesh inwards instead, so you could tackle this with pre-processing.

Hm, I can see how that would work. I'm guessing the transition from point collisions to circle collisions is a lot more complicated than it sounds in theory?

Aikku said:
shouldn't the above equation return a value “close enough” to 0 that I can stay on either edge without issue, as long as I use a threshold? What kinds of bad things could happen?

Yeah, you're right. Trying harder to remember what my problem actually was, maybe it was related to working on a 3D mesh, causing a curved domain. Thus, picking one or the other side can make a big difference on the resulting direction. If two rays start in parallel directions at a nearby location on the same triangle, their traced paths can cross each other if we just rotate across edges but ignore the stretching caused from curvature. This was a problem for me, but can't happen to you, working on a planar mesh.

But still, working on geometry mostly comes with corner cases and robustness issues, and some frustration on that is normal. You should just know that.

Aikku said:
Ah ok, so there isn't really a special way to deal with it side from just “project the vector”.

Ofc. there are many variations. For example:
You could just stop at the very first intersection and handle the rest of the way in the next frame. But this would cause chunky movement.
You could scale the projected direction so the length of the desired path remains the same. But usually it feels more natural to accept the shorter result cause from the projection.
You could ignore the intersection, and find the closest point on the triangle from the resulting point if it ends up in a solid wall. But this is really error prone due to eventually tunneling through thin walls and other such issues.

Aikku said:
1) There is exactly one plane for a triangle, versus N-2 planes for an arbitrary polygon

Oh, i thought your entire geometry is on the same xy plane, sou you could treat it as 2D. If so, polygons over triangles would only cause minor extra complexity. But you surely want to avoid concave polygons and keep them convex.
Even with complex, non planar 3D models, physics engines often merge coplaner triangles to concave polygons for a speed up.
So i would not rule out the option, in case you run into performance issues.

Aikku said:
The way I'm storing the data is using a heavily-compacted format that stores the three vertex indices in 10 bits each, plus the connected triangles of each edge using 11 bits each; trying to make this suit arbitrary polygons would be pretty much impossible without offset tables, and trying to use quads would need re-engineering of the format, as well as having to add special handling for “degenerate” cases.

Yeah, but compression becomes less of an argument if you can half the amount of data in the first place.
Supporting quads and triangles might be the best compromise, since polygons with more vertices tend to be rare in practice.

But just saying. I would not change a working system for some potetnial advantage either, as long as ther is no need for it.

Aikku said:
Hm, I can see how that would work. I'm guessing the transition from point collisions to circle collisions is a lot more complicated than it sounds in theory?

Yes, complexity increases a lot:

You need to classify ‘Voronoi Regions’. In the image i'm in a Voronoi region of a vertex, so need to keep the distance of circle radius from this vertex.
In all other cases of that room edge regions would be enough, be we still need to fins the closest edge.

In 3D the vertex regions become spheres, edge regions become cylinders, and there is a 3rd type of region for planes extruded from faces.

So if all your circles have the same radius and you don't need the mesh for other things / can afford the extra memory, pre-processing the mesh is surely the better option. (You might use 1…4 edges for the arc in the orange corner, so the number of triangles can increase eventually!)

Also: Imagine the room is so narrow the circle would not fit in. Doing it at runtime, players could get stuck or jitter at least, if they try hard to get in. Preprocessing the polygon would just clip the narrow section away, avoiding such issues.

But ofc. it can be done robustly at runtime. It's just more work and has some higher cost.

> causing a curved domain. Thus, picking one or the other side can make a big difference on the resulting direction

Ah ok, I think I understand. That said, the geometry I'm using is very sparsely detailed, so this should hopefully be far less of a problem in practice (ie. if the movement starts drifting in weird directions, there's enough room between edges that the player should be able to manually correct it without too much annoyance).

> But still, working on geometry mostly comes with corner cases and robustness issues, and some frustration on that is normal. You should just know that.

Haha yeah, I've been working on a 3D renderer that's part of the same project (using real 3D maths, not just a raycaster), so I've definitely learned to be patient about these things. An annoyance I ran into with the walkmesh in particular ended up being calculating the intersection point of two line segments; there was a rounding error that was fixed by adding +1 if the sign of the x/y components of v1-v2 was less than 0, or the player just slowly kept moving along the face of the triangle without any clipping happening.

> Ofc. there are many variations. For example: …

Right, I just meant that I was expecting that there was some magic formula I didn't know about that related the movement vector to the edge vector. I'm still getting something wrong, though, since I seem to sometimes be moving in the direction of v1→v2 when I expect v2→v1 (or vice-versa).

> But you surely want to avoid concave polygons and keep them convex. …
> compression becomes less of an argument if you can half the amount of data in the first place.

Hm, yeah, that's true. There is definitely lots of places where I could convert triangles to quads, since most of the geometry is completely flat in places. Thanks, I'll try and keep it in mind if end up needing that.

> so need to keep the distance of circle radius from this vertex.

Oh, right. Yeah, I can see that that would make things a bit more complicated. Doable, sure, but probably a lot more complicated than this project warrants. Thanks for that explanation.

Aikku said:
Haha yeah, I've been working on a 3D renderer that's part of the same project

I saw somebody has ported Quake to GBA:

Really impressive assembly magic.

Personally i've worked on a 3D engine for early Symbian smart phones / Nokia N-Gage.
It was pretty cool. But then the iPhone came out, and the days of software rendering seemed over. : )

Wow, that's pretty intense. I can't even really make sense of the main raster loop; I /think/ it's trying to do texture wraparound without destroying the opposite coordinates with carries, but the coordinates are being bitpacked in a really weird way within the registers and it's making my head hurt haha. The way I did mine was to pack v|u<<16 and dvdx|dudx<<16, then access and step through a 256x256 texture with AND t, vu, #0xFF00; ORR t, vu, lsr #24; LDRB t, [tex, t]; ADD vu, dvdu. That wraps around the 256x256 space, but wrapping around the u coordinate adds a 1/256 carry error into the v coordinate.

Anyway, I've had some sleep now, so hopefully I'll get this walkmesh stuff sorted out a bit easier.

Alright so, late update.

I've been doing some more work on the implementation (higher precision values and stuff, so I can “walk” at fractional speeds), but ran into one of those weird edge case (possibly combined with a bug somewhere).

I've modified the main “walk” routine so that, instead of consulting with a signed area test to see which edge(s) of the triangle I've crossed, I instead immediately try an intersection test/clipping operation. If there is an intersection between the “walk ray" and an edge, then the movement gets clipped, and I iterate to the next triangle and so on, as I used to; the signed area test seems to only be useful for debugging in this particular use case.

However, it seems that due to the higher precision, and the resulting more accurate “sliding” calculations, I'm running into issues I never had before. More specifically, collinearity. If I'm walking parallel to an edge, then the intersection test gets confused because the determinant of the equations that need solving degenerates to 0, and I can't find the intersection point (I'm following the solution from here for reference). And because my intersection test/clipping routine returns “no intersection” in the collinear case (I originally thought this test was only needed when the move vector was 0, or when an edge was degenerate), this results in the player walking right off the edge of a triangle, with the walking routine thinking it's still on the same triangle (no clipping happened, so it thinks you're still walking along a perfectly valid edge).

I've tried “fixing” the issue by adding special handling for the collinear case, where it'll clip to either vertex of the edge, but I can't seem to get the conditions right (I usually end up on the wrong side of the triangle, and everything falls apart even if I don't).

Do you know what the usual way to resolve this particular edge case is? I've tried searching, but I can't seem to hit on the right search terms (eg. I get results like “the intersection between collinear line segments is another line segment” which isn't exactly the same when one of those line segments is directional, in which case there is a clear intersection point).

Aikku said:
Do you know what the usual way to resolve this particular edge case is?

I guess different people come up with different hacks.

Aikku said:
And because my intersection test/clipping routine returns “no intersection” in the collinear case (I originally thought this test was only needed when the move vector was 0, or when an edge was degenerate), this results in the player walking right off the edge of a triangle, with the walking routine thinking it's still on the same triangle (no clipping happened, so it thinks you're still walking along a perfectly valid edge).

The intersection of two collinear line segments is another line segment, not a point. So the intersection routine can only return an arbitrary point on this segment. The method of tracing the player trajectory to detect triangle crossings no longer works.

But you can still test in which triangle the point representing the player is.
You can track the current triangle, and if the player is on a boundary edge he is not allowed to cross, you can snap him back to the closest point on the current triangle. This way he can still slide along the edge, but can't cross it.

If the collinear edge is not a boundary edge, the player can cross it. So you need to update the current triangle. This is a problem in this case:

The player is in the voronoi regions of both the green and the red floor.
So the voronoi regions of triangles (the extruded 3D space along the normal) do not help.
But the edge normal does:

The extruded edge normal gives a plane, and we can test on which side we are robustly.

To sum it up, i propose to track a current triangle on the mesh where the player is currently on.
In cases where it's uncertain which triangle adjacent to crossing edges or vertices should become the current, you can just stick to the previous one.
This should work i guess.