USING RUNS OF CELLS TO TRAVERSE A RAY THROUGH A VOLUME

摘要

Line drawing techniques that employ runs or runs of runs of pixels to draw the line compute line structure information that they use to determine the sequence of runs in the line. This line structure information may be used to compute the positions of a plurality of the runs and then draw the runs in parallel. The line drawing techniques may be also be used with rays in three dimensions. Projections of the ray are made on planes that intersect each other on the ray's major axis. The line drawing techniques are used to determine cells in the planes that are intersected by the projections. The voxels intersected by the ray are then determined using the cells. Runs of voxels in the ray are used in ray traversals. The volume traversed by the ray is subdivided into encoding runs of voxels that may include one or more significant runs containing voxels whose data will affect the ray. Traversal is done by determining for each run of voxels in the ray whether any of the voxels in the ray run are also in a significant run.