# `linear-sim` design notes
This project was cloned from the earlier `picosim` prototype.
## Existing physics simulation library main loops {#existing}
> comparison of main simulation loops from a number of existing physics
> libraries
- [Physically Based Modeling: Principles and Practice (Witkin and Baraff)](#witkin-baraff)
- [Open Dynamics Engine (ODE)](#ODE)
- [Bullet physics library](#bullet)
- [Box2D](#box2d)
- [ParticleSim](#particlesim) -- based on Witkin-Baraff
- [nphysics](#nphysics)
- 3D Physics Engine -- <https://github.com/DarrenSweeney/3D-Physics-Engine>
```
Witkin&Baraff ODE Bullet Box2D ParticleSim nphysics
1997 2001 2007 2007 2013 2013
1. clear forces clear forces world AABB update clear forces clear forces update forces
2. applied forces accumulate forces collision broad phase find contacts for newly capply forces integrate position + velocity
3. constraint forces create and solve LCP detect contacts narrow phintegrate velocity detect collisions update bounding volumes
4. derivative evaluation compute constraint forcessolve joints & PGS solve solve velocity constraintderivative evaluation collision broad phase
5. integrate integrate position + velointegrate integrate position integrate position + velocontinuous & narrow collision detection
6. solve position constraint update joints & sleep islands
7. detect collisions ('TOI contacts') collect contact & joint constraints
8. solve collision position constraints PGS solve velocity constraints
9. solve velocity constraints solve position & joint constraints
10. integrate positions
11. detect new contacts
12. loop 7.-11. until no new contacts
```
note in some cases 'clear forces' takes place at the *end* of the timestep, but
here we show them all at the beginning
one thing to note is that the Siggraph97 (Witkin & Baraff)-style update loops
all end with a single integration phase, while the "Post Impulses" (Catto)-style
update loops may have multiple integration steps with intervening constraint
solving steps
based on these existing main loops, we will try the following order of
operations, which is closest to the Box2D main loop:
1. clear and accumulate forces to get new acceleration
2. derivative evaluation (i.e., compute accelerations from accumulated forces)
3. integrate velocity
4. constrain velocity
5. integrate position
6. constrain position
7. detect and solve collisions in a loop
☞ see [Design](#design) for more details
### Physically Based Modeling: Principles and Practice {#witkin-baraff}
1997 - Witkin, Baraff - *Physically Based Modeling: Principles and Practice* -
Siggraph'97 Course - <http://www.cs.cmu.edu/~baraff/sigcourse/>
overall step outline:
1. clear forces
2. accumulate forces
3. constraint forces
4. derivative evaluation
5. integration
### Open Dynamics Engine (ODE) {#ODE}
2001 -- <http://www.ode.org/>; C/C++
uses modified PGS, multithreaded
has a concept of "islands", the "step" function for an island has the following
"stages", seem to encompass the "modified PGS" solving code:
0. stage 0 performs the following on bodies:
1. applies gravity to all bodies
2. compute intertia tensor and its inverse, and compute rotational force
and add it to the torque accumulator
stage 0 also performs some action on joints invoking an LCP solver
1. stage 1: create the RHS of the constraint equation
2. stage 2 is split into three sub-stages:
a. get the Jacobian information from the constraints
b. compute `A = J * invM * J'`
c. compute `A = Jinv * J'`
3. stage 3:
- invokes the LCP solver
- computes constraint forces
- updates velocities
- computes new positions/orientations
- zeros all force accumulators
### Bullet physics library {#bullet}
2007 -- <https://github.com/bulletphysics/bullet3>; C++
uses PGS/SI with GPU acceleration (OpenCL)
the simulation step function performs
in order:
1. updates world space AABBs
2. compute overlapping pairs -- SAP broad phase (CPU), DBVT (GPU)
3. compute contact points (narrow phase)
4. solve contacts:
i. solve joints
ii. PGS contact solver converts contacts to constraints and solves a
given body buffer + shape buffer + constraint buffer
5. integrate -- enforces a maximum angular motion, applies gravity and
updates position
### Box2D
2007 -- <http://box2d.org/>; C/C++
world step function performs:
* collision detection
* integration
* constraint solution
more detailed outline:
1. finds new contacts for newly created fixtures
2. integrates and solves constraint islands -- this is the two-phase "Post
Impulse (PI)" method where first velocity constraints are solved followed
by position constraints; internally groups of constrained bodies are
called "islands" and form a constraint graph which is then solved:
1. integrates velocity (from forces) of each body and applies damping,
also stores initial object positions; body state is not changed yet
2. solves velocity constraints
3. integrates position; enforces a *maximum velocity*
4. solves position constraints
5. finds new contact ("collision detection" of "TOI contacts")
3. computes TOIs and solves "TOI contacts", which are presumably
"collisions", also solved in groups of "islands"
1. body positions and velocities are copied
2. solves "TOI position constraints"
3. velocity constraints are solved
4. integrates positions for the remainder of the substep
afterwards new contacts are detected and destroyed; this TOI solver loop
proceeds until no new contacts are found
4. forces are cleared
### ParticleSim
2013 - Constrained Particle Sim (Baraff and Witkin) -
<http://www.prism.gatech.edu/~jturner65/cvpages/sim/simProj3.html>
source code: <https://github.com/jturner65/ParticleSim>
1. system apply forces -- (note forces are cleared at end of derivative eval)
- for each force
* for each particle: compute and apply force for that particle
2. handle "click-and-drag" interaction (add "tinker toy" forces)
3. detect and handle particle-ground collisions
4. detect and handle particle-particle collisions
5. "solver" derivative evaluation (moves modified state back to particles) --
- for each particle --
(note the following code is not very clear so it may be off somewhat)
* scale velocity by inverse mass
* use solver to integrate the particle
* advance particle (write new position and velocity) and clear force
accumulator
### nphysics
2013 -- <http://nphysics.org/>; Rust
source code: <https://github.com/sebcrozet/nphysics>
uses PGS with the "Post Impulse (PI)" method (compute velocity constraint
followed by position constraint)
the physics world type allows adding and removing rigid bodies and sensors,
defines a step function:
1. for each "active" rigid body, updates forces, integrates position and
orientation and linear and angular velocities
2. updates positions of sensors that have a parent rigid body
3. updates positions of bounding volumes in collision pipeline
4. performs collision broad phase
5. performs continuous collision detection "motion clamping" for enabled
objects
6. performs collision narrow phase if CCD returned false (no clamping was
done)
7. updates joints
8. updates the activation manager (for island based sleeping/waking)
9. collects rigid body constraints from contacts produced by collision
detection; afterwards collects joint constraints
10. accumulated impulse (PGS) + PI solver: solve second order (velocity)
constraints followed by first order (position) constraints (as well as
joint constraints)
## Design
### Main loop
main loop (cf. [existing](#existing) examples of simulation main loops):
1. derivative evaluation -- accumulate forces and compute acceleration
2. integrate velocity -- apply new acceleration to velocity
3. constrain velocity -- solve velocity constraints
4. integrate position -- apply new velocity to position
5. constrain position -- solve position constraints
6. detect and solve collisions in a loop -- handle collisions and create/destroy
contact constraints
the order of integration here should be equivalent to semi-implicit Euler
### Constraints
constraints restrict values in the phase space (position and velocity) to stay
within certain bounds
general form of an equality constraint:
$$
C(\vec{x}, t) = 0
$$
and an inequality constraint:
$$
C(\vec{x}, t) \geq 0
$$
*example*: halfspace inequality constraint
halfspace defined by a position and a normal vector
### Model
In devising a model there is a choice to be made of what classes of objects and
constraints should be defined.
Currently the prototype has three classes of objects:
1. static objects -- not subject to integration, but having bounding volumes
they may be collided with dynamic objects
2. dynamic objects -- dynamic objects have first derivative of momentum (forces)
first and second time derivatives of position (velocity and acceleration, resp.),
and bounding volumes so they may collide with eachother or with static objects
3. "nocollide" objects^* -- like dynamic objects except they do not have bounding
volumes and are excluded from collision detection
^*: nocollide objects as a separate class of objects has been replaced by adding
a "collidable" flag to static or dynamic objects
For constraints the following considerations are made:
- A dynamic object may be *in contact* with a static object or another dynamic
object; this means that the object(s) are in a configuration such that they
are on the boundary of the inequality constraint defining the non-penetration
condition for "collidable" objects; in this state a velocity constraint must
be enforced
- We would like to have *halfspace constraints*, i.e. to define planes that
restrict the motion of dynamic objects; these are much like static objects
with a "bounding volume" defined by a halfspace, but have some differences:
* a halfspace is somewhat degenerate when considered as a bounding
volume-- unless the plane is aligned to an axis, its bounding volume
will intersect the entire 3D space
* also if considered as a bounding volume only parallel halfspaces aligned
in opposite directions will be in any sense pairwise "resolvable" as a
bilateral halfspace-halfspace constraint; any skew halfspaces will
always intersect
* currently the other bounding volume types are axis-aligned (capsules and
aabbs), whereas halfspaces have an inherent orientation
* continuous collision detection is not *required* to detect a collision
with a halfspace constraint since it is not possible to pass 'through'
the halfspace (as it is with finite bounding volumes), but if exact TOI
is needed then continuous detection is still required
One idea for halfspace constraints would be to make them axis-aligned, so
there are in total 6 orientations (+/-X, +/-Y, +/-Z). An intersection of 6
such halfspaces defines an AABB in which objects would be restricted to
remain.
General planar constraints are required in the case of general dynamic-static
and dynamic-dynamic contacts (the contact plane may be of any orientation). As
noted above, if halfspace constraints are made to be axis-aligned then there is
no need to represent it as a general planar constraint although the detection
and resolution should be roughly the same.
**Bounding volumes**
Do we want to have both *finite* bounding volumes and *infinite* bounding
volumes? Currently the only infinite bounding volume that seems useful is the
halfspace, although one could imagine having infinite bounding volumes such as
octants (e.g. the +X,+Y,+Z octant, offset by some base point), or capsules of
infinite height. Generally, axis-aligned half-spaces are "0-orthants" (*rays*),
and intersections of $n$ mutually orthogonal halfspaces yield $2$-orthants
(*quadrants*) and $3$-orthants (*octants*)
Certainly dynamic objects should be restricted to being finite, although one
could imagine a dynamic object attached to a halfspace constraint, with the
caveats noted above.
We will try having a variant for finite bounding volumes, and a separate variant
for infinite bounding volumes.
**Collision**
*detection* -- discrete, continuous
since static objects don't move, the 'sorted axis' vectors for static objects
can be shared between discrete and continuous detection systems
*contacts* -- contacts are strictly a *distance* criterea; they may be observed
by discrete or continuous collision detection
*Initial implementation*
Broad-phase "sort-and-sweep", a.k.a. "sweep-and-prune" (SAP), detection is based
on having a set of AABBs for each object and sorting these on each axis. This is
encapsulated in the `Broad` struct which contains
1. a 'VecMap' of 'Aabb3's
2. the sorted axes (3) of keys into the 'VecMap' (X,Y,Z)
In the case of *discrete* (instantaneous) collision detection, the 'Aabb3's
correspond to the 'Aabb3's for each object based on position and bounding shape
(both static and dynamic).
For *continuous* collision detection, the static 'Aabb3's are the same, but the
dynamic 'Aabb3's are based on the *swept* bounding volumes of the objects.
*Q*: do we want to use swept spheres or swept AABBs?
Swept spheres allows using a simple ray-intersection test to find the exact
sphere-sphere TOI.
Swept AABBs may be able to be solved by a similar method, taking one object to
be "stationary" and using the relative velocities to determine the TOI.
Swept spheres are usually used when rotation is involved, since an object
remains entirely within its bounding sphere for any orientation.
Since this is a linear simulation, swept spheres seem less appropriate.
**Object creation**
Objects should not be created such that any constraints are violated, or if they
are, they should be resolved somehow before the next simulation step.
Initially we have decided to reject any request to create a static or dynamic
object which violates the non-interpenetration constraint. A rejection returns
an output event with the intersection data from the "failed" distance query,
along with the identifier of the other object. For no-collide objects, no such
constraint exists, so they are always successfully created.
*Q*: how should newly objects be inititalized?
1. When creating a new object, first a *discrete intersection test* needs to be
made to rule out any intersections with existing objects. This is
functionality that should be supported by the collision subsystem, but the
object has not yet been created so it cannot be treated uniformly without
first fully initializing.
*Q*: what collsion data is needed to perform a discrete intersection test?
Here are some possibilities:
- *brute force* -- the new object needs to be tested against $n$ existing
objects, so this is essentially linear in the number of objects; note that
after this succeeds, *then* collision data will need to be created
- *broad phase* -- create broad phase data for the new object and do a "normal"
discrete collision check; note that if the intersection test *fails*, then
this newly created collision data needs to be removed
One issue is that the object geometry is not stored in the collision struct.
This means that if the collision struct is to perform a full collision query, it
needs access to the object data.
*Further notes about object creation*
- When attempting to create a static object, it is only checked for constraint
violation with dynamic objects (not static objects). At this time there's no
reason to check for overlaps with other static objects but there could be in
the future.
- When creating static objects, overlaps are not reported for objects without
the collidable flag set (both the static object being created and any dynamic
objects it overlaps with). Likewise, when creating dynamic objects if the
dynamic object being created does not have the collidable flag set then no
overlaps will be reported, and if the collidable flag is set no overlaps are
reported with other objects (dynamic and static) that do not have the
collidable flag set. This might be undesireable as objects without the
collidable flag set are usually meant to be used as "sensors" such that
overlaps are reported but no collision response is applied.
**Broad phase**
Currently we have separate sorted axes for static objects, instantaneous
(discrete) dynamic objects, and swept (continuous) dynamic objects.
Static objects may have positions changed by the user between frames, so
currently we compute each AABB for all static and dynamic objects.
*Q*: should there instead be two sorted axes (instantaneous + static and swept +
static) instead of three?
Having three sorted axes means that the static object AABBs are not duplicated
in each array, however it may be harder to iterate.
On the other hand having the static objects separate may make it easier to
exclude static vs. static comparisons.
**Mid phase** (continuous only)
The mid-phase consists of taking each identified overlapping pair and returning
the exact AABB TOI start and end, if the objects in fact collide.
**Narrow phase**
For a discrete detection test this should be a discrete test of exact geometry.
For a continuous detection test, this should take into account object motion
during a sub-frame interval.
**Collision loop**
The collision step consists of detecting and resolving collisions in a loop.
Detection proceeds to identify the earliest collision (TOI contact), which is
then resolved. Ignoring contacts for now, such a collision involves one or two
dynamic objects.
We will assume that an identified collision will always result in a non-zero
restitution impulse and that the TOI is strictly < 1.0, so the resolved
object(s) will have a new final position at t==1.0 as a result.
This means that the AABB(s) for the dynamic object(s) needs to be updated so
that any new collision can be detected involving those object(s). The new
current AABB is set and the swept AABB now contains the swept AABB from the TOI
AABB to the new current t==1.0 AABB.
Based on the new AABBs, new collisions involving one of the last involved
objects need to be detected. Having updated the AABBs, the following needs to
to be updated in the broad phase data before detection can take place:
1. sorted axes need to be *resorted* since one or two AABBs moved
2. new overlaps need to be detected for the object(s) involved in the last
collision (but not with each-other directly since they were just resolved)
Note also for the remainder of the pipeline all intermediate results involving
any of the last collided objects need to be removed from the pipeline.
The question of (2.) is again comparing AABBs, but now the swept AABB *start
time* should be equal to the last collision TOI. To properly compare objects
swept AABBs, it seems that the AABBs of *all objects* must be updated in this
way, *however* we know that the original swept AABBs for the entire timestep are
going to *entirely contain* any swept AABB reduced to the interval TOI to
t==1.0.
Consider an object that is knocked by a collision into the portion of the
*beginning* of the AABB for another object, that is, before the collision TOI.
This would register an overlapping pair but the mid-phase would rule out
collision by the sweep test which can take into account the last TOI.
*Q*: when an object which has collided has a modified swept AABB, how can this
be indicated on future iterations when it is no longer included in the "last
collided" objects?
*A*: again since AABBs are conservative and collisions happen in increasing time
order, the modified AABB swept from the first TOI is a superset of the swept
AABB restricted to the later TOI. Mid-phase continuous collision detection based
on swept AABB paths uses only velocities and the final AABBs.
Completing (1.) is possible by fully re-sorting the sorted axes, however if an
effected object is near the last object in a sorted array, comparison are still
made for *all* objects that precede it. It should be possible to create a
modified resort function for this purpose that only looks for the affected
object keys.
Completing (2.) also requires having the set of affected keys. Since we want to
eventually handle collision/contact groups of $n$ objects, an efficient set
representation should be used. We will opt for a sorted vector so that binary
search can be used.
Note that (2.) doesn't allow a way to "skip" to the first affected object, since
objects sorted "earlier" in the list may overlap. However a different overlap
function could be devised to jump directly to the affected objects and scan
below and above just those objects.
The new plan for (1.) is to store the ordered indices into each sorted axis
along with the AABBs, so that positions don't need to be found by scanning the
axes entirely and checking against each resort key. Then the re-sort consists of
jumping to each resort key and individually sorting to the left or right
depending on how a key's ordering has changed. Note that resort keys that have
not yet been re-sorted should be skipped. This can be done by doing a binary
search on the subslice of resort keys *greater* than the current resort key,
since we are traversing them in-order.
To find overlap pairs in (2.), we can now easily 'jump' to the correct position
in the sorted axes with the stored ordered indices assigned to each key. With
the current scheme, each AABB that is sorted *before* a given resort key must be
tested against that key, since a range such as [-inf, +inf] would always be
placed at the front of the list, although it overlaps with *every* other pair in
the list. Namely, intervals are sorted *first* by the minimum, *then* with
respect to the maximum only when the minimums of both intervals are equal. For a
cluster of affected objects near the end of each sorted axis, this would be
about 3*n comparisons in addition to checking that each key is not one of the
resort keys.
To get overlap checking to work symmetrically, there would need to be additional
"reverse" sorted axes, sorted in the opposite direction on maximums.
Note that checking overlaps of dynamic with static objects is a little bit more
complicated since they are sorted in separate arrays. Either every static AABB
from the first until `aabb_static.min >= aabb_dynamic.max` in the forward array,
or from the first until `aabb_static.max <= aabb_dynamic.min` in the reverse
array. It doesn't seem possible to combine these restrictions since ordering is
not preserved in the forward and reverse sortings.
An alternative would be to sort both static and dynamic objects together in the
same sorted axes. Storing object IDs would take up 8 more bytes per key for the
discriminant. An alternative would be to use a special 'Collision Object
Identifier' representation that uses a bit of the `usize` to indicate whether it
is a dyanmic or static object.
Having forward and reverse-sorted arrays does not actually allow starting at a
target resort key and scanning left and right, respectively. If the AABB for the
key in question is completely contained by another AABB, that other AABB will be
sorted *before* it in both the forward and reverse arrays. It seems the best we
can do in this case is to partition resort keys into 'lower' and 'upper' sets
depending on whether they have a lower order index in either the forward or
reverse arrays (default to forward in the case of a tie). This means the worst
case would be n/2 comparisons for a key. For each of the 'predecessor' AABBs, we
can check each remaining key in a partition overlapping with that AABB. Once the
first resort key is reached in the partition, then AABBs need to be checked
whether they come after the first resort key, in which case the first resort key
can be dropped, and the process repeats until all keys are finished.
Having the reverse sorted axes does not seem to help any for a normal
'full-scan' overlap test.
**Contacts**
We want to solve velocity and position constraints of *groups* of contacts.
There should be two cases:
1. During collision detection a single TOI contact (collision) connecting zero,
one, or two resting contact groups
2. Resting contact groups at t==0.0
The criterea for a "*contact*" is strictly *distance* based (`0.0 <=
proximity.distance <= CONTACT_DISTANCE`), however the *type* of contact depends
on the relative velocity of the objects in contact space:
- a *separating* contact has a *positive* velocity along the contact normal
- a *colliding* (a.k.a. "*TOI contact*" or just "collision") has a *negative*
velocity along the contact normal
- a *resting* contact has a *near zero*$^*$ velocity along the contact normal
$^*$: this should be some amount that is "small" relative to the
`CONTACT_DISTANCE`
A '*persistent*' contact is one that was "created" as part of object creation,
or else when a TOI contact was solved and objects remain in contact after
resolution at t==1.0; i.e. a persistent contact is one that already exists in
the collision system at t==0.0 of the current step.
The two different ways of persistent contact creation:
1. During object creation a contact is detected with the existing objects,
adding the object to any existing contact groups or creating a new contact
group; in the three cases that the velocity is:
- positive or zero -- create a persistent contact with 0.0 restitution
- negative -- *do not create* persistent contact; will be detected next
step
*Q*: should the different velocities be taken into account when deciding
what to do with the reported contact?
If all cases are taken to produce a persistent contact, then under the
assumption that persistent contacts always have a restitution of 0.0, then
for apparently 'colliding' (negative) velocity on creation will be nullified
by solving for the velocity constraint of the persistent contact.
The alternative is less clear: the apparent velocity on object creation is
only the velocity for the *current* step, which has already been finalized.
When the persistent contact is created, it is first encountered during the
following step when t==1.0 of the object creation step becomes t==0.0.
Derivative evaluation and integration of the velocity on the next step then
could make a negative velocity into a positive velocity, or vice versa.
It seems somewhat more realistic *not* to create persistent contacts when it
is detected to be a negative (colliding) contact, so as to preserve the
momentum that the created object added to the system.
What can be done in practice is that the *decision* to register a persistent
contact can be made based on the relative velocity at creation time, *even
though* this velocity will be modified at the start of the upcoming step.
Thus a positive or zero contact velocity will produce a persistent contact,
and a negative contact velocity will be left to be detected as a TOI contact
(collision), similar to how TOI contacts at t==1.0 are to be treated (see
below).
2. During collision detection a TOI contact is detected at some time during
[0.0,1.0] of the current step (see discussion below of why collisions
detected at exactly t==1.0 will not be resolved during the current step,
*but* resting or separating contacts will still be registered as persistent
contacts for the upcoming step); for contact velocity at t==1.0:
- zero, positive -- create persistent contact with restitution 0.0
- negative -- ignore/discard; will be detected by collision next step
We want to detect contacts as in (1.) to prevent 'bounce' from creating an
object on a surface caused by just letting collsion detection detect and handle
it as a TOI contact. That is, a simulation step looks like this:
1. An object is created *before* a collision step takes place as an object
creation event.
2. Velocity and positions of objects are integrated according to the result of
derivative evaluation (computed accelerations). If no contact was created
when the object was created, then these will be *un-constrained* for the
newly created object.
3. Collision detection and resolution loop. If the object is not already in
contact, then collision of the object (such as with the surface it was
created in contact with) will result in a restitution velocity leading to a
'bounce' on the first frame.
This raises the point of what can be known about the contact state on the next
step of objects in contact at t==1.0 of the current step. With a semi-implicit
integrator, the *new velocity*, arrived at by derivative evaluation, is used to
integrate the position. Therefore at t==1.0 of the current step, without
performing derivative evaluation for t==0.0 of the next step, it is not possible
to know what the effective velocity is that will transform to t==1.0 of the next
step. *However*, we do know that if the objects are in contact at t==1.0, if the
contact velocity is separating (positive) and derivative evaluation +
integration on the next step causes the contact velocity to become *negative*,
this should be treated as a resting contact. Therefore, we should create all
new contacts observed at t==1.0 (resolved TOI contacts) *or* t==0.0 (newly
created objects), regardless of whether the velocity is zero or positive.
This leaves the question of negative velocities for TOI contacts and "initial"
(creation) contacts.
A TOI contact is a constraint *at the TOI*. A negative velocity at TOI is a
*collision* and will have a zero or positive restitution velocity. A positive
velocity means the objects are separating.
*Q*: do we want to have a way of resolving *velocity constraints* at t==1.0 of
the current step?
The question arises since after a collision resolution is performed at some TOI
and objects are moved to t==1.0 and post-impulse position correction has been
applied: a velocity constraint was never enforced at t==1.0, it was only
enforced at t==TOI, so it *might*$^\dag$ be possible that some velocities can
become negative when measured at t==1.0.
$^\dag$: Since we are considering a *linear* simulation of *convex* bounding
volumes, for an isolated pair of objects this should not really be possible;
when resolving such a constraint for a given separating axis/plane it shouldn't
be possible that the relative contact velocity becomes negative again at some
later time--(a proof should be possible?). When treating groups of interacting
contact constraints the answer is less clear.
The mutual
linearity/convexity of each contact pair *might* ensure the positivity of t==1.0
velocities for the entire group--(could a proof be possible?).
Pseudovelocity shouldn't be factored in to t==1.0 velocity, since it they will
be zeroed.
Since t==1.0 represents some "input" to the next step, the final vaue of that
step should be entirely determined by the state *at* 1.0, that is, the result of
integration when t==1.0 is now t==0.0 of the next "current" step.
*However*, there needs to be consideration for TOI collisions detected *at*
t==1.0. To wit, we want to specify how *persistant* contacts, that is, those
contacts that exist when the next step begins at t==0.0, arise from TOI
contacts (collisions). Some considerations:
- In which of these ranges should we *detect* and *handle* collisions:
* (0.0,1.0)
* (0.0,1.0]
* [0.0,1.0)
* [0.0,1.0]
Consider t==0.0. Any newly created objects should have had any contacts
detected, and *if* the prior collision detection step reliably reports all
contacts at t==1.0, then a "new", undetected TOI contact at t==0.0 should
*not* be possible.
Considering t==1.0, if we want the above to be true for t==0.0, as noted
then all objects within contact distance must be identified as such as the
result of collision detection and response. If the prior collision step
*does not* report new collisions that happen *at* t==1.0, then only those
collisions with TOI strictly *less* than t==1.0 will result in the creation
of persistent contacts. If this is the case then there are three possible
cases for contacts at t==0.0 of the next step:
- a persistent contact that was created on some prior step from a
detected TOI contact
- a TOI contact detected at t==0.0; this could *only* be the case for a
TOI contact that was detected *exactly* at t==1.0 of the prior step
- a contact for a newly created object
*Therefore*, collision detection should only process collisions with TOIs in
the range *$[0.0,1.0)$*, *but* keeping in mind that each such TOI contact
will possibly result in the creation of a *persistent contact* at t==1.0.
(☞ See below "*Further considerations*" for notes about creating
persistent contacts at t==1.0).
This clarifies two points:
(1.) Collision resolution for the current step *never* solves velocity
constraints at t==1.0, either as a TOI contact *or* as a persistent contact.
The velocity at t==1.0 is *not* the final velocity for that instant in time:
it will be determined during the next simulation step when it is the
"current" t==0.0 state, by the result of derivative evaluation and
integration followed by velocity constraint resolution of persistent
contacts *and* possibly TOI contacts with TOI==0.0.
(2.) Therefore, velocity constraints for t==0.0 are *always* only enforced
*on* that step, *not* at t==1.0 of the previous step.
Taking this approach ensures that velocity constraints are never solved
*twice* for the same time instant, i.e. as would happen if a TOI collision
were responded to at t==1.0 and then on the following frame contact velocity
constraints are enforced at the new t==0.0 (since the object has collided at
t==1.0, there is no time for it to move out of contact, so a persistent
contact must be created).
*Further considerations*
When considering how to handle contacts of created objects a similar
question is posed since the created object is giving the value of t==1.0 of
the current step, that is, input to the integration of the t==0.0 of the
next step. Here we want colliding contacts to be left to collision detection
to detect and respond to, *based on the current velocity*. It is true that
derivative evaluation and integration *may* bring the velocity to be
non-negative, in which case the collision system will let the objects
separate and no collision is processed, but the bottom line is that it would
preserve the momentum added to the system by the created object. A zero or
positive velocity however *should* generate a persistent contact for the
created object, to prevent a 'bounce' when forces are applied on the next
step.
*Q*: should t==1.0 TOI contacts instead be handled selectively in a similar
fashion? That is, when such a collision is detected such that the velocity
is negative, it can be ignored and allowed to be responded to by the
collision pass of the next step: as noted this prevents resolving the
velocity constraint twice at the same instant of time (t==1.0 $\rightarrow$
t==0.0). *However*, a persistent contact *may* be created based on the
t==1.0 velocities if it is zero or positive. This can be justified by saying
that at t==1.0/t==0.0, the objects are *in contact*, so an *acceleration*
(derivative evaluation) cannot accelerate the objects towards eachother,
i.e. the constraint is *in effect*, so this contact should be registered.
It should also be noted that some argument should be made that separating
velocities at t==1.0 could also be called as "no contact" for the purposes
of persistent contact creation. Although an acceleration *could* cause the
velocity to become negative in many cases, on those that *wouldn't* then it
avoids the work of registering the contact in the pipeline, just to be
destroyed when the objects separate next step, in many cases.
It could also be argued that since the simulation is essentially a
discretization of a continuous system, a sufficiently positive separating
velocity would have *some* time with which to cause a separation and
subsequent acceleration of an object in the opposite direction to cause a
collision and response.
*Therefore*, whether or not a contact is "*persistent*" should depend on
*velocity* at t==1.0, i.e. only *resting* contacts can become persistent, as
well as *position*, *even though* that velocity does not give an absolutely
accurate prediction of the final object velocity and position at t==0.0 and
t==1.0, resp., of the next time.
In the case of TOI contacts *and* created object contacts, only when
velocity is observed to be "near"$^\ddag$ zero should a persistent contact
be registered.
$^\ddag$: this "resting" contact threshold could be defined as some fraction
of the contact distance, for instance (1/120)th of the contact distance
(currently 0.001) giving a speed of about 20 seconds per 1cm or ~33 minutes
per 1m. This value (0.000008) is small but still sufficently far from zero.
Detection is rather cheap for continuous linear collision, so the cost of
"re-detecting" a separating contact at t==1.0 that turns around and becomes
colliding next frame is not too large.
- We should also ask: what kind of *output*, in terms of reporting contact and
collision, is to be expected?
Currently we only have objects that respond to contacts by solving velocity
and position constraints, but we might also want to add objects that merely
*detect* collision but do not respond (whether by flagging dynamic objects,
or creating another category of objects altogether). In this case, the sole
reason for their being in the collision pipeline is to detect interactions
with other objects. The time ordering may still be of interest so otherwise
up until resolution the detection should proceed the same as for general
static and dynamic objects.
We want to know:
- When objects undergo a *collision restitution*, i.e. when they have been
directly involved in an instantaneous TOI contact. This will indicate
some "impact velocity" which can be reported to allow game logic to do
things like destroy or damage the object in case of violent collisions,
etc.
- When objects *begin* and *end* persistent contacts. This may be used by
game logic to change an objects state according to what kind of
persistent contacts it is participating in.
- As noted above for "sensor" objects, intersection *start* and *end*
times. If more detailed intersection geometry is available that may be
returned as well.
A couple of considerations:
- *Q*: are all persistent contact 'begin contact' events preceded by a TOI
contact? Not in the case of newly created objects. One can also imagine
the case of a curved surface approaching the upper surface of a
rectilinear object at exactly the right height and parallel to the
surface: at any positive separating distance the velocity will negative,
non-zero, but when the curved surface is finally exactly above the flat
surface, the normal is now perfectly perpendicular to the direction of
motion, so there is no colliding contact.
What can be said is that, for a given pair of objects, between a begin
and end contact, no TOI contact event between those same two objects
should occur.
- *Q*: can TOI contact events ever indicate a zero impulse? The idea
behind reporting a collision is that at least one object was modified in
some way. However, it is also the case that with sensor objects, the
collision system should report a kind of TOI "event" *without* impulses.
⚠ For now we will assume that TOI contacts with dynamic objects
result in a non-zero impulse. This should follow from the fact that for
a TOI contact, a negative velocity must be present--*keeping in mind*
that possibly a sufficiently small negative velocity results in a zero
impulse. (A more careful analysis may be able to say something more
definite).
A reprise of different kinds and aspects of "contacts":
- *contact* -- a pair of objects at a time instant with a non-negative
separating distance `<= CONTACT_DISTANCE`
- *colliding contact* -- a contact that has a *negative* contact velocity
along the normal direction (*note*: this could be a *TOI contact* or a
*persistent contact*)
- *resting contact* -- a contact that has a *near zero* (in the range
`[0.0-RESTING_VELOCITY]`) contact velocity along the normal direction
- *separating contact* -- a contact that has a *positive* contact velocity
along the normal direction
- *TOI contact* -- a colliding contact detected by collision detection in
the interval `[0.0,1.0)`
- *persistent contact* -- a resting contact at t==1.0/t==0.0; *note*:
during collision response of TOI contacts, a persistent contact will be
*lerped* to the TOI; when *solving* a persistent contact, the
restitution is always zero, and a positive final separating velocity
(`> RESTING_VELOCITY`) will cause the contact to *break* at that instant
(whether at t==0.0 or at a TOI)
- The lifecycle of a persistent contact looks like this:
1. either an object creation or TOI contact results in a separating
distance of `<= CONTACT_DISTANCE` and velocity `<= RESTING_VELOCITY` at
t==1.0, resulting in the creation of a *persistent contact*
2. at the beginning of a simulation step, all persistent contact groups
are resolved for velocity at t==0.0 and position at t==1.0, and if any
velocities are seen to exceed the resting velocity at t==0.0 *or* if
objects have separated at t==1.0, the persistent contact is *broken*
3. during the collision detection/resolution loop, if a collision is
detected, then any involved persistent contacts are lerped to the TOI
and the combined contact group is solved (a single TOI contact and zero
or more persistent contacts); again if any velocities are seen to
exceed the resting velocity at TOI *or* if objects have separated at
t==1.0, then the contact is *broken*
*Q*: Are these conditions for breaking persistent contacts reasonable?
Conditions for creation: distance+velocity of object creation contact or TOI
contact @ t==1.0
Conditions for breakage: velocity @ t==0.0 or TOI, distance @ t==1.0
What if we had:
Conditions for breakage: distance+velocity @ t==1.0 of either a result of
pre-collision contact resolution or as a result of TOI contact resolution.
This would make the conditions for creation/breakage essentially the same,
however would this cause instability for persistent contacts since the
t==1.0 velocity is not the same as the t==0.0 velocity of the next
resolution phase?
For instance, velocity at t==1.0 is seen to be sufficiently positive so the
contact is broken, *but* the objects are still within contact distance at
t==1.0. Acceleration on the next step causes this velocity to become
negative, so a collision occurs. Because velocity is constant over the step,
such a positive velocity at t==1.0 is *probably* going to indicate a
positive velocity at t==0.0 as well, so in *either case* the contact would
be broken. *However*, I think it makes more sense to consider the separating
velocity *at the time the constraint is solved for*, so t==0.0 or TOI.
Note it *might* make more sense to make *breakage* only dependent on
position at t==1.0.
☞ One clarification that can be made is that, in fact, the position
at t==1.0 of the current step is *equal* to the position at t==0.0 of the
next step. Essentially by checking position at t==1.0, the position at
t==0.0 is *also* checked, so it can be seen as a kind of "early" breakage of
a contact so that it can be excluded from the resolution of persistent
contact constraints in next step. So, to clarify, if *position* at t==1.0 is
seen to be greater than the contact distance *or* if *velocity* at t==0.0
(or TOI) is seen to be greater than the resting velocity, *then* the contact
is broken.
*Q*: Does this imply that a position breakage at t==1.0 really breaks the
contact "*at*" the next step, not the current step? I think it should, if we
are thinking of t==1.0 position as being equivalent to t==0.0 position.
So a persistent contact can break:
- at t==0.0 *or* TOI of the current step by positive separating velocity
- at t==0.0 of the *next step* by positive separating distance
Enforcing the view that contacts *create* at t==1.0 (based on current step
velocity) and *break* at t in the interval `[0.0,1.0)`.
Considering the output events:
- Contact begin events will be output on the step for which the objects
*ended* in contact
- Contact end events can be generated for *any time* during the current
step
Sub-frame 'breakage' time should not *really* be important for output, and
no such sub-frame 'creation' time exists.
How do 'broken' contacts interact with the collision pipeline?
Could a contact be 'created' and then 'broken' on the same frame? No,
because contacts are only created at t==1.0, and TOI contacts are restricted
to the range [0.0,1.0). Such a breakage would at the same *instant*, t==0.0,
but output during the next step. *But*, those objects might have been
affected by an intervening TOI contact with some other object at some time
before t==1.0, modifying the final position and velocity! This contact is
not yet really *persistent* because it did not exist at t==0.0 of the
current frame. Therefore there should be no lerping/solving of the contact
at the intervening TOI, *but* the state of the "potential" persistent
contact needs to be checked. This seems to indicate that *creation* of
potential persistent contacts needs to be finalized *after* all collision
resolution is complete.
So a persistent contact can really only be broken if it already existed at
t==1.0. Can a contact break and then re-form in the same frame? Say that a
persistent contact breaks at t==0.0 due to positive separating velocity, but
at that same instant t==0.0 an object collides, causing a TOI impulse to
restore the velocity to a resting state. The contact will only re-form if
the objects remain in resting contact as measured at t==1.0. Therefore, yes
a contact can *generate* both a 'break' and a 'form' event of the "same"
contact on a single step, *but* once a contact is broken, the creation of
the "new" persistent contact is not finalized until all collision resolution
for the step is finished.
See below for representing persistent contacts.
٭ *Idea*: what if instead of having persistent contacts to prevent
jitter, we handle all collisions at t==0.0 as contacts, i.e. with
restitution value of *zero*, and all other collisions at times in
`(0.0,1.0]` as normal *collisions*. Would this be sufficient to forego
persistent contacts and contact groups for now? The question is really
whether it would be possible to "miss" a TOI contact at t==0.0 and treat it
as a resting contact instead?
For the purposes of output events then there would be two kinds of events:
TOI contacts and resting (t==0.0) contacts, and one resting contact would be
output each frame for 'persistent' contacts. An idea would be to minimally
keep track of individual persistent contacts, so if a resting contact is
solved on the current step, but not on the next step, then a 'end contact'
event is generated, and likewise if a resting contact was not solved on the
previous step, but was solved on the current step, then a 'begin contact'
event would be generated.
This might be a temporary solution to prevent jitter until persistent
contact groups are implemented. Contact groups are still needed to solve
multiple contacts simultaneously, without having to iterate through a large
number of collisions. Upon testing it was possible to generate a large
number of 7000+ iterations with a high-speed collision of 10 capsules. It
seems that the loop is stuck at the same TOI early in the frame and not
making any advancement. This is probably due to multiple collisions
'ping-pong'ing and never quite reaching a zero negative velocity state.
See *Simplified contacts* below.
*Contact representation*
Contact geometry is represented by a planar non-interpenetration constraint,
consisting of a base-point defined as the *midpoint* on the separation axis with
direction determined by a normal direction vector.
For TOI contacts, the restitution is some non-negative velocity (may be zero for
"sticky" collisions), and for persistent contacts the restitution is always
zero.
Each *individual* contact is a pairwise constraint between a dynamic object $A$,
and a dynamic *or* a static object $B$.
A *group* of contacts is an array of such object pairs+constraints such that
the contacts are *linked* by sharing common objects. E.g. objects A,B, C, and
two contacts, (A,B) and (A,C), form a contact group [(A,B),(A,C)] since object A
provides the "link" between object B and object C. Now when solving velocity or
position constraints, an *iterative method* must be used to drive this
interconnected system of contacts to the desired solution.
Collision detection will need to be able to skip objects that are in direct
mutual contact, but still allow detection of collision with other objects, even
those that are part of the same contact group but not *directly* in contact.
First of all, we can use a "stash" (<https://crates.io/crates/stash>) container
in which to store contact groups. This will give out a unique group key that can
be used to test whether two objects are part of the same contact group.
*Simplified contacts*
Any *collision* (contact velocity `< 0.0`) detected at t==0.0 is solved as a
*resting contact* with a restitution of `0.0`. This generates a 'begin contact'
event *if* the same object pair was not in contact on the previous step. For all
object pairs that were in such a contact on the previous step that were no
longer in such a contact on the current step, an 'end contact' event is
generated.
Any *collision* (contact velocity `< 0.0`) detected in the interval (0.0,1.0] is
solved as a *TOI contact*, with the appropriate restitution value.
Issues:
- Collisions are solved individually, not simultaneously in groups; this will
have the problem of many collision loop iterations when three or more objects
collide simultaneously. For now this could be acceptable until contact groups
are implemented.
- Objects created in contact with a colliding (negative) contact velocity will
not register a collision; they will be treated as a resting contact at t==0.0
of the next step, essentially removing that momentum that was injected into
the system. This doesn't really matter for most purposes. Note that contact
events will not be produced until the next step has finished, so between the
time that an object create event is submitted and the next step processes that
event, the game state cannot know there is a contact.
A question is how to represent contacts for keeping track of begin/end events.
Two pairs of sorted vectors could be maintained: dyanamic/static and
dynamic/dynamic for 'previous' and 'current' contacts.
When a contact is detected at t==0.0, that contact can be added to the 'current'
contact vector. If the contact was present in the 'previous' vector, it will be
removed, otherwise a 'begin contact' event is generated.
After all t==0.0 contacts are detected, any contacts remaining in the 'previous'
vector then generate 'break contact' events.
### Contact groups
*Q*: Can groups be partitioned if they don't include mutually interacting
dynamic objects? For example a contact group might be two dynamic objects
resting on a single static object, but not interacting with eachother.
If this is allowed, then the static object could be included in multiple contact
groups. Currently a 1-to-1 map is maintained of objects to contact groups. To
support a 1-to-many relation for static objects, the options are:
1. associate a vector of group IDs to static objects
2. don't keep a map for static objects
in the case of (1.), some objects might have many groups (e.g. a floor object),
and others may usually have none (e.g. a ceiling object)
in the case of (2.), to remove a static object from contact groups, we would
have to iterate over all contacts to find and remove the object
*Q*: in case (2.) do we still want to track the number of contacts a static
object is in?
there is some overhead in incrementing/decrementing and keeping these counters;
there are two uses:
- when processing mid-TOI collisions, if a static and dynamic object are in
contact, the collision is skipped; by having a contact count for the static
object we know whether the dynamic contact group needs to be checked for the
existing contact
- when removing a static object, having a contact count indicates whether
contact groups need to be searched for the static object to remove it, and the
number of contacts can be counted for early stopping
for now we will keep the counter
### Broad phase V2
When looking at adding an instantaneous line-segment test, the initial
broad-phase implementation was found lacking. We had sorted only based on the
minimum AABB endpoints, so binary search could be used to exclude any sorted
AABBs that were found with minimums beyond the maximum of the target segment,
but we would still have to check every AABB to the left of that point as the
maximums were not sorted.
Checking the literature, (Baraff 92), the implementation usually sorts min/max
endpoints together in a single list. We were also not preserving overlap
information between steps, which meant that we were potentially not taking
advantage of temporal coherence.
In the new broad phase we have 3 sorted axes consisting of "endpoints" that are
the floating-point position of each AABB min/max together with the internal ID
of the object corresponding to that endpoint, and also the ordinal position in
the sorted list is stored for each object for reverse look up. We also keep the
resort keys structure.
*Q*: how to handle the `begin_step` phase in the new version?
In the previous broad-phase, the begin-step function presented all the current
static and dynamic AABBs after position integration (and user updates), updated
their values in the broad phase arrays and re-sorted, not yet collecting overlap
pairs.
Dynamic objects will usually have some new positions (unless they happened to
have exactly zero velocity). Static objects can have new positions as a result
of user move events. However, if we change the code to update static objects in
the broad phase at the time the user move event is processed, then there will be
no static updates to process. We could potentially also update each dynamic AABB
at integration time, with the caveat that positions would also need to be
updated again after position constraints determine the final positions. Since
user events and integration do not process objects in the sorted order of the
coordinate axes, these updates would be more or less random in that ordering.
However, there would be nothing to do at `begin_step` since the axes would
already be sorted and overlap states updated.
The number of static objects could be large (>1000), and it is unlikely that
most of them will be moved on a given step. In that case it seems more efficient
to only update them at the time the move event is processed.
Looking at Bullet3, `updateAabbs` is a pass following `integrateTransforms` that
iterates over all collision objects and sets the AABB in the broad phase for
each active non-static object, which performs sort up/down on each endpoint,
adding and removing overlaps.
*Q*: how to handle (dynamic) position changes during collision pipeline
iteration?
In the first version, as a result of collision changing positions, dynamic
objects would have their AABBs updated and their key added to `resort_keys`, and
the static object would have its key added to `resort_keys` as well (to indicate
that it should *not* be checked for additional overlaps). The dynamic resort
keys are then removed from intermediate stages in the pipeline (mid and narrow
TOIs).
*Q2*: Upon re-visiting the original broad-phase implementation, are there ever
more than 2 keys in the ResortKeys at any given time?
ResortKeys get *cleared* after every call to `broad.overlap_pairs_continuous`.
Maybe the intent was that when solving a collision with a contact *group*, there
could be N resort keys.
## Limitations
- the distance criterea for contact is set by a global constant
`linear_sim::collision::CONTACT_DISTANCE`; we might want to make this variable
on a per-object basis (e.g. as the nphysics library does with explicit contact
"margins")
- currently we have objects that are excluded completely from collision
detection, but we might also want to have objects that detect collision but
which are not *constrained* by contacts, i.e. kind of "sensor" or "detector"
objects; these can be similar to dynamic objects except that they do not have
material properties
