The Sort-First Architecture for Interactive 3D Graphics
Carl Mueller / April, 1995
Designing a computer system to support interactive 3D graphics is a
challenging problem. To draw complex scenes on high-resolution
displays in real-time, you need a tremendous amount of computing
power. Moreover, as the processing demands easily exceed that which
can be had from a single processor, you need an architecture that maps
the rendering algorithm to a set of processors and the communications
paths between them.
Let's start with a basic review of the rendering problem. Objects to
be drawn are represented as groups of mathematical "primitives"
defined in a cartesian coordinate system. Drawing the objects
requires two major operations: transformation and rasterization. In
the first operation, the system considers the current viewpoint and
mathematically transforms the primitives' vertex coordinates from
object space into screen space. With the second operation, the system
rasterizes the primitives by examining which screen pixels they
overlap and then coloring in the appropriate contribution for each one.
In order to get cutting-edge performance, one must use multiple
processors for both transformation and rasterization. One must then
decide how to split up and recombine the workload. Since
graphics is a kind of sorting problem (each primitive must be matched
up with the right set of pixels), one must decide at what stage in the
processing to place the shuffling for the sort. The shuffling or
sorting can happen before or after either of the transformation of
rasterization stages, and thus we have the architectures sort-first,
sort-middle, and sort-last.
Each architecture has its own advantages and disadvantages. In this
paper presented at the 1995
Symposium on Interactive 3D Graphics, I briefly review these
issues and discuss why sort-first is an architecture worth persuing.
I go on to cover various sort-first issues. Perhaps the most
important is load-balancing, or deciding how to assign to the
processors nearly equal portions of the workload (thus resulting in an
My dissertation work involves the implementation of a sort-first
system. To this end, I must solve a variety of issues, including
load-balancing, dealing with primitive migration, and support of
high-level database operations, all the while keeping overhead down
and efficiency up.
In my 1997 paper I examine
the issues involving support of hierarchical graphics databases
on the sort-first architecture. This paper was published in the
proceedings of the 1997 Parallel Rendering Symposium. There's a
page with color plates as
well (it's big: 3.5 MB).