ABSTRACT
Given that we want to rasterize P primitives for a particular frame, and assuming that each primitive consists of an average of p pixels, the complexity of rasterization is in general O(Pp). Previous stages in the graphics pipeline (e.g., transformations and culling) work with the vertices of primitives only. In general, the complexity of these previous stages is O(Pv), where v is the average number of vertices of a primitive. Usually p v, so we must ensure that rasterization algorithms are extremely efficient in order to avoid making the rasterization stage a bottleneck in the graphics pipeline.
