Computer Graphics (CG) Papers

The Reality of Simulated Actors

Digital Paint Systems: An Anecdotal and Historical Overview

Cameraless Movies, or Humans Wait in the Wings

Infinite Regular Hexagon Sequences on a Triangle

George Lucas Discovers Computer Graphics

The [alpha][delta][gamma]'s of Digital Media Convergence

HWB-A More Intuitive Hue-Based Color Model

Review of The Algorithmic Beauty of Plants

Planar 2-Pass Texture Mapping and Warping

The Video Computer: Image Computing in the Studio

Creating the General-Purpose Image Computer

Plants, Fractals, and Formal Languages

Computer Power for Film and Flight

Special Effects for Star Trek II: The Genesis Demo, Instant Evolution with Computer Graphics

3-D Transformations of Images in Scanline Order

The Reality of Simulated Actors

*Communications of the ACM*, 36-39, Jul 2001

Abstract. Revisit the topic of the Nov 2000 *Scientific
American* article (see Cameraless Movies below), with tighter predictions and perceptions. The subhead
(chosen by the editor) is: The acting of actors will survive the digital
revolution; their on-screen appearance may not.

Digital Paint Systems: An Anecdotal and Historical Overview

*IEEE Annals of the History of Computing*, Vol 23, No 2, Apr-Jun 2001, 4-30 (and cover)

Abstract. This document is based on lectures by the author and Dick Shoup (his article is pp 32-37 of the same issue) on early paint programs at the Computer History Museum in California, Jan 2000. A chronology of pre-1980 digital paint systems is presented, followed by a detailed anecdotal history of some of them, emphasizing the author's experience at Xerox Palo Alto Research Center (PARC) and the New York Institute of Technology (NYIT). See sampling of early paint images, presented in this article. The download below is large (about 40 mb). It includes both my paper and Dick's.

Cameraless Movies, or Digital Humans Wait in the Wings

*Scientific American*, 72-78, Nov 2000

SUBTITLE (the "deck"): Characters, scenes and entire movies have been crafted digitally. But can animators create realistic digital humans to star in computer-generated films? Actors want to know

ABSTRACT: The completely computer-generated movie is already with us, but is still in the realm of cartoons. When will a "live-action" movie be computer generated? In particular, will human actors be replaced by computer graphic simulations? It is argued that the representations of actors might be replaced but not the acting. In other words, it is valuable to separate the actor from his or her representation, as we do in animation already and as we do on the internet too, when using avatars. The article also estimates, with as much accuracy as can be mustered, when we might expect the representations of humans might reach the point of realism: Not so soon as sometimes predicted.

Infinite Regular Hexagon Sequences on a Triangle

*Experimental Mathematics*, Vol 9, No 3, Nov 2000, 397-406

Abstract. The well-known dual pair of Napoleon equilateral triangles intrinsic to each triangle is extended to infinite sequences of them, shown to be special cases of infinite regular hexagon sequences on each triangle. A set of hexagon-to-hexagon transformations, the hex operators, is defined for this purpose, a set forming an abelian monoid under function composition. The sequences result from arbitrary strings of hex operators applied to a particular truncation of a given triangle to a hexagon. The deep structure of the sequence constructions reveals surprising infinite sequences of non-concentric, symmetric equilateral triangle pairs parallel to one of the sequences of hexagons and provides the most visually striking contribution. Extensive experimentation with a plane geometry educational program inspired all theorems, proofs of which utilize eigenvector analysis of polygons in the complex plane.

©1997-2011, Alvy Ray Smith, All Rights Reserved.

The figure above, from the paper, shows the first two elements of two infinite "sceptre" sequences and two infinite regular hexagon sequences, for any triangle. A sceptre is a pair of congruent equilateral triangles with parallel sides, such that a vertex of each lies on a side of the other - see the figure, where a red-blue pair of equilaterals forms a sceptre. Its name is derived from "symmetric, congruent, equilateral pairs of triangles". The hexagon sequences are centered over the centroid of the given triangle, which is almost obscured by the other forms. (It is almost entirely enclosed by the gray parallelogram.) Notice that the sceptres have sides parallel one of the sequences of hexagons, and their diagonals (dashed line) pass through the centroid of the given triangle. Less obvious: If you join the topmost red triangle vertex to the leftmost blue triangle vertex, the line formed is parallel the other sequence of regular hexagons.

