Gnollrunner said:
We are apparently giving advice about two different algorithms.

Yes. But you can make a good character controller with allowed penetration - it's not a bug.
And my proposal is not related to physics simulation either. No velocities or forces - just minimizing penetration.

So it's up to anyone to make a choice. I have used both methods in the past and can't tell any general preference. Both have their limitations, issues and devils in the details.

Physics engines mostly use a mix both methods.
For example, if we only do sweeping along movement to prevent collisions, such method has no way to resolve penetrations in case they happen anyway (which they will). If a penetrating body has zero velocity, there is no point in time to find where the collision happened, so a pure sweeping method will not resolve the penetration.

So you always need to deal with penetration in a non physical way, e.g. by separating intersecting bodies slowly but not affecting velocity or generating forces eventually.
Basically a hack, necessary because in practice you can't guarantee to avoid penetrations.

What we mostly see is sweeping actually only used if an optional Continuous Collision Detection feature is enabled. That's expensive, and usually only used for fast moving bodies. Iirc, Bullet for example always uses the approximation of treating any body like a sphere for its CCD feature, so not very accurate.
The most important way to deal with collisions is indeed a set of multiple contact points, and each contact has some penetration going on, which it tries to minimize, similar to how i proposed. But ofc. solving for contact forces of multiple dynamic bodies trying to respect laws of physics is much harder then our proposals here.

However, afaict pretty any game engine implements its character controller using its physics engine, because it already exposes all required and optimized functionality.
Stand alone Physics Engines also usually have a character controller built in. It's a standard feature. So i don't agree with sweeping being the general way to handle collisions for character controllers, which usually move rather slowly.
But they are not purely physical either. Mostly they are implemented using kinematic bodies, giving more control about how it feels, how they interact with other dynamic bodies, etc.
It's also common to gather a set of nearby faces, and using raytracing sensors to prevent collisions from happening, or to handle difficult movement like stepping stairs.

So it's a mix of various things, and implementations differ a lot across games if we go into details.
There surely is no point to argue which methods are better or what we should or shouldn't recommend. Sharing some things which worked for us is all we can do.

Gnollrunner said:
To the OP: If you are doing something more akin to a physics engine you should probably ignore my posts. However, sweeping spheres and/or capsules does work very well for a character controller and it's very smooth once you get the bugs out.

Yeah, for my character controller, I'm going with the sweeping(a capsule) approach, like you said, normally I don't allow penetration to happen.

But, penetrable or not, I think to solve the “jittering” problem for which I started this thread, the most important aspect that I'm missing is brought up by both of you guys, that is to consider all contacts(or possible contacts) simultaneously. I've never thought about this before, what I had in mind was to predict the jittering trajectory and apply some smoothing algorithm to it, for which now I realized is pretty off track. Actually, I think the “Touching List” concept is quite applicable to the implementation I had so far.

@JoeJ Well I'm not going to really get into a rat's nest discussion. The OP is writing his own collider of some sort. If he's sweeping spheres (multiple spheres, ellipses or capsules) , what I suggested works for multi geometry collisions because I've implemented it and tested it. I'm not trying to give him a bunch of random stuff I've never tried myself. If he's doing something else, then good luck.

JoeJ said:
The Minkowsky Sum approach would be useful for example in a Billiard game

Okay, quite a comprehensible example. Pretty interesting concept.

zzaustin said:

Actually, I think the “Touching List” concept is quite applicable to the implementation I had so far.

OK, well if any more questions pop up you can ask them here. Good luck.

Gnollrunner said:
what I suggested works for multi geometry collisions because I've implemented it and tested it.

I do not understand your proposal well enough so i could implement it. There are some flaws on explanation, e.g. the cross product of the two normals in our narrowing corner example would give a direction tangent to the expected. To get a proper blocking normal we would need to do another cross with some ‘forward direction’ (e.g. the movement)?
And second, this would tell me about about a blocking direction, but still not about a blocking obstacle position, which we need as well?

I'm curious, but those questions bother me each time this topic comes up here.
Can you explain your algorithm using the example of the narrowing edge?
To simplify the example, let's replace it with a angled ceiling like this:

How do you prevent the character from creeping towards the corner so it gets stuck?

JoeJ said:

How do you prevent the character from creeping towards the corner so it gets stuck?

You are looking at a 2D example which does not make sense. In this 2D example the character goes as far as it can and then it will be stuck as it should be. In a 3D example the force needs to be skewed slightly one way or the other (in or out of the screen) or else again the character would stop (again as it should). If the force is skewed it moves at the cross-product of the normals of the planes or the reverse direction. You do a dot-product of the force vector and the aforementioned cross-product, to determine if you have to flip the vector.

