glassner@arisia.Xerox.COM (Andrew Glassner) (10/11/89)
This is the final posting of this message. I am reposting for two reasons: first, to reach students and faculty at schools that run on a quarters schedule (and thus may have missed earlier postings) and second to urge anyone who has thought of contributing to actually get around and do it! Think of the number of times you've seen a message like "I'd like an algorithm to do X..." followed by a flurry of "Me too"s. Often there's some lively discussion, which ends with a good summary in some form: a piece of pseudo-code, an equation, or a pointer to a more general technique in the literature that didn't seem applicable at first. That level of activity evidences interest in a topic. A good answer should live on after the lifetime of its net dicussion. If you have provided the definitive answer to one of these discussion, you're sitting on a Gem! I encourage folks to think back on their times of developing code and remember where you got stuck. Did you find a good solution to your problem? Probably someone else will get stuck at that point again someday - write down your solution and share it with the world. If you've contributed and shared on the net, please consider contributing to this book. You may never see "how do I convert a 24 bit picture to 8 bits" again! -Andrew -------- CONTRIBUTE TO A NEW BOOK FOR COMPUTER GRAPHICS PROGRAMMERS! Contributions are solicited for a new book, tentatively titled GRAPHICS GEMS. This book will be a collection of short notes by and for computer graphics programmers and researchers. The basic idea is to create a book similar to the CRC Mathematics Handbook, only tailored to the subject of computer graphics. The motivation for Graphics Gems comes from a desire to document and share the many techniques that are a necessary part of every graphics programmer's toolbox, yet don't appear in the standard literature. Each Gem represents a solution to a problem: not necessarily a research result, nor even a deep observation, but simply a good, practical technique for dealing with a typical computer graphics programming problem. A typical Gem may be a code fragment, a short analysis of an interesting problem, a bit of mathematics, a data structure, or a geometric relationship. Here are some appropriate topics for Gems - this list contains only a few suggestions for topics that might be covered by interesting Gems, and is far from complete: Two Dimensions: Fill, smooth, blur, dither, 2d plots, line drawing, curve drawing, bounding boxes, overlapping boxes, efficient bitblit (example: automatic selection of tick marks on a plot). Three Dimensions: Scan conversion, highlight detection, shading, isosurfaces, ray intersection, form factor calculation, visibility, texturing, transformations, deformations, smoothing, 3d plotting, parameterizations, surface subdivision, texturing functions, bounding boxes (example: fast shading formulae). Graphics: Colormap hacking, object manipulations, sampling, filtering, optics, interaction techniques, modelling primitives, efficient rendering, edge detection (example: reconstruction from stochastic sampling). General Math: Algebra, calculus, geometry (e.g. why normals don't move under the same transformations as surfaces). Programming: Numerical integration, root finding, root polishing, data structures (objects), data structures (programs), inner loops, interactive debugging, graphical debugging, color map hacking, over- and under-flow detection and correction, unusual functions (e.g. polynomial root-finding). Most Gems will be about 1 or 2 final printed pages (4 or 5 pages of typewritten, double-spaced manuscript), though if you choose to include source code the listings may run longer. Rough figures and equations will be professionally redrawn by the publisher. Each contributor will have a chance to review the final copy for his or her Gems before publication. Each Gem will be clearly identified with the name and affiliation of its contributor(s). Each contributor will receive a complimentary copy of the final book. If you have developed a nice solution to a problem that others might encounter, be it a data structure, an inner loop, or even an algebraic simplification that makes your programs shorter and more robust, then it would probably make a splendid Graphics Gem. Write it up and send it to the editor at the address below, either in hardcopy or electronic mail. Acceptable formats are plain text, nroff, TeX, MacWrite, and Microsoft Word (Macintosh). I would like to receive a rough draft of all Gems by November 1989. Contribute and share your favorite tricks and techniques with the rest of the community! Send your Graphics Gems to: Andrew Glassner Editor, Graphics Gems Xerox PARC 3333 Coyote Hill Road Palo Alto, CA 94304 USA email: glassner.pa@xerox.com phone: (415) 494 - 4467
yackob@eeserv.ee.umanitoba.ca (Kerry Yackoboski) (02/20/91)
I've heard a lot about this book, and on the strength of how often it's mentioned, I'm considering ordering it. Can one person who uses the book give us a short description of what the book contains? Is it mainly code, or are the algorithms well-explained? Or is there no code? What language are the routines written in? Designed for a certain machine? I hope nobody takes a lot of time to review it - a few lines would help greatly. thanks, Kerry. -- Kerry Yackoboski <yackob@eeserv.ee.umanitoba.ca> The Scanning Tunneling Microscopy Laboratory in the Cellar U of Manitoba, Winnipeg, Canada
ccplumb@rose.uwaterloo.ca (Colin Plumb) (02/20/91)
Graphics Gems is a collection of techniques (some are formal enough to count as algorithms) contributed by various people. They range from 1 to maybe 10 pages long each and are categorized by subject. There is example code in C in the appendix, which is not particularly machine specific. The details of getting pixels onto a screen which fills half of a "Graphics programming with your IBM PC" book is not discussed. It's simply a *great* reference book. -- -Colin
wilson@cs.ucf.edu (tom wilson) (02/20/91)
In article <1991Feb19.193857.15697@ccu.umanitoba.ca> yackob@eeserv.ee.umanitoba.ca (Kerry Yackoboski) writes: >Can one person who uses the book give us a short description >of what the book contains? Is it mainly code, or are the >algorithms well-explained? Or is there no code? What language >are the routines written in? Designed for a certain machine? I don't have it yet, but here's what Paul Heckbert told me about it: From: Paul Heckbert <ph@miro.berkeley.edu> Message-Id: <9008290410.AA02927@miro.Berkeley.EDU> Here's a table of contents for the graphics gems book: Path: pasteur!miro.Berkeley.EDU!ph From: ph@miro.Berkeley.EDU (Paul Heckbert) Newsgroups: comp.graphics Subject: Graphics Gems table of contents Date: 3 Aug 90 02:14:21 GMT Organization: University of California at Berkeley Here is a table of contents for the book "Graphics Gems" that will be coming out through Academic Press at SIGGRAPH: "Graphics Gems", edited by Andrew Glassner, 833 pages total, 158 page C code appendix. The C code will be available in a few days via anonymous ftp (watch comp.graphics for an announcement). (c) copyright 1990, Academic Press, New York (*) Indicates an implementation in C in Appendix II Preface Introduction Mathematical Notation Pseudo-Code Contributors 1. 2D Geometry Useful 2D Geometry - Andrew Glassner Trigonometry Summary Useful Trigonometry - Andrew Glassner Trigonometric Functions at Select Points - Alan W. Paeth Triangles - Ronald Goldman Generating Random Points in Triangles (*) - Greg Turk Fast Line-Edge Intersections on a Uniform Grid (*) - Andrew Shapira Anti-Aliasing Summary Area of Intersection: Circle and a Half-Plane - Kelvin Thompson Area of Intersection: Circle and a Thick Line - Kelvin Thompson Area of Intersection: Two Circles - Kelvin Thompson Anti-Aliasing Summary Vertical Distance From a Point to a Line - Kelvin Thompson A Fast 2D Point-on-Line Test (*) - Alan W. Paeth Fast Circle-Rectangle Intersection Checking (*) - Clifford A. Shaffer 2. 2D Rendering Circles of Integral Radius on Integer Lattices - Alan W. Paeth Nice Numbers for Graph Labels (*) - Paul S. Heckbert Efficient Generation of Sampling Jitter Using Look-up Tables (*) - Joseph M. Cychosz Scan Conversion Summary Fast Anti-Aliasing Polygon Scan Conversion (*) - Jack C. Morrison Generic Convex Polygon Scan Conversion and Clipping (*) - Paul S. Heckbert Concave Polygon Scan Conversion (*) - Paul S. Heckbert Fast Scan Conversion of Arbitrary Polygons - Bob Wallis Line Drawing Summary Digital Line Drawing (*) - Paul S. Heckbert Symmetric Double Step Line Algorithm (*) - Brian Wyvill Rendering Anti-Aliased Lines (*) - Kelvin Thompson An Algorithm for Filling in 2D Wide Line Bevel Joints - Jack Ritter Rendering Fat Lines on a Raster Grid - Bob Wallis Two-Dimensional Clipping: A Vector-Based Approach (*) - Hans J.W. Spoelder, Fons H. Ullings Periodic Tilings of the Plane on a Raster Grid - Greg Lee, Mike Penk, Bob Wallis 3. Image Processing Anti-Aliasing Filters Summary Convenient Anti-Aliasing Filters That Minimize "Bumpy" Sampling - Mark J. Pavicic FIlters for Common Resampling Tasks - Ken Turkowski Smoothing Enlarged Monochrome Images - John Olsen Median Finding on a 3x3 Grid (*) - Alan W. Paeth Ordered Dithering (*) - Stephen Hawley A Fast Algorithm for General Raster Rotation - Alan W. Paeth Useful 1-to-1 Pixel Transforms - Dale Schumacher Alpha Blending - Kelvin Thompson 4. Frame Buffer Techniques Frame Buffers and Color Maps - Andrew Glassner Reading a Write-Only Write Mask - Alan W. Paeth A Digital "Dissolve" Effect (*) - Mike Morton Mapping RGB Triples onto Four Bits (*) - Alan W. Paeth What Are the Coordinates of a Pixel? - Paul S. Heckbert Proper Treatment of Pixels as Integers (*) - Alan W. Paeth Normal Coding - Andrew Glassner Recording Animation in Binary Order for Progressive Temporal Refinement (*) - Paul S. Heckbert 1-to-1 Pixel Transforms Optimized Through Color Map Manipulations - Dale Schumacher A Seed Fill Algorithm (*) - Paul S. Heckbert Filling a Region in a Frame Buffer - Ken Fishkin Precalculating Addresses for Fast Fills, Circles, and Lines - Bill Wallace A SImple Method for Color Quantization: Octree Quantization - Michael Gervautz, Werner Purgathofer 5. 3D Geometry Useful 3D Geometry - Andrew Glassner An Efficient Bounding Sphere (*) - Jack Ritter Intersection of Two Lines in Three-Space - Ronald Goldman Intersection of Three Planes - Ronald Goldman Mapping Summary Digital Cartography for Computer Graphics - Alan W. Paeth Albers Equal-Area Conic Map Projection (*) - Paul D. Bame Boxes and Spheres Summary Spheres-to-Voxels Conversion - Claudio Montani, Roberto Scopigno A Simple Method for Box-Sphere Intersection Testing (*) - James Arvo 6. 3D Rendering 3D Grid Hashing Function (*) - Brian Wyvill Backface Culling - Jeff Hultquist Fast Dot Products for Shading - Mark Lee Scanline Depth Gradient of a Z-Buffered Triangle - Kelvin Thompson Simulating Fog and Haze - Andrew Glassner Interpretation of Texture Map Indices - Andrew Glassner Multidimensional Sum Tables - Andrew Glassner 7. Ray Tracing A Simple Ray Rejection Test - Jack Ritter Ray-Object Intersection Summary Intersection of a Ray with a Sphere - Jeff Hultquist An Efficient Ray-Polygon Intersection (*) - Didier Badouel Fast Ray-Polygon Intersection - Andrew Woo Fast Ray-Box Intersection (*) - Andrew Woo Shadow Attenuation for Ray Tracing Transparent Objects - Andrew Pearce 8. Numerical and Programming Techniques Root Finding Summary Cubic and Quartic Roots (*) - Jochen Schwarze A Bezier Curve-Based Root Finder - Philip J. Schneider Using Strum Sequences to Bracket Real Roots of Polynomial Equations (*) - D.G. Hook, P.R. McAree Distance Measures Summary A High-Speed, Low Precision Square Root (*) - Paul Lalonde, Robert Dawson A Fast Approximation to the Hypotenuse (*) - Alan W. Paeth A Fast Approximation to 3D Euclidean Distance - Jack Ritter Full-Precision Constants - Kelvin Thompson COnverting between Bits and Digits - Kelvin Thompson Storage-Free Swapping - Brian Wyvill Generating Random Integers - Andrew Glassner Fast 2D-3D Rotation - Jack Ritter Bit Patterns for Encoding Angles - Ken Shoemake Bit Interleaving for Quad- or Octrees (*) - Clifford A. Shaffer A Fast HSL-to-RGB Transform (*) - Ken Fishkin 9. Matrix Techniques Matrix Identities - Kelvin Thompson Rotation Matrix Methods Summary Transforming Axes - Kelvin Thompson Fast Matrix Multiplication - Kelvin Thompson A Virtual Trackball - Jeff Hultquist Matrix Orthogonalization (*) - Eric Raible Rotation Tools - Michael E. Pique Matrix Inversion (*) - Richard Carling Matrices and Transformations - Ronald Goldman Efficient Post-Concatenation of Transformation Matrices (*) - Joseph M. Cychosz 10. Modeling and Transformations Transformation Identities - Ned Greene Fixed-Point Trigonometry with CORDIC Iterations (*) - Ken Turkowski Using Quaternions for Coding 3D Transformations (*) - Patrick-Gilles Maillot 3D Viewing and Rotation Using Orthonormal Bases (*) - Steve Cunningham The Use of Coordinate Frames in Computer Graphics - Ken Turkowski Forms, Vectors, and Transforms (*) - Bob Wallis Properties of Surface-Normal Transformations - Ken Turkowski Transforming Axis-Aligned Bounding Boxes (*) - James Arvo Constructing Shapes Summary Defining Surfaces from Sampled Data - Mark Hall Defining Surfaces from Contour Data - Mark Hall Computing Surface Normals for 3D Models - Andrew Glassner Calculation of Reference Frames along a Space Curve - Jules Bloomenthal 11. Curves and Surfaces Planar Cubic Curves - Andrew Glassner Explicit Cubic Spline Interpolation Formulas - Richard Rasala Fast Spline Drawing - Julian Gomez Some Properties of Bezier Curves - Ronald Goldman Tutorial on Forward Differencing - Bob Wallis Integration of Bernstein Basis Functions - Ronald Goldman Solving the Nearest-Point-on-Curve Problem (*) - Philip J. Schneider An Algorithm for Automatically Fitting Digitized Curves (*) - Philip J. Schneider Appendix I: C Utilities Graphics Gems C Header Files - Andrew Glassner 2D and 3D Vector C Library - Andrew Glassner Memory Allocation in C - Jeff Hultquist Two Useful C Macros - Eric Raible How to Build Circular Structures in C - Kelvin Thompson How to Use C Register Variables to Point to 2D Arrays - Kelvin Thompson Appendix 2: C Implementations The C Code follows the same order as the Gems References Index I believe the monthly FAQ lists the ftp sites which have the source code, and I think found bugs have been fixed (?). Tom
nad@cl.cam.ac.uk (Neil Dodgson) (02/20/91)
In article <1991Feb19.193857.15697@ccu.umanitoba.ca> yackob@eeserv.ee.umanitoba.ca (Kerry Yackoboski) writes: > I've heard a lot about this book, and on the strength >of how often it's mentioned, I'm considering ordering it. >Can one person who uses the book give us a short description >of what the book contains? Is it mainly code, or are the >algorithms well-explained? Or is there no code? What language >are the routines written in? Designed for a certain machine? >I hope nobody takes a lot of time to review it - a few lines would >help greatly. > thanks, Kerry. 600 pages of text explaining algorithms, techniques and useful little snippets of information. This is followed by 200 pages of C code implementing the algorithms. If you work in computer graphics then it is worth buying it --- but don't buy it if you know only a little about graphics, spend your money on something like Foley, van Dam, Feiner and Hughes first. A review for Graphics Gems is to appear (or has appeared) in "University Computing": ---------------------------------------------------------------------- Glassner, the editor of this 800 page tome, says "I have wanted a book like this for a long time". In it he has collected over a hundred gems of wisdom from over fifty of the leading lights in the international graphics community. His aim was to produce an anthology of short notes, each explaining the nuts and bolts of the programming and implementation of some detail in the field of computer graphics. The result is a large, well-presented volume brimming with useful information and hints for every graphics programmer. While there is certainly no way a single book could hope to cover the details of [italic]all[enditalic] computer graphics techniques, [italic]Graphics Gems[enditalic] still manages to cover topics ranging across the whole spectrum of computer graphics, and the gems themselves are generally well written and of good quality. With such a large number of authors one could hardly expect a consistent writing style across the gems but Glassner aimed to make the [italic]presentation[enditalic] as consistent as possible. I found that this consistent presentation, accompanied by excellent design and layout, made the book a pleasure to read. Another outcome of fifty-three different authors is the differing depths of the gems. I found that most of them are easy to read and comprehend but a few go quite deep into their subject and a couple of these probably go deeper than is necessary in the context. Quite a number of the gems are too terse to be useful to a novice. Having said that, this book is not designed for a novice. Nor is it a graphics textbook. Rather, it is a reference handbook for a graphics programmer and I believe that it will make an excellent addition to any existing library of graphics books. ---------------------------------------------------------------------- Disclaimer for people in the U.S., where there are too many lawyers: I have no connection with either Academic Press or Addison Wesley, I just like the books. Neil Dodgson, | nad@cl.cam.ac.uk Computer Laboratory, | Pembroke Street, | Cambridge, U.K. CB2 3QG |