Efficiently Splitting Indexed Triangle Lists

The task of the collideMgr object is to split these indexed triangle lists into a single message for each voxel. However, this task is rather difficult to perform efficiently, because we must somehow collect all the points referenced by a each set of triangles.

Let there be $p$ total (unsplit) points, $v$ voxels, and $t$ triangles per voxel. Since the number of voxels can be large, and triangles should be distributed among voxels relatively evenly, $p$ is normally much larger than $t$.

The brute-force solution- for each point, check to see if any relevant triangle references it- is clearly $O(pt)$. Since the process will be repeated once for every voxel, the brute force approach is $O(vpt)$.

We of course can do better by first marking the points used by each triangle, then collecting all the marked points. If we mark points using a table, this approach is $O(t+p)$ for each voxel, because it takes $O(p)$ time to clear all the marks initially, $O(t)$ time to mark some of the points, and then $O(p)$ again to collect the marked points. Repeating for every voxel gives $O(v(t+p))$ overall.

Theoretically, we could eliminate the factor of $p$ by marking each voxel's $O(t)$ referenced points with a hashtable. In practice, the large constant factor associated with a hashtable access^A.3 makes this approach unattractive.

A much better solution is to mark all referenced points in a linked array structure. Each entry of this array indicates whether the corresponding point has been marked, and if so, links to the next marked point. Then marking a new point takes (a very small) constant time; and all referenced points can be collected by following the links, in $O(t)$ time. We can also clear all the marks by following the links. Thus the only $O(p)$ operation needed is initialization, for a total run time across all voxels of $O(vt+p)$. Since both $v$ and $p$ can be large, this is a substantial improvement.