# Proximity queries
Proximity queries are based on low level routines in the math_utils::geometry::primitive
module. These routines are:
- nearest point query -- returns the nearest points in a pair of primitives; this is
only implemented currently for simplex and line types
- intersection -- discrete and continuous intersection query; discrete returns only a
boolean result; continuous returns the intersection geometry
This crate defines a *proximity query* that returns the following information for a pair
of objects:
- distance (or interpenetration depth)
- half_axis -- when objects are not overlapping, this is their separating axis (the
vector between their nearest points) scaled by 0.5; when objects are overlapping, this
vector resolves the intersection exactly by translating object A by this vector and
object B by the negative of this vector
- midpoint -- when objects are not overlapping, this is the point that lies exactly in
the middle of their separating axis; when objects are overlapping, resolving the
intersection by translating each objects relative to the half_axis results in this
point being the contact point of the resolved object pair
- normal -- this defines the orientation of the separating (contact) plane orienated
from object B towards object A
Some additional observations on the relation between these variables:
- given a computed `midpoint` and a `half_axis`:
* `midpoint + half_axis == nearest_b`
* `midpoint - half_axis == nearest_a`
* `nearest_a + half_axis == midpoint`
* `nearest_b - half_axis == midpoint`
- regardless of whether the objects are overlapping or not, translating the object A
by the half_axis and object B by the negative half_axis will result in the points
nearest_a and nearest_b on the respective objects now being identical with the
midpoint
- the midpoint and the normal together define the *planar constraint* for the contact
constraint defined by the proximity query (`constraint_planar` method, and the
Proximity type is convertable into a Planar constraint by the From/Into trait
implementation)
This Proximity query type is useful in most situations, however it may return more
information than is needed. In benchmarks, computing `query_segment_point` is possibly
over 30 times more expensive than doing a simple distance squared query on the output of
`nearest_point`. Some of the cost is due to:
- `distance` almost always requires a `sqrt()` call; we may want to be able to return
squared distance when we only need to compare distances without needing to know the
exact distance
- `normal` -- this is a normalized (unit) vector; similar to distance, we might want to
return a non-normalized normal vector
# Testbed example
Currently the testbed scenarios are mapped to keys 0-9.
However there are now more scenarios than there are number keys, so we would like to
group them together and provide sub-states.
- Simulation tests:
* drop test
* collision test
* stack test
* ball pit
* hull pit (NEW)
* sphere/hull pit (NEW)
- Penetration resolution tests:
* capsule/capsule
* cuboid/cuboid
* capsule/cuboid
* triangle/triangle
* hull/hull
- Bounding volume tests:
* OBBs
# Constraints interface
Currently we have two constraint types which are Contacts and Distance
constraints.
Each constraint has two basic methods:
1. `constrain_velocity`
2. `constrain_position`
However their interfaces are not completely uniform: the
`Contact::constrain_velocity` method takes an additional `restitution`
parameter, and `Contact::constrain_position` is a static method instead of a
regular method, and returns an additional proximity query result.
1. for `Contact::constrain_velocity`, can we do `restitution` lookup from the
objects themselves?
The issue seems to be that resting contacts have a restitution of zero, so
there are really two different kind of contacts. We might have a
`constrain_velocity_with_restitution` function or method that takes a
`restitution` parameter. Then the `Contact::constrain_velocity` implementation
calls this subroutine with `0.0` as the restitution. In the collision case,
call the `constrain_velocity_with_restitution` function directly.
Another option would be adding a restitution field to `Contact`, but all
persistent contacts have a restitution of zero so it would be a waste of
memory.
*Q*: is `contact.plane` used at all?
*A*: yes contact plane normal is used in `constrain_velocity` for determining
the velocity normal component. Actually it seems that only the plane normal is
used so the `Contact` constraint type could be made smaller by removing the
base point of the plane and just containing the normal.
2. in `Contact::constrain_position`, we are given objects with an unknown
Proximity and we calculate it first thing; essentially at the time that
`constrain_position` is called we don't have an updated Contact constraint,
and the Proximity query could be overlapping (in which case it needs to be
resolved). A contact could be created from this Proximity query result,
however, the `proximity.distance` and Proximity `proximity.half_axis` fields
are needed to compute the resolution.
The returned Proximity result is then used to determine whether the Contact
constraint needs to be removed (objects no longer in contact), or otherwise to
update the Contact constraint plane normal.
Should we update the Contact constraint to contain more of the necessary
information, and have `constrain_position` return a new constraint?
First, as far as the input proximity goes, only one of the `distance` or
`half_axis` fields are actually needed: the separating axis can be derived by
`distance * normal`, since we have added a debug assertion to verify that the
`normal` and `half_axis` always point in the same direction. A compromise may
be to redefine `Contact` to contain the `normal` and the `distance` for each
contact.
Updating `Contact::constrain_position` to have a different signature is
complicated because it is used in a couple different places: in the system
constrain positions phase and in the collision resolve loop.
**System update**
1. constrain velocities
2. update positions
3. constrain positions
After updating positions, Contact `distance` and `normal` fields will not be
correct.
Currently, in `Contact::constrain_position`, a proximity query is performed for
the object pair at `T==1.0`, and if it is negative, then the object is moved by
applying a pseudoimpulse at `T==0.0`, and a new proximity query is performed at
`T==1.0` (which is checked by a debug assertion to be correctly resolved).
Either the first proximity query or the updated proximity query are returned
(depending if a pseudoimpulse was applied or not).
`constraint::Manager::constrain_positions` repeatedly calls
`Contact::constrain_position` until no further impulses are applied; on the
final iteration when no impulses are applied, if the proximity distance output
by a `Contact::constrain_position` call is greater than the contact distance,
then that Contact is removed, otherwise the contact normal is updated from the
final proximity query.
Things to keep in mind:
- an updated proximity calculated by `Contact::constrain_position` may not be
the final proximity for that contact pair if one of the objects is also
updated in another constraint in the same island; that is, the proximities
calculated by `Contact::constrain_position` are only accurate on the last
iteration of the island when all constraints are shown to be satisfied
- therefore, we may update the Constact constraints during iteration, but their
values will not be valid until the final iteration; i.e. a new proximity query
must be performed on every iteration (this is actually what is done currently)
**Collision resolve loop**
The `Collision::resolve_collision` has a similar constrain positions phase as
the constraint manager constrain positions function, however now there is a
colliding contact and potentially two different constraint islands.
On every iteration, the proximity returned by `Contact::constrain_position` is
saved for the colliding contact as `collision_final_proximity`, and proximities
for contacts in each island are saved in `final_proximities_island_{a,b}`.
`Collision::resolve_collision` requires a final pass over the constraint islands
to `braod.add_resolved` for each Contact constraint. In this pass the "final
proximities" are checked for removal, or else update the contact normal.
**Plan**
- update the Contact state on every call to `contact.constrain_position`; this
may result in a Contact having a `distance > CONTACT_DISTANCE`
- we can either use a `remove_contacts` list which is cleared on every iteration
(as in the constraint manager), or we can perform a final pass to check
Contact distance for removal (as in the collision resolver)
