422 lines
18 KiB
Plaintext
422 lines
18 KiB
Plaintext
|
|
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 <mlm@nl.cs.cmu.edu>.
|
|
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 <raveling@venera.isi.edu>. 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 <madd@std.com>. 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 <sam@okeeffe.berkeley.edu>. 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 <foo@rice.edu>.
|
|
|
|
|
|
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 <leech@cs.unc.edu>
|
|
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:
|