This also gives you the correct velocity. For example, if you go straight into a wall or (a crevice for the double plane collision) you will in fact stop. If you are at a slight angle, you go slightly to one side. A very oblique angle gives you much more movement.

Gnollrunner said:
You are looking at a 2D example which does not make sense.

Why would it make no sense? It's the very first test case i use for such things.
Ok, i've drawn it in 3D:

If the character moves to the left, how do you calculate it can't go any further, and which direction of movement is allowed and which not? (Assuming your approach is about preventing penetrations with a guarantee.)

The cross product of the normals points along the Z direction from our view. I tried to visualize this with a cylinder at some perspective. So this does not help.
If we take another cross of that with each of the the normals again, we would get proper blocking directions pointing to the right. So eventually you clip velocity with both those planes, which would prevent further movement to the left.
But then, if the player keeps pushing but also nudges along the Z direction, he likely will be able to drift further towards the left corner.
And if he tries to get back, the algorithm will block this direction as well, since there are still the same two collisions happening, but your ‘force vector’ is reversed. Then the player is ‘stuck’ and can't move anywhere?

I also wonder what you do if there is only contact, so just one normal and the whole idea makes no more sense at all.
Or what if there are 3 contacts, and we can't take a cross product from 3 normals.

So there must be more to your approach to make it work, or likely i just get it completely wrong…

JoeJ said:

Ok, i've drawn it in 3D:

If the character moves to the left, how do you calculate it can't go any further, and which direction of movement is allowed and which not? (Assuming your approach is about preventing penetrations with a guarantee.)

I seriously don't understand your issue. If the ball is being pushed directly left, it's stuck. What else would it do? It hits both planes. It may hit the top plane first and move along it, or the bottom first and move along that, but eventually it will hit both, and since the force vector is directly left it can't move at that point. That exactly what we want. Now assuming X is left-right, Y is up-down, and Z is in-out of the screen, if the force is generally left but there is some Z component to it, it has to slide in towards the camera or away from it. Note the Z axis is along the cross-product of the two plane normals so it's moving along the that vector which is the cross-product of the normals. So what exactly is the confusion?

The cross product of the normals points along the Z direction from our view. I tried to visualize this with a cylinder at some perspective. So this does not help.
If we take another cross of that with each of the the normals again, we would get proper blocking directions pointing to the right. So eventually you clip velocity with both those planes, which would prevent further movement to the left.

Anytime the contact point on the ball, to ball center vector, opposes the force vector we can't go that direction. It doesn't have to oppose it directly, just with 90 degrees. Normally we calculate the new response path as the OP showed in his first post. But we can't exactly do that here. Let's say we consider the bottom plane. We contacted it and we are moving parallel to it. Then we contact the top plane. Moving parallel to either plane still doesn't let us move since each is blocked by the other, so we are ostensibly stuck. But before we give up, we try the cross-product. Unless our force is directly down the negative X axis the dot-product of the force vector with the cross-product (normalized) will give us our movement distance.

The only issue is since the cross-product can give us a vector either in or out of the screen depending on the order we selected the planes, we have to make sure to compensate for that, which is fairly trivial. In fact, the dot product will let us know as it will give a negative answer if it's pointing the wrong way. So now we can move since we have a direction and distance, and it will be clear of both planes.

But then, if the player keeps pushing but also nudges along the Z direction, he likely will be able to drift further towards the left corner.

No, he slides in or out of the screen. You can't move though geometry when sweeping a sphere. The same thing as I wrote above applies if he keeps pushing.

And if he tries to get back, the algorithm will block this direction as well, since there are still the same two collisions happening, but your ‘force vector’ is reversed. Then the player is ‘stuck’ and can't move anywhere?

No, when you move, you ignore touching geometry that doesn't block the force vector. There is a contact vector associated with touching geometry. It's not like glue.

I also wonder what you do if there is only contact, so just one normal and the whole idea makes no more sense at all.

Come on, that's the easy case. The OP drew that in his first post, and you drew it too. How can it be you don't get it now.

Or what if there are 3 contacts, and we can't take a cross product from 3 normals.

I alluded to that in an earlier post. In more detail the general algorithm is to check pairs of touching geometry. So you have two cross-products in that case. If the 3rd contact in the touching list is blocking the cross product of the other two, you are still blocked as you should be. If both cross products are available, you simply do dot-products with the force vector and find the one that is the closest match.

So there must be more to your approach to make it work, or likely i just get it completely wrong…

There are some details, but I thought it was obvious if you know about the sweep algorithm, that you can't move through geometry. You of course always check all geometry along the path you are going. That's kind of standard. There are no special vector projections for corners or anything like that. My addition simply takes care of multi-geometry collision response, and I would assume other people do similar things. There is no other difference from the standard sweep.