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