A method for adaptive parallel processing of rendering is presented. Whitman presents a historical perspective, classifying previous methods as either data non-adaptive, where the tiling is predetermined and does not change over time, or data adaptive, in which the tiling varies depending on the input data (shape, size, and distribution on the frame buffer). Whitman’s approach consists of splitting the frame buffer into rectangles, a method already used in prior work, but Whitman improves on previous approaches by limiting overhead in preprocessing, handling worst-case scenarios, and adaptively partitioning the workload.

Two phases in the rendering process are worth studying. The preprocessing of the data constitutes an average of 13 percent of the time taken in a sequential implementation of the rendering algorithm and includes transformation, face rejection, clipping, and perspective projection. The actual rendering represents 86 percent of the average sequential rendering time, including hidden surface removal, antialiasing, shading, and other visual effects. The 1 percent left is called postprocessing and involves displaying the data on a frame buffer.

The preprocessing phase is customized to take into account the number of processors available. Different strategies are recommended depending on the number of polygons to render and the number of processors available. The author indicates that possible improvements on this processing phase also depend on other system variables (such as disk  accesses). 

Parallelizing the rendering involves starting with a static scheme under which the global rendering job is equally divided among available processors. As soon as a processor finishes its task, it searches for the processor with the most work left to do. This processor’s task is then partitioned into two subtasks, one of which is assigned to each of the two processors. This scheme allows for a self-assignment of the processors to the tasks left to be done, without adding a large overhead on the processors, as most of the overhead work is performed by processors that would have been idle in a nonadaptive approach.

Whitman presents the heuristic used for determining the amount of work a processor has left to do at any given time, based on the number of scan-lines left to process. A study of anomalous situations, graphics decomposition methods, and the complexity of the algorithm follows. Some results are published, showing that the speedup over simple data-adaptive methods is between 66 percent and 90 percent, while necessitating modification of less than 3 percent of the code.

This specialized subject will gain in interest over the next few years as more computer manufacturers consider multiprocessing as a valid solution to the ever-growing demand for improved computer graphics performance. Naturally, a minimal overhead parallel graphics rendering system is a prime candidate for the scientific markets.