A Caltech Library Service

A scan line algorithm for displaying parametrically defined surfaces

Blinn, James F. (1978) A scan line algorithm for displaying parametrically defined surfaces. ACM SIGGRAPH Computer Graphics, 12 (3). p. 27. ISSN 0097-8930. doi:10.1145/965139.807364.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


This paper presents a scan line algorithm for drawing picture of parametrically defined surfaces. A scan line algorithm is characterized by the order in which it generates the picture elements of the image. These are generated left to right, top to bottom in much the same was as a picture is scanned out on a TV screen. Parametrically defined surfaces are those generated by a set of bivariate functions defining the X, Y and Z position of points on the surface. The primary driving mechanism behind such an algorithm is the inversion of the functions used to define the surface. To keep the algorithm general enough to apply to a wide variety of functional forms, this inversion is done numerically. It is only required to provide mechanism for evaluating the function and its derivatives at any parametric location. The algorithm proceeds in two phases. First, a numerical search is made to find the local maxima of the Y definition function within the desired parameter ranges. These determine when portions of the surface first become visible as the scan plane progresses down the screen. Secondly, the actual scan conversion process is performed, maintaining a list of segments of the surface intersecting the current scan plane. As the scan plane passes local maxima of the Y function new segments are added to the list. In addition, any existing segments are updated to reflect their intersection with the updated scan plane. All intersection calculations are performed by a bivariate Newton-Raphson solution of the defining equations. If the solution does not converge, it is due to the scan plane passing a local minimum, causing segments to be deleted from the active list. Finally, within one scan line, an X scan must be performed to generate the Z information about the surface for each picture element. This is also performed by a bivariate Newton-Raphson iteration with a different set of defining functions.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1978 ACM.
Subject Keywords:Computer Graphics, Hidden Surface Elimination, Bicubic Patches, Numerical Inversion
Issue or Number:3
Classification Code:CR Categories: 5.12, 5.13, 5.17, 5.4, 8.2
Record Number:CaltechAUTHORS:20160613-163040854
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67894
Deposited On:14 Jun 2016 00:00
Last Modified:11 Nov 2021 03:56

Repository Staff Only: item control page