IV. A NEW RESAMPLING TECHNIQUE

The Original Resampling Algorithm

Before describing the new resampling method, the method on which it is based is discussed. To begin, a brief description of the original and resampled spaces is given. The original space is some 3D curvilinear grid. This grid is labeled in i,j,k space, and each 3D unit is a cell. For the resampled grid data, the size is regular (though not necessarily cubical), and this grid is in x,y,z space. Here the 3D unit is a voxel. To aid the resampling process, the original algorithm also has a third grid, a course grid to separate the irregular grid. This course grid helps to reduce the search space when determining which cells influence which voxels.

In the particular problem studied, a CFD simulation from a turbo jet compressor, the irregular data has a size of 18 X 46 X 60. The rectilinear grid, in x,y,z space, has dimensions 64 X 128 X 128. (These values are obtained by doubling each dimension of the irregular grid, and using the next highest power of two to reduce aliasing artifacts). The intermediary course grid has dimensions 5 X 5 X 5.

It is worth noting there are three distinct cases when locating the influence of cells on voxels. The easiest case is a cell and a voxel covering (approximately) the same volume space. The second is a voxel being larger than the size of a cell. In this case, points within the cell determine the value of the voxel. The last case is a cell larger than a voxel. Here, the two points closest to the voxel determine the voxel's value. If there exist many instances of either cases two or three, the image may lose quality.

Abstractly, the resampling algorithm has the structure

• Initialize
• Cast the irregular grid into a course grid
• Determine which voxels contain or are contained by cells
• For all tagged voxels
  • find the influencing ijk points
  • calculate the value
• Render the resulting vector field

The original algorithm consists of three main steps. First, after some initialization steps, the irregular grid is separated into a small number (5 X 5 X 5) of course ijk space cells. Each of these cells merely contains which points from the original curvilinear grid are within it.

Next, the algorithm resamples the data into a rectilinear grid. Initially, the algorithm determines for each cell the voxels that the cell influences. For each such voxel, a flag is set to indicate the voxel requires processing. (It is possible that some voxels lie outside the cell space, and hence should not have any value.) Then, for this regular grid, the algorithm computes for each tagged voxel which irregular points it contains; or, which ijk cell contains the voxel, if the voxel is smaller than a cell. If the latter is the true, the algorithm locates the two closest ijk points, and uses those to calculate the voxel's value. If the former, the voxel's value is the weighted average of the ijk points within the voxel.

Lastly, the algorithm computes a vector field from the rectilinear grid. The volume-tracing rendering algorithm then uses the vector field to generate a 3D image.

The New Resampling Algorithm

The new algorithm is similar to the original. The difference is how the algorithm determines which cells influence which voxels. The new algorithm has the form

• Initialize
• For each cell, determine which voxel(s) it influences and store in (each) voxel's list
• For all voxels having a non empty list, calculate the value
• Render the resulting vector field

Rather than separating the two steps to determine which voxels should have a value, and to find which particular ijk points influence those values, these now occur in one step. Also, there is no intermediate course grid, since its only purpose is to lessen the number of cells traversed for each voxel. Instead, each voxel has a list of ijk points which influence its value. This improves the original algorithm by removing the N3 search for each voxel, through the irregular cell structure. Instead, there is one search through the curvilinear grid, during which the algorithm creates a list for each voxel, of influencing ijk points.

To find which ijk points influence a voxel, the following occurs. For each cell, the algorithm checks whether the min and max of the eight points overlap more than one voxel. If not, that voxel contains the cell, and its eight points are added to the voxel's list. (The algorithm always checks to ensure that it includes no duplicate cell points). Otherwise, the algorithm 3D scan converts the curvilinear cell to determine which voxels the cell influences. The procedure adds the appropriate cell points to each voxel's lists.

The former algorithm simply uses the min and max values of a cell to determine that a voxel is inside an ijk cell. The problem with this is that a curvilinear cell is not generally the same size as its min-max values. The min and max 3D points provide a bounding box for the ijk cell; this ensures that no voxel will be missed, but the bounding box often is larger than the cell. Therefore, the previous algorithm inaccurately includes some curvilinear points as influencing a given voxel.

After the algorithm generates each voxel's list, the algorithm continues as the original. Only now, for each voxel the algorithm knows the influencing ijk points; thus, the algorithm simply calculates the inverse-distance weighted average. As before, the new technique then generates a vector field, and lastly renders a 3D image based on the vector field.

---