Frequently Asked Questions
Section 0. General Information
(C) 1998 Joseph O'Rourke.
comp.graphics.algorithms is an unmoderated
newsgroup intended as a forum for the discussion of the
algorithms used in the process of generating
computer graphics. These algorithms may be recently proposed in published journals or papers, old or previously known algorithms, or hacks used incidental to the process of computer graphics. The scope of these algorithms may range from an efficient way to multiply matrices, all the way to a global illumination method incorporating raytracing, radiosity, infinite spectrum modeling, and perhaps even mirrored balls and lime jello.
It is hoped that this group will serve as a forum for programmers and researchers to exchange ideas and ask questions on recent papers or current research related to computer graphics.
comp.graphics.algorithms is not:
for requests for gifs, or other pictures
for requests for image translator or processing software; see
alt.binaries.pictures.utilities [now degenerated to pic postings]
alt.graphics.pixutils (image format translation)
comp.sources.misc (image viewing source code)
for requests for compression software; for these try:
Archives may be found at:
It is archived in the same manner that all other newsgroups are being archived there, namely there is an Index file with all the subjects, and all the articles are being kept in a hierarchy based on the year and month they are posted.
The FAQ is posted on the 1st and 15th of every month. The easiest way to get it is to search back in your news reader for the most recent posting, with Subject:
comp.graphics.algorithms Frequently Asked Questions
It is posted to comp.graphics.algorithms, and cross-posted to news.answers and comp.answers.
If you can't find it on your newsreader,
you can look at the latest HTML version at either of these two sites:
The exaflop version should be up-to-date and is nicely converted; the ohio-state site is sometimes out of date.
Finally, you can ftp the FAQ from several sites, including:
The (busy) rtfm.mit.edu site lists many alternative "mirror" sites.
Also can reach the FAQ from http://www.geom.umn.edu/software/cglist/, which is worth visiting in its own right.
The keywords in brackets are used to refer to the books in later questions. They generally refer to the first author except where it is necessary to resolve ambiguity or in the case of the Gems.
Basic computer graphics, rendering algorithms
Computer Graphics: Principles and Practice (2nd Ed.),
J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hughes, Addison-Wesley
1990, ISBN 0-201-12110-7
Computer Graphics: Principles and Practice, C version
J.D. Foley, A. van Dam, S.K. Feiner, J.F. Hughes, Addison-Wesley=20
ISBN: 0-201-84840-6, 1996, 1147 pp.
An Introduction to Splines for Use in Computer Graphics and
Richard H. Bartels, John C. Beatty, Brian A. Barsky, 1987, ISBN
Curves and Surfaces for Computer Aided Geometric Design:
A Practical Guide, 3rd Edition, Gerald E. Farin, Academic Press
1993. ISBN 0-12-249052-5
The Algorithmic Beauty of Plants,
Przemyslaw W. Prusinkiewicz, Aristid Lindenmayer, Springer-Verlag,
1990, ISBN 0-387-97297-8, ISBN 3-540-97297-8
Tricks of the Graphics Gurus,
Dick Oliver, et al. (2) 3.5 PC disks included, $39.95 SAMS Publishing
Introduction to computer graphics,
Hearn & Baker
Radiosity and Realistic Imange Sythesis,
Michael F. Cohen, John R. Wallace, Academic Press Professional
1993, ISBN 0-12-178270-0 Apparently now out of print
Radiosity: A Programmer's Perspective
Ian Ashdown, John Wiley & Sons 1994, ISBN 0-471-30444-1, 498 pp.
Radiosity & Global Illumination
Francois X. Sillion snd Claude Puech, Morgan Kaufmann 1994, ISBN
1-55860-277-1, 252 pp.
Texturing and Modeling - A Procedural Approach
David S. Ebert (ed.), F. Kenton Musgrave, Darwyn Peachey, Ken Perlin,
Setven Worley, Academic Press 1994, ISBN 0-12-228760-6,
ISBN 0-12-2278761-4 (IBM disk)
Visualization Toolkit, 2nd Edition, The: An Object-Oriented Approach to 3-D
Graphics (Bk/CD) (Professional Description)
William J. Schroeder, Kenneth Martin and Bill Lorensen,
Prentice-Hall 1996, ISBN: 0-13-954694-4
See Subject 0.07 for source.
PC Graphics Unleashed
Scott Anderson. SAMS Publishing, ISBN 0-672-30570-4
For image processing,
Fractal Image Compression,
Michael F. Barnsley and Lyman P. Hurd, AK Peters, Ltd, 1993
Fundamentals of Image Processing,
Anil K. Jain, Prentice-Hall 1989, ISBN 0-13-336165-9
Digital Image Processing,
Kenneth R. Castleman, Prentice-Hall 1996
(Description and errata at: "http://www.phoenix.net/~castlman")
Digital Image Processing, Second Edition,
William K. Pratt, Wiley-Interscience 1991, ISBN 0-471-85766-1
Digital Image Processing (3rd Ed.),
Rafael C. Gonzalez, Paul Wintz, Addison-Wesley 1992, ISBN
The Image Processing Handbook (2nd Ed.),
John C. Russ, CRC Press 1994, ISBN 0-8493-2516-1
Digital Image Warping,
George Wolberg, IEEE Computer Society Press Monograph 1990, ISBN
A Programmer's Geometry,
Adrian Bowyer, John Woodwark, Butterworths 1983,
ISBN 0-408-01242-0 Pbk
[Samet:Design & Analysis]
Introduction to Solid Modeling
Martti Mantyla, Computer Science Press 1988,
The computational geometry community maintains its own bibliography of publications in or closely related to that subject. Every four months, additions and corrections are solicited from users, after which the database is updated and released anew. As of 31 Mar 1998, it contained 11,275 bib-tex entries. See Jeff Erickson's page on "Computational Geometry| Bibliographies": http://www.cs.duke.edu/~jeffe/compgeom/biblios.html#geombib
The bibliography can be retrieved from:
ftp://ftp.cs.usask.ca/pub/geometry/geombib.tar.gz - bibliography proper
ftp://ftp.cs.usask.ca/pub/geometry/o-cgc19.ps.gz - overview published in '93 in SIGACT News and the Internat. J. Comput. Geom. Appl.
ftp://ftp.cs.usask.ca/pub/geometry/ftp-hints - detailed retrieval info
The ACM SIGGRAPH Online Bibliography Project, by Stephen Spencer (email@example.com). The database is available for anonymous FTP from the ftp://siggraph.org/publications/bibliography directory. Please download and examine the file READ_ME in that directory for more specific information concerning the database.
'netlib' is a useful source for algorithms, member inquiries for SIAM, and bibliographic searches. For information, send mail to firstname.lastname@example.org, with "send index" in the body of the mail message.
You can also find free sources for numerical computation in C via ftp://usc.edu/pub/C-numanal. In particular, grab numcomp-free-c.gz in that directory.
Check out Nick Fotis's computer graphics resources FAQ -- it's packed with pointers to all sorts of great computer graphics stuff. This FAQ is posted biweekly to comp.graphics.
This WWW page contains links to a large number of computer graphic related pages: http://www.dataspace.com:84/vlib/comp-graphics.html
There's a Computer Science Bibliography Server at: http://glimpse.cs.arizona.edu:1994/bib/ with Computer Graphics, Vision and Radiosity sections
A comprehensive bibliography of color quantization papers and articles (CQUANT97) is available at http://www.ledalite.com/library-/cgis.htm.
Modelling physically based systems for animation: http://www.cc.gatech.edu/gvu/animation/Animation.html
The University of Manchester NURBS Library: ftp://unix.hensa.ac.uk/pub/misc/unix/nurbs/
For an implementation of Seidel's algorithm for fast trapezoidation and triangulation of polygons. You can get the code from: ftp://ftp.cs.unc.edu/pub/users/narkhede/triangulation.tar.gz
Ray tracing bibliography: ftp://ftp.eye.com/pub/graphics/papers/rtbib95.tar.Z ftp://ftp.eye.com/pub/graphics/papers/rtbib95.zip
Quaternions and other comp sci curiosities: ftp://ftp.netcom.com/pub/hb/hbaker/hakmem/hakmem.html
Directory of Computational Geometry Software, collected by Nina Amenta (email@example.com) Nina Amenta is maintaining a WWW directory to computational geometry software. The directory lives at The Geometry Center. It has pointers to lots of convex hull and voronoi diagram programs, triangulations, collision detection, polygon intersection, smallest enclosing ball of a point set and other stuff. http://www.geom.umn.edu/software/cglist/lowdvod.html
A compact reference for real-time 3d computer graphics programming: http://www.cs.mcgill.ca/~zed
For the most up-to-date versions of RADBIB98 (a global illumination bibliography), GITHESIS (a subset of RADBIB98 devoted to global illumination theses), and IBR98 (an image-based rendering bibliography). http://www.ledalite.com/library-/rrt.htm
The "Electronic Visualization Library" (EVlib) is a domain secific digital library for Scientific Visualization and Computer Graphics: http://visinfo.zib.de/
BSP Tree FAQ by Bretton Wade: http://reality.sgi.com/bspfaq/
Gamma and Color FAQs by Charles A. Poynton has
The documents are mirrored in Darmstadt, Germany at ftp://ftp.igd.fhg.de/pub/doc/colour/
Graphics Gems source code.
http://www.acm.org/tog/GraphicsGems/ This site is now the offical distribution site for Graphics Gems code.
Master list of Computational Geometry software:
Described in [Goodman & O'Rourke], Chap. 52.
There are a number of interesting items in http://theory.lcs.mit.edu/~seth including:
Code for 2D Voronoi, Delaunay, and Convex hull
Mike Hoymeyer's implementation of Raimund Seidel's O( d! n ) time linear programming algorithm for n constraints in d dimensions
geometric models of UC Berkeley's new computer science building
Sources to "Computational Geometry in C", by J. O'Rourke can be found at ftp://grendel.csc.smith.edu/pub/compgeom.
Greg Ferrar has uploaded his heavily commented C++ 3D rendering library at ftp://ftp.math.ohio-state.edu/pub/users/gregt
TAGL is a portable and extensible library that provides a subset of Open-GL functionalities. ftp://sunsite.unc.edu/pub/packages/programming/graphics/tagl21.tgz
Try ftp://x2ftp.oulu.fi for /pub/msdos/programming/docs/graphpro.lzh by Michael Abrash. His XSharp package has an implementation of Xiaoulin Wu's anti-aliasing algorithm (in C).
Example sources for BSP tree algorithms can be found in ftp://ftp.qualia.com/pub/bspfaq/
Mel Slater (firstname.lastname@example.org) also made some implementations of BSP trees and shadows for static scenes using shadow volumes code available http://www.dcs.qmw.ac.uk/~mel/BSP.html ftp://ftp.dcs.qmw.ac.uk/people/mel/BSP
WINGED.ZIP, a C++ implementation of Baumgart's winged-edge data structure: http://www.ledalite.com/library-/cgis.htm
CGAL, the Computational Geometry Algorithms Library, is written in C++ and is available at URL http://www.cs.ruu.nl/CGAL/ . It consists of three parts. The first part is the kernel, which consists of constant size non-modifiable geometric primitive objects. The second part is a collection of basic geometric datastructures and algorithms, which are parameterized by traits classes that define the interface between the datastructure or algorithm, and the primitives they use. The third part consists of non-geometric support facilities.
A C++ NURBS library written by Lavoie Philippe. Version 2.1. Results may be exported as POV-Ray, RIB (renderman) or VRML files. It also offers wrappers to OpenGL: http://lowrent.org/nurbs