Character controller crossing seams

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
lidgren
Posts: 21
Joined: Mon May 27, 2019 6:28 pm

Character controller crossing seams

Post by lidgren »

Hi! I'm using the character controller from the demos and I've ran into a problem... I've added physics for my environment in a gridlike fashion; and when running around on a "grid cell" (which is a static box shape) it's all fine; but when crossing the line into a new cell, which has the same floor height as the previous one; the controller loses "support" briefly (well, actually for 5-10 60hz frames) and makes the character wobble up and down. I realize this must be because we lose support of the current cell and "fall onto" the next cell, which takes time. I'm at a loss on how to solve this tho... it looks like any penetration depth will provide support, yet it seems to fall deep enough into the next static object to create an upward reaction.
Any tips on what to do?

--michael
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Character controller crossing seams

Post by Norbo »

Seams in separate objects are a tricky business. When the capsule moves near the seam, it's possible for contacts to be generated with a nearby box such that the normal does not point perfectly vertically as it would on a single flat surface. That misaligned normal can redirect the character's motion upward, causing a little jump.

In an ideal world, you could check each contact against all other nearby geometry (or something mathematically equivalent), and correct or remove the contact if the normal violates the full surface. That's what meshes do- every triangle in the vicinity of a contact has a chance to say 'no, that contact normal could not actually be created because it would violate the assumption of a single continuous surface'. It's relatively cheap and easy to do that analysis for meshes since you've already got all the triangles you need in cache and the logic can be vectorized pretty easily.

Doing a similar analysis across all object types for all objects around any contact is technically possible, just computationally difficult. I have some ideas for this (at least for things like compounds), but I won't be able to get to it in the near future.

So that leaves mitigations:
1) Reduce the grid body and character body speculative margins. Speculative contacts generated too far from the character are more likely to point in wonky directions. If the character's moving fast relative to the timestep duration, then one of those wonky normals could end up having an effect in the solver, causing a more significant jump. Downside: this won't 100% fix the issue, just reduce it, and you get less automatic continuous collision detection so you might need to turn on explicit CCD for the character, for example:

Code: Select all

new CollidableDescription(shapeIndex, speculativeMargin, ContinuousDetectionSettings.Continuous(0.0001f, 0.0001f))
2) Replace the box grid with a single mesh. The mesh boundary smoothing will eliminate bad normals and there won't be a bounce.
3) Add a bounding box expansion to CharacterControllers.PrepareForContacts so that the bounding box doesn't stop overlapping with the ground during the bounce, preserving support and the movement constraints so long as MinimumSupportContinuationDepth is high enough. It doesn't get rid of the bump, but the constraints could mitigate it.

I'll do #3 in a minute.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Character controller crossing seams

Post by Norbo »

lidgren
Posts: 21
Joined: Mon May 27, 2019 6:28 pm

Re: Character controller crossing seams

Post by lidgren »

