Source: {"pile_set_name": "USPTO Backgrounds"}

1. Field of the Invention
The invention relates to three-dimensional graphics, and, more particularly, to geometry processing in a three-dimensional graphics rendering pipeline.
2. Related Art
Displaying large three-dimensional models at high frame rate requires substantial system performance, both in terms of computations and memory bandwidth. One of the computational bottlenecks in such systems is the geometry processing of the graphics rendering pipeline, which typically requires more processing than a single processor system can provide.
In order to attain satisfactory performance levels for such geometry processing, multiple operations must be performed concurrently. In other words, concurrent processing is required. Concurrent-processing has two basic forms: pipelining and parallelism. A more detailed description of these problems and related issues is set forth in Foley et al., xe2x80x9cComputer Graphics: Principles and Practice, 2nd ed.xe2x80x9d, Addison-Wesley, 1990, pp. 866-882, herein incorporated by reference in its entirety.
The present invention is directed to the parallelism form of concurrent processing. It has been proposed that the geometry processing of the graphics pipeline be parallelized by distributing the graphics primitives amongst multiple processors for concurrent processing, and replicating state-changing commands at each processor. Such an approach is set forth in Foley et al., xe2x80x9cComputer Graphics: Principles and Practice, 2nd ed.xe2x80x9d, Addison-Wesley, 1990, pp. 881, incorporated by reference above. However, the computational overhead in replicating such state-changing commands at each processor limits the performance benefits that may be achieved via distribution of the graphics primitives amongst multiprocessors. Thus, there is a need in the art to increase the performance of graphics rendering systems through parallelization of geometry processing amongst multiple processors.
The problems stated above and the related problems of the prior art are solved with the principles of the present invention, method for parallelizing geometric processing in a graphics rendering pipeline. More specifically, the geometric processing of an ordered sequence of graphics commands is distributed over a set of processors by the following steps. The sequence of graphics commands is partitioned into an ordered set of N subsequences S0 . . . SNxe2x88x921, and an ordered set of N state vectors V0 . . . VNxe2x88x921 is associated with the ordered set of subsequences S0 . . . SNxe2x88x921. A first phase of processing is performed on the set of processors whereby, for each given subsequence Sj in the set of subsequences S0 . . . SNxe2x88x922, state vector Vj+1 is updated to represent state as if the graphics commands in subsequence Sj had been executed in sequential order. A second phase of the processing is performed whereby the components of each given state vector Vk in the set of state vectors V1 . . . VNxe2x88x921 generated in the first phase is merged with corresponding components in the preceding state vectors V0 . . . Vkxe2x88x921 such that the state vector Vk represents state as if the graphics commands in subsequences S0 . . . Skxe2x88x921 had been executed in sequential order. Finally, a third phase of processing is performed on the set of processors whereby, for each subsequence Sm in the set of subsequences S1 . . . SNxe2x88x921, geometry operations for subsequence Sm are performed using the state vector Vm generated in the second phase. Furthermore, in the third phase, geometry operations for subsequence S0 are performed using the state vector V0.
Advantageously, the present invention provides a mechanism that allows a large number of processors to work in parallel on the geometry operations of the three-dimensional rendering pipeline. Moreover, this high degree of parallelism is achieved with very little synchronization (one processor waiting from another) required, which results in increased performance over prior art graphics processing techniques.