`
`disk enclosed
`
`IBM
`
`SAMSUNG-1008
`
`Page 1 of 659
`
`SAMSUNG-1008
`Page 1 of 659
`
`

`

`
`
`GRAPHICS
`
`GEMS
`
`*
`
`|||
`
`
`
`SAMSUNG-1008
`
`Page 2 of 659
`
`SAMSUNG-1008
`Page 2 of 659
`
`

`

`
`
`This is a volume in
`
`The Graphics Gems Series
`
`A Collection of Practical Techniques
`for the Computer Graphics Programmer
`
`Series Editor
`
`‘ Andrew Glassner
`Xerox Palo Alto Research Center
`
`Palo Alto, California
`
`SAMSUNG-1008
`
`Page 3 of 659
`
`SAMSUNG-1008
`Page 3 of 659
`
`

`

`
`
`GRAPHICS
`
`GEMS
`
`III
`
`
`
`
`
`
`edited by
`
`DAVID KIRK
`
`California Institute of Technology
`Computer Graphics Laboratory
`Pasadena, California
`
`ACADEMIC PRESS, INC.
`
`Harcourt Brace jovanovich, Publishers
`Boston
`San Diego NewYork
`London
`Sydney Tokyo Toronto
`
`SAMSUNG-1008
`
`Page 4 of 659
`
`SAMSUNG-1008
`Page 4 of 659
`
`

`

`
`
`This book is printed on acid-free paper.
`
`6?)
`
`Copyright © 1992 by Academic Press, Inc.
`All rights reserved.
`No part of this publication may be reproduced or
`transmitted in any form or by any means, electronic
`or mechanicalLincluding photocopy, recording, or
`any information storage and retrieval system, without
`permission in mining from the publisher.
`
`ACADEMIC PRESS, INC.
`1250 Sixth Avenue, San Diego, CA 92101-4311
`
`United Kingdom Edition published by
`ACADEMIC PRESS LIMITED
`24~28 Oval Road, London NW1 7DX
`
`Library of Congress Cataloging-in—Publication Data
`
`Graphics gems III/ edited by David Kirk.
`p.
`cm.—-(’l‘he Graphics gems series)
`Includes bibliographical references and index.
`ISBN 0~12—409670~0 (with IBM disk: alk. paper).—ISBN
`0—12-409671-9 (with Macintosh disk: alk. paper)
`1. Computer graphics.
`1. Kirk, David, 1960~ .
`T385.G6973
`1992
`006.6’6—dc20
`
`II. Series.
`
`92-4467
`CIP
`
`Printed in the United States of America
`92939495MM987654321
`
`SAMSUNG-1008
`
`Page 5 of 659
`
`SAMSUNG-1008
`Page 5 of 659
`
`

`

`
`
`About the Cover
`
`Cover image copyright © 1992 TheIVALlS Group, RenderMan® image created by The VALlS Group,
`reprinted from Graphics Gems III, edited by David Kirk, copyright © 1992 Academic Press, Inc. All
`rights reserved.
`This cover image evolved out of a team effort between The VALIS Group, Andrew Glassner,
`Academic Press, and the generous cooperation and sponsorship of the folks at Pixar. Special thanks
`go to Tony Apodaca at Pixar for post-processing the gems in this picture using advanced Render-
`Man® techniques. The entire cover image was created using RenderMan® from Pixar.
`We saw the Graphics Gems III cover as both an aesthetic challenge and an opportunity ’to'
`demonstrate the kind of images that can be rendered with VALIS’ products and Pixar’s RenderMan®.
`Given the time constraints, all of the geometry had to be kept as simple as possible so as not to
`require any complex and lengtlw modeling efforts. Since RenderMart®works best when the geometric
`entities used in a 3-D scene are described by high order surfaces, most of the objects consisted of
`surfaces made up of quadric primitives and bicubic patches. Andrew’s gem data and the Archimedean
`solids from the VALIS Prime RliBTM library are—the only polygonal objects in the picture.
`Once all of the objects were defined, we used'Pixar’s Showplacem, a 3-D scene arranging
`application on the Mac, to position the objects and compose the scene. Showplace also allowed us to
`position the camera and the standard light sources as well as attach shaders to the objects.
`In RenderMan®, shaders literally endow everything in the image with their own characteristic
`appearances, from the lights and the objects to the atmosphere. The shaders themselves are
`procedural descriptions of a material or other phenomenon written in the RenderMan® Shading
`Language. We did not use any scanned textures or 2-D paint retouching software to produce this
`picture.
`.
`Where appropriate, we used existing shaders on the surfaces of objects in this picture, taken from
`our commercially available VG ShadersTM + VG LooksTM libraries. For example,we used Hewn Stone
`Masonry (Volume 3) to create the temple wall and well; Stone Aggregate (Volume 3) for the
`jungle-floor, and polished metal (Volume 2) for the gold dish. In addition to these and other existing
`shaders, several new shaders were created for this image. The custom shaders include those for the
`banana leaves, the steamy jungle atmosphere, the well vapor, and the forest canopy dappled lighting
`efiect.
`Shaders also allowed us to do more with the surfaces than merely effect the way they are colored.
`In RenderMan®, shaders can transform simple surfaces into more complex forms by moving the
`surface geometry to add dimension and realistic detail. Using shaders we turned a cylinder into a
`stone well, spheres into boulders and rocks, and a flat horizontal plane into a jungle floor made up of
`stones and pebbles.
`Similarly, we altered the surface opacity to create holes in surfaces. In this instance, we produced
`the ragged edges of the banana leaves and the well vapor by applying our custom RenderMan®
`shaders to flat pieces of geometry before rendering with PhotoRealistic RenderMan®.
`Initially, this image was composed at a screen resolution of 450 X 600 pixels on a Macllfx using
`Showplace. Rendering was done transparently over the network on a Unix® workstation using Pixar’s
`NetRenderManTM. This configuration afi‘orded us the convenience and flexibility of using a Mac for
`design and a workstation for quick rendering and preview during the picture-making process.
`Once the design was complete, the final version of the image was rendered at 2250 X 3000 pixel
`resolution. The final rendering of this image was done on a 486 PC/DOS machine with Truevision’s
`RenderPakTM and Horizon860TM card containing 32 MBytes of RAM.
`During the rendering process, RenderMan® separates shadows into a temporary file called a
`shadow map. The 2k X 2k shadow map for this image was rendered in less than an hour. However,
`using shaders to alter the surface geometry increases rendering time and memory requirements
`dramatically. As a result, we had to divide the image into 64 separate pieces and render each one
`individually. The total rendering time for all 64 pieces was 41.7 hours. Once these were computed,
`
`SAMSUNG-1008
`
`Page 6 of 659
`
`SAMSUNG-1008
`Page 6 of 659
`
`

`

