Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Rebrand Bevy XPBD and Switch Solvers #346

Closed
Jondolf opened this issue Mar 5, 2024 · 3 comments · Fixed by #397
Closed

Rebrand Bevy XPBD and Switch Solvers #346

Jondolf opened this issue Mar 5, 2024 · 3 comments · Fixed by #397
Labels
A-Dynamics Relates to rigid body dynamics: motion, mass, constraint solving, joints, CCD, and so on P-High This is particularly urgent, and deserves immediate attention

Comments

@Jondolf
Copy link
Owner

Jondolf commented Mar 5, 2024

I am making this as an early notice of major upcoming changes and to explain their rationale. There are important issues that need to be addressed, and I want to be as transparent as possible.

Within the next couple of months, we will attempt to transition away from Extended Position-Based Dynamics (XPBD) and rebrand bevy_xpbd. This involves a partial rewrite of the internals and a rename for the crate.

There is a lot of text here, so if you want to skip to how this might affect you, feel free to skip ahead to the Questions and Conclusion sections. For full context, however, I recommend reading on.

Why?

bevy_xpbd started as a small project with the idea of trying to build an ECS-first physics engine for Bevy using this shiny new simulation method called Extended Position-Based Dynamics. XPBD looked very promising and intriguing, providing great stability through an innovative substepping scheme and expressive position-based constraints.

However, as I've come to learn over the crate's development, using XPBD comes with several issues. Perhaps the most serious one is that XPBD is technically patented by NVIDIA.

There is no prior record of NVIDIA coming after projects using XPBD, and there are several existing open source implementations of it, but the patent still exists. This is a potential risk to me as the author of bevy_xpbd, people distributing projects using it, and to the ecosystem as a whole. bevy_xpbd can not be officially adopted by Bevy as long as it uses XPBD, nor can it be recommended by its maintainers. For the benefit of everyone involved, we must transition away from XPBD.

As an initial action, I have added a warning about this in the README that links to this issue. For projects using bevy_xpbd right now, there should be no reason to panic, but it is important to be aware of the legal concerns. While this is very unlikely to cause issues for smaller projects in practice, it is technically up to the user to have the rights to distribute the library in their works.

Aside from potential patenting issues, XPBD also has some problems on the simulation side of things.

  • Overlap is solved by pushing bodies apart at a position-level. This makes cases where bodies are constantly overlapping (like squished in a confined box) very energetic and potentially explosive.
  • Position-based constraints can often have high-frequency oscillation where bodies are always slightly moving back-and-forth. Looking up close, this can sometimes be noticeable. XPBD rarely (if ever) reaches a completely stable and relaxed state without sleeping.
  • Friction is typically not quite as robust as it is with impulse-based methods. There are several ways of handling it, some better than others, but it can still have some issues.
  • With the Gauss-Seidel approach to XPBD, the order in which constraints are solved can have quite a large impact on the end result.
  • Some features seem more challenging to implement, and there are fewer learning resources and references for the usage of XPBD in game physics.

Overall, XPBD does not seem like the right choice for Bevy's physics. Especially the legal implications can be considered to be a critical blocker for potential official adoption, and not worth the risks.

Why Now?

When I began working on bevy_xpbd, I was not yet aware of the patent. It was a small hobby project I was making for fun, and I never expected it to gain the traction it has.

Now, bevy_xpbd has become one of the most popular crates in the ecosystem, and is being used in more and more projects. It is becoming increasingly important to address the potential issues before serious projects using bevy_xpbd are released. This is a concern shared between me and the maintainers of Bevy itself.

In the early days of the crate, the XPBD part also played a larger role and was one of the core selling points. Nowadays, the focus has shifted more towards building a physics engine that specifically suits Bevy's needs and provides native ECS-like APIs. As such, the name bevy_xpbd is no longer as representative of the goals of the project, even though XPBD is still used internally.

The New Solver

We will switch XPBD to an impulse-based approach, the standard in the domain of physics simulation. The details are unclear as of now, but the most likely contender is what Erin Catto (the author of the Box2D physics engine) calls TGS Soft, or Temporal Gauss-Seidel Soft. It is an impulse-based solver with an XPBD-like substepping scheme and soft constraints, which add spring-like damping to constraint responses. It is also extremely close to the solver that Rapier recently switched to.

