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

Intersecting Simplices

  • Base case necessary for many algorithms
  • Difficult to think of all the cases at first

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

Discrete Convex Shapes: Polyhedra

  • Two equivalent definitions of convex polyhedra:
    1. using vertices: $P = \mathrm{conv}(V)$ with $V$ a finite set of vertices
    2. using faces: $P = \{ \mathbf{x} \in \mathbb{R}^3 | A\mathbf{x} \ge \mathbf{b} \}$ where the rows of $A$ and $\mathbf{b}$ define planes
  • Reference book: Günter M. Ziegler, Lectures on Polytopes

Connectivity of Convex Polyhedra

  • The graph of convex polyhedra are planar and tri-connected
  • Recovering faces from a graph requires an embedding or rotation system
  • Convention: store neighbors of a vertex in counter-clockwise order

Adjacency List

  • 0: 1, 4, 3
  • 1: 0, 2, 5
  • 2: 1, 3, 6
  • 3: 0, 7, 2
  • 4: 0, 5, 7
  • 5: 1, 6, 4
  • 6: 2, 7, 5
  • 7: 3, 4, 6

Recovering Faces from an Embedded Graph

  • Start from some directed edge $(u, v)$
  • Find $w$, the predecessor of $u$ in the list of neighbors of $v$
  • Repeat with edge $(v, w)$ until returning to the starting point

Adjacency List

  • 0: 1, 4, 3
  • 1: 0, 2, 5
  • 2: 1, 3, 6
  • 3: 0, 7, 2
  • 4: 0, 5, 7
  • 5: 1, 6, 4
  • 6: 2, 7, 5
  • 7: 3, 4, 6

Pre-processing polyhedra

  • Often need to do many operations with the same polyhedron
  • Don't want to traverse the entire polyhedron at each step
  • Need a data-structure that's invariant to translations and rotations

Polyhedral Hierarchies

See [Dobkin and Kirkpatrick, 1990] or [Edelsbrunner, 1987]

  • $P_0$ is the input polyhedron $P$
  • $P_k$ is a tetrahedron
  • Each step removes $O(n)$ vertices from $P_{i-1}$ (thus $k = O(\log n)$)
  • None of the vertices removed between $P_{i-1}$ and $P_i$ are adjacent in $P_i$
  • Those vertices also have bounded degrees

Constructing a Polyhedral Hierarchy Ⅰ

  • Greedy selection of vertices to delete

define $\mathrm{VerticesToDelete}\left(P\right):$
$S \gets \emptyset$
$I \gets \emptyset$
for each vertex $v$ of $P$:
if $v$ is not in $S$ and $v$ has degree less than $8$:
$I \gets I \cup \{v\}$
for each vertex $u$ adjacent to $v$:
$S \gets S \cup \{u\}$
return $I$

Constructing a Polyhedral Hierarchy Ⅱ

  • Remove vertices selected in $I$ one at a time
  • This results in one loop of edges around a hole that needs to be patched up
  • By simulation of simplicity, we can patch it up using triangles
  • Note: there's only one vertex of $P_{i-1}$ not in $P_{i}$ on the other side of the new faces

Using a Polyhedral Hierarchy for Intersection Tests

  • Start with tetrahedra at the bottom of the hierarchy: constant-time base case
  • Keep track of two points $\mathbf{p}_i$ and $\mathbf{q}_i$: minimum-distance pair
  • Whenever $\mathbf{p}_i = \mathbf{q}_i$: we're done and the polyhedra intersect
  • Otherwise update them with the minimum of:
    1. The current minimum distance between $P_i$ and $Q_i$
    2. The part of $P_{i-1}$ that's closer than $\mathbf{p}_i$ to $Q_{i-1}$
    3. The part of $Q_{i-1}$ that's closer than $\mathbf{q}_i$ to $P_{i-1}$
  • The last two cases involve constant-size polyhedra too!

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{a} \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