Aikku said:
starts by normalizing vector b…

Btw, the square root should not be needed for this.

For example, if we want to project a point to a line, we can do:

vec3 line = lineB - lineA; // difference of the two line end points
vec3 diff = point - lineA;

vec3 lineDir = normalize(line);
float t = dot(lineDir, diff);
vec3 closestPoint = lineA + lineDir * t;

But we can also do:

vec3 line = lineB - lineA;
vec3 diff = point - lineA;

float t = dot(line, diff) / dot(line, line);
vec3 closestPoint = lineA + line * t;

So the length of the line is not needed, squared length is enough.

Huh, interesting. I'll keep that formula in mind (it might come in handy), but I don't think it's applicable to my current setup; I'm projecting the move vector onto the normalized edge vector, rather than a point onto the edge (though I guess it could be useful in those weird corner cases, where I'd want to clamp t to be 0.0~1.0).

The reason I need to normalize the edge vector is because in my code, I've already intersected against the edge at that point, so I need to “rotate” the move vector to face in the same (or opposite) direction as the edge. I guess a vector projection isn't exactly correct (since it'll be off by a factor of cos(theta)), but it's easier to calculate than doing an actual rotation, and feels more “natural” anyway, since it gives a kind of “friction factor” to the movement.

Aikku said:
but I don't think it's applicable to my current setup;

It is. Notice the diff variable in my snippet is a vector.
Doing minor changes to illustrate:

vec3 edge = vertexB - vertexA;

float t = dot(edge, myVector) / dot(edge, edge);
vec3 projectedVector = edge * t;

// same as
// normalize(edge);
// vec3 projectedVector = edge * dot(edge, myVector);

If you have normalized edge directions in memory already, it's ofc. not worth it.
But in general this is applicable very often.

That was actually the first thing I thought of, but I discarded it after a minute of thought because I couldn't reconcile the last step (your vec3 projectedVector = edge * t part; I was thinking “what value would need to be added to make this correct?”). Thanks for pointing that out and clearing it up, I'll put it in my code now.

Alright, so I have another update and request for help. Sorry if it's getting tedious by now, but it's borderline impossible to find any good resources about the implementation details.

I ended up with code that was fairly robust about point collisions (the only issue I was having was that the low precision was stopping projected-edge movements/slides), and then decided to extend it with circle collisions.

The way I implemented that was to run a circle-wall collision test before running any edge tests against the current polygon, since the latter is mostly about keeping track of which polygon the actor is standing on. The “issue” I'm having is that the code I implemented feels overly-complicated, and I'm not sure if I'm just missing something more obvious.

So basically, the circle-wall collision test runs fairly standard point-capsule intersections. But as you probably know, there is the possibility that the wall that was hit by the bounding circle lies on a different polygon, something like this:

(I'm not trying to implement a swept-circle test or anything like that at the moment, just trying to clip the final position)

So what my code is doing is to recursively run the circle-wall collision test for every polygon that contains an edge covered by the bounding circle until it either finds a wall, or all polygons touched by the circle have been checked/collided with. In the above example, it would've checked the triangle at the top of the image to find the wall.

That example would've been easy enough to handle. But the reason I'm doing it recursively is explained by this example:

In this case, I would need to scan four polygons before finally seeing the wall I'm colliding with.

The code I'm using keeps a list of which polygons have already been checked to avoid going around in circles forever (eg. if the triangle fan above didn't have a wedge missing), or moving backwards… but this whole implementation feels a bit wrong.

I know that checking the other polygons /is/ necessary, but recursion feels wrong. Shouldn't it be possible to just run some sort of loop instead, or is the recursion actually needed to cover all possible cases? I'm especially skeptical of needing to keep around a list of which polygons have been scanned.

Aikku said:
I know that checking the other polygons /is/ necessary, but recursion feels wrong. Shouldn't it be possible to just run some sort of loop instead, or is the recursion actually needed to cover all possible cases? I'm especially skeptical of needing to keep around a list of which polygons have been scanned.

Not sure how you do your recursion. I assume your triangles have adjacency information, e.g. each edge knowing about its adjacent triangle, and you use this to implement a growing selection of triangles until the circle is fully contained.

That's not bad. A typical problem is the list of visited nodes as you mention. If your data set is small, you could replace it with a bit vector, setting one bit per visited triangle. Then the cost of a check is O(1), but you need to set all bits to zero each time you start the search.

A different way would be to put just the walls into a spatial acceleration structure, e.g. a regular grid. If the grid cell size is equal or larger than the circle size, you need to iterate 4 cells at most, so iterating the walls contained in those 4 cells overlapping the sphere.

I assume your triangles have adjacency information, e.g. each edge knowing about its adjacent triangle, and you use this to implement a growing selection of triangles until the circle is fully contained.

Yep, that's exactly correct.

The bit-vector idea is interesting, actually. My adjacency structure limits the number of polygons to 2047 in total, so that's 2047 bits of data to keep around, which isn't too bad; I've barely touched the “EWRAM” section (256KiB total), so I could easily place this data there.

A different way would be to put just the walls into a spatial acceleration structure, e.g. a regular grid.

I'd thought of that, but decided that it might end up overly complicated. But thinking on it a bit more, maybe some sort of BSP tree could work if I end up going with that.

---

Not sure how you do your recursion

At the moment, the pseudocode is basically:

1. If the current polygon has already been checked (or the maximum recursion level has been entered), return the current closest-distance-to-wall.
2. Find the closest point on each edge segment to the actor position. For every wall collision on this polygon, clip the position and update the current closest-distance-to-wall (and set the slide-against-wall vector if that wall collision is closer). For every edge that's inside the actor's “bounding circle” but isn't a wall, initiate a recursion on the adjacent polygon (updating the closest-distance-to-wall and slide-against-wall vector as needed).
3. Return the current closest-distance-to-wall.

Aikku said:
I'd thought of that, but decided that it might end up overly complicated. But thinking on it a bit more, maybe some sort of BSP tree could work if I end up going with that.

BSP is a cool concept, but it has serious downsides like complexity, lack of flexibility and hindering content creation. Looking back, maybe the Build engine avoiding this was the smarter way than the Doom engine.

Personally, i always thought of the ‘growing selection’ idea as a replacement for BSP to achieve drawing in front to back order. We could have a graph of convex polygons, and start Dijkstra from the polygon we're currently in. Then we could just draw further polygons as they are visited form the search algorithm, and the order would be correct. No need to preprocess the levels, no need to slice polygons, increasing their number.
Never tried this, though. But maybe the Build engine did it in a way like that.

Aikku said:
initiate a recursion on the adjacent polygon

Ofc. you can always replace recursive function calls with a loop, implementing things like a traversal stack. It's faster, and once you're used to it, it's usually more intuitive as well.

We could have a graph of convex polygons, and start Dijkstra from the polygon we're currently in. Then we could just draw further polygons as they are visited form the search algorithm, and the order would be correct

Huh, that's actually an interesting idea. It took me a few minutes to work through it, but it does sound simpler. I'd probably be paranoid about edge cases where there's two walls that are equidistant from the current search node, though.

implementing things like a traversal stack

… Okay, now that you've mentioned the magic words, that seems really obvious in hindsight. Thanks for that haha.