Does this mean worse stability in comparison to XPBD? No, it's most likely the opposite! Erin Catto compared solvers in his Solver2D project, and found that TGS Soft surpasses almost every other solver in nearly all tests, even beating XPBD in tasks it is supposed to be great at. His XPBD implementation did have some flaws, like incorrectly handled friction, but TGS Soft should definitely be a great replacement, and Rapier also saw substantial improvements with a similar approach.

I started initial experimentation with the solver a few weeks ago, and will continue to do so. I unfortunately have my matriculation exams this month, but after them, I will start seriously working on the solver rework.

Another option to consider is to try to make the solver easily swappable via plugins. This way, an XPBD solver could still be provided by a third party crate (with the appropriate warnings). This is a secondary goal however.

The Rebrand

As we will no longer be using XPBD, we will need to rename and rebrand the crate.

I have not decided on a name yet (edit: it will most likely be bevy_dynamics), but it will be something that is independent of the solver or other implementation details in order to avoid similar situations in the future. Feel free to leave suggestions!

One unfortunate side effect of this is that it will also impact third party crates that extend bevy_xpbd, like bevy-tnua-xpbd2d/bevy-tnua-xpbd3d by @idanarye, bevy_xpbd_interp by @rubengrim, and bevy_xpbd_3d_parenting by @ActuallyHappening. Once we rebrand bevy_xpbd, third party crates like these should also be renamed if they wish to support the new crate. I sincerely apologize for any trouble this causes.

How It Will Happen

I will briefly cover the steps that I plan on taking to make this solver switch and rebrand happen.

  1. Issue a warning in advance, and explain the plan. This is the purpose of this issue.
  2. Replace XPBD with another approach, most likely TGS Soft. This will hopefully happen by the end of April if all goes well, but I do not have a precise estimate.
    • This will require changes to the integrator, a rework of the solver and all constraints, and modifications to scheduling.
    • I will try my best to retain all existing functionality without regressions.
    • I will also make more examples to directly compare XPBD to the new approach.
  3. Update the documentation and README to reflect the changes, leaving a note about the rebrand for at least the first release of the new crate.
  4. Release a final version of bevy_xpbd, with a deprecation warning.
  5. Rename the repository and publish the first version of the new crate.
  6. Announce the rebrand everywhere: On Reddit, the Bevy Discord, my blog, and so on.

The rebrand is bound to cause confusion, which is why I am making this issue so far in advance. There will be a time period where people will continue to look for bevy_xpbd even after the rename, and we will just need to inform them of the rebrand.

I will also try my best to periodically share my progress in the Bevy Discord, both to promote the changes and to show where we're at. Feel free to ask me (@jondolfdev) anything there.


Questions

What does this mean for projects that use bevy_xpbd?

XPBD is patented by NVIDIA. There should be no reason to panic, but it is important to be aware of it. While it is very unlikely to cause issues for smaller projects in practice, it is technically up to the user to have the rights to distribute the library in their works. Just know that there are plans to address the issue in the coming months, so there should be no need to stop using bevy_xpbd for projects that are in development.

Once the rebrand happens, if all goes well, you will simply need to change the name of the crate. All existing functionality should remain the same. For any other changes that may happen, there will be a migration guide.

What does this mean for crates that extend bevy_xpbd?

bevy_xpbd will be renamed. Authors of crates with xpbd as part of the name will need to rename their projects if they wish to support the new crate. Similarly, xpbd feature flags should be changed to reflect the new name.

The structure of bevy_xpbd is also likely to change a bit, which might require minor modifications to some projects. There will be a migration guide to ease the migration.

What does this mean for the engine overall?

This should not be a downgrade, but rather the opposite! I am hopeful that the new solver will be better than XPBD, and it will make some new features and improvements easier to implement.

Transitioning away from XPBD will also remove one of the major blockers from having the physics engine as a potential option for an official Bevy physics integration some day in the future. Of course, there are still other blockers, like performance, some missing features, and a reliance on Parry, but it is a big step forward and should also make it easier to address some of the other issues.

Conclusion

To summarize: XPBD is patented by NVIDIA, and has characteristics that prevent it from being the best choice for physics in Bevy. Over the coming months, we will transition away from XPBD and rename the crate.

Projects in development may continue using bevy_xpbd in the meanwhile. Just be aware of the potential risks with distributing it, as it is technically up to the user to have the rights to do so.

This is an unfortunate situation, but something that is very important to address for the sake of everyone involved. Feel free to ask any questions here or on Discord, and thank you for your understanding.