Thanks! I tried the patch and continuous detection; and altho it feels slightly better, it's still noticable; and empirically there still seems to be about the same amount of unsupported frames (5-10 at 60hz) when crossing a seam. It'll do for now and I might look into merging the floor cubes later on (they're all static).
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Character controller crossing seams

Post by Norbo »

Hmm- with the patch and a suitable MinimumSupportContinuationDepth, there should be no unsupported frames if boundary seams are actually the problem. In the demos there are no unsupported frames across boxgrid seams with it. It may still move vertically a little bit, but significantly less and the Supported flag should remain true throughout.

Is the MinimumSupportContinuationDepth being set to a large enough magnitude? Notably, since it's a minimum depth, it needs to be negative to allow continuing support during separation.

Edit:
Also, the MinimumSupportContinuationDepth will only do anything up to the same magnitude as the character shape's speculative margin. The demos CharacterInput just set MinimumSupportContinuationDepth = -speculativeMargin for that reason.
lidgren
Posts: 21
Joined: Mon May 27, 2019 6:28 pm

Re: Character controller crossing seams

Post by lidgren »

For posterity; I didn't solve the problem; but increasing the radius of the capsule to the same as the demo (0.5) instead of what I previously used (0.15) helped a great deal; and only a handful of frames or less are unsupported.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Character controller crossing seams

Post by Norbo »

Hmm... with the latest master, I still don't observe it in the demos with 0.15 radius. There still might be something wonky going on that would be worth tracking down. If you can get it to happen in the demos (with an appropriate speculative margin/MinimumSupportContinuationDepth/vertical glue force), that'd be very useful information.
jens
Posts: 3
Joined: Mon Apr 06, 2020 8:58 am

Re: Character controller crossing seams

Post by jens »

Hi there!

I'm currently integrating BepuPhysics into my game Blockscape and I have the same problem. It is quite a big issue I must say. In Blockscape you play in a procedurally generated world made out of small blocks. The world is a big octree where the smallest nodes are 8^3 meters in size. To make this discussion simple we can say that each node equals one static mesh in Bepu. Now if you drive a car in this landscape it will jump like crazy every time the car crosses a node (static mesh) border.

edit: Using Continuous collision detection helps a bit but it's still not acceptable. SpeculativeMargin seems to have no effect.

best regards
Jens
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Character controller crossing seams

Post by Norbo »

Yup, a bunch of relatively small separate meshes interacting with high speed objects is close to worst case for a lack of boundary smoothing.
SpeculativeMargin seems to have no effect.
Is that after modifying both the mesh and the problematic objects interacting with the mesh? The effective speculative margin of a pair is the max of each member of the pair. To see a change, you'll need to set both to values closer to 0. (This is not without tradeoffs, of course, so it's not the solution I would want to rely on in the long term.)

There is no easy and high quality solution for that specific use case right now. Usually I'd recommend bundling more geometry into a single mesh so you get boundary smoothing, but that's harder for a game with streaming dynamic geometry.

Elaborating on some of the things I mentioned earlier, there are a few classes of solution:
1) Use contact callbacks to modify the normals of manifolds or reject the contacts outright. You can get a sorta-okay solution with heuristics sometimes, but getting all the way to robust behavior is complex (see MeshReduction). Common failure modes in halfway solutions are not getting rid of all the bumps or just letting objects fall through the world.
2) Combine more geometry into a single Mesh to allow MeshReduction to eliminate all bumps. Wouldn't be able to use the default constructor anymore; the sweep builder would be too slow. It would likely involve constructing per-node subtrees, inserting those subtrees into the Mesh tree, and running incremental refinement on the top level tree-of-subtrees as geometry is added/removed/changed. Done properly, this would let you store the entire geometry in a single Mesh efficiently.
3) Create a custom collidable with a layout compatible with the streaming/dynamic content and use the MeshReduction on its output.
4) Create a version of Mesh which is aware of adjacent border triangles and can use them as a part of MeshReduction to prune out surface-violating contacts. This would look like redundant triangles that don't generate contacts, but are included in the MeshReduction process.
5) Create a top-level contact post-processing step that examines every collidable that could conceivably overlap a contact. Perform a general purpose version of the mesh reduction across all collidables. Most forms introduce significant overhead, so it'd have to be some opt in process.

All of these things could be done by an enterprising user, but they're pretty difficult. As far as my own plans go:
1) The long term plan does include something like a combination of 2, 3 and 4. Not sure when, >>2 months.
2) #5 is an interesting research project I'd like to fiddle with, but it's kind of hard to justify working on in the near term when there's so much else to do. Wouldn't expect to see it this year.
3) A Tree builder/refinement revamp that would make #2 easier is in the relatively near term plans- <2 months is possible.
jens
Posts: 3
Joined: Mon Apr 06, 2020 8:58 am

Re: Character controller crossing seams

Post by jens »