`
`
`ABOUT THE COVER
`
`the TIFF tools from Pixar's RenderMan ToolkitTM were used to join the pieces together into a single,
`33 MByte image file.
`When the image was ready for output to film, we transferred the image file to a removable
`cartridge and sent it to a local output service. They output the electronic file onto 4 X 5 Ecktachrome
`color film and had it developed. The transparency was then sent to Academic Press in Cambridge,
`Massachusetts where they added the title and other elements to the final cover and had everything
`scanned and turned into four-color separations which were then supplied to their printer.
`We hope you like this image. Producing it was fun and educational. As you might guess: many
`“ graphic gems” were employed in the software used to produce this picture.
`
`Mitch Prater, Senior Partner
`Dr. Bill Kolomyjec, Senior Partner
`RoseAnn Alspektor, Senior Partner
`The VALIS Group
`Pt. Richmond, CA
`March, 1992
`
`vi
`
`SAMSUNG-1008
`
`Page 7 of 659
`
`SAMSUNG-1008
`Page 7 of 659
`
`

`

`
`
`SAMSUNG-1008
`
`Page 8 of 659
`
`
`
`The Symbol © denotes gems that have accompanying C implentations in the Appendix.
`
`xvii
`
`m x
`
`xz'
`
`xxvz‘iz'
`
`17
`
`20
`
`vii
`
`Foreword _
`By Andrew Glassner
`
`Preface
`
`Mathematical Notation
`
`Pseudo-Code
`
`Contributors
`
`_|_
`IMAGE PROCESSING
`
`Introduction
`
`1. Fast Bitmap Stretching ©
`Tomas Moller
`
`2. General Filtered Image Rescaling <C>
`Dale Schumache’r
`
`3; Optimization of Bitmap Scaling Operations ©
`Dale Schumacher
`
`4. A Simple Color Reduction Filter ©
`‘ Dennis Bragg
`
`SAMSUNG-1008
`Page 8 of 659
`
`

`

`
`
`CONTENTS
`
`5. Compact lsocontours from Sampled Data
`Douglas Moore and Joseph Warren
`
`6. Generating Isovalue Contours from a Pixmap ©
`Tim Feldman
`
`7. Compositing Black-and-Whl'te Bitmaps
`David Salesz'n and Ram Barzel
`
`8. 25-1) Depth-of—Field Simulation for Computer
`Animation
`
`Cary Scofield
`
`9. A Fast Boundary Generator for Composited
`Regions ©
`Eric Fuman
`
`L
`NUMERiCAL AND PROGRAMMING
`
`TECH N Q U ES
`
`Introduction
`
`1. IEEE Fast Square Root ©
`Steve Hill
`’
`
`2. A Simple Fast Memory Allocator ©
`Steve Hill
`3. The Rolling Ball ©
`Andrew J. Hanson
`
`.
`
`_
`
`4. Interval Arithmetic ©
`Jon Rokne
`
`5. Fast Generation of Cyclic Sequences ©
`Alan W Paeth
`
`6. A Generic Pixel Selection Mechanism
`
`Alan W Paeth
`
`viii
`
`23
`
`29
`
`34
`
`36
`
`39
`
`47
`
`48
`
`49
`
`51
`
`61
`
`.
`
`67
`
`77
`
`SAMSUNG-1008
`
`Page 9 of 659
`
`SAMSUNG-1008
`Page 9 of 659
`
`

`