Sketches and scripts for
*The Geometer's Sketchpad* (TGS),
illustrating the theorems, are available
here. The
file *hex.txt* is a text file explaining the other files available. A
Java version
of one of the theorems is now online. Try out the theorem interactively.

See other recent geometric art.

A poem, *Tools of Vision*, by Neelon Crawford, Oct 2000, 35

Friend and expert photographer, Neelon Crawford, is publishing a book of his photographs of "big science" - those superb instruments such as telescopes and accelerators that are used to see the largest and smallest things in our universe. He has asked scientists at the various facilities and his friends to contribute words on the general topic of "tools of vision". My contribution is this poem, my first in print. Tools of Vision is the exhibition catalog for Neelon's photographs on exhibit in the Rotunda Gallery of the National Academy of Sciences, Washington DC, 26 Sep 2000 - 15 Jan 2001. See Polar Fine Arts for photos and writings.

George Lucas Discovers Computer Graphics

*IEEE Annals of the History of Computing*, Vol 20, No 2: 48-49, 1998

EXCERPT: My colleagues and I have been blessed by a
sequence of individuals of a unique variety I call *accidental visionarie*s . . . .
Three of them, Alexander Schure (patron of the New York Institute of Technology's
computer graphics lab), George (*Star Wars*) Lucas, and Steven Jobs (cofounder of
Apple), have directly influenced my life . . . . This story, for example, is about how
filmmaker Lucas discovered computer graphics. (Available electronically, for a
fee, from the IEEE Annals 1998 archives. This article is included in a set,
called *Graphics Remembrances*, edited by Jules Bloomenthal.)
[Note Rodney Stock's remembrance, immediately following mine, of a key
moment in the discovery of the distributed ray-tracing paper that would
solve motion blur for Pixar.]

*Computer Graphics World*, 27-29, Jul 1998

Abstract. On the 25th anniversary of SIGGRAPH, a computer-graphics pioneer reflects on the achievements of the past and the hopes for the future Moore's Law put into more useful form ("10x in 5"). Several dreams that have come true in computer graphics. A list of challenges and non-challenges, the real "to do" list.

The [alpha][delta][gamma]'s of Digital Media Convergence

*Proceedings Graphics Interface '98*, 51-56, 1998

Abstract. There is no theoretical roadblock obstructing the integration of different media types into a single digital medium—after all, bits are bits—but there are several real problems hindering the so-called digital convergence. The alpha problem is that between premultiplied and non-premultiplied alpha. The gamma problem concerns the nonlinearity that many of today's applications insist on burning into their image data. The delta problem is about the integration of the discrete and the continuous—eg, samples (pixels) and geometry. The subtleties of these are explored—eg, "square pixels" and non-rectangular images—and a current example of how wrong things can get—the US digital television transmission formats battle—is elaborated.

HWB—A More Intuitive Hue-Based Color Model

With Eric Lyons, *the journal of graphics tools*, Vol 1, No 1: 3-17, 1996

Abstract. The two most common color selector models, other than RGB (Red-Green-Blue), are the hue-based HSV (Hue-Saturation-Value) and HSL (Hue-Saturation-Lightness) color models. It is shown that both of these models are flawed. A closely related model, HWB (Hue-Whiteness-Blackness), is introduced that avoids the flaws, is slightly faster to compute, and is very easy to teach to new users: Choose a hue. Lighten it with white. Darken it with black. That whitening is not the complement of blackening is explained. (The two pages below should be consulted for fixes to errata in the paper.)

C code implementing the color transforms in the paper:

download HWB to RGB transforms

download HSV to RGB transforms

With Jim Blinn, *SIGGRAPH 96 Conference Proceedings*, Annual Conference Series, 259-268, 1996

