Object interaction using tabulated spheres subsets

Tabulated Sphere Subsets (TSSs) provide a fast way to approximate collision tests between objects whose motion is constrained. A TSS is a subset of a set of spheres that approximate the shape of two objects that might collide. The subset represents only those spheres that can collide under the constrained motion. A TSS is created in three steps: 1) approximating the mesh with spheres; 2) searching the space of possible motion to find which spheres may collide: 3) extracting the spheres required for collision tests and building the table. We applied TSSs to jaw motion and skin/muscle interaction in a model dog and measured the number of spheres generated and the number of calculations needed for collision tests. In these cases TSSs outperforms several standard techniques.