Norbo wrote: Tue Apr 07, 2020 8:02 pm Yup, a bunch of relatively small separate meshes interacting with high speed objects is close to worst case for a lack of boundary smoothing.
SpeculativeMargin seems to have no effect.
Is that after modifying both the mesh and the problematic objects interacting with the mesh? The effective speculative margin of a pair is the max of each member of the pair. To see a change, you'll need to set both to values closer to 0. (This is not without tradeoffs, of course, so it's not the solution I would want to rely on in the long term.)
Ah! In my tests I only modified the dynamics margin. Modifying the static as well does have an effect! A very small margin helps quite a bit.
Norbo wrote: Tue Apr 07, 2020 8:02 pm There is no easy and high quality solution for that specific use case right now. Usually I'd recommend bundling more geometry into a single mesh so you get boundary smoothing, but that's harder for a game with streaming dynamic geometry.
What does more geometry mean in this case? Bigger world nodes so that crossing borders happens less often? Or is there a way to create som kind of "skirt" that would help the solver?
Norbo wrote: Tue Apr 07, 2020 8:02 pm Elaborating on some of the things I mentioned earlier, there are a few classes of solution:
1) Use contact callbacks to modify the normals of manifolds or reject the contacts outright. You can get a sorta-okay solution with heuristics sometimes, but getting all the way to robust behavior is complex (see MeshReduction). Common failure modes in halfway solutions are not getting rid of all the bumps or just letting objects fall through the world.
Please forgive me if I have no idea of what I'm talking about now but what would happen if you always use the face normals as is? I could see that you would sometimes get strange normals if the terrain was made out of something like boxes but faces are infinitely thin so why would you change the normals?
Norbo wrote: Tue Apr 07, 2020 8:02 pm 2) Combine more geometry into a single Mesh to allow MeshReduction to eliminate all bumps. Wouldn't be able to use the default constructor anymore; the sweep builder would be too slow. It would likely involve constructing per-node subtrees, inserting those subtrees into the Mesh tree, and running incremental refinement on the top level tree-of-subtrees as geometry is added/removed/changed. Done properly, this would let you store the entire geometry in a single Mesh efficiently.
3) Create a custom collidable with a layout compatible with the streaming/dynamic content and use the MeshReduction on its output.
4) Create a version of Mesh which is aware of adjacent border triangles and can use them as a part of MeshReduction to prune out surface-violating contacts. This would look like redundant triangles that don't generate contacts, but are included in the MeshReduction process.
5) Create a top-level contact post-processing step that examines every collidable that could conceivably overlap a contact. Perform a general purpose version of the mesh reduction across all collidables. Most forms introduce significant overhead, so it'd have to be some opt in process.

All of these things could be done by an enterprising user, but they're pretty difficult. As far as my own plans go:
1) The long term plan does include something like a combination of 2, 3 and 4. Not sure when, >>2 months.
2) #5 is an interesting research project I'd like to fiddle with, but it's kind of hard to justify working on in the near term when there's so much else to do. Wouldn't expect to see it this year.
3) A Tree builder/refinement revamp that would make #2 easier is in the relatively near term plans- <2 months is possible.
Interesting stuff here. Thank you for the very detailed answer!
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Character controller crossing seams

Post by Norbo »

What does more geometry mean in this case? Bigger world nodes so that crossing borders happens less often? Or is there a way to create som kind of "skirt" that would help the solver?
I was referring to larger nodes (or one single giant mesh), yes.

A skirt could help in some cases- if some extra geometry dropped below the 'real' geometry, it would block contacts that would violate the skirt surface. Of course, generating such a skirt that doesn't interfere with adjacent geometry would be difficult and sometimes impossible.
Please forgive me if I have no idea of what I'm talking about now but what would happen if you always use the face normals as is? I could see that you would sometimes get strange normals if the terrain was made out of something like boxes but faces are infinitely thin so why would you change the normals?
Face normals would work okay for concave surfaces, but it would break convex surface collisions:
convexborderissue.png
convexborderissue.png (4.4 KiB) Viewed 19981 times
The 'true' normal, in black, would be changed to one of the red normals instead. It would create some nasty hitchy behavior.
lidgren
Posts: 21
Joined: Mon May 27, 2019 6:28 pm

Re: Character controller crossing seams

Post by lidgren »

Would it be possible to create a shape that would always return a (physically inaccurate) normal of, say, upwards, regardless of point of collision? It's not a solution per se, just spitballing ideas.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Character controller crossing seams

Post by Norbo »

Yup, you could. For a heuristic that simple, you could also use the contact callbacks to modify the normal.
Post Reply