`
`
`CONTENTS
`
`7. Nonuniform Random Points Sets Via Warping
`Peter Shirley
`
`8. Cross Product in Four Dimensions and Beyond
`Ronald N. Goldman
`
`9. Face-Connected Line Segment Generation in an
`n—Dimensional Space
`Diane?" Badouel and Charles A. Wilthm‘ch
`
`ll
`«
`MODELING AND TRANSFORMATIONS
`Introduction
`
`1. Quaternion Interpolation with Extra Spins ©
`Jack Morrison
`
`2. Decomposing Projective Transformations
`v Ronald N. Goldman
`
`3. Decomposing Linear and Affine Transformations
`Ronald N. Goldman
`
`4. Fast Random Rotation Matrices ©
`James Arvo
`
`5. Issues and Techniques for Keyframing Transformations
`Paul Dana
`
`6. UniformRandom Rotations ©
`Ken Shoemake
`
`. Interpolation Using Bézier Curves ©
`Gershon Elbe?"
`
`8. Physically Based Superquadrics ©
`A. H. Barr
`
`80‘
`
`84
`
`'89\
`
`95
`
`96
`
`98
`
`108
`
`117
`
`121
`
`124
`
`133
`
`I37
`
`SAMSUNG-1008
`
`Page 10 of 659
`
`SAMSUNG-1008
`Page 10 of 659
`
`

`

`
`
`
`
`CONTENTS
`
`2—D GEOMETRY AND ALGORITHMS
`
`lV
`
`Introduction
`
`l. A Parametric Elliptical Arc Algorithm <C>
`Jerry Van Alcen and Ray Simar
`
`2. Simple Connection Algorithm for 2-D Drawing ©
`Claudio Rosatz'
`3. A Fast Circle Clipping Algorithm ©
`Raman V. Sr‘z'nz‘vasan
`'
`
`4. Exact Computation of 2-D Intersections ©
`Clifiord A. Shafier and Charles D. Feus‘tel
`
`5. Joining TWO Lines with a Circular Arc Fillet ©
`Robert D. Miller
`
`6. Faster Line Segment Intersection ©
`Franklin Antonio
`
`7. Solving the Problem of Apollonius and Other
`Related Problems
`Constantin A. Sevici
`
`L
`3—D GEOM ETRY AN D ALGORITH MS
`
`Introduction
`
`1. Triangles Revisited
`Fernando J. Lopez-Lopez
`
`.
`
`2. Partitioning a 3-D Convex Polygon with an
`Arbitrary Plane <C>
`Norman Chin
`
`3. Signed Distance from Point to Plane <C>
`Priamos Georgiades
`
`I
`
`)
`
`163
`
`164
`
`173
`
`182
`
`188
`
`193
`
`199
`
`203
`
`213
`
`215
`
`219
`
`223
`
`SAMSUNG-1008
`
`Page 11 of 659
`
`SAMSUNG-1008
`Page 11 of 659
`
`

