Intersecting Objects

Applications

  • Motion Planning & Robotics
  • Computer Graphics & Animation
  • Constructive Solid Geometry

Convex Decompositions

\[\mathbf{a}, \mathbf{b} \in C \Leftrightarrow \text{the line from } \mathbf{a} \text{ to } \mathbf{b} \subseteq C\]
  • Non-convex objects are complicated
  • May have disconnected intersection spaces

$\Rightarrow$ Assumption: every object is the union of convex objects $K = \bigcup_i C_i$

Simplices

A $k$-simplex is the convex hull of $k + 1$ affinely independent vertices

$2$-simplex

Triangle

$3$-simplex

Tetrahedron

$4$-simplex

Pentatope

Radon's Theorem

Given $A$, a set of $d + 2$ vertices in $\mathbb{R}^d$
We can partition $A$ into two sets $A^+$ and $A^-$
such that $\mathrm{conv}(A^+)$ intersects $\mathrm{conv}(A^-)$.

>

Radon's Theorem

Given $A$, a set of $d + 2$ vertices in $\mathbb{R}^d$
We can partition $A$ into two sets $A^+$ and $A^-$
such that $\mathrm{conv}(A^+)$ intersects $\mathrm{conv}(A^-)$.

Proof:
Find a non-zero solution of the linear system

\[\begin{bmatrix} x_1 & x_2 & x_2 & x_4 & x_5 \\ y_1 & y_2 & y_3 & y_4 & y_5 \\ z_1 & z_2 & z_3 & z_4 & z_5 \\ 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix} \begin{bmatrix} \lambda_1 \\ \lambda_2 \\ \lambda_3 \\ \lambda_4 \\ \lambda_5 \\ \end{bmatrix} = \mathbf{0}\]

Then consider the partition

\[\begin{align*} A^+ &= \{ \mathbf{p}_i | \lambda_i > 0\} \\ A^- &= \{ \mathbf{p}_i | \lambda_i \le 0\} \\ \end{align*}\]

both have convex hulls containing

\[\sum_{\mathbf{p}_i \in A^+} \frac{\lambda_i\mathbf{p}_i}{L} = -\sum_{\mathbf{p}_i \in A^-} \frac{\lambda_i\mathbf{p}_i} {L}\]

where $L = \sum_{\mathbf{p}_i \in A^+} \lambda_i$

Naïve Intersection Test

define $\mathrm{Intersect2D}\left(A, B\right):$
for each edge $e_1$ of $A$:
for each edge $e_2$ of $B$:
if $e_1$ intersects $e_2$:
return true
for each triangle $T$ of $A$:
for each vertex $v$ of $B$:
if $v$ is inside of $T$:
return true
for each triangle $T$ of $B$:
for each vertex $v$ of $A$:
if $v$ is inside of $T$:
return true
return false

define $\mathrm{Intersect3D}\left(A, B\right):$
do twice:
for each triangle $t$ of $A$:
for each edge $e$ of $B$:
if $t$ intersects $e$:
return true

for each tetrahedron $T$ of $A$:
for each vertex $v$ of $B$:
if $v$ is inside of $T$:
return true

swap A and B

return false

Quadratic Time

Minkowski Sum

\[\begin{align*}A + B &= \{\mathbf{a} + \mathbf{b} | \mathbf{a} \in A, \mathbf{b} \in B \} \\ A - B &= \{\mathbf{a} - \mathbf{b} | \mathbf{a} \in A, \mathbf{b} \in B \} \end{align*}\]

Object Space

Configuration Space

Designing an Efficient Intersection Test

\[\mathrm{dist}(A, B) = \min_{\mathbf{x} \in A - B} ||x||\]

Solve the optimization problem without calculating the faces of $A - B$

Based on Gilbert, Johnson, Keerthi 1988

GJK Algorithm

  • Assume we know a triangle of $A - B$ (a "guess" of the intersection point)
  • Origin is not currently in the simplex
  • Find a closer simplex: on the other side of which edge is the origin?
  • Use that edge + the point furthest away from it
  • Key idea: $\max_{\mathbf{x} \in A - B} \mathbf{x} \cdot \mathbf{d} = \max_{\mathbf{x} \in A} \mathbf{x} \cdot \mathbf{d} - \max_{\mathbf{x} \in B} \mathbf{x} \cdot \mathbf{(-d)}$

GJK Algorithm

  • Repeat until the origin is in the simplex

GJK Algorithm

  • Repeat until the origin is in the simplex

GJK Algorithm

  • If there is no intersection, we can never enclose the origin

GJK Algorithm

  • If there is no intersection, we can never enclose the origin
  • Stop when origin is on the wrong side of the simplex built by the algorithm

GJK Algorithm

define $\mathrm{Intersect}\left(A, B\right):$
$\mathbf{d} \gets$ some arbitrary direction
$\mathbf{a} \gets \mathrm{argmax}_{\mathbf{x} \in A} \mathbf{x} \cdot \mathbf{d} - \mathrm{argmax}_{\mathbf{x} \in B} \mathbf{x} \cdot (-\mathbf{d})$
$\mathbf{d} \gets -\mathbf{a}$
$S \gets \{\mathbf{a}\}$
until $\mathbf{0}$ is inside the simplex:
$\mathbf{a} \gets \mathrm{argmax}_{\mathbf{x} \in A} \mathbf{x} \cdot \mathbf{d} - \mathrm{argmax}_{\mathbf{x} \in B} \mathbf{x} \cdot (-\mathbf{d})$
$\mathbf{S} \gets \mathbf{S} \cup \{\mathbf{a}\}$
if $\mathbf{x} \cdot \mathbf{d} < 0$:
return false
if origin inside the simplex:
return true
$S \gets$ the face of S nearest to the origin
$\mathbf{d} \gets $ the normal to $S$, oriented to point towards the origin

GJK in 3D