From aoki@faerie.Berkeley.EDU Wed Apr 26 06:09:17 1989
Path: leah!csd4.milw.wisc.edu!indri!ames!pasteur!faerie!aoki
From: aoki@faerie.Berkeley.EDU (Paul M. Aoki)
Newsgroups: comp.graphics
Subject: Enough already! [was: Lets Create a Monthly message] (TOO LONG)
Message-ID: <12917@pasteur.Berkeley.EDU>
Date: 26 Apr 89 10:09:17 GMT
References: <18148@yoyodyne.mips.com.mips.COM>
Sender: news@pasteur.Berkeley.EDU
Reply-To: aoki@faerie.Berkeley.EDU (Paul M. Aoki)
Organization: Postgres Research Group, UC Berkeley
Lines: 420
In article <18148@yoyodyne.mips.com.mips.COM> koblas@mips.COM (David Koblas) writes:
>Recently comp.graphics has been deluged with many messages under a
>few small categories. A medium while back it was brought up that
>there should be a "Monthly Posting", recently I've began to believe
>that this would be a wonderful idea.
People have been grumbling for YEARS, so here's a first stab at a
comp.graphics "read this before posting"/"commonly-asked questions"
meta-posting. I am hoping that this will annoy one of the real graphics
hackers enough so that s/he will do the job right, a graphics guru I ain't
(to say the least).
Notes:
0. I'm not maintaining this -- I'm leaving Berkeley (and possibly all computer
networks if I'm not lucky) in a month -- so don't send mail or suggestions
to me. Think of this as "hit and run" :-)
1. You think I did a lousy job? You're right. I took 30 minutes and hacked
up some old postings. Any time you spend flaming me (news or mail) would be
better spent taking this over and improving it. This was not assembled in
any particular order, nor are these necessarily the "best" articles on the
topic, they are just what I happened to have stashed away from two years
(ARGGGH!) of scanning this dreck. Well, the FTP summary did take a while to
assemble, and I think this does cover most of the "common question" material
except those mentioned in 3.
2. Good summaries of RGB-to-XYZ, colorimetry, and references on raytracing
are needed.
3. There isn't much real code here. For that, people should be referred
to the albanycs archive (see the end of the posting). A summary of the code
and other stuff in the archives would be useful, but too hard to maintain.
4. This is already too long.
----------------
Paul M. Aoki aoki@postgres.Berkeley.EDU ...!ucbvax!aoki
CS Division, Dept. of EECS // UCB // Berkeley, CA 94720 (415) 642-1863
"Oh, Animage. That's not REAL animation, that's for Japanese animation
freaks. Really awful stuff -- Speed Racer with girls in bikinis .."
==============================================================================
Contents:
Efficient flood-fill algorithms (Ken Fishkin)
Point-in-polygon tests (Paul Heckbert)
Ray-sphere intersection (Paul Heckbert)
Color quantization (aka "24bits to 8bits") (Paul Heckbert)
*The* halftoning/dithering reference (Rob Tow)
Where to get Pixar films (Ed Falk)
Summary of free UNIX graphics software, FTP sites, etc.
==============================================================================
From: fishkin@pixar.UUCP (Ken Fishkin)
Date: 24 Apr 89 17:33:56 GMT
The fill algorithms alluded to are extremely ineffecient.
Allow me to recommend:
Marc S. Levoy, "Area Flooding Algorithms".
Presented at SIGGRAPH '82 2-D Animation Tutorial.
Uri Shani, "Filling Regions in Binary Raster Images: A Graph-Theoretic
Approach", pp. 321-327, SIGGRAPH '80.
Alvy Ray Smith, "Tint Fill", pp. 276-283, SIGGRAPH '79.
Alvy Ray Smith, "Fill Tutorial Notes", presented at '82 SIGGRAPH
2-D Animation Tutorial.
Ken Fishkin, "An Analysis and Algorithm for Filling Propogation",
pp. 203-212, Graphics Interface '85.
==============================================================================
From: ph@pixar.UUCP (Paul Heckbert)
Date: Tue Jul 14 14:37:56 PDT 1987
There's a big difference between point-in-polygon testing for convex polyons
and for concave polygons. It's easy to write robust software for the former
but the latter is often prone to numerical problems and special cases
(hence all the discussion here).
Here's a quick summary of some of the 2-d point-in-polygon methods I know:
POLYGON TYPE TIME METHOD
convex O(n) dot product with line equation for each edge
(represent polygon as an intersection of half-planes)
star O(logn) binary search on angle from "center" of polygon, test
inclusion in a single triangle
(decompose polygon into triangles radiating from center)
this method requires preprocessing.
concave O(n) Jordan Curve Theorem: intersect a ray out of the
polygon with the edges, count intersections;
odd means inside, even means outside.
concave O(n) winding number method
Trace a ray out of the polygon and compute the total
number of intersections which cross the ray going from
right to left minus the number that cross from left to
right. The winding number=0 when outside the polygon.
The two concave methods work for non-simple polygons (polygons which intersect
themselves) too, although they give different results, as described in the
"PostScript Language Referance Manual". These methods are described more fully
in Preparata & Shamos's book "Computational Geometry".
For 3d point-in-polygon testing it's cheaper to project the point and polygon
to 2d and test inclusion in the projected polygon than to test against planes,
as you did. Project onto either the x-y, y-z, or z-x plane, use whichever one
has the largest projection.
==============================================================================
From: ph@pixar.UUCP (Paul Heckbert)
Date: Mon Jul 20 12:42:47 PDT 1987
The "best" computational formula I've seen for ray-sphere intersection
testing is what you called the "brute force" method, and goes something
like this:
------------------------------------------
#define EPSILON 1e-7 /* tolerance to roundoff errors */
/*
* SphereIntersect: find intersection of ray X=P+tD (where |D|=1)
* with sphere |C-X|^2 = r^2 by solving the quadratic equation:
* |V-tD|^2 = t^2 - 2t(V.D) + (V.V-r^2) = 0
* where V=C-P.
* The roots are:
* t = V.D +- sqrt((V.D)^2 - V.V + r^2)
*/
SphereIntersect(P, D, C, r2, tp)
double P[3], D[3]; /* ray origin point and direction */
double C[3], r2; /* sphere center and radius_squared */
double t[2]; /* t at intersection points (if any) */
{
double V[3], b, disc;
s m a
0 0 3 V = vsub(C, P); /* vector subtract */
0 3 2 b = vdot(V, D); /* dot product */
0 4 4 disc = b*b - vdot(V, V) + r2;
if (disc < 0.) return 0; /* ray misses sphere */
1 0 0 disc = sqrt(disc);
0 0 1 t[0] = b-disc; /* first root */
0 0 1 t[1] = b+disc; /* second root */
return 2; /* return #roots */
}
------------------------------------------
The numbers under "s m a" are the #sqrts, #multiplies, and #add/subtracts,
respectively. With this scheme, it takes 7 multiplies and 9 adds to
determine if the ray hits the sphere, and 1 sqrt, 2 additions more to
find t at both intersection points. I'd wager that this is "optimal"
given this set of inputs, outputs, and operators.
[ General tip to fellow optimization freaks:
I've found that I can often knock off a few superfluous multiplies
and divides if I use the quadratic formula:
roots of x^2-2b*x+c=0 are x=b+-sqrt(b*b-c)
instead of the tired old formula:
roots of a*x^2+b*x+c=0 are x=(-b+-sqrt(b*b-4*a*c))/(2*a) ]
==============================================================================
From: ph@miro.Berkeley.EDU (Paul Heckbert)
Date: 24 Dec 88 03:03:31 GMT
The topic of color image quantization seems to recur in comp.graphics
every three months or so. Sometimes it's satisfying, to see others
citing my work, but other times...
In article <571@epicb.UUCP> david@epicb.UUCP (David P. Cook) writes:
> The simplest method of reducing a 24 bit colored image to a smaller set
> of colors is to do popularity reduction. ... a more complex method,
> commonly called Color Cube Compression (devised by Paul Heckbert) ...
> The original article for this method may be found in SigGraph proceedings.
The paper you're referring to is (in refer(1) format):
%A Paul S. Heckbert
%T Color Image Quantization for Frame Buffer Display
%J Computer Graphics (SIGGRAPH '82 Proceedings)
%V 16
%N 3
%D July 1982
%P 297-307
I NEVER CALLED MY METHOD "COLOR CUBE COMPRESSION" AND I NEVER WILL.
FLAME{ People could give comp.graphics a tinge of integrity of they'd glance at
the references first before summarizing them to the rest of the world }EMALF.
Let's get our terminology straight (this is not just my terminology,
but the terminology of the image processing/pattern recognition community).
QUANTIZATION is a mapping from a continuous domain to a discrete domain
or from a large discrete domain to a small one,
for instance mapping analog voltage to discrete, 8-bit quantities
in a A/D converter, or, to use a political example,
categorizing a person as "liberal" or "conservative".
COLOR IMAGE QUANTIZATION is quantization of color images,
where a common problem is converting 24-bit rgb image data into
an 8-bit image and specially selected colormap, so it can be
displayed on an 8-bit frame buffer.
An extreme example of image quantization is the creation of bitmaps:
the quantization of grayscale data to one bit per pixel.
This can be done with THRESHOLDING, HALFTONING, or DITHERING.
COMPRESSION is transformation of digital data for more efficient storage
and transmission, for instance Huffman encoding of arbitrary
data streams or run-length encoding of pictures.
In the most ambitious forms of compression, anything goes --
in TRANSFORM CODING you transform a signal or picture into,
say, the frequency domain and compress it there (with a combination
of quantization, masking, and run-length encoding tricks) --
whereas in color image quantization for most frame buffer
architectures, you have a fixed number of bits for each pixel,
so you can't use run-length, Huffman, transform coding, or any of
the other exotic compression techniques.
Quantization is thus a specific form of compression.
CLASSIFICATION is roughly a synonym for quantization, but
its meaning in syntactic pattern recognition is the assignment of
an object to a class based on a set of measured features,
e.g. classifying a rock based on its color, density, and hardness.
In remote sensing, classification usually refers to the categorization
of pixels from multispectral satellite data into one of several
classes such as "forest", "water", "meadow", "snow", etc.
Classification can be either "supervised" or "unsupervised" depending
on whether the set of classes is known a priori or not.
(The median cut algorithm is thus an unsupervised classification
algorithm.)
See the book [Duda & Hart, Pattern Classification, Wiley] for more.
CLUSTERING is a general term, a synonym for classification.
The problem I addressed in my siggraph '82 paper was color image quantization.
I discussed two algorithms for doing this, which I called the popularity
algorithm and the median cut algorithm. As David mentioned, the popularity
algorithm makes a histogram of the colors in the picture and selects the
K most frequent as the colormap. The median cut algorithm recursively fits
a box around the colors used by the picture, in a 3-D color space, and splits
the box along the longer dimension at its median. This continues until K
boxes are made. The centroid of each is selected as the colormap entry.
David failed to mention that prequantization of the original image's colors
from 24=8+8+8 bit colors to, say, 15=5+5+5 bit colors is critical to the
popularity algorithm's success. Prequantization clusters nearby colors,
ameliorating the general flaws in the popularity algorithm.
I mentioned the popularity algorithm in the paper not as a recommended
solution, but as a simpler algorithm with which to contrast the superior
median cut algorithm.
In my paper I also mentioned that Euclidean distance in RGB space is not a
good color difference metric, that more perceptual color spaces would give
better results.
There are a number of variations on the median cut algorithm that I and others
have explored. In the paper, I split the boxes recursively,
developing a balanced binary k-d tree [Bentley & Friedman,
Data Structures for Range Searching, Computing Surveys, Dec. 1979],
but a better variation is to always split the largest, or perhaps the most
populous box. I also mentioned a variation we can call "variance minimization"
in which the box is split at the point that minimizes the sum of variances of
the two sub-boxes.
Wan, Wong, and Prusinkiewicz have investigated variance minimization
and found that always splitting the box with the maximum variance,
along the axis with maximum variance, at the plane that minimizes the sum of
the new variances, is the best heuristic among the algorithms they tested
at minimizing the mean squared error of the whole quantization.
They took a more quantitative and objective approach rather than a more
perceptual, subjective one. See their paper:
%A S. J. Wan
%A K. M. Wong
%A P. Prusinkiewicz
%T An Algorithm for Multidimensional Data Clustering
%J ACM Trans. on Mathematical Software
%V 14
%N 2
%D June 1988
%P 153-162
%K quantization, clustering
%Z discusses alternatives to median cut and k-means
Campbell et al described a "Color Cell Compression" algorithm at SIGGRAPH 86,
which is properly titled because it is not just a quantization scheme. In CCC,
each 4x4 cell of pixels is represented by two colors, the pattern of which
is indicated by a 4x4 bitmap, and which are each encoded by 8-bit color
indices into a colormap constructed with the median cut (or similar)
color image quantization algorithm. They achieve compression to 2-bits per
pixel with good results for certain types of images. Their method is
properly called compression and not quantization because each pixel is not
encoded by a unique group of bytes. Their paper was:
%A Graham Campbell, et al
%T Two Bit/Pixel Full Color Encoding
%J Computer Graphics (SIGGRAPH '86 Proceedings)
%V 20
%N 4
%D Aug. 1986
%P 215-223
%K color image compression, color image quantization
==============================================================================
From: tow@arisia.Xerox.COM (Rob Tow)
Date: 21 Apr 89 19:43:16 GMT
>Buy this book:
"Digital Halftoning"
Robert Ulichney
The MIT Press
Cambridge, MA and London, England
(c) 1987 MIT
ISBN 0-262-21009-6
==============================================================================
From: falk@sun.Eng.Sun.COM (Ed Falk)
Date: 14 Apr 89 15:56:46 GMT
In article <14198@gryphon COM>, shaulp@pnet02 cts com (Shaul Peleg) writes:
>
> I have heard SOOOOO much about those famous Pixar animations ( and even
> caught a bit of one on the Oscars ) and I was wondering if there is any way
> for one to get a hold of these on video tape?
Luxo Jr is VHS, $14 95+shipping
Red's Dream is VHS, $19 95+shipping
shipping is $5 for first copy, $2 for each additional
add 6% tax for CA
They take Visa, Mastercard & American Express
Mail to
Direct Cinema Limited
Post Office Box 69799
Los Angeles, CA 90069
U S A
Phone 213/652-8000
==============================================================================
0. IMAGE FILE FORMAT DOCUMENTATION
Many of the image file formats (TIFF, GIF, IFF, etc.) are
documented in files on
surya.waterloo.edu (129.97.129.72):doc
1. IMAGE PROCESSING/FILE-FORMAT-CONVERSION PACKAGES
Package
Author or contact person (Internet address)
Availability
Formats understood, , [only writes format]
Other nifties
FBM
Michael L. Mauldin (mlm@nl.cs.cmu.edu)
anonymous FTP, nl.cs.cmu.edu (128.2.222.56):/usr/mlm/ftp/fbm.tar.Z
CMU "face", [Diablo], FBM, GIF, IFF, PBM, , [PostScript],
Sun raster, raw grayscale
Coming soon: TIFF (maybe). Has blue-noise halftoning, which no one
else has (yet).
PBM
Jef Poskanzer (jef@rtsg.ee.lbl.gov)
anonymous FTP, expo.lcs.mit.edu (18.30.0.212):contrib/pbm.tar.Z
[ASCII], CBM, , (1 bit), [GraphOn], [LaserJet],
MacPaint, MGR, PBM, , [PostScript], [Printronix],
Sun icon, Sun raster, (1 bit), X10 bitmap, X10 xwd,
X11 bitmap, X11 xwd, "unknown" bitmap
Coming soon: FaceSaver and pixmap (grayscale/color) routines,
halftoning/normalization programs, and more!
ALV
Phill Everson (everson@compsci.bristol.ac.uk)
mail request (alv-request@compsci.bristol.ac.uk)
Sun raster, old ALV
Runs under SunView I only.
Utah Raster Toolkit
Spencer Thomas, et al. (toolkit-request@cs.utah.edu)
anonymous FTP, cs.utah.edu (128.110.4.21):pub/toolkit-2.0.tar.Z
[Abekas A60], [Abekas A62], , MacPaint, [PostScript],
RLE, , , , raw grayscale
This thing is huge (2.7MB compressed)!
TIFF
Sam Leffler (sam@ucbvax.berkeley.edu)
anonymous FTP, ucbvax.berkeley.edu (128.32.137.3):pub/tiff.tar.Z
, [PostScript], TIFF
Lots of frame-buffer-grab utilities.
2. RAYTRACERS
MTV (Mark VanderWettering), RPI (George Kyriazis), QRT (Steve Koren),
DBW (David B. Wecker), Tokyo Tech (Masataka Ohta), "Fritzz" ("Fritzz"),
"minimal" (Joe Cychosz, Paul Heckbert), PostScript (Paul Heckbert/John Hartman)
These are available via anonymous FTP from one or more of the sites
listed below. Several contain lists of references used in coding the
tracer.
3. MISC. SOFTWARE
Most of the useful code that has passed through comp.graphics
is archived on one or more of:
albanycs.albany.edu (128.204.1.4):pub/graphics
drizzle.cs.uoregon.edu (128.223.4.1):pub
uunet.uu.net (192.48.96.2):graphics
This includes:
Heckbert median-cut color-quantization
random hunks of dithering code
teapots and teapot generators a-plenty :-)
==============================================================================