`

`
`
`(CONTENTS
`
`
`
`4
`
`. Grouping Nearly Coplanar Polygons into Coplanar
`Sets
`
`David Salesin and_Filippo Tampieri
`
`Newell’s Method for Computing the Plane Equation
`of a Polygon
`Filippo Tampieri
`Plane-to-Plane Intersection ©
`Priamos Georgiades
`
`. Triangle—Cube Intersection ©
`Douglas Voorhies
`. Fast n—Dimensional Extent Overlap Testing <C>
`Len Wanger and Mike Fusco
`
`‘
`
`. Subdividing Simplices ©
`Doug Moore
`
`10' Understanding Simploids
`Doug Moore
`
`11.
`
`Converting Bézier Triangles into Rectangular
`Patches
`Dani Lischinslci
`
`12. Curve Tesselation Criteria through Sampling
`Terence Lindgren, Juan Sanchez, and Jim Hall
`
`i
`RAY TRACING AND RADIOSITY
`
`Introduction
`
`1
`
`2
`
`. Ray Tracing with the BSP Tree ©
`Kelvin Sung and Peter Shirley
`
`. Intersecting a Ray with a Quadn'c Surface
`Joseph M. Cychosz and Warren N. Waggenspaclc, Jr.
`
`225‘
`
`231
`
`233
`
`236
`
`240
`
`244
`
`250
`
`256
`
`262
`
`269
`
`271
`
`275
`
`xi
`
`SAMSUNG-1008
`
`Page 12 of 659
`
`SAMSUNG-1008
`Page 12 of 659
`
`

`

`
`
`CONTENTS
`
`. Use of Residency Masks and Object Space Partitioning
`to Eliminate Ray—Object Intersection Calculations
`Joseph M. Gychosz
`. A Panoramic Virtual Screen for Ray Tracing ©
`F. Kenton Musgrave
`
`. Rectangular Bounding Volumes for Popular
`Primitives
`Ben Tmmbare
`
`. A Linear-Time Simple Bounding Volume Algorithm
`Xiaolz'n Wu
`
`. Physically Correct Direct Lighting for Distribution Ray
`Tracing <C>
`'
`'
`Changyaw Wang
`. Hemispherical Projection of a Triangle ©
`Bumz'ng Bian
`
`. Linear Radiosity Approximation Using Vertex-to-Vertex
`Form Factors
`V
`Nelson L. Mcm: and Michael J. Allison
`
`10.
`
`Delta Form-Factor Calculation for the Cubic
`
`Tetrahedral Algorithm
`Jefirey C. Be'ran—Koehn and Mark J. Pavicz'c
`
`11.
`
`Accurate Form-Factor Computation ©
`Filippo Tampiem'
`
`fl
`RENDERING
`
`Introduction
`1. The Shadow Depth Map Revisited ©
`Andrew Woo
`
`xii
`
`284
`
`288
`
`295
`
`301
`
`307
`
`314
`
`318
`
`324
`
`329
`
`337
`
`338
`
`SAMSUNG-1008
`
`Page 13 of 659
`
`SAMSUNG-1008
`Page 13 of 659
`
`

`

`
`
`’ CONTENTS
`
`2. Fast Linear Color Rendering ©
`Russell 0. H Cheng
`. Edge and Bit-Mask. Calculations for Anti-Aliasing ©
`Russell C. H. Cheng
`
`3
`
`. Fast Span Conversion: Unrolling Short Loops ©
`Thom Grace
`
`. Progressive Image Refinement Via Gn‘dded
`Sampling
`Steve Hollasch
`
`. Accurate’Polygon Scan Conversion Using Half-Open
`Intervals
`Kurt Fleischer and David Salesz'n
`
`. Darklights
`Andrew S. Glassner
`
`. Anti—Aliasing in Triangular Pixels
`Andrew S. Glasgner
`
`. Motion Blur on Graphics Workstations <C>
`John Snyder, Ronen Barzel and Steve Gabriel
`
`10.
`
`The Shader Cache: A Rendering Pipeline Accelerator
`James Arvo and Cary Scofield
`
`E;
`C UTILITIES
`
`Graphics Gems C Header File
`Andrew Glassner
`
`2-D and 3-D Vector C Library—Corrected and Indexed
`Andrew Glassner
`
`Useful C Macros for Vector Operations
`Steve Hollasch
`
`343
`
`' 349
`
`. 355
`
`358
`
`362
`
`366
`
`369
`
`374
`
`383
`
`393
`
`396
`
`405
`
`Xlli
`
`SAMSUNG-1008
`
`Page 14 of 659
`
`SAMSUNG-1008
`Page 14 of 659
`
`

`

`
`
`CONTENTS
`
`L
`APPENDIX
`
`C IMPLEMENTATIONS
`
`Fast Bitmap Stretching
`
`General Filtered Image Rescaling
`
`Optimization of Bitmap Scaling Operations
`
`A Simple Color Reduction Filter
`
`Generating lsovalue Contours from a Pixmap
`
`A Fast Boundary Generator for Composited
`Regions
`
`IEEE Fast Square Root
`A Simple Fast Memory Allocator
`
`The Rolling Ball
`
`Interval Arithmetic
`
`Fast Generation of Cyclic Sequences
`
`Face-Connected Line Segment Generation in an
`n—Dimensional Space
`
`Quaternion Interpolation with Extra Spins
`
`Fast Random Rotation Matrices
`Uniform Random Rotations
`
`Interpolation Using Bézier Curves
`
`Physically Based Superquadrics
`
`A Parametric Elliptical Arc Algorithm
`
`Simple Connection Algorithm for 2-D Drawing
`
`A Fast Circle Clipping Algorithm
`
`Exact Computation of 2-D Intersections
`
`1.1
`
`1.2
`
`1.3
`
`1.4
`
`1.6
`
`1.9
`
`11.1
`
`11.2
`
`' 11.3
`
`11.4
`
`11.5
`
`11.9
`
`111.1
`
`111.4 ‘
`
`111.6
`
`111.7
`
`111.8
`
`IV.1
`
`1V.2
`
`1V.3
`
`1V.4
`
`xiv
`
`411
`
`414
`
`425
`
`429
`
`432
`
`441
`
`446
`
`448
`
`452
`
`454
`
`458
`
`460
`
`461
`
`463
`
`465
`
`468
`
`472
`
`478 ,
`480
`
`487
`
`491
`
`SAMSUNG-1008
`
`Page 15 of 659
`
`SAMSUNG-1008
`Page 15 of 659
`
`

`

`
`
`’CONTENTS
`
`Joining Two Lines with a Circular Arc Fillet
`
`Faster Line Segment Intersection
`
`Partitioning a 3-D Convex Polygon with an
`Arbitrary Plane
`
`Signed Distance from Point to Plane
`
`Grouping Nearly Coplanar Polygons into
`Coplanar Sets
`
`Newell’s Method for Computing the Plane Equation
`of a Polygon
`
`Plane-to-Plane Intersection
`
`Triangle—Cube Intersection
`
`Fast n—Dimensional Extent Overlap Testing
`
`Subdividing Sirnplices
`
`Converting Bézier Triangles into Rectangular
`Patches
`'
`
`'Ray Tracing With the BSP Tree
`
`Intersecting a Ray with a Quadric Surface
`
`A Panoramic Virtual Screen for Ray Tracing
`
`Rectangular Bounding Volumes for
`Popular Primitives
`
`Physically Correct Direct Lighting for Distribution
`Ray Tracing
`
`Hemispherical Projection of a Triangle
`
`IV.5
`
`IV.6
`
`V.2
`
`V.3
`
`V4
`
`V5
`
`V.6
`
`V7
`
`V8
`
`V.9
`
`V.11
`
`v1.1
`
`V1.2
`
`v1.4
`
`v1.5
`
`VI.7
`
`V1.8
`
`V1.10
`
`Delta Form-Factor Calculation for the
`
`VI.11
`
`VII.1
`
`VII.2
`
`Cubic Tetrahedral Algorithm
`
`Accurate Form—Factor Computation
`
`The Shadow Depth Map Revisited
`
`Fast Linear Color Rendering
`
`496
`
`500‘
`
`502
`
`- 5-11
`
`512
`
`517
`
`519
`
`521
`
`536
`
`538
`
`547
`
`551
`
`555
`
`562
`
`569
`
`575
`
`577
`
`582
`
`583
`
`SAMSUNG-1008
`
`Page 16 of 659
`
`SAMSUNG-1008
`Page 16 of 659
`
`

`

`
`
`CONTENTS
`
`VII.3
`
`Edge and Bit-Mask Calculations for Anti-Aliasing
`
`VII.4
`
`Fast Span Conversion: Unrolling Short Loops
`
`VII.5
`
`Progressive Image Refinement Via Gridded
`Sampling
`
`VII.6 Accurate Polygon Scan Conversion Using
`Half-Open Intervals
`
`VII.9 Motion Blur on Graphics Workstations
`
`References
`
`Index
`
`‘
`
`I
`
`586
`
`594
`
`597
`
`599
`
`606
`
`61 1
`
`. 625
`
`xvi
`
`SAMSUNG-1008
`
`Page 17 of 659
`
`SAMSUNG-1008
`Page 17 of 659
`
`

`

`
`
` FOREWORD
`
`by Andrew Glassner
`
`techniques, and
`Welcome to Graphics Gems III, an entirely new collection of tips,
`algorithms for the practicing computer graphics programmer. Many ideas that were once
`passed on through personal contacts or chance conversations can now be found here,
`clearly explained and demonstrated. Many are illustrated with accompanying source code.
`It is particularly pleasant for me to see new volumes of Gems, since each is something
`of a surprise. The original volume was meant to be a self-contained collection. At the last
`moment we included a card with contributor’s information in case there might be enough
`interest to someday prepare a second edition. When the first volume was finished and at
`the printer’s, I returned to my research in rendering, modeling and animation techniques.
`As with the first volume, I was surprised by the quantity and quality of the contributions
`that came flowing in. We realized there was a demanda need for an entirely new second
`volume, and Graphics Gems II was born. The same cycle has now repeated itself again,
`and we have happily arrived at the creation of a third collection of useful graphics tools.
`Since the first volume of Graphics Gems was published, I have spoken to many readers
`and discovered that these books have helped people learn graphics by starting with
`working codes and just exploring intuitively. I didn’t expect people to play with the codes
`so freely, but I think I now see why this helps. It is often exciting to start learning a new
`medium by simply messing around in it, and understanding how it flows. My piano teacher
`encourages new students to begin by spending time playing freely at the keyboard: keep a
`few scales or chord progressions in mind, but otherwise explore the spaces of melody,
`harmony, and rhythm. When I started to learn new mediums in art classes, I often spent
`time simply playing with the medium: squishing clay into odd shapes or brushing paint on
`paper in free and unplanned motions. Of course one often moves on to develop control
`and technique in order to communicate one’s message better, but much creativity springs
`from such uncontrolled and spirited play.
`It is difficult for the novice to play at programming. There is little room for simple
`expression or error. A simple program does not communicate with the same range and
`strength as a masterfully simple line drawing or haunting melody. A programmer cannot
`hit a few wrong notes, or tolerate an undesired ripple in a line. If the syntax isn’t right, the
`program won’t compile;
`if the semantics aren’t right,
`the program won’t do anything
`interesting. There are exceptions to the latter statement, but they are notable because of
`their rarity. If you're going to write a program to accomplish a task, you’ve got to do some
`things completely right, and everything else almost perfectly. That can be an intimidating
`realization, particularly for the beginner: if a newly constructed program doesn’t work, the
`problem could be in a million places, anywhere from the architecture to data structures,
`
`_
`
`xvii
`
`
`
`i
`
`SAMSUNG-1008
`
`Page 18 of 659
`
`SAMSUNG-1008
`Page 18 of 659
`
`

`

`
`
`
`'
`FO REWO RD
`
`algorithms, or coding errors. The chance to start with something that already works
`removes the barrier to exploration: your program already works. If you want to change it,
`you can, and you will discover which new ideas work and which ones don’t.
`I believe that the success of the Graphics Gems series demonstrates something very
`positive about our research and practice communities. The modern view of science is an
`aggregate of many factors, but one popular myth depicts the researcher as a dispassionate
`observer who seeks evidence for some ultimate truth. The classical model is that this
`objective researcher piles one recorded fact upon another, continuously improving an
`underlying theoretical basis. This model has been eroded in recent years, but it remains
`potent in many engineering and scientific texts and curricula. The practical application of
`computer graphics is sometimes compared to a similarly theoretical commercial industry:
`trade secrets abound, and anything an engineer learns remains proprietary to the firm for
`as long as possible, to capitalize on the advantage. I do not believe that either of these
`attitudes are accurate or fruitful in the long run. Most researchers are biased. They believe
`something is true, from either experience or intuition, and seek support and verification
`for that truth. Sometimes there are surprises along the way, but one does not simply
`juggle symbols at random and hope to find a meaningful equation or program. It is our
`experience and insight that guide the search for new learning and limited truths, or the
`clear demonstration of errors of the guiding principle. I hail these prejudices, because
`they form our core beliefs, and allow us to choose and judge our work. There are an
`infinite number of interesting problems, and many ways to solve each one. Our biases help
`us pick useful problems to solve, and to judge the quality and elegance of the solution. By
`explicitly Stating our beliefs, we are better able to understand them, emphasizing some
`and'expunging others, and improve. Programmers of graphics software know that the
`whole is much more than the sum of the parts. A snippet of geometry can make a complex
`algorithm simple, or the correct, stable analytical solution can replace an expensive
`numerical approximation. Like an orchestral arranger,
`the software engineer weaves
`together the strengths and weaknesses of the tools available to make a new program that
`is more powerful than any component.
`When we share our components, we all benefit. Two products may share some basic
`algorithms, but that alone hardly makes them comparable. The .fact that so many people
`have contributed to Gems shows that we are not afraid to demonstrate our preferences
`for what is interesting and what is not, what is good and what is bad, and what is
`appropriate to share with colleagues.
`I believe that the Graphics Gems series demonstrates some of the best qualities in the
`traditional models of the researcher and engineer. Gems are written by programmers who
`work in the field who are motivated by the opportunity to share some interesting or useful
`technique with their colleagues. Thus we avoid reinventing the Wheel, and by sharing this
`information, we help each other move towards a common goal of amassing a body of
`useful techniques to be shared throughout the community.
`I believe computer graphics has the potential to go beyond its current preoccupation
`with photorealism and simple surfaces and expand into a new creative medium. The
`materials from which we will shape this new medium are algorithms. As our mastery of
`algorithms grows, so will our ability to imagine new applications and make them real,
`enabling new forms of creative expression. I hope that the algorithms in this book will
`, help each of us move closer to that goal.
`
`xviii
`
`SAMSUNG-1008
`
`Page 19 of 659
`
`SAMSUNG-1008
`Page 19 of 659
`
`

`

`
`
`This volume attempts to continue along the path blazed by the first two
`volumes of this series, capturing the spirit of the creative graphics
`programmer. Each of the Gems represents a carefully crafted technique
`or idea that has proven useful for the respective author. These contribu-
`tors have graciously allowed these ideas to be shared with you. The
`resulting collection of ideas,
`tricks,
`techniques, and tools is a rough
`sketch of the character of the entire graphics field. It represents the
`diversity of the field, containing a wide variety of approaches to solving
`problems, large and small. As such, it “takes the pulse” of the graphics
`community, and presents you with ideas that a wide variety of individuals
`find interesting, useful, and important. I hope that you will find them so as
`well.
`
`This book can be used in many ways. It can be used as a reference, to
`find the solution to a specific problem that confronts you. If you are
`addressing the same problem as one discussed in a particular Gem,
`you’re more than halfway to a solution, particularly if that Gem provides
`C orC + + code. Many of the ideas in this volume can also be used as a
`starting point for new work, providing a fresh point of View. However you
`choose to use this volume, there are many ideas contained herein.
`This volume retains the overall structure and organization, mathemati-
`cal notation, and style of pseudo—code as in the first and second volumes.
`Some of the individual chapter names have been changed to allow a
`partitioning that is more appropriate for the current crop of Gems. Every
`attempt has been made to group similar'Gems in the same chapter. Many
`of the chapter headings appeared in the first two volumes, although some
`are new. Ray tracing and radiosity have been combined into one chapter,
`since many of the gems are applicable to either technique. Also, a chapter
`more generally titled “Rendering” has been added, which contains many
`algorithms that are applicable to a variety of techniques for making
`pictures.
`As in the second volume, we have taken some of the important sections
`from the first volume and included them verbatim. These sections
`
`are entitled “Mathematical Notation,” “Pseudo-Code,” and the listings,
`
`xix
`
`
`
`SAMSUNG-1008
`
`Page 20 of 659
`
`SAMSUNG-1008
`Page 20 of 659
`
`

`

`
`
`'
`
`PREFACE
`
`“Graphics Gems C Header File,” and “2-D and 3-D Vector Library,” the
`last of which was revised in volume two of Graphics Gems.
`At the end of most Gems, there are references to similar Gems whether
`in this volume or the previous ones,
`identified by volume and page
`number. This should be helpful in providing background for the Gems,
`although most of them stand quite well on their own. The only back-
`ground assumed in most cases is a general knowledge of computer
`graphics, plus a small amount of skill in mathematics.
`The C programming language has been used for most of the program
`listings in the Appendix, although several of the Gems have C + +
`implementations. Both languages are widely used, and the choice of
`which language to use was left to the individual authors. As in the first
`two volumes, all of the C and 0+ + code in this book is in the public
`domain, and is yours to study, modify, and use. AS of this writing, all of
`the code listings are available via anonymous ftp transfer from the
`machines ‘weedeater.math.yale.edu’ (internet address 128.36.28.17), and
`‘princetonedu" (internet address 128.112.128.1). ‘princetonedu’ is the
`preferred site. When you connect to either of these machines using ftp,
`_ log in as ‘anonymous’ giving your full e—mail address as the password.
`Then use the ‘cd’ command to move to the directory ‘pub/ Graphics-
`Gems’ on ‘Weedeater’, or the directory ‘pub/Graphics/GraphicsGems’
`on ‘princeton’. Code for Graphics Gems I,
`II, and III is kept
`in
`directories named ‘Gems’, ‘Gemsll’, and ‘GemslII’, respectively. Down-
`load and read the file called ‘README’ to learn about where the code is
`
`kept, and how to report bugs. In addition to the anonymous ftp site, the
`source listings of the gems are available on the enclosed diskette in either
`IBM PC format or Apple Macintosh format.
`Finally, I’d like to thank all of the people who have helped along the
`way to make this volume possible. First and foremost, I’d like to thank
`Andrew Glassner for seeing the need for this type of book and starting the
`series, and to Jim Arvo for providing the next link in the chain. I’d also
`like to thank all of the contributors, who really comprise the heart of the
`book. Certainly, without their cleverness and initiative, this book would
`not exist.
`I owe Jenifer Swetland and her assistant Lynne Gagnon a great
`deal for their magical abilities applied toward making the whole produc-
`tion process go smoothly. Special thanks go to my diligent and thoughtful
`reviewers—Terry Lindgren, Jim Arvo, Andrew Glassner, Eric Haines,
`Douglas Voorhies, Devendra Kalra, Ronen Barzel and John Snyder. With-
`out their carefully rendered opinions, my job would have been a lot
`harder. Finally, thank you to Craig Kolb for providing a safe place to keep
`the public domain C code.
`
`SAMSUNG-1008
`
`Page 21 of 659
`
`SAMSUNG-1008
`Page 21 of 659
`
`

`

`
`
`lln {
`
`
`MATH EMATICAL
`
`NOTATION
`
`
`Geometric Objects
`
`0
`
`,b,C
`,Q
`,m
`
`,Bmg>~we: ‘P
`
`the number 0,
`point (0, 0, 0)
`real numbers (lower-case italics)
`
`the zerovvector, the point (0,0), the
`
`points (upper-case italics)
`lines (lower-case bold)
`vectors (upper-case bold) (components A)
`matrix (upper-case bold)
`angles (lower—case greek)
`
`Derived Objects
`
`the vector perpendicular to A (valid only in 2D, where
`Ai = (—Ay,Ax))
`the inverse of matrix M
`
`the transpose of matrix M
`
` M*
`
`the adjoint of'matrix M (M‘1 = det(M) )
`
`» det(M)
`
`determinant of M
`same as above
`
`element from row 1, column j of matrix M (top-left is
`(0, 0))
`all of row i of matrix M
`
`SAMSUNG-1008
`
`Page 22 of 659
`
`SAMSUNG-1008
`Page 22 of 659
`
`

`

`II
`
`-
`
`SAMSUNG-1008
`
`Page 23 of 659
`
`
`
`
`
`MATHEMATICAL NOTATION
`
`Ma
`A ABC
`LABC
`
`all of column j of matrix M
`triangle formed by points A, B, C
`angle formed by points A, B, C with vertex at B
`
`Basic Operators
`
`+)—)/’*
`
`X
`
`standard math operators
`the dot (or inner or scalar) product
`the cross (or outer or vector) product
`
`Basic Expressions and Functions
`
`n i
`
`[X]
`[X]
`al b
`a mod b
`
`Bye)
`
`xxii
`
`floor of x (largest integer not greater than x)
`ceiling of x (smallest integer not smaller than x)
`modulo arithmetic; remainder of a + b
`same as above
`Bernstein polynomial = (
`n!
`binomial coefficient ——-—.—-_-
`(n — 1)!1!
`
`)ti(1 ~ 0“”, i = 0 -
`
`-
`
`SAMSUNG-1008
`Page 23 of 659
`
`

`

`
`
`
`
`PSEUDO-CODE
`
`
`
`Declaratiens (not required)
`
`name: TYPE <— initialValue;
`examples:
`‘
`7rzreal <— 3.14159;
`v: array [0.3] of integer
`
`<— [0, 1,2, 3];
`
`Primitive Data Types
`
`array [lowerBound..upperBoundi of TYPE;
`boolean
`char
`
`integer
`real
`double
`
`point
`vector
`
`matrixS
`
`equivalent to:
`matrix3: record [array [02] of array [02] of real;];
`example: m: Matrix3 (— [[1.0, 2.0, 3.0], [4.0, 5.0, 6.0], [708.0, 9.01];
`m[2][l] is 8.0
`m[0][2] <— 3.3,‘
`
`assigns 3.3 to upper-right corner of matrix
`
`xxiii
`
`
`
`SAMSUNG-1008
`
`Page 24 of 659
`
`SAMSUNG-1008
`Page 24 of 659
`
`

`

`
`
`PSEU DO-CODE
`
`matrix4
`
`equivalent to:
`matrix4: record [array [0.3] of array [03] of real;l;
`example: m: Matrix4 <— l
`I
`l1.0,2.0,3‘0,4.0],
`[5.0, 6.0, 7.0, 8.0],
`l9.0,10.0, 11.0, 12.0],
`[130,140, 15,016.00;
`ml3ll1l is 14.0
`
`mlOllBl <- 3.3;
`
`assigns 3.3 to upper-right comer of matrix
`
`Records (Structures)
`
`Record definition:
`Box: record [
`
`left, right, top, bottom: integer;
`l;
`
`newBox: Box (— newlBoxl;
`dynamically allocate a new instance of Box and return a pointer to it
`
`newBox.left «— 10;
`this same notation is appropriate whether newBox is a pointer or
`structure
`
`Arrays
`
`v: array [0.3] of integer <— lO, 1,2, 3]; u is a four-element array of integers
`
`lel <- 5;
`
`assign to third element of 1)
`
`Comments
`
`A comment may appear anywhere—it is indicated by italics
`
`xxiv
`
`SAMSUNG-1008
`
`Page 25 of 659
`
`SAMSUNG-1008
`Page 25 of 659
`
`

`

`
`
`PSEUDO—CODE
`
`Blocks
`
`begin
`
`Statement;
`Statement;
`
`end;
`
`Conditionals and Selections
`
`if Test
`
`then Statement;
`[else Statement];
`
`result = select Item from
`instance: Statement;
`endcase: Statement;
`
`else clause is optional
`
`Flow Control
`
`for ControlVariable: Type <— InitialBtpr, NextFJtpr do
`Statement;
`~
`endloop;
`
`until Test do
`
`Statement;
`endloop;
`
`while Test do
`Statement;
`endloop;
`
`loop; go directly to the next endloop
`
`exit; go directly to the first statement after the next endloop
`
`returnlvalue]
`
`return value as the result of this function} call
`
`XXV
`
`
`
`SAMSUNG-1008
`
`Page 26 of 659
`
`SAMSUNG-1008
`Page 26 of 659
`
`

`

`
`
`PSEUDO-CODE
`
`Logical Connectives
`
`or, and, not, xor
`
`Bitvvise Operators
`
`bit-or, bit-and, bit-xor
`
`Relations
`
`=, *1 >’ >3 <? 5
`
`Assignment Symbol
`(—
`
`lnote: the test for equality is =)
`
`Available Functions
`
`These functions are defined on all data types
`
`minla, bl
`maxla, b)
`absla)
`sinlxl
`cosix)
`tanlx)
`
`arctan (y)
`arctan2ly, x)
`arcsin (y)
`arccos(y)
`rshiftlx, bl
`lshiftlx, b)
`swapla, b)
`lerpla, l, h)
`
`returns minimum of a and b
`returns maximum of a and b
`returns absolute value of a
`sinlx)
`coslx}
`tanlx)
`
`arctanly)
`arctan(y /x), defined for all values of x and y
`arcsin (y)
`arccosly)
`shift x right b bits
`shift x left b bits
`swap 0 and b
`linear interpolation: ((1 — a)*l} + (a*h) = I + (a*(h — U)
`
`'
`
`xxvi
`
`SAMSUNG-1008
`
`Page 27 of 659
`
`SAMSUNG-1008
`Page 27 of 659
`
`

`

`
`
`PSEUDO—CODE
`
`clamp(v, l, h)
`
`return I if!) < I, else 11 if u > h, else u: min(h,max(l, U))
`
`round x towards 0 to first integer
`round x away from 0 to first integer
`I round x to nearest integer, if frac(x) = .5, round towards
`
`0 f
`
`ractional part of x
`
`,
`
`floor(x) or [x] ,.
`ceiling(x) or [x]
`round(x)
`
`frac(x)
`
`fl
`
`
`
`mmm‘brmwziy'fi'fli.rye-r32::15:
`
`
`xxvii
`
`SAMSUNG-1008
`
`Page 28 of 659
`
`SAM