### The Sort-First Architecture for Interactive 3D Graphics

Carl Mueller / April, 1995

#### Introduction

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.

#### Basic Rendering

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.

#### Parallel Rendering

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.

#### Sort-First

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
efficient system).
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).