Section 1 of 2 - Prev - Next
Archive-name: graphics/faq
COMP.GRAPHICS.MISC FAQ
Last update: 16Oct95
This document answers a number of the most frequently asked questions
about graphics on the Internet. To avoid wasting bandwidth and as a
matter of politeness please look for the answer to your question in
this document BEFORE posting to comp.graphics.misc.
If your copy of the FAQ is more than a couple of weeks old, you may
want to seek out the most recent version. The latest non-HTML version
of this FAQ is always available on rtfm.mit.edu as
/pub/usenet/news.answers/graphics/faq.
In case you're reading the ASCII version of the FAQ, the HTML version
is at http://www.primenet.com/~grieggs/cg_faq.html.
Send your updates to me at grieggs@primenet.com. I reserve the right
to reject or modify submissions based on my interpretation of the role
of the FAQ.
_________________________________________________________________
Contents
* Editorial
* Copyright
* Changes since last revision
* Other Graphics-related FAQs and FAQ-like documents
* General References
+ Books
+ Eratta
+ Other
* Specific References
+ Ray-Tracing and Global Illumination
+ Graphics File Formats
+ Spatial Data Structures
+ PEX and PHIGS
+ OpenGL
+ Morphing
+ Radiosity
* How do I ...
+ draw 3D objects on a 2D screen?
+ quantize 24-bit images down to 8 bits?
+ convert color to grayscale?
+ convert grayscale to black & white?
+ rotate a raster image by an arbitrary angle?
+ draw a circle as a Bezier (or B-spline) curve?
+ tell whether a point is within a planar polygon?
+ tessellate a sphere?
+ ray-trace height fields?
+ find the area of a 3D polygon?
+ convert between vector formats?
+ get files if I can't ftp?
* Where can I get ...
+ format documents for TIFF, IFF, GIF, etc.?
+ free image manipulation software?
+ free plotting software?
+ standards documents?
+ 3D objects?
+ MRI and CT scan volume data?
+ MPSC and AOEGA info?
* Graphics-related Mailing Lists
+ Imagine mailing list
+ DCTV mailing list
+ Rayshade Users mailing list
+ Lightwave mailing list
+ Video Toaster mailing list
+ Mailing List For Massive Parallel Rendering
+ Netpbm mailing list
+ POV-Ray mailing list
+ RayDream mailing list
+ Computational Geometry mailing list
+ Photoshop mailing list
+ 3DStudio mailing list
+ KPT mailing list
+ KODAK Photo CD mailing list
+ Caligari TrueSpace mailing list
+ Global Illumination mailing list
+ Fractal Design Painter mailing list
* SIGGRAPH
+ SIGGRAPH information online
+ How to join ACM/SIGGRAPH
+ SIGGRAPH Online Bibliography Project
_________________________________________________________________
Editorial
I've decided to add a copyright notice to the FAQ. I've had several
requests to include portions of the FAQ in various compilations and
books and while I don't mind, I would like to make sure that readers
of such excerpts can find the latest version of the actual FAQ. I'd
also like to tone down the activities of those who try to make money
from the volunteer work of others...
As far as I am concerned, the FAQ has never been available for
publication without permission anywhere but on the Internet.
_john
_________________________________________________________________
Copyright
The comp.graphics.misc FAQ is Copyright (c) 1995 John T. Grieggs. It
may be freely distributed electronically on the Usenet and via the
Internet, but may not be reprinted in whole or in part in
non-electronic form without prior permission of the editor (me).
What this means in English is that if you want to reprint or quote the
FAQ or part of it in a book or on a CD-ROM, I want to know about it,
in advance, and reserve the right to put conditions on such
activities. To date I have allowed 6 or 7 authors to do what they
wanted, and refused permission to 1 blatantly tacky commercial
venture.
Links to the HMTL version are welcome and even encouraged.
_________________________________________________________________
Changes since last revision
Copyright notice (me). It's pretty innocent, but I'm sure I'll hear
about it if anyone finds it offensive...
New version of ImageMagick (me). hollende@onecert.fr also sent in a
version update, but by the time I checked, it had already incremented
to yet another. :-)
Fractal Design Painter mailing list (kima@netcom.com).
Significantly updated ACR/gr info (Len.Makin@mel.dit.csiro.au).
New xgraph info (me).
New robotx version and location (Len.Makin@mel.dit.csiro.au).
New plotting packages: XGobi, XgPlot, and PLOTMTV (which obsoletes
Drawplot) (Len.Makin@mel.dit.csiro.au).
Special thanks to Len.Makin@mel.dit.csiro.au for sharing his research
on net-available plotting packages!
New address, and WWW page, for Global Illumination mailing list
(Francois.Sillion@imag.fr).
Fixed broken URLs (jsam@cs.adelaide.edu.au).
Small correction to the SIGGRAPH Online Bibliography section (me).
Don't forget to send your contributions to grieggs@netcom.com! If you
just post, I may not see it for one reason or another...
_________________________________________________________________
Other Graphics-related FAQs and FAQ-like documents
The comp.graphics.misc FAQ attempts to cover a wide range of
material. If you don't find what you need here, try one of these more
focused documents.
comp.graphics.algorithms FAQ
Maintained by Jon Stone (jdstone@destin.dazixco.ingr.com), the
comp.graphics.algorithms FAQ contains questions and answers
about computer graphics algorithms. There is some overlap
between this document and the one you are reading, for
historical reasons. It is available on rtfm.mit.edu as
/pub/usenet/news.answers/graphics/algorithms-faq.
comp.graphics.animation FAQ
Maintained by Francisco X DeJesus (dejesus@vislab.navy.mil),
the comp.graphics.animation FAQ contains questions and answers
about computer graphics animation. He maintains a HTML version
at http://www.ridgecrest.ca.us/fx/cga-faq.html. The non-HTML
version is still available on rtfm.mit.edu as
/pub/usenet/news.answers/graphics/animation-faq.
Graphics File Formats FAQ
Maintained by James Murray (jdm@netcom.com), the Graphics File
Formats FAQ contains information on graphics file formats,
including raster, vector, metafile, PDL, 3D object, animation,
and multimedia formats. It is available on rtfm.mit.edu as
/pub/usenet/news.answers/graphics/fileformats-faq.
Color Space FAQ
Maintained by David Bourgin (david.bourgin@ufrima.imag.fr), the
Color Space FAQ contains questions and answers about colors and
color spaces. It is available on rtfm.mit.edu as
/pub/usenet/news.answers/graphics/colorspace-faq.
Frequently Asked Questions about Gamma and Colour
Charles Poynton has written FAQs on Gamma and Color Spaces. His
FAQs are available from his web page,
http://www.inforamp.net/~poynton/ in a variety of formats.
Text versions may be obtained at ftp.inforamp.net in the
/pub/users/poynton/doc/colour directory.
Computer Graphics Resource Listing
Maintained by Nick Fotis (nfotis@theseas.ntua.gr), the CGRL
contains questions and answers about general graphics
documents, sort of like this document. It came into existence
for political reasons. There is no clear division of
responsibility between his document and mine, but I do tend to
keep this one a bit more terse and free of commercial material.
As a result, the CGRL is much larger and is stored in six
parts. You can get the parts at rtfm.mit.edu as
/pub/usenet/news.answers/graphics/resources-list/part[1-6], or
get the auto-HTMLed version at
http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/r
esources-list/top.html.
_________________________________________________________________
General References
BOOKS
* 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
* Procedural Elements for Computer Graphics, David F. Rogers, McGraw
Hill 1985, ISBN 0-07-053534-5
* Mathematical Elements for Computer Graphics (2nd Ed)., David F.
Rogers and J. Alan Adams, McGraw Hill 1990, ISBN 0-07-053530-2
* Fundamentals of Three-Dimensional Computer Graphics, Alan Watt,
Addison-Wesley 1990, ISBN 0-201-15442-0
* An Introduction to Ray Tracing, Andrew Glassner (ed.), Academic
Press 1989, ISBN 0-12-286160-4
* Graphics Gems, Andrew Glassner (ed.), Academic Press 1990, ISBN
0-12-286165-5
* Graphics Gems II, James Arvo (ed.), Academic Press 1991, ISBN
0-12-064480-0
* Graphics Gems III, David Kirk (ed.), Academic Press 1992, ISBN
0-12-409670-0 (with IBM disk) or 0-12-409671-9 (with Mac disk)
* Graphics Gems IV, Paul Heckbert (ed.), Academic Press 1994, ISBN
0-12-336156-7 with MAC floppy, ISBN 0-12-336155-9 with PC floppy
* Digital Image Processing (3rd Ed.), Rafael C. Gonzalez, Richard E.
Woods, Addison-Wesley 1992, ISBN 0-201-50803-6
* A Programmer's Geometry, Adrian Bowyer, John Woodwark,
Butterworths 1983, ISBN 0-408-01242-0 Pbk
* Advanced Animation and Rendering Techniques, Alan Watt, Mark Watt,
Addison-Wesley 1992, ISBN 0-201-54412-1
ERATTA
Errata for "An Introduction to Ray Tracing" is available on
wuarchive.wustl.edu as /graphics/graphics/books/erratas/IntroToRt.
Errata for "Digital Image Warping" is available on wuarchive.wustl.edu
as /graphics/graphics/books/erratas/Digital-Image-Warping.
Errata for "Photorealism and Ray Tracing in C" is available on
wuarchive.wustl.edu as
/graphics/graphics/books/erratas/Photorealism-and-ray-tracing-in-C.
Errata for the "Graphics Gems" series are available on
wuarchive.wustl.edu in /graphics/graphics/books.
OTHER
An automatic mail handler at Brown University allows users of
"Computer Graphics: Principles and Practice," by Foley, van Dam,
Feiner, and Hughes, to obtain text errata and information on
distribution of the software packages described in the book. Also,
users can send the authors feedback, to report text errors and
software bugs, make suggestions, and submit exercises. To receive
information describing how you can use the mail handler, simply mail
graphtext@cs.brown.edu and put the word "Help" in the Subject line.
Use the Subject line "Software-Distribution" to receive information
specifically concerning the software packages SRGP and SPHIGS.
All C code from the "Graphics Gems" series is available via anonymous
ftp from princeton.edu. Look in the directory
pub/Graphics/GraphicsGems for the various volumes (Gems, GemsII,
GemsIII, GemsIV), and get the README file first.
A list of computer graphics, computational geometry and image
processing journals is available from Juhana Kouhia,
jk87377@cs.tut.fi.
_________________________________________________________________
Specific References
RAY-TRACING AND GLOBAL ILLUMINATION
Rick Speer maintains a cross-indexed ray-tracing bibliography. The
bib is in the form of a PostScript file. The printout is 41 pages
long. It may be found on wuarchive.wustl.edu as
/graphics/graphics/bib/RT.BIB.Speer/speer.rt.bib.ps.Z, and on
plaza.aarnet.edu.au as
/graphics/graphics/bib/RT.BIB.Speer/speer.rt.bib.ps.gz.
While useful, this document has not been updated since 1991. Is there
a more recent version out there somewhere that I don't know about?
Ian Ashdown maintains ray tracing and radiosity/global illumination
bibliographies. These are in "refer" format, and so can be searched
electronically (a simple awk script to search for keywords is included
with each). The bibliographies have been combined, and are available
on hobbes.lbl.gov as /pub/doc/RadBib95.Z. There are also some other
interesting papers in the same directory.
Tom Wilson (twilson@dab.ge.com) has collected over 300 abstracts from
ray tracing related research papers and books. The information is
essentially in plaintext, and Latex formatting programs are included.
This collection is available at most of the sites mentioned above as
"rtabs.*".
GRAPHICS FILE FORMATS
* Graphics File Formats, David Kay and John Levine,
Windcrest/McGraw-Hill 1992, ISBN 0-8306-3060-0 $36.95 hardcover,
ISBN 0-8306-3059-7 $24.95 paper. Comments - 26 formats, no
software (this is good, IMHO - I prefer books which are not
platform-dependent). Questions about this book may be sent to
gbook@iecc.cambridge.ma.us.
* Programming for Graphics Files in C and C++, by John Levine, J.
Wiley & Sons, 1994, ISBN 0-471-59854-2 $29.95 softcover. A good
complement to Kay & Levine's book: less text info about the
formats, but working code (IBM PC code) is given for many of the
basic operations for each type of format. Diskette can be ordered
separately.
* Encyclopedia of Graphics File Formats by James D. Murray and
William vanRyper, O'Reilly & Associates, Sebastopol, CA July,
1994, 900 pages, $59.95 (includes a CD-ROM) Softcover ISBN:
1-56592-058-9, Email: orders@ora.com. Good introduction to
graphics file format issues for both vector and raster formats,
plus specific descriptions of nearly 100 file formats. CD-ROM
includes sample images, original format spec documents where
available, and C code snippets. Also a lot of free and shareware
image conversion/manipulation software for Unix, DOS, Windows, and
Mac. Much of this is available on the net (and indeed the book
tells you where), but having it all pulled together is very
useful. Tom Lane (tgl@sss.pgh.pa.us) says: "My only complaint is
that there are too many typos in the printed text. Check the
original spec document whenever you find something unclear or
dubious."
SPATIAL DATA STRUCTURES
* The Design and Analysis of Spatial Data Structures, H. Samet,
Addison-Wesley, Reading, MA, 1990. ISBN 0-201-50255-0.
* Applications of Spatial Data Structures: Computer Graphics, Image
Processing, and GIS, H. Samet, Addison-Wesley, Reading, MA, 1990.
ISBN 0-201-50300-0.
PEX AND PHIGS
* PEXlib Programming Manual, Tom Gaskins, 1154 pages, O'Reilly &
Associates, ISBN 1-56592-028-7
* PEXlib Reference Manual, edited by Steve Talbott, 577 pages,
O'Reilly & Associates, ISBN 1-56592-029-5
* PHIGS Programming Manual, Tom Gaskins, 908 pages, O'Reilly &
Associates, ISBN 0-937175-85-4 (softcover), ISBN 0-937175-92-7
(casebound)
* PHIGS Reference Manual, edited by Linda Kosko, 1099 pages,
O'Reilly & Associates, ISBN 0-937175-91-9
* A Primer for PHIGS, Hopgood, Duce & Johnston, 298 pages, Wiley,
ISBN 0-471-93330-9
There is an analysis of OpenGL vs. PEX, Analysis of PEX 5.1 and OpenGL
1.0, Allen Akin, available on sgi.sgi.com as
/sgi/opengl/doc/analysis.ps.Z.
OPENGL
* OpenGL Programming Guide, Neider, Davis & Woo, Addison-Wesley,
1993
* OpenGL Programming Guide, The Official Guide to Learning OpenGL,
Release 1", Addison-Wesley, ISBN 0-201-63274-8
There is an analysis of OpenGL vs. PEX, Analysis of PEX 5.1 and OpenGL
1.0, Allen Akin, available on sgi.sgi.com as
/sgi/opengl/doc/analysis.ps.Z.
MORPHING
Warping is the deformation of an image by mapping each pixel to a new
location. Morphing is blending from one image or object to another
one. Valerie Hall has written an excellent introduction to warping and
morphing. This is available for anonymous ftp from
marsh.cs.curtin.edu.au in the directory
pub/graphics/bibliography/Morph. There are three files:
* /pub/graphics/bibliography/Morph/morph_intro.ps.Z (PostScript
version, many pictures)
* /pub/graphics/bibliography/Morph/morph_intro.txt.Z (text version)
* /pub/graphics/bibliography/Morph/m_responses.Z (Responses to
morphing questions)
The files are compressed, so you must use binary transfer and
uncompress them afterwards.
The definitive book on the topic:
* Digital Image Warping, George Wolberg, IEEE Computer Society Press
Monograph 1990, ISBN 0-8186-8944-7
RADIOSITY
Radiosity is a technique for generating very realistic scenes using
global illumination (a radiative transfer problem).
* Radiosity and Realistic Image Synthesis, Michael F. Cohen, John R.
Wallace, Academic Press, 1993, ISBN 0-12-178270-0
* Radiosity and Global Illumination, Francois Sillion, Claude Puech,
Morgan Kaufmann, 1994, ISBN 1-55860-277-1
* Radiosity: A Programmer's Perspective, Ian Ashdown, John Wiley &
Sons, 1994, ISBN 0-471-30444-1 (book only), ISBN 0-471-30488-3
(with diskette)
_________________________________________________________________
How do I ...
This section provides brief answers to some of the most frequently
asked how-to questions. More verbose answers can generally be found in
the literature mentioned in the General References section.
HOW DO I DRAW 3D OBJECTS ON A 2D SCREEN?
There are many ways to do this. Some approaches map the viewing
rectangle onto the scene, by shooting rays through each pixel center
and assigning color according to the object hit by the ray. Other
approaches map the scene onto the viewing rectangle, by drawing each
object into the region, keeping track of which object is in front of
which.
The mapping mentioned above is also referred to as a "projection", and
the two most popular projections are perspective projection and
parallel projection. For example, to do a parallel projection of a
scene onto a viewing rectangle, you can just discard the Z coordinate
(divide by depth), and "clip" the objects to the viewing rectangle
(discard portions that lie outside the region).
For details on 3D rendering, the Foley, van Dam, Feiner and Hughes
book, "Computer Graphics: Principles and Practice" would be a good
place to start reading. Chapter 6 is "Viewing in 3D", and chapter 15
is "Visible-Surface Determination". For more information go to chapter
16 for shading, chapter 19 for clipping, and branch out from there.
HOW DO I QUANTIZE 24-BIT IMAGES DOWN TO 8 BITS?
Find a copy of "Color Image Quantization for Frame Buffer Display" by
Paul Heckbert, SIGGRAPH '82 Proceedings, page 297. There are other
algorithms, but this one works well and is fairly simple.
Implementations are included in most raster toolkits (check out the
various free image manipulation software available).
A variant method is described in "Graphics Gems", p. 287-293 (but no
code), and there is further information in "Graphics Gems II", p.
126-133 (code available online but not in book). Spencer Thomas'
article in Gems II on Efficient Inverse Color Map Computation (p.
116-125) is also relevant, and code is provided in the book and
online, as well as in the Utah Raster Toolkit. Note that the code from
the "Graphics Gems" series is all available from an FTP site, as
described above.
Also check out John Bradley's "Diversity Algorithm", which is
incorporated into the xv package and described in the back of the
manual.
The ImageMagick package contains another quantizing algorithm which is
presented as "doing a better job than the other algorithms, but
slower".
Ian Ashdown (Ledalite@mindlink.bc.ca) is maintaining a bibliography of
color quantization papers and articles that is available at
hobbes.lbl.gov as /pub/doc/cquant95.Z. It includes both the original
presentations of the algorithms and their implementation in popular
computer magazines such as Dr. Dobb's Journal and The C/C++ Users
Journal.
HOW DO I CONVERT COLOR TO GRAYSCALE?
The NTSC formula is:
luminosity = .299 red + .587 green + .114 blue
For additional information, please refer to the Color Space FAQ.
HOW DO I CONVERT GRAYSCALE TO BLACK & WHITE?
The definitive book on the topic:
* Digital Halftoning, Robert Ulichney, MIT Press 1987, ISBN
0-262-21009-6
But before you go off and start coding, check out the variety of free
image manipulation software available. Almost all of the packages
mentioned can do some form of gray to b&w conversion.
For additional information, please refer to the Color Space FAQ.
HOW DO I ROTATE A RASTER IMAGE BY AN ARBITRARY ANGLE?
The obvious but wrong method is to loop over the pixels in the source
image, transform each coordinate, and copy the pixel to the
destination. This is wrong because it leaves holes in the destination.
Instead, loop over the pixels in the destination image, apply the
*reverse* transformation to the coordinates, and copy that pixel from
the source. This method is quite general, and can be used for any
one-to-one 2-D mapping, not just rotation. You can add anti-aliasing
by doing sub-pixel sampling.
However, there is a much faster method, with antialising included,
which involves doing three shear operations. The method was originally
created for the IM Raster Toolkit; an implementation is also present
in PBMPLUS. Reference: A Fast Algorithm for Raster Rotation", by Alan
Paeth (awpaeth@watcgl.waterloo.edu) Graphics Interface '86
(Vancouver). An article on the IM Raster Toolkit appears in the same
journal. An updated version of the rotation paper appears in "Graphics
Gems" under the original title.
HOW DO I DRAW A CIRCLE AS A BEZIER (OR B-SPLINE) CURVE?
The short answer is, "You can't." Unless you use a rational spline
you can only approximate a circle. The approximation may look
acceptable, but it is sensitive to scale. Magnify the scale and the
error of approximation magnifies. Deviations from circularity that
were not visible in the small can become glaring in the large. If you
want to do the job right, consult the article:
"A Menagerie of Rational B-Spline Circles" by Leslie Piegl and Wayne
Tiller in IEEE Computer Graphics and Applications, volume 9, number 9,
September, 1989, pages 48-56.
For rough, non-rational approximations, consult the book:
Computational Geometry for Design and Manufacture by I. D. Faux and M.
J. Pratt, Ellis Horwood Publishers, Halsted Press, John Wiley 1980.
For the best known non-rational approximations, consult the article:
"Good Approximation of Circles by Curvature-continuous Bezier Curves"
by Tor Dokken, Morten Daehlen, Tom Lyche, and Knut Morken in Computer
Aided Geometric Design, volume 7, numbers 1-4 (combined), June, 1990,
pages 33-41 [Elsevier Science Publishers (North-Holland)]
HOW DO I TELL WHETHER A POINT IS WITHIN A PLANAR POLYGON?
Consider a ray originating at the point of interest and continuing to
infinity. If it crosses an odd number of polygon edges along the way,
the point is within the polygon. If the ray crosses an even number of
edges, the point is either outside the polygon, or within an interior
hole formed from intersecting polygon edges. This idea is known in the
trade as the Jordan curve theorem; see Eric Haines' article in
Glassner's ray tracing book (above) for more information, including
treatment of special cases.
Another method is to sum the absolute angles from the point to all the
vertices on the polygon. If the sum is 2 pi, the point is inside, if
the sum is 0 the point is outside. However, this method is about an
order of magnitude slower than the previous method because evaluating
the trigonometric functions is usually quite costly.
Code for both methods (plus barycentric triangle testing) can be found
in the Ray Tracing News, Vol. 5, No. 3, available from princeton.edu
as /pub/Graphics/RTNews/RTNv5n3.Z.
This code has been updated and expanded. A long article on the topic
appears in _Graphics Gems IV_ and the code (along with a timing test
program) is available from princeton.edu as
/pub/Graphics/GraphicsGems/GemsIV/GGemsIV.tar.Z.
HOW DO I TESSELLATE A SPHERE?
One simple way is to do recursive subdivision into triangles. The
base of the recursion is an octahedron, and then each level divides
each triangle into four smaller ones. Jon Leech has posted a nice
routine called sphere.c that generates the coordinates. It's available
for FTP on ftp.ee.lbl.gov and princeton.edu.
HOW DO I RAY-TRACE HEIGHT FIELDS?
Height fields are a special case in ray-tracing. They have a number
of uses, such as terrain rendering, and some optimization is possible.
Thus, they get their own FAQ section. Note that further references can
no doubt be located via the ray-tracing bibs in section 16 above.
The following paper seems to be the definitive reference: "Grid
Tracing: Fast Ray Tracing For Height Fields", F. Kenton Musgrave,
July, 1988.
This is available as "Research Report YALEU/DCS/RR-639" from Yale
University, it's also in the SIGGRAPH '91 Fractal Modeling in 3D
Computer Graphics and Imaging course notes, and (best of all) it's
available on the net, at princeton.edu, as
/pub/Graphics/Papers/musg88.ms.Z.
An implementation of this paper may be found in Rayshade.
Another paper exists: "Parametric Height Field Ray Tracing", D. W.
Paglieroni, S. M. Peterson, Proceedings of Graphics Interface '92,
Canadian Information Processing Society, Toronto, Ontario, May 1992,
p. 192-200
And still one more: "The Synthesis and Rendering of Eroded Fractal
Terrains", Musgrave, Kolb, Mace, Computer Graphics Vol 23, No. 3
(SIGGRAPH '89 Proceedings) p. 41-50
HOW DO I FIND THE AREA OF A 3D POLYGON?
The area of a triangle is given by (in C notation)
area = 0.5 * ( ( x[0] * y[1] ) + ( x[1] * y[2] ) + ( x[2] * y[0] ) -
( x[1] * y[0] ) - ( x[2] * y[1] ) - ( x[0] * y[2] ) );
and the area of a planar polygon is given by
area = 0.0;
for ( i = 0; i
Section 1 of 2 - Prev - Next
© allanswers.org | Terms of use