Voxel Interference

To determine interference between voxels of an object (and then which polygons must be tested against each other), the following steps must be undertaken:

• Computation of the inverse transformation matrices if they don't already exist:

  

• Computation of the transformation matrix from the reference frame of A to the reference frame of B:

  

  and the transformation matrix from B to A:

  

• Using the matrices computed in the previous step, determine minimum and maximum values of each object in the other's reference frame (in the same manner as when determining global bounding boxes).

• From these minimum and maximum values, determine the range of voxels (submatrices) that must be checked for spatial interference.

• Check each voxel from the submatrix of B against each voxel from the submatrix of A.

  
Figure: Interference submatrices computed in local coordinates (Source: Garcia-Alonso [GASF94])

If the object containers don't intersect, then there won't be any interference submatrices, and the two objects don't need to be tested further. Calculating the interference submatrices involves transforming the minimum and maximum values of an object into the reference frame of the other object, and then determining new minimum and maximum values in this reference frame (see figure where the submatrices are shaded). If the interference submatrices don't contain any polygons, then no further testing has to be carried out. Otherwise, each non-empty voxel from the submatrix of B is transformed and tested for interference with the voxels in the submatrix of A, an example of which is shown in figure .

  
Figure: The subset of voxels of A that have interference with one voxel of B (Source: Garcia-Alonso [GASF94])

Pairs of polygons that need to be checked for interference can then be formed, and these are then inserted into an ordered list which is passed onto the next stage after all voxels have been transformed and checked.