@Jondolf Jondolf pinned this issue Mar 5, 2024
@Jondolf Jondolf added P-High This is particularly urgent, and deserves immediate attention A-Dynamics Relates to rigid body dynamics: motion, mass, constraint solving, joints, CCD, and so on labels Mar 5, 2024
@unwx
Copy link

unwx commented Mar 15, 2024

Is there any plan to use GPU for the physics engine? As I understand it, XPBD currently operates solely on the CPU, correct? Theoretically, this could significantly improve performance.

If so, at what stage of development is this? Looking at Bevy, they started using wgpu from the early stages of development. Would it be a good idea to take a similar step: a new solver (for example, TGS Soft) but focused on the GPU?

Bevy was built on wgpu from the very beginning, which meant most of the hard work of supporting WebGPU was already done

@entropylost
Copy link

@unwx using the GPU is most likely not worth it; unless the shape of the problem is very regular, aka colliding a bunch of spheres or something, it'd be really hard to make the GPU happy about the branching for colliding all the different shapes. Apparently, PhysX does so anyways, but I feel like there wouldn't be much benefit in any case. A system for simulating particle effects on the GPU may be valuable though, but that's beyond the scope of this crate.

@Jondolf
Copy link
Owner Author

Jondolf commented Jun 14, 2024

Hi! It's been a while, so here's a quick update on the state of things.

XPBD Patent

A while ago, we sent an email to NVIDIA asking about the legality of using XPBD to create an open source, MIT-licensed, physics simulation library. We actually got a response from Miles Macklin, one of the inventors of XPBD, who is also listed in the XPBD patent.


I don't believe there is any restriction here – you can already find many open source and commercial examples of XPBD implementations online.

The wording is a bit vague, but it is encouraging that it seems like using XPBD should be fine. Of course the patent is assigned to NVIDIA itself however, so I believe they technically hold the power (I am not a lawyer).

Either way, I'd like to transition away from XPBD even for reasons unrelated to the patent. The upcoming release still uses it for joints, because changing them to be impulse-based would delay things unreasonably, but the rest of the engine has already transitioned away from XPBD completely. In the future, I might also rework joints so that they don't use XPBD.

The Rebrand

The new name of Bevy XPBD will very likely be Avian Physics, or just Avian for short 🪶

My criteria for the ideal name were:

  • Related to physics or motion in some way (avian: relates to birds and flight).
  • Not tied to a specific physics implementation like bevy_xpbd was.
  • Unique and has its own brand identity. Like Bepu, Jolt, Havok, and so on!
  • Relatively short, ideally 4-6 characters.
  • Easy to pronounce and spell.
  • SEO-friendly and googleable.
  • Ideally has some kind of connection to Bevy, and relates to birds or flight 🐦
  • …but not strictly tied to it. Maybe one day we find a way to use the engine without the Bevy core and the ECS?
  • I just personally like the name and how it looks.

I had dozens (or even hundreds) of name ideas, most of which were already taken or only satisfied a few of these criteria. A bunch of community members also helped with great suggestions, thanks for all of them :)

After a couple of months(!) trying to come up with a name, I landed on Avian, because it fits basically all of these criteria perfectly. It's nice and short, not reserved by any existing projects, and overall just feels like a pretty natural name for a Bevy physics engine.

I have already designed a logo, with the help of other community members:

Avian banner logo

Of course, we could always spend more time bikeshedding names, but I'm personally very content with Avian.

Crate Naming

The new crates will be called avian2d and avian3d. I ditched the bevy_ prefix, because:

  • Again, maybe one day we find a way to use the engine without the Bevy core and the ECS?
  • A name like bevy_avian would sort of imply that it is a Bevy integration for an avian crate, not the core crate itself. Things could get confusing if someone else then made an avian crate.
  • 3rd party crate names don't have to be as long, and we could even have official sub-crates like avian_collision, avian_spatial, and avian_math (although in practice, these might just have their own names)
  • Several people stated they prefer names without the prefix. This is also not uncommon: big-brain, big_space, lightyear, leafwing-input-manager (and other Leafwing crates) are all Bevy plugins.

The repository and documentation will of course continue to mention that it is a crate for Bevy.

Release Strategy

