Decomposing $X$ into cells

At the outset, $X$ is decomposed into a collection of cells without considering collision detection. Suppose that $X$ is an $n$-dimensional rectangular subset of ${\mathbb{R}}^n$. If $X$ is more generally a smooth manifold, then the rectangular subset can be defined in a coordinate neighborhood. If desired, identifications can be used to respect the topology of $X$; however, coordinate changes are technically needed at the boundaries to properly express velocities (recall Section 8.3).

The most common cell decomposition is obtained by splitting $X$ into $n$-dimensional cubes of equal size by quantizing each coordinate. This will be called a cubical partition. Assume in general that $X$ is partitioned into a collection ${\cal D}$ of $n$-dimensional cells. Let $D \in {\cal D}$ denote a cell, which is a subset of $X$. It is assumed here that all cells have dimension $n$. In the case of cubes, this means that points on common boundaries between cubes are declared to belong to only one neighboring cube (thus, the cells may be open, closed, or neither).

Note that $X$ is partitioned into cells, and not ${X_{free}}$, as might be expected from the methods in Chapter 6. This means that collision detection and other constraints on $X$ are ignored when defining ${\cal D}$. The cells are defined in advance, just as grids were declared in Section 5.4.2. In the case of a cubical partition, the cells are immediately known upon quantization of each coordinate axis.