Abstract. A classical problem of imaging—the *matting
problem*—is separation of a non-rectangular foreground image from a (usually)
rectangular background image-for example, in a film frame, extraction of an actor from a
background scene to allow substitution of a different background. Of the several attacks
on this difficult and persistent problem, we discuss here only the special case of
separating a desired foreground image from a background of a constant, or almost constant,
*backing* color. This backing color has often been blue, so the problem, and its
solution, have been called *blue screen matting*. However, other backing colors, such
as yellow or (increasingly) green, have also been used, so we often generalize to *constant
color matting*. The mathematics of constant color matting is presented and proven to be
unsolvable as generally practiced. This, of course, flies in the face of the fact that the
technique is commonly used in film and video, so we demonstrate constraints on the general
problem that lead to solutions, or at least significantly prune the search space of
solutions. We shall also demonstrate that an algorithmic solution is possible by allowing
the foreground object to be shot against *two* constant backing colors-in fact,
against two completely arbitrary backings so long as they differ everywhere.

*Review of* The Algorithmic Beauty of Plants

Przemyslaw Prusinkiewicz and Aristid Lindenmayer,
Springer-Verlag, New York, 1990, in
*IEEE Computer Graphics and Applications*, Jul 1990, 85-86.

*Computer Graphics World*, Nov 1988, 90-94.
Also, *Geometry and Imaging—Two Distinct Kinds of Graphics*, Proceedings of the
Nippon Computer Graphics Conference (NICOGRAPH 88), Nov 1988, 229-239). Also,
*Geometry vs Imaging-Extended Abstract*, Visualization in Supercomputing,
edited by Raul H Mendez, Springer-Verlag, NY, 1990, 151-156. Also,
*Geometry vs Imaging: Extended Abstract*, Geometric Analysis and Computer Graphics,
edited by P. Concus, R. Finn, and D. Hoffman, Springer-Verlag, NY, 1991, 169-174.

Planar 2-Pass Texture Mapping and Warping

*Computer Graphics*, Vol 21, No 4, Jul 1987, 263-272 (SIGGRAPH 87 Conference Proceedings).

Abstract. The 2-pass transformation replaces
a 2D (2-dimensional) transformation with a sequence of orthogonal, simpler 1D
transformations. It may be used for the closely related processes of texture
mapping and warping in computer graphics and image processing. First, texture
maps onto planar quadric and superquadric surfaces and, second, planar bicubic
and biquadratic warps of images are shown to be 2-pass transformable. A
distinction between serial and parallel warps is introduced to solve a confusion
in terms between computer graphics and image processing. It is shown that an *n*^{th}
order serial polynomial warp is equivalent to an (*n*^{2}+*n*)^{th}
order parallel polynomial warp. It is also shown that the serial equivalent of a
parallel polynomial warp is generally not a polynomial warp, being more
complicated than a polynomial. The ususual problem of bottlenecking and the
usual one of anialiasing are discussed in the 2-pass context.

The Video Computer: Image Computing in the Studio

*Television Technology: A Look Toward the 21st Century*, Society of Motion Picture
and Television Engineers, Feb 1987, 23-27 (Selections
from the 21st Annual SMPTE Television Conference, San Francisco). Also published in
*SMPTE Journal*, Vol 97, No 3, Mar 1988, 207-208.

Abstract. A general-purpose *video
computer* is proposed which combines many studio or post-production
functions, now available only in separate pieces of equipment, and extends their
functionality. The ideal machine is described and the current state of the idea
is given. The restrictions of realtime and broadcast day are compared. The
conclusion is that video computers are already a viable idea within the
broadcast-day-turnaround criterion and that the hardware exists as so-called *image
computers*, general-purpose digital computers for the class of computations
on images. Consequently software houses could immediately begin preparing
applications on video computers for the broadcast video market.

Creating the General-Purpose Image Computer

*Computer Graphics World*, Jun 1986, pp 63-64.

A description of the Pixar Image Computer, a general-purpose computer for that class of problems dealing with images.

Plants, Fractals, and Formal Languages

*Computer Graphics*, Vol 18, No 3, Jul 1984, 1-10
(SIGGRAPH 84 Conference Proceedings). Also issued as tutorial notes at SIGGRAPH 84.