My plans for the next release(s) are the following:

  1. Release Bevy XPBD 0.5 once Bevy 0.14 releases.
    • For the most part, this is just an update for the new Bevy version to help with migration, with no large new features or breaking changes.
    • This is already on the bevy-0.14 branch, but note that it currently depends on some forks and is not final.
  2. Release Avian 0.1 once Bevy 0.14 releases.
    • This has the entire rework with all the new features and changes.
    • There is already a WIP avian branch. I am in the process of making PRs targeting this branch to add all of my changes. Once everything is ready, I will merge avian to main, and the rebrand will be complete!

I recommend that third party crates for bevy_xpbd also rebrand accordingly to the avian naming once the crate is released.

Coming in Avian 0.1

The new crate has lots of cool new stuff! This includes:

  • A completely rewritten contact solver using impulse-based TGS Soft instead of XPBD.
    • Performance and stability are significantly better for collision-heavy applications.
    • A similar solver is used by Box2D V3, Bepu, and nowadays Rapier.
    • I hope to cover this in more detail in a future blog post.
  • A rewritten narrow phase.
    • Runs once per frame instead of once per substep. Results in huge performance gains for apps with several substeps.
    • Less allocations, overall better performance.
    • Several bugs related to collision events fixed, like Collision events are sent when not actually in contact #224.
    • More capable and cleaner, logic refactored to be a system parameter.
  • Speculative collision, a cheap but relatively robust form of Continuous Collision Detection (CCD).
    • Enabled for all bodies by default, eliminating effectively all tunneling with minimal performance impact. Any remaining overlap is due to contact softness.
    • Similar to Bepu and Box2D V3.
  • Opt-in sweep-based Continuous Collision Detection (CCD).
    • More expensive than speculative collision, but can be used as an additional safety net to prevent all tunneling.
    • Non-exclusive: can be used together with speculative collision.
    • Doesn't use substepping. This is cheaper, but can lead to "time loss", and doesn't handle secondary collisions properly.
  • Joint improvements
    • Improved stability. Several joints are less stretchy and have less high-frequency jitter.
    • Spherical joint limits are more capable. Elliptic cones and pyramidal limits!
    • (Hopefully) local frames, allowing you to specify reference orientations in addition to the local anchors.
  • A reworked module structure, with a clearer seperation of concerns.

And much more! There are still a few more things I need to work on, but everything should hopefully be ready in time for Bevy 0.14.

This is a packed release, and I still have a ton of further work planned. I haven't had as much time for general maintenance and responding to issues during this rework (sorry about that!) but I'll try to spend some more time on that after the release, along with opening lots of new issues.

As usual, I plan on writing up a migration guide and a blog post for the release when I have time. Stay tuned for more updates :)

