# BEGINNER.NOT.TXT

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 :-) ============================================================================== �