Drake
Collaboration diagram for Collision Cliques:

The Principle

Collision cliques filter collisions by defining a group (or clique) of collision elements. Membership in a clique precludes collision with any other member of that same clique. The underlying idea of collision cliques is that of the mathematical clique. This mathematical concept applies very naturally to the graph-based discussion of collision filtering. A clique in a graph is, loosely, a completely connected subgraph; there is an edge between each of the nodes in the subgraph. For collision filtering, that implies that all of the pairs that can be created from combinations of the clique members are filtered out.

It is common to simulate a robot such that collisions between any two bodies of the robot are ignored (see SDF File Collision Semantics). This behavior is easily represented with collision cliques; the whole robot belongs to a single clique.

The Implementation

In Drake, cliques are represented as integer identifiers. Each collision element tracks the set of cliques to which it belongs. When a pair of collision elements are considered for collision computation, their two sets of cliques are intersected; a non-empty resultant set means that this pair is filtered. The cost of the intersection is O(n + m), where the two elements belong to n and m different cliques, respectively. This is the worst case. In principle, it would come up whenever the pair of collision elements are not filtered by a clique. In practice, this cost is mitigated as follows:

  1. Clique comparisons are only evaluated when the underlying bounding volume hierarchy (BVH) is restructured. In most cases, only a small, local portion of the BVH is restructured at any time, reducing the number of actual clique tests done.
  2. The representation of the clique sets to which a collision element belongs provides opportunities to short-circuit the full O(n + m) test in common cases.

Drake automatically applies cliques in two different cases:

  1. If a body has multiple collision elements, all of those elements are put into the same clique.
  2. The collision elements of two bodies are all put into the same clique if:
    1. the bodies are adjacent (one is the parent of the other in the tree), and
    2. the joint connecting them is not a floating joint.

There are several implications of this:

  1. A body that is represented by multiple, overlapping collision elements will not report meaningless collisions between those elements.
  2. Collisions between adjacent bodies will not provide constraints on the valid range of joint motion. These constraints will have to act directly on the joint state value.
Note
These heuristics may lead to important collision element pairs being filtered. There is currently no interface for manipulating cliques programmatically. This will be implemented when the use case becomes clear. However, there is a workaround. As an example, consider two adjacent bodies, A and B. Their collision elements will automatically be put into a common clique. However, we may want collisions between element E on B and collision elements on A to not be filtered. We can create a massless body Z to hold E and use a weld (fixed) joint to attach Z to B. Z will not be adjacent to A, so E will interact with A's elements.

Next topic: Collision Filter Groups