Jondolf added a commit that referenced this issue Jul 1, 2024
…collision (#385)

# Objective

*Note: This is for the `avian` branch, which will later be pushed to `main`.*

Bevy XPBD currently uses Extended Position-Based Dynamics for its solver. While it has worked quite well, it does have several issues:

- Solving deep overlap is very energetic and explosive.
- Position-based constraints often have high-frequency oscillation where bodies are always slightly moving back-and-forth. XPBD rarely (if ever) reaches a truly stable and relaxed state without sleeping.
- A ton of substeps are needed for minimizing jitter and making systems of bodies stable.
- Friction is typically not quite as robust as it is with impulse-based methods. There are several ways of handling it, some better than others, but it can still have some issues.
- Many features can be more challenging to implement and expose APIs for, and there are fewer learning resources and references for the usage of XPBD in game physics.

Additionally, XPBD even has some potential legal ambiguities, see #346.

Aside from XPBD itself, there are also several other issues with the current collisions and rigid body dynamics:

- Narrow phase collision detection is run at every substep instead of just once per frame like most physics engines. This can be very bad for performance.
- There is no support for any kind of Continuous Collision Detection, so tunneling can be a big issue.
- It is not possible to configure the behavior of collisions aside from the number of substeps.
- #224
- Sleeping in 0.4 just doesn't work.

These are big issues, and I don't currently see XPBD as the best option for the contact solver going forward. Extensive rewrites and fixes are needed.

## Solution

This PR consists of three major parts:

- Rewrite the contact solver to use an impulse-based TGS Soft solver instead of XPBD.
- Rework the narrow phase and other collision detection logic.
- Implement speculative collision, a form of Continuous Collision Detection.

They all relate to each other, and are covered in detail below.

### Substepped Impulse-Based Solver With Soft Constraints

The contact solver has been rewritten to use **TGS Soft**, a substepped impulse-based solver using soft constraints. The choice was largely motivated by the wonderful Erin Catto's [Solver2D] experiments, where TGS Soft was deemed as quite a clear winner.

Box2D V3 was used as the primary inspiration for the core implementation of the new solver. Engines such as Rapier and Bepu also use a very similar approach.

#### Terminology

- **Projected Gauss-Seidel (PGS)**: The classic iterative approach to solving constraints (contacts and joints) using the [Gauss-Seidel](https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method) numerical method. Reframed by Erin Catto as [Sequential Impulses](https://box2d.org/files/ErinCatto_SequentialImpulses_GDC2006.pdf).
- **Temporal Gauss-Seidel (TGS)**: Same as PGS, but prefers *substepping* over *iteration*, running more simulation steps with smaller time steps rather than simply iteratively solving constraints. Substeps tend to be more effective than iterations, as shown in the [Small Steps in Physics Simulation](https://mmacklin.com/smallsteps.pdf) paper by Macklin et al.
- **Baumgarte stabilization**: When solving contact constraints using impulses, boost the impulses using a **bias** to account for overlap and actually push the bodies apart.
- **Soft constraints**: Similar to Baumgarte stabilization, but more stable and controlled. Based on the [harmonic oscillator](https://en.wikipedia.org/wiki/Harmonic_oscillator), soft constraints dampen constraint responses, and can be tuned intuitively with a frequency and damping ratio.
- **Warm starting**: Store the constraint impulses from the previous frame and initialize the solver by applying them at the start of the current frame. This helps the solver converge on the solution faster, and is especially helpful when objects are coming to rest.
- **Relaxation**: Baumgarte stabilization and soft constraints can add unwanted energy. Relaxation helps remove it by solving constraints a second time, but without a bias.

Please refer to the [Solver2D] post for a more complete overview of what TGS and soft constraints are, how they work, and how they relate to other approaches.

#### Solver Overview

As stated earlier, contacts use TGS Soft. However, joints still currently use XPBD, so the new solver is actually a kind of hybrid solver. I do plan on transitioning joints away from XPBD in the future though.

Below is a high-level overview of the new structure of the solver.

1. Broad phase collision detection collects potential collision pairs into `BroadCollisionPairs`.
2. Narrow phase collision detection computes contacts for the pairs and adds them to `Collisions`.
3. A `ContactConstraint` is generated for each contact manifold, and added to `ContactConstraints`.
4. Substepping loop, running `SubstepCount` times.
	1. Integrate velocities, applying gravity and external forces.
	2. Warm start the solver.
	3. Solve velocity constraints with bias (soft constraints).
	4. Integrate positions, moving bodies based on their velocities.
	5. Relax velocities by solving constraints again, but *without* bias.
	6. Solve XPBD constraints (joints) and perform XPBD velocity projection.
5. Apply restitution as a post-phase.
6. Finalize positions by applying `AccumulatedTranslation`.
7. Store contact impulses for next frame's warm starting.

Refer to the code for implementation details. The contact logic and constraints are quite heavily commented and should hopefully be relatively easy to follow.

#### New Solver Results

Collisions have significantly less drift than before, and performance is much better. Below is a pyramid with a base of 64 boxes, simulated with 4 substeps, with sleeping disabled.

**Old**: XPBD has substantial drift, and the pyramid quickly collapses in on itself. This even happens with a much larger number of substeps, although to a slightly lesser degree. Performance is very poor, even with just 4 substeps. 

https://github.com/Jondolf/bevy_xpbd/assets/57632562/ca0ff2f5-dfad-4395-a662-be41cdd7bfcf

**New**: With TGS Soft, the pyramid stays stable. There is a very small amount of drift over a long period of time, but even that can be mitigated by configuring the contact behavior through the `SolverConfig` and/or by adding more substeps.

https://github.com/Jondolf/bevy_xpbd/assets/57632562/a4a48e95-d8e9-459e-bfbb-26d0d12bb8ac

Impulses even out and stabilize *much* better with TGS Soft, even with deep overlap. In overlapping cases, the old XPBD implementation was significantly more explosive. Below is an example where colliders are dynamically enlarged to fill up a container.

**Old**: With XPBD, overlap causes explosions even before the shapes fill the container. Once they do fill the container, they jitter very strongly and explode through the walls. This is typically very undesirable for games.

https://github.com/Jondolf/bevy_xpbd/assets/57632562/e2d47c7e-b03a-45a7-93f9-8c5909564af0

**New**: Overlap is solved perfectly smoothly with no explosions. The contact impulses even out without jitter. With no space to go, the shapes prioritize stability over perfectly hard contacts that would cause explosiveness.

https://github.com/Jondolf/bevy_xpbd/assets/57632562/78f3d158-42a1-4841-b68d-3a6e3e06e451

An important thing to note is that the new solver uses several tolerances and thresholds that are length-based. The old solver also had some tolerances, but now they are much more important for stability.

Without any tuning, a 2D game using pixels as length units might have collision issues, because the tolerances would be wrong for that application. For example, below is a scene with stacks of balls that have a radius of 5.0, with no tuning whatsoever:

![No tuning](https://github.com/Jondolf/bevy_xpbd/assets/57632562/1e548a85-85ba-4811-9a92-b91ca8142927)

The contacts are too soft. To fix this, there is a new `PhysicsLengthUnit` resource, which can be thought of as a kind of pixels-per-meter conversion factor. It is only for scaling the internal tolerances (and debug rendering gizmos!) however, and doesn't scale objects or velocities in any way.

`PhysicsLengthUnit` can be easily set when adding `PhysicsPlugins` for an app:

```rust
fn main() {
    App::new()
        .add_plugins((
            DefaultPlugins,
            // A 2D game with 20 pixels per meter
            PhysicsPlugins::default().with_length_unit(20.0),
        ))
        .run();
}
```

And with that, we get the stability and behavior we expect:

![With the appropriate length unit](https://github.com/Jondolf/bevy_xpbd/assets/57632562/1a64fef5-539d-450d-96da-43fdbaceb430)

[Solver2D]: https://box2d.org/posts/2024/02/solver2d/

### Collision Detection Refactor

The narrow phase and the `PostProcessCollisions` schedule are now run in the `PhysicsSchedule` instead of the `SubstepSchedule`. This greatly improves performance, and also makes collision events and reacting to collisions less awkward and footgunny: previously, the contact data was always from the *last* substep, but at that point, the contact is often already mostly resolved.

Moving narrow phase collision detection out of the substepping loop is possible by simply storing contact data in local space and computing the updated separation distance at each substep using the current poses of the bodies. This way, the contact data is (approximately) accurate even with the bodies moving relative to each other within substeps.

A few other improvements have been made as well:

- The narrow phase logic has been extracted into a `NarrowPhase` system parameter.
- The broad phase now outputs intersection pairs with the entities in ascending order instead of based on the minimum X extent. This fixes issues where bodies moving past each other on the X axis counts as a separate collision, causing problems with collision events.
- #224 is fixed.
- The warnings logged for overlapping bodies have less false alarms.

### Speculative Collision

Tunneling is a phenomenon where fast-moving small objects can pass through thin geometry such as walls due to collision detection being run at discrete time steps:

![Tunneling](https://github.com/Jondolf/bevy_xpbd/assets/57632562/a7b6af19-caf1-4c72-9747-aa834e452e47)

Moving the narrow phase out of the substepping loop has the unfortunate consequence that it increases the risk of tunneling as collisions are not computed as frequently. A solution for this is needed before we commit to the narrow phase change.

One of the primary solutions to tunneling is **Continuous Collision Detection**. There are two common forms:

1. **Sweep-based CCD**: Each collider with CCD enabled is swept from the current position to the predicted one (or from the previous position to the current one). If a hit is detected, the bodies are moved to the time of impact. Contact resolution can be left to the next frame, or to avoid "time loss", performed immediately with a substepping scheme that can also consider secondary collisions.
2. **Speculative CCD**: Contact points are predicted by the narrow phase for fast-moving objects before they actually touch. Speculative collision response is handled by pushing back the part of velocity that would cause penetration.

Sweep-based CCD can be much more expensive and more complex, especially with substepping and non-linear sweeps. Speculative collision on the other hand is very cheap while still being quite robust, although in rare cases it can miss collisions or cause ghost collisions.

The new solver implements speculative collision, which is enabled for *all* bodies *by default*. In my experiments, this is efficient, improves stability, and eliminates almost *all* tunneling except when caused by contact softness. This approach seems to also be taken by both Bepu and Box2D.

Below is a high-level overview of how speculative collision is currently implemented.

- The speculative margin is the maximum distance at which a collision pair generates speculative contacts. This is unbounded for every rigid body by default, which eliminates almost all tunneling.
- Each AABB is expanded in the movement direction based on the body's velocity, clamped by the speculative margin if it is bounded. (Box2D might have a way to avoid this expansion, but I haven't looked into it yet)
- The effective speculative margin is the actual margin used for contact computation, and it is clamped based on the velocities. This is used as the maximum separation distance for contact / closest point computation.
- When actually solving the contact (normal part, no friction), use the softness parameters only if the contact is penetrating. Otherwise it is speculative, and we bias the impulse to cancel out the velocity that would cause penetration.
- Apply restitution in a separate phase after the substepping loop.

![Speculative collision](https://github.com/Jondolf/bevy_xpbd/assets/57632562/ba895617-4ee9-4a36-bc42-b5b6ebacac11)

From a user's point of view, this happens completely in the background. However, if desired, the speculative margin can be configured for an entity using the `SpeculativeMargin` component, or even globally using `default_speculative_margin` in `NarrowPhaseConfig`.

Below is an example of balls being shot at high speeds at thin walls and spinning objects, with just a single substep to eliminate the effect of substepping. The simulation is paused and stepped manually a few times to closer see the behavior.

**Old**: Almost all of the balls simply pass through the thin geometry. With more substeps, this tunneling could been reduced, but never removed completely. Increasing the substep count would also hurt performance.

https://github.com/Jondolf/bevy_xpbd/assets/57632562/03f9f623-0c5f-4228-a913-29bfaad23dc4

**New**: The balls never tunnel straight through the walls, and often even hit the spinning objects. You can still see many balls phasing through the walls, but this is mostly due to contact softness, in cases where a body hits another body hard enough to force it through the wall.

https://github.com/Jondolf/bevy_xpbd/assets/57632562/70526783-762a-452c-87fd-fe23789560f9

Of course, bodies getting pushed through the ground by other bodies is still an issue. This could be reduced in the future by solving contacts against static objects *after* dynamic-dynamic contacts, giving them higher priority and stiffness. This is follow-up material however, and cases where this is an issue should be quite rare in games.

Sweep-based CCD will also be added as an option in a follow-up. I already have an implementation ready locally.

## Performance Results

Comparing this branch to the `avian` branch (which still has the old solver), there is a roughly 4-5x performance improvement for collision-heavy scenes, with the difference growing with the number of collisions and the number of substeps.

The benchmarks below use 8 substeps.

![Benchmark with 8 substep](https://github.com/Jondolf/bevy_xpbd/assets/57632562/a369b674-5710-4c85-85ef-60e5585dafd7)

With just a single substep, the difference is smaller, but this branch is still faster, up to 2x.

![Benchmark with 1 substep](https://github.com/Jondolf/bevy_xpbd/assets/57632562/a753902b-99f4-4d5b-bfcc-a1852ae8cf3c)

## Other Changes

This is such a big rework that it is unfortunately almost impossible to cover every change. Below are some noteworthy changes however.

### Sleeping Rework

- Sleeping in 0.4 was broken, and bodies never fell asleep properly. This has been fixed.
- Bodies now store a `PhysicsChangeTicks` component. This is used to detect what component changes are made by the user *outside* of physics schedules, and what changes are made by the physics engine. This way, we can ignore changes made by the physics engine and have more control over when bodies are woken up.
- For now, bodies can only sleep when they are not in contact with other dynamic bodies. This is because the current per-body sleeping approach is quite buggy and has stability issues. In the future, I plan on implementing simulation islands and doing per-island sleeping like most other physics engines.

### Integrator Rework

- Velocity integration and position integration now run in separate systems and in different parts of the schedule: `IntegrationSet::Velocity` and `IntegrationSet::Position`. This is needed for the new solver.
- The semi-implicit Euler integration scheme now has its own module with proper docs and tests.
- Integration uses `par_iter_mut`.

### Scheduling Changes

- `PhysicsStepSet` now has `First` and `Last` variants, so users can easily schedule systems before or after physics in the `PhysicsSchedule`.
- The narrow phase and the `PostProcessCollisions` schedule are now run in `PhysicsStepSet::NarrowPhase` instead of `SubstepSet::NarrowPhase`.
- Integration is now run in `IntegrationSet::Velocity` and `IntegrationSet::Position` instead of `SubstepSet::Integrate`.
- `SubstepSet` has been removed.
	- The solver runs in `PhysicsStepSet::Solver`.
	- The solver's system sets are in `SolverSet`.
	- Substepping is performed in `SolverSet::Substep`.
	- The substepping loop's system sets are in `SubstepSolverSet`.

### New Configuration Options

- `NarrowPhaseConfig` has new `default_speculative_margin` and `contact_tolerance` properties.
- The new `SolverConfig` resource can be used for tuning collisions.
- The new `PhysicsLengthUnit` resource can be used as a scaling factor for internal length-based tolrances.
	- Existing length-based tolerances and thresholds are now scaled by this, like the `linear` property of `SleepThreshold`.
	- Debug rendering is also scaled by the length unit.

### Examples

- `XpbdExamplePlugin` has been renamed to `ExampleCommonPlugin`, and it no longer adds `PhysicsPlugins` automatically.
- 2D examples have `PhysicsLengthUnit` configured.
- The `one_way_platform` example's logic has been modified to account for `PostProcessCollisions` no longer running in the `SubstepSchedule`.
- The collision logic for the kinematic character controller examples has been rewritten to run in the `PhysicsSchedule` without jitter or stability issues.

### Miscallaneous

- `ColliderAabb` now has the `grow` and `shrink` methods.
- `ContactData` now stores feature IDs for contact matching, which is needed for warm starting.
- `ContactData` property `index` has been removed.
- 3D tangent impulses are now 2D vectors instead of scalar values.

---

## Migration Guide

### New Contact Solver

The contact solver has been rewritten. In practice, this has the following effects:

- Collisions should be much more stable.
- Resolving overlap is no longer nearly as explosive.
- Less substeps are generally needed for stability.
- Tunneling is much more rare.
- Performance is better.

However:

- Contacts may even be *too* soft by default for some applications. This can be tuned with the `SolverConfig`.
- Static friction is currently not considered separately from dynamic friction. This may be fixed in the future.
- Restitution might not be quite as perfect in some instances (this is a tradeoff for speculative collision to avoid tunneling).
- 2D applications may need to configure the `PhysicsLengthUnit` to get the best stability and behavior.

The `PhysicsLengthUnit` can be thought of a pixels-per-meter scaling factor for the engine's internal length-based tolerances and thresholds, such as the maximum speed at which overlap is resolved, or the speed threshold for allowing bodies to sleep. It does *not* scale actual physics objects or their velocities.

To configure the `PhysicsLengthUnit`, you can insert it as a resource, or simply set it while adding `PhysicsPlugins`:

```rust
fn main() {
    App::new()
        .add_plugins((
            DefaultPlugins,
            // A 2D game with 20 pixels per meter
            PhysicsPlugins::default().with_length_unit(20.0),
        ))
        .run();
}
```

### Custom Constraints

Custom constraints using XPBD are currently still possible. However, the traits and systems are now located in the `dynamics::solver::xpbd` module, and users should run `solve_constraints` in `SubstepSolverSet::SolveUserConstraints` instead of `SubstepSet::SolveUserConstraints`.

### Scheduling Changes

Several scheduling internals have been changed. For example:

- The narrow phase and `PostProcessCollisions` schedule are now run in `PhysicsStepSet::NarrowPhase` instead of `SubstepSet::NarrowPhase`.
- Integration is now run in `IntegrationSet::Velocity` and `IntegrationSet::Position` instead of `SubstepSet::Integrate`.
- `SubstepSet` has been removed.
	- The solver runs in `PhysicsStepSet::Solver`.
	- The solver's system sets are in `SolverSet`.
	- Substepping is performed in `SolverSet::Substep`.
	- The substepping loop's system sets are in `SubstepSolverSet`.

Systems running in `PostProcessCollisions` may need to be modified to account for it being moved outside of the substepping loop.
Jondolf added a commit that referenced this issue Jul 5, 2024
Closes #346.

The `avian` branch has been used for developing a lot of the features for the next evolution of Bevy XPBD, **Avian Physics**. This PR merges the numerous improvements and reworks to `main`, completing the rebrand. See #346 for background.

Note that some other changes were already merged to `main` in separate PRs.

After this is merged, I will:

- Rename the repository to "avian"
- Do a quick final pass to make sure there are no obvious issues or regressions
- If everything is fine, release `avian2d` and `avian3d`
- Add release notes and a migration guide here on GitHub (I have them ready to go)
- Post a more in-depth blog post on my website (I have it ready to go)
- Post about the release on Discord and Reddit
@Jondolf Jondolf unpinned this issue Jul 6, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-Dynamics Relates to rigid body dynamics: motion, mass, constraint solving, joints, CCD, and so on P-High This is particularly urgent, and deserves immediate attention
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants