Serial Performance

The 871,414 triangle dragon model of Figure  presented in [#!CL96!#] took 3.132 seconds on an Origin 2000 ^4.2.

Figure: Dragon model.

The remaining tests use a much simpler model- a tessellated plane perturbed by small harmonic waves. This simple model is easy to scale to any desired number of triangles; while retaining much of the character of an actual surface. No collisions actually occur in the simple model.

Figure  shows the wall-clock time per complete collision detection for a range of different numbers of triangles on a Linux PC ^4.3. The smallest figure shown is 1,024 triangles, which take 1.4 milliseconds or 1.4 microseconds per triangle. The largest figure is 1,048,576 triangles, which take 2.1 seconds or 2.1 microseconds per triangle. The much larger dataset cannot fit entirely in cache and is hence slightly slower.

Figure: Time per step for serial benchmark

This serial result is competitive with the figure of 2 microseconds per triangle given for the serial algorithm of Gottschalk et al. in [#!GLM96!#]. Further, the observed performance of the voxel algorithm is indeed linear in the number of triangles.