This message is automatically posted once a week in an effort to cut down on the repetitive junk in comp.graphics. It was last changed on 04feb91. If you have answers to other frequently asked questions that you would like included in this posting, please send me mail. If you don't want to see this posting every week, please add the subject line to your kill file. Thank you. --- Jef Jef Poskanzer jef@well.sf.ca.us {ucbvax, apple, hplabs}!well!jef "...Is this a trick question?" - - - - - - - - - - Contents: 1) General references for graphics questions. 2) Drawing three-dimensional objects on a two-dimensional screen. 3) Quantizing 24 bit images down to 8 bits. 4) Converting color into grayscale. 5) Quantizing grayscale to black&white. 6) Rotating a raster image by an arbitrary angle. 7) Free image manipulation software. 8) Format documents for GIF, TIFF, IFF, BIFF, NFF, OFF, etc. 9) Converting between vector formats. 10) How to get Pixar films. 11) How do I draw a circle as a Bezier (or B-spline) curve? 12) How to order standards documents. 13) How to FTP by email. 14) How to tell whether a point is within a planar polygon. 15) How to tesselate a sphere. 1) General references for graphics questions: 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 Principles of Interactive Computer Graphics (2nd Ed.), Newman and Sproull, McGraw Hill, ISBN 0-07-046338-7 Procedural Elements for Computer Graphics, David F. Rogers, McGraw Hill, ISBN 0-07-053534-5 Mathematical Elements for Computer Graphics 2nd Ed., David F. Rogers and J. Alan Adams, McGraw Hill, ISBN 0-07-053530-2 Applied Concepts in Microcomputer Graphics, Bruce Artwick, Prentice-Hall, ISBN 0-13-039322-3 Digital Picture Processing, vols. 1&2, Azriel Rosenfeld and Avi Kak, Academic Press 1976 Three Dimensional Computer Graphics, Alan Watt, Addison-Wesley, 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.), Acedemic Press 1990, ISBN 0-12-286165-5 More specific technical references can be obtained from an ACM/SIGGRAPH mail daemon. Send a message to graf-bib-server@decwrl.dec.com Just place important keywords in the Subject: field of your mail message. E.g., Subject: ray traced musical spheres Please be as specific as possible. "Graphics" is too vague and would only flood the mailer. Additional keywords help. Some of the complete reference files are obtainable via anonymous ftp thru gatekeeper.dec.com (pub/misc/graf-bib) [megabytes]. Additional years references will be added over time. 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. Finally, all C code from "Graphics Gems" is available via anonymous ftp from weedeater.math.yale.edu. Look in the directory pub/GraphicsGems/src, and get the README file first. 2) Drawing three-dimensional objects on a two-dimensional screen. The simple answer is, you divide by the depth. For a more verbose explanation, see any of the above references. 3) Quantizing 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 (see item 7 below). 4) Converting color into grayscale. The NTSC formula is: luminosity = .299 red + .587 green + .114 blue 5) Quantizing grayscale to black&white. The only reference you need for this stuff is: Digital Halftoning, Robert Ulichney, MIT Press, ISBN 0-262-21009-6 But before you go off and start coding, check out the image manipulation software mentioned in item 7 below. All of the packages mentioned can do some form of gray to b&w conversion. 6) Rotating 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 (see below); 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 toolkit appears in the same journal. An updated version of the rotation paper appears in "Graphics Gems" (see section [1]) under the original title. 7) Free image manipulation software. There are a number of toolkits for converting from one image format to another, doing simple image manipulations such as size scaling, plus the above-mentioned 24 -> 8, color -> gray, gray -> b&w conversions. Here are pointers to some of them: PBMPLUS, by Jef Poskanzer. Comprehensive format conversion and image manipulation package. The latest version is always available via anonymous FTP as export.lcs.mit.edu:contrib/pbmplus.tar.Z and ftp.ee.lbl.gov:pbmplus.tar.Z. The version of 22nov89 (which currently is still the latest version, except for the one official patch so far) was posted to comp.sources.misc, and is therefore accessible via mail to one of the archive servers. This version is also available in the X11R4 release tape. IM Raster Toolkit, by Alan Paeth (awpaeth@watcgl.uwaterloo.ca). Provides a portable and efficient format and related toolkit. The format is versatile in supporting pixels of arbitrary channels, components, and bit precisions while allowing compression and machine byte-order independence. The kit contains more than 50 tools with extensive support of image manipulation, digital halftoning and format conversion. Previously distributed on tape c/o the University of Waterloo, an FTP version will appear someday. Utah RLE Toolkit. Conversion and manipulation package, similar to PBMPLUS. Available via FTP as cs.utah.edu:pub/urt-*, weedeater.math.yale.edu:pub/urt-*, and freebie.engin.umich.edu:pub/urt-*. Fuzzy Pixmap Manipulation, by Michael Mauldin . Conversion and manipulation package, similar to PBMPLUS. Version 1.0 available via FTP as nl.cs.cmu.edu:/usr/mlm/ftp/fbm.tar.Z, uunet.uu.net:pub/fbm.tar.Z, and ucsd.edu:graphics/fbm.tar.Z. Img Software Set, by Paul Raveling . Reads and writes its own image format, displays on an X11 screen, and does some image manipulations. Version 1.3 is available via FTP as export.lcs.mit.edu:contrib/img_1.3.tar.Z, and venera.isi.edu:pub/img_1.3.tar.Z along with a large collection of color images. Xim, by Philip R. Thompson. Reads and writes its own image format, displays on an X11 screen, and does some image manipulations. Available in your nearest X11R4 source tree as contrib/clients/xim. A more recent version is available via ftp from video.mit.edu. It uses x11r4 and the OSF/Motif toolkit to provide basic interactive image manipulation and reads/writes GIF, xwd, xbm, tiff, rle, xim, and other formats. xloadimage, by Jim Frost . Reads in images in various formats and displays them on an X11 screen. Available via FTP as export.lcs.mit.edu:contrib/xloadimage*, and in your nearest comp.sources.x archive. TIFF Software, by Sam Leffler . Nice portable library for reading and writing TIFF files, plus a few tools for manipulating them and reading other formats. Available via FTP as ucbvax.berkeley.edu:pub/tiff/*.tar.Z or uunet.uu.net:graphics/tiff.tar.Z ALV, a Sun-specific image toolkit. Version 2.0.6 posted to comp.sources.sun on 11dec89. Also available via email to alv-users-request@cs.bris.ac.uk. popi, an image manipulation language. Version 2.1 posted to comp.sources.misc on 12dec89. ImageMagick, an X11 package for display and interactive manipulation of images. Uses its own format (MIFF), and includes some converters. Available via FTP as export.lcs.mit.edu:contrib/ImageMagick.tar.Z Khoros, a huge (~100 meg) graphical development environment based on X11R4. Khoros components include a visual programming language, code generators for extending the visual language and adding new application packages to the system, an interactive user interface editor, an interactive image display package, an extensive library of image and signal processing routines, and 2D/3D plotting packages. Available via FTP as pprg.unm.edu:pub/khoros/*. Don't forget to set binary mode when you FTP tar files. For you MILNET folks who still don't have name servers, the IP addresses are: export.lcs.mit.edu 18.30.0.238 ftp.ee.lbl.gov 128.3.254.68 cs.utah.edu 128.110.4.21 nl.cs.cmu.edu 128.2.222.56 venera.isi.edu 128.9.0.32 ucbvax.berkeley.edu 128.32.133.1 weedeater.math.yale.edu 130.132.23.17 freebie.engin.umich.edu 141.212.68.23 pprg.unm.edu 129.24.13.10 Please do *not* post or mail messages saying "I can't FTP, could someone mail this to me?" There are a number of automated mail servers that will send you things like this in response to a message. See item 13 below for details on some. Also, the newsgroup alt.graphics.pixutils is specifically for discussion of software like this. You may find useful information there. 8) Format documents for GIF, TIFF, IFF, BIFF, NFF, OFF, etc. You almost certainly don't need these. Read the above item 7 on free image manipulation software. Get one or more of these packages and look through them. Chances are excellent that the image converter you were going to write is already there. But if you still want one of the format documents, many such files are available by anonymous ftp from titan.rice.edu (128.42.1.30) in directory public/graphics.formats. These files were collected off the net and are believed to be correct. This archive includes pixel formats, and two- and three-dimensional object formats. Other file format descriptions are welcome, send to Mark Hall . 9) Converting between vector formats. A lot of people ask about converting from HPGL to PostScript, or MacDraw to CGM, or whatever. It is important to understand that this is a very different problem from the image format conversions in item 7. Converting one image format to another is a fairly easy problem, since once you get past all the file header junk, a pixel is a pixel -- the basic objects are the same for all image formats. This is not so for vector formats. The basic objects -- circles, ellipses, drop-shadowed pattern-filled round-cornered rectangles, etc. -- vary from one format to another. Except in extremely restricted cases, it is simply not possible to do a one-to-one conversion between vector formats. On the other hand, it is quite possible to do a close approximation, rendering an image from one format using the primatives from another. As far as I know, no one has put together a general toolkit of such converters, but two different HPGL to PostScript converters have been posted to comp.sources.misc. Check the index on your nearest archive site. A related frequent question is how to convert from some vector format to a bitmapped image - from PostScript to Sun raster format, or HPGL to X11 bitmap. For example, some of the commercial PostScript clones for PC's allow you to render to a disk file as well as a printer. Also, the PostScript interpreters in the NeXt box and in Sun's X11/NeWs can be used to render to a file if you're clever. But in general, the answer is no. However, if someone were to put together a vector to vector conversion toolkit, adding a vector to raster converter would be trivial. 10) How to get Pixar films. The various John Lasseter / Pixar computer animated shorts are available on video tape. You can order them from Direct Cinema Limited: Film Price Luxo, Jr. $14.95 Red's Dream $19.95 Tin Toy $24.95 Knickknack $24.95 Luxo, Jr./Red's Dream/Tin Toy $49.95 All tapes are on 1/2" VHS NTSC. Add $10/tape for PAL format. Also available: Tin Toy T-shirt $15.00 Knickknack 3D T-shirt $15.00 (includes glasses) Add $5 S&H for the first tape or shirt, $2 for each additional tape or shirt. Foreign shipping, add $3/tape or shirt. Call 800/525-0000 (213/396-4774 international) to charge to your credit card. Call first to verify prices and availability. Or, just write to: Direct Cinema Limited 1749 14th Street Santa Monica, CA 90404-4342 11) 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. 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)] 12) How to order standards documents. The American National Standards Institute sells ANSI standards, and also ISO (international) standards. Their sales office is at (212) 642-4900, mailing address is 1430 Broadway, NY NY 10018. It helps if you have the complete name and number. Some useful numbers to know: CGM (Computer Graphics Metafile) is ANSI X3.122-1986. GKS (Graphical Kernel System) is ANSI X3.124-1985. PHIGS (Programmer's Hierarchical Interactive Graphics System) is ANSI X3.144-1988. IGES is ASME/ANSI Y14.26M-1987. Language bindings are often separate but related numbers; for example, the GKS FORTRAN binding is X3.124.1-1985. Standards-in-progress are made available at key milestones to solicit comments from the graphical public (this includes you!). ANSI can let you know where to order them; most are available from Global Engineering at 800/854-7179. 13) How to FTP by email. There are a number of sites that archive the Usenet sources newsgroups and make them available via an email query system. You send a message to an automated server saying something like "send comp.sources.unix/fbm", and a few hours or days later you get the file in the mail. There are also a couple of sites that will perform general FTP retrievals for you in response to a similar mail query. For information on using one of them, send a message like this: To: info-server@cs.net request: info topic: help-ftp request: end (NOTE: this server is currently "down for repairs". No estimate on when or if it will return.) And for info on another one, send this: To: bitftp@pucc.bitnet help Please be considerate, and don't over-use these services. If people start using them to retrieve hundreds of megabytes of GIF files, they will probably disappear. 14) How to 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 intersectiong 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. 15) How to tesselate 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 weedeater.math.yale.edu.  saved: