I'd like to code something that lets a character move around any irregular mesh while always staying on the surface. This is regardless of orientation and without involving gravity.

The common approach I know of to this is sweeping/raycasting ahead to find the next piece of ground they will hit or should be on.

I could dive in but I'm also aware that there are a number of edge cases and pitfalls to be aware of. I've tried to find some tutorials that look into it but haven't been able to turn up anything at all. Does anyone know a good reference for this?

Cheers

I don't know of any references off the top of my head - maybe someone else can help out there.

I'm not sure if by 'raycasting ahead' you mean raycasting forward, or moving forward and then raycasting down, or something else. But I can imagine there being various failure cases associated with that approach (as you allude to).

If the only requirement is to move about the surface while always being oriented correctly with respect to the surface, my first thought would be treat the surface as a navigation mesh, more or less, and move in 'navigation mesh' space. Each triangle/polygon could have its own local coordinate system, which the character would move in while on that triangle/polygon. If an edge were reached, you'd re-express the character transform in the new coordinate system and continue from there.

There are edge cases (as you say) that are probably somewhat independent of the technique used. For example, at a 90-degree concave seam, a character with non-zero extents could be embedded in a surface immediately after changing polygons. And of course there's the general issue that without some sort of smoothing, the character orientation will 'snap' when crossing boundaries where the normals differ significantly.

It may be that you need more general physics behavior and that a navigation mesh approach wouldn't work for you. But, it's the first thing that comes to my mind (partially because it could avoid some of the difficulties associated with a more general collision- or raycasting-based approach).

That's an approach I took some time ago, for exactly the reasons you said; ie., it was less edge-case-prone than collision/raycast testing and the only noteworthy issue I had to work around was float inaccuracy on edges detecting wrong tris at times. I was happy with it, but it has a few of its own quirks like those you mentioned, as well as needing to predetermine every tri's neighbouring tris which leads to needing a bit more thought about what goes in a level, how interactions will work between two separate meshes, and the like.

For now, I'm just interested in exploring the sweeping/raycasting approach. Not that it's necessarily the approach I'll take, but I believe it's fairly widely used so I'm hoping to find something that discusses its hidden pitfalls and what it needs to be made decently robust.

You may already be aware of this, but one thing I'll mention that could be relevant for any raycasting-based method is that there are some things you can do to increase the robustness of mesh raycasting. I think Christer Ericson discusses this some in his book 'Real-Time Collision Detection'. In any case, there are some tricks you can use to reuse results between triangles (or at least ensure that the results are numerically equivalent) in order to avoid 'slipping through the cracks' between triangles. It seems like robust mesh raycasting would probably be a prerequisite of sorts for any reliable raycasting-based method, so that might be a good starting point.

A naive raycasting-based approach (which you may have already considered) might be something like this. Move the character in the current direction by the current delta, and then raycast through the character's local up axis to find the next surface point. (Depending on the nature of the mesh, you might need to differentiate between multiple intersection points, e.g. one where the line enters the mesh and one where it exits.)

The problem I see with this is that it doesn't really capture the nature of the movement correctly in the general sense. For example, at a 90-degree 'cliff', the next raycast may miss the mesh entirely or hit some distant triangle, rather than detecting that the character should 'turn a corner', as it were. Or, if there's a steep grade (e.g. an 80-degree slope), the next raycast might lead to an unnatural 'jump' due to the intersection point being relatively far into the next triangle. (Not sure how clear what I'm describing is without illustration.) In that sense at least, it seems like the navigation mesh approach does a better job of reflecting the true nature of the problem.

Anyway, you said you think raycasting is commonly used for this, so maybe there are good solutions to these problems. Also, if there are constraints in place (e.g. the mesh doesn't have sharp angles and/or the movement deltas are limited), you may be able to get away with the method I described earlier (something like that is described here).

Maybe someone else will jump in with further ideas

Yep, it's cases like that (cliffs and such) that prevent me from just going at it. You're definitely anticipating the same kinds of problems I'm worried about, I'm just hoping there's something published/experienced that addresses them (and the ones we haven't thought of).

I have Ericson's book buried somewhere; I was stuck puzzling over buggy ellipsoid-to-mesh collision detection guides for some months until finding his book and algorithm that actually works. (I am going to take this moment dive off-topic and warn any readers to NOT use Fauerby's or Nettle's guide to collision detection. Still bitter.)

So thank you for the reminder about Ericson; I wouldn't have thought of checking it. I'll be using Unreal, so the physics engine behind the raycasting is already done for me, but I wouldn't be surprised if the book still has something on this thread's topic.

This might be an old paper, but I've been using this approach for many years, and still loving it
http://www.peroxide.dk/papers/collision/collision.pdf

The sample code is an excellent start and quite robust, as I remember.

Hi bmarci, the thought is appreciated but that's Fauerby's; one of the papers I wrote about above, recommending that people avoid it.

Quote

(I am going to take this moment dive off-topic and warn any readers to NOT use Fauerby's or Nettle's guide to collision detection. Still bitter.)

Here's one link (I haven't read) looking at some problems it has. There's another rather academic paper out there that goes deeper into its numerical robustness, but I can't find a link anymore. 

Personally I didn't run into those particular issues; the problem I had with Fauerby's code is that it works thanks to 2 bugs that exist in the code - but not accounted for in the algorithm - actually cancelling each other out. I had unthinkingly not-implemented one of those 2 bugs and had to get real intimate with things to find the problem. After struggling with my OpenGL version I redid it in Unity for the sake of visual debugging, and could see that the sphere would periodically pass through a surface, yet also get the surface normal wrong and coincidentally push the sphere back out. It does achieve the result of not penetrating a flat surface, but adds jitter, but that's what kept it working. If I recall correctly this only affected the sliding, not colliding, part of the algorithm. 

I wrote a post about this maybe 4 (?) years ago, but I had a quick check of my post history yesterday and it seems it's not recorded.

Since you've had long success with it you could say I'm being too harsh. It did work to a practical degree, with a little jitter, when following his code to the letter - bugs included. And I admit that's quite likely to be good enough for almost everything, but it was very frustrating for me before finding happiness with Ericson's book.

So if it's still kind-of good enough for almost everything, why don't I go with it? Because it's actually a bit off topic, so I see I have to make the question a bit clearer after I submit this post.

What I'm looking for is something that has demonstrated experience with the pitfalls of finding upcoming terrain when using sweeps/raycasts. Those pitfalls are pretty much about dealing with edge-case geometry, and I'm hoping to find something published where someone has really dealt with the problems and knows which hiccups don't matter, which do, what to do about them, and what restrictions to work with. 

The key difference is that Fauerby's article shows how to do sphere-mesh collision detection, while the thread's topic assumes that collision detection is already available (even if it's a posteriori), and is hoping for more expertise on what to do with the results when trying to track terrain.

Thanks for the consideration nonetheless.

... Wait, can we not edit posts after a little time anymore? I guess I can only clarify the topic here then.

Topic Clarification:

I'm looking for something published that speaks from experience of dealing with the problems of using sweeps/raycasts (and not calculating the path across every tri on a mesh) to detect upcoming terrain, and knows which hiccups don't matter, which do, what to do about them, and what restrictions to work with.

This assumes a physics engine is already available (Unreal's in this case) for doing the sweeps/rays/collision detection. It's advice on what to do with the results that I'm wondering about.

Found the other article that talks about robustness issues in Fauerby's paper.

https://arxiv.org/ftp/arxiv/papers/1211/1211.0059.pdf