A polyhedral C-space obstacle

Most of the previous ideas generalize nicely for the case of a polyhedral robot that is capable of translation only in a 3D world that contains polyhedral obstacles. If ${\cal A}$ and ${\cal O}$ are convex polyhedra, the resulting ${\cal C}_{obs}$ is a convex polyhedron.

Figure 4.20: Three different types of contact, each of which generates a different kind of ${\cal C}_{obs}$ face.

There are three different kinds of contacts that each lead to half-spaces in ${\cal C}$:

1. Type FV: A face of ${\cal A}$ and a vertex of ${\cal O}$
2. Type VF: A vertex of ${\cal A}$ and a face of ${\cal O}$
3. Type EE: An edge of ${\cal A}$ and an edge of ${\cal O}$ .

These are shown in Figure 4.20. Each half-space defines a face of the polyhedron, ${\cal C}_{obs}$. The representation of ${\cal C}_{obs}$ can be constructed in $O(n + m + k)$ time, in which $n$ is the number of faces of ${\cal A}$, $m$ is the number of faces of ${\cal O}$, and $k$ is the number of faces of ${\cal C}_{obs}$, which is at most $nm$ [411].