Newsgroups: comp.graphics,comp.graphics.algorithms From: ph+@cs.cmu.edu (Paul Heckbert) Subject: Graphics Gems IV Date: Tue, 17 May 1994 05:46:15 GMT The book "Graphics Gems IV", which I edited, was just printed and should be appearing in bookstores about now (mid-May). title: Graphics Gems IV editor: Paul S. Heckbert published: AP Professional (Academic Press), Boston, 1994 price: $49.95 575 pages, comes with either MAC or IBM floppy disk ISBN 0-12-336156-7 with MAC floppy ISBN 0-12-336155-9 with IBM (DOS) floppy (5.25") Below are two things: * the preface to the book, to explain what it is about * the table of contents ====================================================================== PREFACE This book is a cookbook for computer graphics programmers, a kind of ``Numerical Recipes'' for graphics. It contains practical techniques that can help you do 2D and 3D modeling, animation, rendering, and image processing. The 52 articles, written by 54 authors worldwide, have been selected for their usefulness, novelty, and simplicity. Each article, or ``Gem'', presents a technique in words and formulas, and also, for most of the articles, in C or C++ code as well. The code is available in electronic form on the IBM or Macintosh floppy disk in the back pocket of the book, and is available on the Internet via FTP (see address below). The floppy disk also contains all of the code from the previous volumes: Graphics Gems I, II, and III. You are free to use and modify this code in any way you like. A few of the Gems in this book deserve special mention because they provide implementations of particularly useful, but non-trivial algorithms. Gems IV.6 and IV.8 give very general, modular code to polygonize parametric and implicit surfaces, respectively. With these two and a polygon renderer, you could probably display 95% of all computer graphics models! Gem I.5 finds 2D Voronoi diagrams or Delaunay triangulations. These data structures are very widely used for mesh generation and other geometric operations. In the area of interaction, Gem III.1 provides code for control of orientation in 3-D. This could be used in interactive 3-D modelers. Finally, Gem I.8 gives code to find collisions of polyhedra, an important task in physically-based modeling and animation. This book, like the previous three volumes in the Graphics Gems series, lies somewhere between the media of textbook, journal, and computer bulletin board. Textbooks explain algorithms very well, but if you are doing computer graphics programming, then they may not provide what you need: an implementation. Similarly, technical journals seldom present implementations, and they are often much more theoretical than a programmer cares for. The third alternative, computer bulletin boards such as the USENET news group comp.graphics.algorithms, occasionally contain good code, but because they are unmoderated and unedited, they are so flooded with queries that it is tedious to find useful information. The Graphics Gems series is an attempt at a middle ground, where programmers worldwide can contribute graphics techniques that they have found useful, and the best of these get published. Most of the articles are written by the inventors of the techniques, so you will learn their motivations and see their programming techniques firsthand. Also, the implementations have been selected for their portability; they are not limited to UNIX, IBM, or Macintosh systems. Most of them will compile and run, perhaps with minor modifications, on any computer with a C or C++ compiler. Assembling this book has been a collaborative process involving many people. In the Spring of 1993, a call for contributions was distributed worldwide via electronic mail and word of mouth. Submissions arrived in the Summer of 1993. These were read by me and many were also read by one or more of my outside reviewers: Eric Haines, Andrew Glassner, Chandrajit Bajaj, Tom Duff, Ron Goldman, Tom Sederberg, David Baraff, Jules Bloomenthal, Ken Shoemake, Mike Kass, Don Mitchell, and Greg Ward. Of the 155 articles submitted, 52 were accepted for publication. These were revised and, in most cases, formatted into Latex by the authors. Coordinating the project at Academic Press in Cambridge, Massachusetts, were Jenifer Niles and Brian Miller. Book composition was done by Rena Wells at Rosenlaui Publishing Services in Houston, Texas, and the cover image was made by Eben Ostby of Pixar, in Richmond, California. I am very thankful to all of these people and to the others who worked on this book for helping to make it a reality. Great thanks also to the "Graphics Gems" series editor, Andrew Glassner, for inviting me to be editor for this volume, and to my wife, Bridget Johnson-Heckbert, for her patience. There are a few differences between this book and the previous volumes of the series. Organizationally, the code and bibliographies are not collected at the back of the book, but appear with the text of the corresponding article. These changes make each Gem more self-contained. The book also differs in emphasis. Relative to the previous volumes, I have probably stressed novelty more, and simplicity less, preferring an implementation of a complex computer graphics algorithm over formulas from analytic geometry, for example. In addition to the "Graphics Gems" series, there are several other good sources for practical computer graphics techniques. One of these is the column ``Jim Blinn's Corner'' that appears in the journal "IEEE Computer Graphics and Applications". Another is the book "A Programmer's Geometry", by Adrian Bowyer and John Woodwark (Butterworth's, London, 1983), which is full of analytic geometry formulas. A mix of analytic geometry and basic computer graphics formulas is contained in the book "Computer Graphics Handbook: Geometry and Mathematics" by Michael E. Mortensen (Industrial Press, New York, 1990). Another excellent source is, of course, graphics textbooks. Code in this book is available on the Internet by anonymous FTP from princeton.edu (128.112.128.1) in the directory pub/GraphicsGems/GemsIV. The code for other "Graphics Gems" books is also available nearby. Bug reports should be submitted as described in the README file there. Paul Heckbert, March 1994 ====================================================================== TABLE OF CONTENTS Below is the table of contents for "Graphics Gems IV". This table also serves as an index to the code in the FTP collection. Note that every article has text that appears in the book but not in the FTP archive, and some articles contain no C or C++ code. file or book chapter title and author directory chapter ------------------------------------------------------------ I POLYGONS AND POLYHEDRA centroid.c I.1 Centroid of a Polygon Gerard Bashein and Paul R. Detmer convex_test/ I.2 Testing the Convexity of a Polygon Peter Schorn and Frederick Fisher ptpoly_weiler/ I.3 An Incremental Angle Point in Polygon Test Kevin Weiler ptpoly_haines/ I.4 Point in Polygon Strategies Eric Haines delaunay/ I.5 Incremental Delaunay Triangulation Dani Lischinski vert_norm/ I.6 Building Vertex Normals from an Unstructured Polygon List Andrew Glassner I.7 Detecting Intersection of a Rectangular Solid and a Convex Polyhedron Ned Greene collide.c I.8 Fast Collision Detection of Moving Convex Polyhedra Rich Rabbitz ------------------------------------------------------------ II GEOMETRY II.1 Distance to an Ellipsoid John C. Hart dist_fast.c II.2 Fast Linear Approximations of Euclidean Distance in Higher Dimensions Yoshikazu Ohashi outcode/ II.3 Direct Outcode Calculation for Faster Clip Testing Walt Donovan and Tim Van Hook sph_poly.c II.4 Computing the Area of a Spherical Polygon Robert D. Miller II.5 The Pleasures of `Perp Dot' Products F. S. Hill, Jr. II.6 Geometry for N-Dimensional Graphics Andrew J. Hanson ------------------------------------------------------------ III TRANSFORMATIONS arcball/ III.1 Arcball Rotation Control Ken Shoemake III.2 Efficient Eigenvalues for Visualization Robert L. Cromwell inv_fast.c III.3 Fast Inversion of Length- and Angle-Preserving Matrices Kevin Wu polar_decomp/ III.4 Polar Matrix Decomposition Ken Shoemake euler_angle/ III.5 Euler Angle Conversion Ken Shoemake III.6 Fiber Bundle Twist Reduction Ken Shoemake ------------------------------------------------------------ IV CURVES AND SURFACES data_smooth/ IV.1 Smoothing and Interpolation with Finite Differences Paul H. C. Eilers IV.2 Knot Insertion using Forward Differences Phillip Barry and Ron Goldman IV.3 Converting a Rational Curve to a Standard Rational Bernstein-Bezier Representation Chandrajit Bajaj and Guoliang Xu curve_isect/ IV.4 Intersecting Parametric Cubic Curves by Midpoint Subdivision R. Victor Klassen patch_conv.C IV.5 Converting Rectangular Patches into Bezier Triangles Dani Lischinski nurb_polyg/ IV.6 Tessellation of NURB Surfaces John W. Peterson IV.7 Equations of Cylinders and Cones Ching-Kuang Shene implicit.c IV.8 An Implicit Surface Polygonizer Jules Bloomenthal ------------------------------------------------------------ V RAY TRACING V.1 Computing the Intersection of a Line and a Cylinder Ching-Kuang Shene ray_cyl.c V.2 Intersecting a Ray with a Cylinder Joseph M. Cychosz and Warren N. Waggenspack, Jr. vox_traverse.c V.3 Voxel Traversal along a 3D Line Daniel Cohen multi_jitter/ V.4 Multi-Jittered Sampling Kenneth Chiu, Peter Shirley, and Changyaw Wang minray/ V.5 A Minimal Ray Tracer Paul S. Heckbert ------------------------------------------------------------ VI SHADING VI.1 A Fast Alternative to Phong's Specular Model Christophe Schlick VI.2 R.E versus N.H Specular Highlights Frederick Fisher and Andrew Woo VI.3 Fast Alternatives to Perlin's Bias and Gain Functions Christophe Schlick VI.4 Fence Shading Uwe Behrens ------------------------------------------------------------ VII FRAME BUFFER TECHNIQUES VII.1 XOR-Drawing with Guaranteed Contrast Manfred Kopp and Michael Gervautz VII.2 A Contrast-Based Scalefactor for Luminance Display Greg Ward dyn_range/ VII.3 High Dynamic Range Pixels Christophe Schlick ------------------------------------------------------------ VIII IMAGE PROCESSING emboss.c VIII.1 Fast Embossing Effects on Raster Image Data John Schlag coons_warp.c VIII.2 Bilinear Coons Patch Image Warping Paul S. Heckbert convolve.c VIII.3 Fast Convolution with Packed Lookup Tables George Wolberg and Henry Massalin thin_image.c VIII.4 Efficient Binary Image Thinning using Neighborhood Maps Joseph M. Cychosz clahe.c VIII.5 Contrast Limited Adaptive Histogram Equalization Karel Zuiderveld mrsfoley.im VIII.6 Ideal Tiles for Shading and Halftoning Alan Wm Paeth ------------------------------------------------------------ IX GRAPHIC DESIGN IX.1 Placing Text Labels on Maps and Diagrams Jon Christensen, Joe Marks, and Stuart Shieber graph_layout/ IX.2 Dynamic Layout Algorithm to Display General Graphs Laszlo Szirmay-Kalos ------------------------------------------------------------ X UTILITIES trilerp.c X.1 Tri-linear Interpolation Steve Hill interp_fast.c X.2 Faster Linear Interpolation Steven Eker vec_mat/ X.3 C++ Vector and Matrix Algebra Routines Jean-Francois Doue GraphicsGems.c X.4 C Header File and Vector Library GraphicsGems.h Andrew Glassner and Eric Haines ====================================================================== Paul Heckbert ph@cs.cmu.edu Computer Science Dept., Carnegie Mellon University 5000 Forbes Ave, Pittsburgh PA 15213-3891, USA