Abstract. Although fractal models of natural
phenomena have received much attention recently, there are other models of
complex natural objects which have been around longer in Computer Imagery but
are not widely known. These are procedural models of plants and trees. An
interesting class of these models is presented here which handles plant growth,
sports an efficient data representation, and has a high "database
amplification" factor. It is based on an extension of the well-known formal
languages of symbol strings to the lesser-known formal languages of labeled
graphs. It is so tempting to describe these plant models as "fractal"
that the similarities of this class of models with fractal models are explored
in an attempt at rapprochement. The models are not fractal so the common parts
of fractal theory and plant theory are abstracted to form a class of objects,
the *graftals*. This class may prove to be of great interest to the future
of Computer Imagery. Determinism is shown to provide adequate complexity,
whereas randomness is only convenient and often inefficient. Finally, a
nonfractal, nongraftal family of trees by Bill Reeves is introduced to emphasize
some of the paper's nongrammatical themes.

Computer Power for Film and Flight

*Supercomputers*, Hearings before the Committee on
Science and Technology, U.S. House of Representatives, Ninety-Eighth Congress,
No 47, US Government Printing Office, Nov 15-16, 1983, 242-246. Reprinted in *Telematics
and Informatics*, Vol 2, No 4, 1985, 293-398.

Abstract. Recent incorporation of computer graphics into feature-length films -- Return of the Jedi, Star Trek II: The Wrath of Khan, and Tron, to name a few -- has inspired a belief that entire films might soon be generated by computer. It is shown below that even so-called "supercomputers" of today [1983] fall quite short of the power required for this goal. True supercomputers are needed with capabilities just now being conceived and with cost commensurate with typical filmmaking practice. [I predict that a movie will be computed in 1995-2000.]

Some of the most sophisticated and spectacular applications of computer graphics are found in current films.

*Abacus*, Vol 1, No 1, Fall 1983, 28-45 (Cover story).

A simple tutorial on the use of computer graphics in movies. Inaugural issue of the magazine.

*Proceedings of the Nippon Computer Graphics Conference* (NICOGRAPH 82), Tokyo, Japan, Nov 1982, 11 pages.

Abstract. The organization of a 3-dimensional computer animation system is described. The basic theoretical foundations of 3D graphics are covered with emphasis on the practical applications. This includes the following topics: antialiasing (sampling and filtering, spatially and temporally), and analytic geometry (splines, polygons, quadrics, and patches). The major subsystems of a typical system are described in some detail: modeling (rigid, articulated, and procedural models), animation (of camera and model), subdivision (hierarchies of primitives, fractals), visible-surface decision (culling, hidden-surface removal, shadows), texture generation (for backgrounds and surfaces), rendering (antialiasing, texturing, shading, bump-mapping), and compositing (matting). The importance of simplified logistics and good human interfaces is emphasized.

*Special Effects for* Star Trek II: The
Genesis Demo, *Instant Evolution with Computer Graphics*

*American Cinematographer*, Vol 63, No 10, Oct 1982, 1038-1039, 1048-1050.

Complete details on the creation and production of
the *Genesis Effect* scene in *Star Trek II*.

Computer Graphics Manual, Jan 1981, 108-112 (Proceedings of ComputerVision 81).

3-D Transformations of Images in Scanline Order

With Ed Catmull, *Computer Graphics*, Vol 14, No 3, Jul 1980, 279-285 (SIGGRAPH 80 Conference
Proceedings). Also issued as tutorial notes at SIGGRAPH 82.

Abstract. Currently texture mapping onto projections of 3D surfaces is time consuming and subject to considerable aliasing errors. Usually the procedure is to perform some inverse mapping from the area of the pixel onto the surface texture. It is difficult to do this correctly. There is an alternate approach where the texture surface is transformed as a 2D image until it conforms to a projection of a polygon placed arbitrarily in 3-space. The great advantage of this approach is that the 2D transformation can be decomposed into two simple transforms, one in horizontal and the other in vertical scanline order. Sophisticated light calculation is also time consuming and difficult to calculate correctly on projected polygons. Instead of calculating the lighting based on the position of the polygon, lights, and eye, the lights and eye can be transformed to a corresponding position for a unit square which we can consider to be a canonical polygon. After this canonical polygon is correctly textured and shaded it can be easily conformed to the projection of the 3D surface.

