freezy
Physics: Make collision model dynamic
Currently, all objects in the physics world except the balls are static, i.e. they can't move. It would be great if VPE could support movement of collidable objects.
At the same time, there are still performance bottlenecks, for example rolling over a dropped target or the (currently deactivated) non-legacy kicker make the simulation stutter.
So how can we add more complexity and make it faster at the same time? Well, that's the challenge of this issue. ;)
Status Quo
Let's start with how the simulation currently works. When starting play mode, VPE creates colliders from all the collidable objects and indexes those colliders with a Quadtree. A quadtree is a spatial index method which allows to quickly find overlaps of two-dimensional boxes. This is important for the first phase, the broadphase.
During gameplay, the simulation needs to find out with which object each ball collides next. Instead of looping through all colliders, the broadphase serves to discard the majority of colliders by looking at their axis aligned bounding boxes (AABB) and overlap them with the ball's bounding box (more precisely, the balls's AABB plus its velocity vector). For this, the quadtree is used.
Once the number of potential colliders is reduced, the exact time of impact is calculated. This is called the narrowphase. The goal here is to find the actual collider the ball collides with next and the time it collides.
If the time is smaller than maximal phyiscs time (1/1000 th of a second), the engine is sure that the collision would happen within the next cycle. It then changes the next execution time from 1/1000th of a second to exactly the time, the collision happens (based on current velocities), as long as the time is not ridiculously small (it then sets the time to the current time plus a very small timestep (this seems to be some kind of deadlock protection)).
In the next cycle, it then checks if the ball is near a wall with velocity to the wall (hitting) and then performs the hit the collision is applied, which means the ball changes velocity and direction depending on the collider's attributes.
Apart from the quad tree generation, all the above is done in each simulation step. Currently, we run at 1kHz, so a thousand steps per second. This happens once per frame, where we simulate all the steps of the time passed since the last frame.
Note that all of the above only concerns ball/object collision. Ball/ball collision is a separate loop and uses an octree index (the 3D version of the quadtree). In the code, the Static* classes are used for ball/object, and the Dynamic* classes for ball/ball collisions. In the dynamic loop, the octree generation is part of each step.
So you see that the difference between dynamic and static is that for the static simulation, the spatial index is only created once, while dynamic simulations either re-create the index every step or update it. Then it goes as usual into broadphase, narrowphase and collision.
Improvements
Based on the above, it should be clear that in order to make collisions dynamic, we need to work on the spatial index. Not doing anything is always faster than doing something, so I would start by letting the user define which objects are static and which ones can move, to limit the size and computation time of generating and updating the index.
We would then have three loops:
- Dynamic (ball/ball)
- Semi-dynamic (ball/movable objects where the objects don't collide among themselves)
- Static (ball/fixed objects).
The question is which index method to use. I don't think using the current quadtree implementation is feasible. It would just slow down every step even more, and as mentioned in the beginning, we're already above budget.
Here are the options I've been looking at so far:
Use a different quadtree
I've found marijnz/NativeQuadtree. It also uses DOTS and seems a lot faster than what we have today. There is a experiment_rects branch that supports AABB matching. This seems like the easiest approach, basically a drop-in replacement for what we have now (incomplete integration here).
It's probably not the most stable solution though, because the project is very young and not a lot maintained. Maybe there are other (native) quadtree libraries with a more mature base.
Use a different indexing method
There are other spatial indexing methods such as BVHs. There's a good overview on this SO post. Unity's new DOTS physics package is based on that. It might be worth looking at, since it's based on DOTS as well.
I've posted in the forum a while ago about freeing up the APIs, which they said they would if we were to provide more details, which I haven't been able to do yet (DOTS hasn't seen a release in almost a year now, so I doubt that it would have changed). So we'd have to clone Unity's physics package and do the changes ourselves until they go upstream.
There is also marijnz/NativePhysicsBVH from the same author mentioned above, also based on DOTS.
And of course, there might be other native packages that would do the job as well.
Replace broadphase and narrowphase by DOTS physics
DOTS physics is Unity's new physics engine that ships with DOTS. If you read through the Design Philosophy, it looks exactly what we're looking for.
We might be able to build on DOTS physics, i.e. generate our own colliders (maybe even only partially), let Unity handle broad- and narrowphase, and use our code for collision. This is the most complicated approach, but probably the most stable and performant.
Profiling
To confirm that the static broadphase is indeed one of the main bottlenecks, here a screenshot of the profiler during a ball rolling over a dropped target:
Obviously all results should be validated by the profiler, so getting into how the profiler works is part of this issue as well.
The Status Quo is not fully correct, I think: (from Freezy:)
[...] Once the number of potential colliders is reduced, the exact time of impact is calculated. This is called the narrowphase. The goal here is to find the actual collider the ball collides with next.
When that collider is found, the collision is applied, which means the ball changes velocity and direction depending on the collider's attributes.
Apart from the quad tree generation, all the above is one simulation step. Currently, we run at 1kHz, so a thousand steps per second. This happens once per frame, where we simulate all the steps of the time passed since the last frame. [...]
Correct in my opinion (AFAIK):
Once the number of potential colliders is reduced, the exact time of impact is calculated. This is called the narrowphase. The goal here is to find the actual collider the ball collides with next and the time it collides.
If the time is smaller than maximal phyiscs time (1/1000 th of a second), the engine is sure that the collision would happen within the next cycle. It then changes the next execution time from 1/1000th of a second to exactly the time, the collision happens (based on current velocities), as long as the time is not ridiculously small (it then sets the time to the current time plus a very small timestep (this seems to be some kind of deadlock protection)).
In the next cycle, it then checks if the ball is near a wall with velocity to the wall (hitting) and then performs the hit the collision is applied, which means the ball changes velocity and direction depending on the collider's attributes.
Apart from the quad tree generation, all the above is done in each simulation step. Currently, we run at 1kHz, so a thousand steps per second. This happens once per frame, where we simulate all the steps of the time passed since the last frame. [...]
I corrected this because this has a high impact on how to handle dynamic collisions. We would have to take the velocity of the surfaces into account and calculate the impact time correctly. We can not just "animate" a static collider in my opinion..