*Computer Graphics*, Vol 13, No 2, Aug 1979,
276-283 (SIGGRAPH 79 Conference Proceedings). Also Technical Memo No 6, Computer Graphics
Lab, New York Institute of Technology, Jul 1978, issued as tutorial notes at SIGGRAPHs 78, 80-82.

Abstract. To fill a connected area of a digital image is to change the color of all and only those pixels in the area. Fill algorithms for areas defined by sharp boundaries (eg, a white area surrounded by a black curve) have been implemented at several color computer graphics installations. This paper presents an algorithm for the more difficult problem of filling areas with shaded boundaries (eg, a white area surrounded by a curve consisting of several shades of gray). These images may arise from digitizing photographs or line drawings with a scanning video camera, or they may be generated by programs which produce antialiased line segments or dekink black-and-white images. When an area in such an image is to be filled with a new color, it is desirable to have the fill algorithm understand the shaded edges and maintain the shading with shades of the new color instead of the old. The tint fill algorithm presented here accomplishes this task. Its name arises from its ability to change only the tint (hue and saturation) of a pixel, leaving the value (blackness) unchanged. Although the algorithm was motivated by and is written in terms of color, it has a more general interpretation, which is also presented.

*Computer Graphics*, Vol 12, No 3, Aug 1978,
12-19 (SIGGRAPH 78 Conference Proceedings). Reprinted in Tutorial: Computer Graphics,
edited by John C Beatty and Kellogg S Booth, IEEE Computer Society Press, Silver Spring,
MD, 2^{d} edition, 1982, 376-383.

Abstract. Digital control of color
television monitors -- in particular, via frame buffers -- has added precise
control of a large subset of human colorspace to the capabilities of computer
graphics. This subset is the gamut of colors spanned by the red, green, and blue
(RGB) electron guns exciting their respective phosphors. It is called the *RGB
monitor gamut*. Full-blown color theory is a quite complex subject involving
physics, psychology, and physiology, but restriction to the RGB monitor gamut
simplifies matters substantially. It is linear, for example, and admits to
familiar spatial representations. This paper presents a set of alternative
models of the RGB monitor gamut based on the perceptual variables hue (*H*),
saturation (*S*), and value (*V*) or brightness (*L*). Algorithms
for transforming between these models are derived. Particular emphasis is placed
on an RGB to HSV nontrigonometric pair of transforms which have been used
successfully for about four years in frame buffer painting programs. These are
fast, accurate, and adequate in many applications. Computationally more
difficult transform pairs are sometimes necessary, however. Guidelines for
choosing among the models are provided. Psychophysical corrections are described
within the context of the definitions established by the NTSC (National
Television Standards Committee).

*Tutorial: Computer Graphics*, edited by John C Beatty
and Kellogg S Booth, IEEE Computer Society Press, Silver Spring, MD, 2d
edition, 1982, pp 501-515. Also Technical Memo No 7, Computer Graphics Lab, New York
Institute of Technology, Jul 1978, issued as tutorial notes at SIGGRAPHs 78-82.

First two paragraphs of the Introduction: Paint is a menu-driven computer program for handpainting 2-dimensional images in full color. It is a highly interactive software package with which a human artist may employ the power of a digital computer to compose paintings that are entirely of his own creation. The "canvas" is actually a large piece of ditigal computer memory that is displayed for the artist on a conventional color television monitor. His "brush" is an electronic stylus resembling an ordinary pen. Its shape can be any 2-dimensional shape he desires, so long as it fits into the canvas memory space. He may choose any color he desires from a "palette" of 256 colors. If this is an inadequate selection, he may mix his own set of colors from a vast set of possibilities.

The main purpose of this tutorial is to describe in detail how an artist accomplishes these acts and what his choices are. In fact, the tutorial is designed to be read as a textbook for Paint users.

This is the paint document on which several patent
trials have hinged since it is the first place where RGB painting is recorded,
in its *Appendix B: Paint3, The RGB Version of Paint*. It also records one
of the earliest histories in its *Appendix C: Brief History of Paint Programs*.
(Appendix A is a listing of three early equipment configurations used for
painting at NYIT.) See also
*Paint*, *Table Paint,* and *Texas*
as memos that also figured into these litigations.

download the original Paint memo