_ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_, ritter@versatc.UUCP (Jack Ritter) writes: >Given a cluster of points in 3 space, is there >a good method for finding the minimum radius >sphere which encloses all the points? If not >minimum, at least "small"? Certainly it should >be tighter than the sphere which encloses the >minimum bounding box. > >I have a feeling the solution is iterative. If >so, I could provide a good initial guess for the >center & radius. The solution is not iterative. A simple solution is available in a two step process, and is characterized by whether three, or only two of the points are on the surface of the optimal sphere. Given the points, A, B, and C. Searching for the center of the optimal sphere, P, with the smallest radius, R. Checking the midpoints. set P = point halfway between A and B set R = 1/2 of length from A to B If length from C to P is less than or equal to R ---> done Repeat with line A-C, and B-C if needed. Extending the midpoints at right angles. build the line which intersects A-B at a right angle through the midpoint of A-B, call the line D. build the line which intersects A-C at a right angle through the midpoint of A-C, call it E. P is the point where D and E intersect. (Solve the simultaneous equations; R is the length A-P) ----------------------------------------------------------------------------- From: bullerj@handel.colostate.edu (Jon Buller) Subject: Re: Pixar's noise function Organization: Colorado State University, Ft. Collins CO 80523 In article <3599@pixar.UUCP> aaa@pixar.UUCP (Tony Apodaca) writes: >In article <2553@ssc-vax.UUCP> coy@ssc-vax.UUCP (Stephen B Coy) writes: >> ...My question: Does anyone out there know what this >>noise function really is? > > Three-dimensional simulated natural textures using pseudorandom >functions were simultaneously and independently developed by Darwyn >Peachey and Ken Perlin in 1984-5. Both have papers in the 1985 >Siggraph Proceedings describing their systems. Perlin, in particular, >describes in detail how noise() is implemented and can be used creatively [A description of the properties of the noise function goes here...] > If you have ever been interested in realistic computer graphics, do >whatever it takes to get a look at Perlin's paper. In 1985, his pictures >were absolutely astounding. In 1989, they are STILL astounding. No kidding, some of those pictures are INCREDIBLE. Here is my code for a look-alike to the Pixar Noise function, and while I can't say anything about exactly what Pixar's looks like, I think this is probably close. After reading the 1985 SIGGRAPH papers on 3d texturing, (and seeing my prof's code to do a similar thing) I wrote this. It uses a quadratic B-Spline instead of the cubic Hermite interpolant implied in the paper. Also note that DNoise is just the x, y, and z derivatives of Noise (which are also B-Splines). The hashing functions are from Knuth's Art of Computer Programming (I don't remember which volume though). I know the code is Pascal, and all of you will hate it, but I believe I write better Pascal than C... One final note, this was Lightspeed Pascal 2.0 for the Macintosh, but things have been reformatted slightly to get it on the net. I hope this is what you all wanted. -------- More: One other thing you might notice, Noise is C1 continuous, DNoise is only C0. This means that DNoise will have creases in it (along the planes of the random grid. To see this, crank out a square: 0x); xa = floor(P1 * (xi * phi - floor(xi * phi))); xb = floor(P1 * ((xi + 1) * phi - floor((xi + 1) * phi))); xc = floor(P1 * ((xi + 2) * phi - floor((xi + 2) * phi))); yi = floor(p->y); ya = floor(P2 * (yi * phi - floor(yi * phi))); yb = floor(P2 * ((yi + 1) * phi - floor((yi + 1) * phi))); yc = floor(P2 * ((yi + 2) * phi - floor((yi + 2) * phi))); zi = floor(p->z); za = floor(P3 * (zi * phi - floor(zi * phi))); zb = floor(P3 * ((zi + 1) * phi - floor((zi + 1) * phi))); zc = floor(P3 * ((zi + 2) * phi - floor((zi + 2) * phi))); p000 = pts[xa + ya + za & NUMPTS - 1]; p100 = pts[xb + ya + za & NUMPTS - 1]; p200 = pts[xc + ya + za & NUMPTS - 1]; p010 = pts[xa + yb + za & NUMPTS - 1]; p110 = pts[xb + yb + za & NUMPTS - 1]; p210 = pts[xc + yb + za & NUMPTS - 1]; p020 = pts[xa + yc + za & NUMPTS - 1]; p120 = pts[xb + yc + za & NUMPTS - 1]; p220 = pts[xc + yc + za & NUMPTS - 1]; p001 = pts[xa + ya + zb & NUMPTS - 1]; p101 = pts[xb + ya + zb & NUMPTS - 1]; p201 = pts[xc + ya + zb & NUMPTS - 1]; p011 = pts[xa + yb + zb & NUMPTS - 1]; p111 = pts[xb + yb + zb & NUMPTS - 1]; p211 = pts[xc + yb + zb & NUMPTS - 1]; p021 = pts[xa + yc + zb & NUMPTS - 1]; p121 = pts[xb + yc + zb & NUMPTS - 1]; p221 = pts[xc + yc + zb & NUMPTS - 1]; p002 = pts[xa + ya + zc & NUMPTS - 1]; p102 = pts[xb + ya + zc & NUMPTS - 1]; p202 = pts[xc + ya + zc & NUMPTS - 1]; p012 = pts[xa + yb + zc & NUMPTS - 1]; p112 = pts[xb + yb + zc & NUMPTS - 1]; p212 = pts[xc + yb + zc & NUMPTS - 1]; p022 = pts[xa + yc + zc & NUMPTS - 1]; p122 = pts[xb + yc + zc & NUMPTS - 1]; p222 = pts[xc + yc + zc & NUMPTS - 1]; xf = p->x - xi; x1 = xf * xf; x2 = 0.5 * x1; x1 = 0.5 + xf - x1; x0 = 0.5 - xf + x2; yf = p->y - yi; y1 = yf * yf; y2 = 0.5 * y1; y1 = 0.5 + yf - y1; y0 = 0.5 - yf + y2; zf = p->z - zi; z1 = zf * zf; z2 = 0.5 * z1; z1 = 0.5 + zf - z1; z0 = 0.5 - zf + z2; return z0 * (y0 * (x0 * p000 + x1 * p100 + x2 * p200) + y1 * (x0 * p010 + x1 * p110 + x2 * p210) + y2 * (x0 * p020 + x1 * p120 + x2 * p220)) + z1 * (y0 * (x0 * p001 + x1 * p101 + x2 * p201) + y1 * (x0 * p011 + x1 * p111 + x2 * p211) + y2 * (x0 * p021 + x1 * p121 + x2 * p221)) + z2 * (y0 * (x0 * p002 + x1 * p102 + x2 * p202) + y1 * (x0 * p012 + x1 * p112 + x2 * p212) + y2 * (x0 * p022 + x1 * p122 + x2 * p222)); } Vector Dnoise(p) Vector *p; { Vector v; int xi, yi, zi; int xa, xb, xc, ya, yb, yc, za, zb, zc; double xf, yf, zf; double x2, x1, x0, y2, y1, y0, z2, z1, z0; double xd2, xd1, xd0, yd2, yd1, yd0, zd2, zd1, zd0; double p000, p100, p200, p010, p110, p210, p020, p120, p220; double p001, p101, p201, p011, p111, p211, p021, p121, p221; double p002, p102, p202, p012, p112, p212, p022, p122, p222; xi = floor(p->x); xa = floor(P1 * (xi * phi - floor(xi * phi))); xb = floor(P1 * ((xi + 1) * phi - floor((xi + 1) * phi))); xc = floor(P1 * ((xi + 2) * phi - floor((xi + 2) * phi))); yi = floor(p->y); ya = floor(P2 * (yi * phi - floor(yi * phi))); yb = floor(P2 * ((yi + 1) * phi - floor((yi + 1) * phi))); yc = floor(P2 * ((yi + 2) * phi - floor((yi + 2) * phi))); zi = floor(p->z); za = floor(P3 * (zi * phi - floor(zi * phi))); zb = floor(P3 * ((zi + 1) * phi - floor((zi + 1) * phi))); zc = floor(P3 * ((zi + 2) * phi - floor((zi + 2) * phi))); p000 = pts[xa + ya + za & NUMPTS - 1]; p100 = pts[xb + ya + za & NUMPTS - 1]; p200 = pts[xc + ya + za & NUMPTS - 1]; p010 = pts[xa + yb + za & NUMPTS - 1]; p110 = pts[xb + yb + za & NUMPTS - 1]; p210 = pts[xc + yb + za & NUMPTS - 1]; p020 = pts[xa + yc + za & NUMPTS - 1]; p120 = pts[xb + yc + za & NUMPTS - 1]; p220 = pts[xc + yc + za & NUMPTS - 1]; p001 = pts[xa + ya + zb & NUMPTS - 1]; p101 = pts[xb + ya + zb & NUMPTS - 1]; p201 = pts[xc + ya + zb & NUMPTS - 1]; p011 = pts[xa + yb + zb & NUMPTS - 1]; p111 = pts[xb + yb + zb & NUMPTS - 1]; p211 = pts[xc + yb + zb & NUMPTS - 1]; p021 = pts[xa + yc + zb & NUMPTS - 1]; p121 = pts[xb + yc + zb & NUMPTS - 1]; p221 = pts[xc + yc + zb & NUMPTS - 1]; p002 = pts[xa + ya + zc & NUMPTS - 1]; p102 = pts[xb + ya + zc & NUMPTS - 1]; p202 = pts[xc + ya + zc & NUMPTS - 1]; p012 = pts[xa + yb + zc & NUMPTS - 1]; p112 = pts[xb + yb + zc & NUMPTS - 1]; p212 = pts[xc + yb + zc & NUMPTS - 1]; p022 = pts[xa + yc + zc & NUMPTS - 1]; p122 = pts[xb + yc + zc & NUMPTS - 1]; p222 = pts[xc + yc + zc & NUMPTS - 1]; xf = p->x - xi; x1 = xf * xf; x2 = 0.5 * x1; x1 = 0.5 + xf - x1; x0 = 0.5 - xf + x2; xd2 = xf; xd1 = 1.0 - xf - xf; xd0 = xf - 1.0; yf = p->y - yi; y1 = yf * yf; y2 = 0.5 * y1; y1 = 0.5 + yf - y1; y0 = 0.5 - yf + y2; yd2 = yf; yd1 = 1.0 - yf - yf; yd0 = yf - 1.0; zf = p->z - zi; z1 = zf * zf; z2 = 0.5 * z1; z1 = 0.5 + zf - z1; z0 = 0.5 - zf + z2; zd2 = zf; zd1 = 1.0 - zf - zf; zd0 = zf - 1.0; v.x = z0 * (y0 * (xd0 * p000 + xd1 * p100 + xd2 * p200) + y1 * (xd0 * p010 + xd1 * p110 + xd2 * p210) + y2 * (xd0 * p020 + xd1 * p120 + xd2 * p220)) + z1 * (y0 * (xd0 * p001 + xd1 * p101 + xd2 * p201) + y1 * (xd0 * p011 + xd1 * p111 + xd2 * p211) + y2 * (xd0 * p021 + xd1 * p121 + xd2 * p221)) + z2 * (y0 * (xd0 * p002 + xd1 * p102 + xd2 * p202) + y1 * (xd0 * p012 + xd1 * p112 + xd2 * p212) + y2 * (xd0 * p022 + xd1 * p122 + xd2 * p222)); v.y = z0 * (yd0 * (x0 * p000 + x1 * p100 + x2 * p200) + yd1 * (x0 * p010 + x1 * p110 + x2 * p210) + yd2 * (x0 * p020 + x1 * p120 + x2 * p220)) + z1 * (yd0 * (x0 * p001 + x1 * p101 + x2 * p201) + yd1 * (x0 * p011 + x1 * p111 + x2 * p211) + yd2 * (x0 * p021 + x1 * p121 + x2 * p221)) + z2 * (yd0 * (x0 * p002 + x1 * p102 + x2 * p202) + yd1 * (x0 * p012 + x1 * p112 + x2 * p212) + yd2 * (x0 * p022 + x1 * p122 + x2 * p222)); v.z = zd0 * (y0 * (x0 * p000 + x1 * p100 + x2 * p200) + y1 * (x0 * p010 + x1 * p110 + x2 * p210) + y2 * (x0 * p020 + x1 * p120 + x2 * p220)) + zd1 * (y0 * (x0 * p001 + x1 * p101 + x2 * p201) + y1 * (x0 * p011 + x1 * p111 + x2 * p211) + y2 * (x0 * p021 + x1 * p121 + x2 * p221)) + zd2 * (y0 * (x0 * p002 + x1 * p102 + x2 * p202) + y1 * (x0 * p012 + x1 * p112 + x2 * p212) + y2 * (x0 * p022 + x1 * p122 + x2 * p222)); return v; } ----------------------------------------------------------------------------- END OF RTNEWS _ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_ I don't get it. Why doesn't every CG Software vendor supply a >ray tracer. It's definitely the easiest renderer to write. Yes, >they are slo-o-o-o-o-o-w, but they sound glitzy and (I bet) would >stimulate sales, even if buyers never used them. Having worked at two CG Software companies, I know firsthand how the "to do" list grows faster than you can possibly implement features (no matter how many programmers you have -- c.f."The Mythical Man-Month"). Jeff is right that ray tracing sounds glitzy, and, yes, it is another factor to toss into the sales pitch -- but it is not at all clear that it is worth the effort. Most (if not all) ray tracers assume either infinite rendering time or infinite disk space. In the real world (a 68020 and a 144Meg disk) this is not the case. The raytracer I wrote at Neo Visuals was written in Fortran -- ergo no dynamic memory allocation -- so I had to work on optimizing it without significantly increasing the memory used. This mostly involved intelligently choosing when to fire rays. The renderer performs a Watkins-style rendering, and fires secondary rays from a pixel only if the surface at that pixel needs to be raytraced. Memory constraints prevented me from using any spatial subdivision methods. Yes, ray traced images are great sales tools. They are also sometimes not entirely honest -- novice users ("I want a system to animate Star Wars quality images, about ten minutes of animation a day on my XT") are not aware of the expense of raytracing, and very few salesmen go out of their way to point this out. However, these same users, unsure of the technology, put together a list of buzzwords (amongst them "raytracing") and go out to find that piece of software which has the most features on their list. Hence I coined the phrase "buzzword compatible" while at Neo-Visuals (and also "polygons for polygons sake" -- but that's another story). I have also seen demos, animations, and pictures at trade shows, presented by hardware and software vendors, which were extremely and deliberately misleading. A very common example is to show nice animation that was not really created with your software product. The animation having been typically created by special programs and add-ons. An obvious example was Abel, marketing their "Generation 2" software with "Sexy Robot", "Gold", "Hawaiian Punch", etc. I only mention Abel because they are no longer in business -- I don't want to mention any names of existing companies. I hadn't intended this to be a flame. But that sums up why not all software vendors bother with raytracing, and how it can be abused if not handled carefully. ==================== On Steve Upstill's remarks on the Renderman standard: Disclaimer: I have not read the Renderman specs, and have spoken to people who liked it and people who didn't. I would like to say that while I was at Neo-Visuals, Tom Porter and Pat Hanrahan did indeed drop by to ask us about our needs, and to ensure that the interface would be compatible with our system. As I recall, we asked that the interface be able of handling arbitrary polygons (n vertices, concave, etc). As I recall, I was playing devil's advocate at the meeting, questioning whether rendering had settled down enough to be standardized. So yes, at least Neo-Visuals did get to have a say and contribute to the interface. I spoke to one rendering person at Siggraph who didn't appreciate the way Pixar had handed down the interface and said "thou shalt enjoy." Well the alternative would be a PHIGS-like process: years spent in committees trying to hash out a compromise which will in all likelihood be obsolete before the ink is dry. In fact, two hardware vendors decided to take matters into their own hands and came up with PHIGS+. Yes, the interface is probably partly a marketing initiative by Pixar. Why would they do it otherwise? Why should they do it otherwise? I would guess that Pixar hopes to have the standard adopted, then come out with a board which will do Renderman rendering faster than anyone else's software. This seems a natural progression. More and more rendering features have been appearing in hardware -- 2D, 3D, flat shaded, Gouraud, and now Phong and texture maps. It is very probable that in a few years, "renderers" will be hardware, except for experimental, research, and prototype ones. ----------------------------------------------------------------------------- Minimum Bounding Sphere, continued ---------------------------------- by Jack Ritter, {ames,apple,sun,pyramid}!versatc!ritter I noticed in "The Ray Tracing News" an answer to my query about minimum bounding spheres. The answer following my question assumes there are 3 points. (Search for "Ray Traced Bounding Spheres"). This is wrong; I meant n points in 3 space. Since then, Lyle Rains, Wolfgang Someone and I have arrived at a fast way to find a tight bounding sphere for n points in 3 space: 1) Make 1 pass through pts. Find these 6 pts: pt with min x, max x, min/max y, min/max z. Pick the pair with the widest dimensional span. This describes the diameter of the initial bounding sphere. If the pts are anywhere near uniform, this sphere will contain most pts. 2) Make 2nd pass through pts: for each pt still outside current sphere, update current sphere to the larger sphere passing through the pt on 1 side, and the back side of the old sphere on the other side. Each new sphere will (barely) contain its previous pts, plus the new pt, and probably some new outsiders as well. Step 2 should need to be done only a small fraction of total num pts. The following is code (untested as far as I know) to increment sp: typedef double Ordinate; typedef double Distance; typedef struct { Ordinate x; Ordinate y; Ordinate z; } Point; typedef struct { Point center; Distance radius; } Sphere; Distance separation(pa, pb) Point *pa; Point *pb; { Distance delta_x, delta_y, delta_z; delta_x = pa->x - pb->x; delta_y = pa->y - pb->y; delta_z = pa->z - pb->z; return (sqrt(delta_x * delta_x + delta_y * delta_y + delta_z * delta_z)); } Sphere *new_sphere(s, p) Sphere *s; Point *p; { Distance old_to_p; Distance old_to_new; old_to_p = separation(&s->center, p); if (old_to_p > s->radius) { /* could test vs r**2 here */ s->radius = (s->radius + old_to_p) / 2.0; old_to_new = old_to_p - s->radius; s->center.x = (s->radius * s->center.x + old_to_new * p->x) / old_to_p; s->center.y = (s->radius * s->center.y + old_to_new * p->y) / old_to_p; s->center.z = (s->radius * s->center.z + old_to_new * p->z) / old_to_p; } return (s); } Jack Ritter, S/W Eng. Versatec, 2710 Walsh Av, Santa Clara, CA 95051 Mail Stop 1-7. (408)982-4332, or (408)988-2800 X 5743 UUCP: {ames,apple,sun,pyramid}!versatc!ritter [This looks to be a good quick algorithm giving a near-optimal solution. Has anyone come up with an absolutely optimal solution? The "three point" solution (in last issue) gives us a tool to do a brute force search of all triplets, but this is insufficient to solve the problem. For example, a tetrahedron's bounding sphere cannot be found by just searching all the triplets, as all such spheres would leave out the fourth point. - EAH] ----------------------------------------------------------------------------- Comments on "A Review of Multi-Computer Ray-Tracing" --------------------------------------------------- by Thierry Priol I read with a great interest in the hardcopy "Ray Tracing News (May 1989)" "A Review of Multi-Computer Ray-Tracing". But, D.A.J. Jevans said that our work presented in CGI "may even serve to cloud the important issues in multi-computer ray-tracing"! I do not agree with this remark. The presentation at CGI describes only a first step in using multi-processor ray tracing algorithms. It is true that there were no interesting results in this paper. D.A.J. Jevans also said that a hypercube architecture is hardware specific. I do not agree. This kind of architecture represents a great part of distributed memory architectures. Our algorithm is not specific for this topology and can work on a SYMULT-2010 which uses a mesh topology. However, I agree when he said that our algorithm provides little in the way of new algorithms, since we used Cleary's algorithm. But we think that for the moment, the main problem is not to create new algorithms but to make experiments with some algorithms presented by several authors because most of them have been simulated but not implemented. Our experiments show that many problems due to distributed computing (not only load and memory balancing) were not solved by the authors. At present, our algorithm has been modified to take into account load balancing and we have several results not yet published. These new results may give some important conclusions about the Cleary approach (processor-volume association). We are working now on a new algorithm based on a global memory on distributed memory architectures! For my mind it is the best solution to obtain load and memory balancing. The ray coherence property is a means to have a sort of locality when data is read in the global memory (best use of caches). We are very interested (D. Badouel, K. Bouatouch and myself) in submitting to the "Ray-tracing News" a short paper which summarizes our work in parallel ray-tracing algorithm for distributed memory architecture. This contribution should present two ray tracing algorithms with associated results. This work has not been yet published outside France. ======== USENET cullings follow =============================================== Subject: Dataflow architectures and Ray Tracing From: kyriazis@rpics (George Kyriazis) Newsgroups: comp.arch,comp.graphics Organization: RPI CS Dept. Hi! I am wondering if anybody knows if there have been any attempts to port a ray tracing algorithm on a dataflow computer, or if there has been such a machine especially built for ray tracing. I am posting to both comp.arch and comp.graphics since I think that it concerns both newsgroups. It seems to me that a dynamic dataflow architecture is more appropriate to this problem because of the recursiveness and parallelism of the algorithm. Thanks in advance for any info... ----------------------------------------------------------------------------- Subject: Re: Pixar's noise function Summary: my noise, better described (I hope) Reply-To: bullerj@handel.colostate.edu.UUCP (Jon Buller) Organization: Colorado State University, Ft. Collins CO 80523 In article <...> jamesa@arabian.Sun.COM (James D. Allen) writes: >In article <...>, aaa@pixar.UUCP (Tony Apodaca) writes: >> In article <...> coy@ssc-vax.UUCP (Stephen B Coy) writes: >> > ...My question: Does anyone out there know what this >> >noise function really is? >> >> ... Conceptually, noise() >> is a "stochastic three-dimensional function which is statistically >> invariant under rotation and translation and has a narrow bandpass >> limit in frequency" (paraphrased from [Perlin1985]). This means that >> you put three-space points in, and you get values back which are basically >> random. But if you put other nearby points in, you get values that are >> very similar. The differences are still random, but the maximum rate of >> change is controlled so that you can avoid aliasing. If you put a set >> of points in from a different region of space, you will get values out >> which have "the same amount" of randomness. > > Anyone willing to post a detailed description of such an > algorithm? (Jon Buller posted one, but I couldn't figure it out: > what is `Pts'?) Sorry about not really describing my program to anyone, I know what it does, and I never expected anyone else to see it (isn't it obvious) :-) What it does is: pass a location in space, and an array of random numbers (this is 'Pts'). I fill the array with 0.0 .. 1.0 but any values or range will work. (I have other textures which color based on distance to the nearest point of a random set, hence the name, It has 4 values per entry at times.) Step 1: change the location to a group of points to interpolate. This is where xa,xb,xc,...zc come in, any location with the same coords (when trunc'ed) will produce the same xa...zc values, making the same values for the interpolation at the end. These xa..zc are then hashed in to the 'Pts' array to produce p000...P222, these 27 random numbers are then interpolated with a Quadratic 3d B-Spline (the long ugly formula at the end). The variables based on xf,yf, and zf (I believe they are x0..z2) are the B-Spline basis functions (notice to get DNoise, just take the (partial) derivatives of the basis functions and re-evaluate the spline). Step 2: now you have a value that is always smaller than the largest random number in 'Pts' (equal to in the odd case that major bunches of the numbers are also the maximum in the range). By the same argument, all numbers returned are larger than the smallest number in the array. (this can be handy if you don't want to have to clip your values to some limit.) I hope this explains the use of the routine better. Sorry I didn't realize that earlier. If you have any other questions about it, mail them to me, and I'll do my best to explain it. Jon ----------------------------------------------------------------------------- From: tadguy@cs.odu.edu (Tad Guy) Newsgroups: comp.graphics Subject: Re: DBW_render for SUN 3 ? Organization: Old Dominion University, Norfolk, VA daniel@unmvax.unm.edu writes: >Has anyone converted the public domain ray trace program called DBW_render >to run on a SUN workstation? Ofer Licht has done just that. His modified DBW_Render is available via anonymous ftp from xanth.cs.odu.edu as /amiga/dbw.zoo. It is also designed to use ``DistPro'' to distribute the computations between many machines (this is available as well as /amiga/distpro.zoo). His address: Ofer Licht (ofer@gandalf.berkeley.edu) 1807 Addison St. #4 Berkeley, CA 94703 (415) 540-0266 ----------------------------------------------------------------------------- From: eugene@eos.UUCP (Eugene Miya) Newsgroups: comp.graphics Subject: Re: Steel colors Organization: NASA Ames Research Center, Calif. In article <...> jwl@ernie.Berkeley.EDU.UUCP (James Wilbur Lewis) writes: >In article <...> jep@oink.UUCP (James E. Prior) writes: >>I've noticed that when I look closely at reasonably clean bare steel in good >>sunlight that it appears to have a very fine grain of colors. >> >>What is this due to? > >Probably a diffraction-grating type effect due to scratches, roughness, or >possibly crystalline structure at the surface. Funny you should mention this. I was sitting with my officemate, George Michael, he says Hi Kelly, and we were talking about stuff and he brought up the subject of polish. He said there were people at Livenomore who were researching the issue of polish for big mirrors, but that polish really isn't well understood, still open interesting physical science questions. Polish consists of minute "scratches" which have a set of interesting properties. You can probably [write] to them and get TRs on the topic. Polish is more than iridescence. Also, since somebody asked, the date on the Science article by Greenberg on Light reflection models for graphics is 14 April 1989, page 166. It will provide simple models for this type of stuff. ----------------------------------------------------------------------------- From: ritter@versatc.UUCP (Jack Ritter) Newsgroups: comp.graphics Subject: Dirty Little Tricks Organization: Versatec, Santa Clara, Ca. 95051 I've come up with a fast approximation to 3D Euclidean distance ( sqrt(dx*dx+dy*dy+dz*dz) ). (It's probably not original, but .....) 1) find these 3 values: abs(dx), abs(dy), abs(dz). 2) Sort them (3 compares, 0-3 swaps) 3) Approx E.D. = max + (1/4)med + (1/4)min. (error: +/- 13%) max + (5/16)med + (1/4)min has 9% error. max + (11/32)med + (1/4)min has 8% error. As you can see, only shifts & adds are used, and it can be done with integer arithmetic. It could be used in ray tracing as a preliminary test before using the exact form. We all have our dirty little tricks. ----------------------------------------------------------------------------- From: kyriazis@turing.cs.rpi.edu (George Kyriazis) Newsgroups: comp.graphics Subject: Obfuscated ray tracer Organization: RPI CS Dept. A while ago, while it was still snowing, I was feeling adventurous, and a nice weekend I decided to write an obfuscated ray tracer. A friend of mine told me that is not too obfuscated for the "Obfuscated C Contest", I had already wasted one whole day, so I gave up. Today, I was cleaning up my account, and I thought it would be a very appropriate posting for comp.graphics. It is a hacker's approach to ray tracing; produces a text image on the screen. No shading; different characters represent different objects. The source code is 762 bytes long. I KNOW that I'll get flamed, but who cares! :-) Have fun people! So, here it is: Compile with cc ray.c -o ray -lm /* (c) 1988 by George Kyriazis */ #include #define Q " #define _ define #_ O return #define T struct #_ G if #_ A(a,b) (a=b) #define D double #_ F for #define P (void)printf(Q #define S(x) ((x)*(1/*p-"hello"[6])/*comment*/*x)) T oo{D q,r,s,t;};int m[1]={2};T oo o[2]={{10,10,10,18},{15,15,17,27}};int x,y;D I(i){D b,c,s1,s2;int*p=0,q[1];b=i/*p+1["_P]+(1-x*x)*erf(M_PI/i)/1*/**q+sin(p);{ {b=2*-(i+o)->s;c=S(x-i[o].q)+S(y-o[i].r)+S(i[o].s)-(o+i)->t;}A(s1,S(b));}{G((s2 =(S(b)-4*c)<0?-1:sqrt(-4*c+S(b)))<0){O(b-(int)b)*(i>=0-unix);}}s1=(-b+s2)/2;s2= s1-s2;s1=s1<=0?s2:s1;s2=s2<=0?s1:s2;O s1-1);i= A(i,i+1))G(z<(A(zz,I(i))))z=zz,ii=i;G(!!z)P%d",ii);else P%c",32-'\0');}P\n");}} ----------------------------------------------------------------------------- Subject: Contents of FTP archives, skinner.cs.uoregon.edu From: markv@tillamook.cs.uoregon.edu (Mark VandeWettering) Newsgroups: comp.graphics Organization: University of Oregon CIS Dept. Recently, the ftp archive of raytracing stuff was moved from our dying VAX-750 (drizzle.cs.uoregon.edu) to our new fileserver, which is called skinner.cs.uoregon.edu, or just cs.uoregon.edu. There is more diskspace available, and I have expanded the archives to contain several new items. I thought I would post the README here to let people know of its availability. skinner.cs.uoregon.edu contains information largely dealing with the subject of raytracing, although a radiosity tracer or solid modeler would be a welcome addition to the contents there. I am always busy looking for new software aquisitions, so if you have anything you wish to put there, feel free to send me a note. Mark VandeWettering -cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut-cut The old README was dated, so I thought I would update this new one... dr-xr-xr-x 2 ftp 512 Feb 11 18:53 bibs contains bibliographies for fields that I am interested in, such as graphics and functional programming. drwxrwxr-- 2 ftp 512 May 13 23:44 gif.fmt descriptions of the gif format. Too many people wanted this, so I thought I would make it available. drwxrwxr-x 2 root 512 May 24 22:25 grafix-utils Utilities for converting among graphics formats etc. Now includes fuzzy bitmap, should also include pbm and utah raster toolkit soon. drwxrwxr-- 2 ftp 1024 May 14 15:45 hershey The Hershey Fonts. Useful PD fonts. drwxrwxr-x 2 root 512 May 24 22:26 mtv-tracer My raytracer, albeit a dated version. dr-xr-xr-x 2 ftp 512 Feb 16 17:24 musgrave Copies of papers on refraction by Kenton Musgrave. drwxrwxr-x 2 root 512 May 24 22:26 nff Haines SPD raytracing package, with some other NFF images created by myself & others. Useful for the mtv raytracer. drwxr-xr-x 2 ftp 1536 May 24 11:44 off-objects Some interesting, PD or near PD images from the OFF distribution. dr-xr-xr-x 2 ftp 512 Feb 15 22:48 polyhedra Polyhedra from the netlib server. I haven't done anything with these... dr-xr-xr-x 2 ftp 512 Mar 6 17:45 qrt The popular raytracer for PCs. dr-xr-xr-x 2 ftp 512 May 24 22:26 rayfilters Filters to convert the MTV output to a number of devices... drwxrwxr-x 2 root 512 May 24 22:26 raytracers Other raytracers.... -rw-r--r-- 1 ftp 323797 May 24 01:47 sunrpc.tar.Z SUN RPC v.3.9 [All issues of the email version of "The RT News" have been put in the directory "RTNews" since this posting.] ----------------------------------------------------------------------------- END OF RTNEWS _ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_, but send contributions and subscriptions requests to Eric Haines] All contents are US copyright (c) 1989 by the individual authors Contents: Introduction A SIGGRAPH Report, by Eric Haines Ray Tracing Poll, from the roundtable discussion _An Introduction to Ray Tracing_, Announcement and Errata _Graphics Gems_ Call for Contributions, by Andrew Glassner New People and Address Changes Bugs in MTV's Ray Tracer, by Eric Haines Bug in SPD, from Pete Segal Solid Textures Tidbit, by Roman Kuchkuda Sundry Comments, by Jeff Goldsmith Texture Mapping Question, by Susan Spach ======== USENET cullings follow ======== Ray Traced Image Files, by Prem Subramanyan Image Collection, by Paul Raveling MTV-Raytracer on ATARI ST - precision error report, by Dan Riley Question on Ray Tracing Bicubic Parametric Patches, by Robert Minsk ------------------------------------------------------------------------------- Introduction Now that the "RT News" is posted on comp.graphics, I'd like to make a few changes. First of all, you really don't need to get on the subscription list of the RT News if you're an avid reader of comp.graphics. However, I do want to maintain an emailing list of people interested in ray tracing. So, I'll be keeping a single address list of interested people (which I will call the "contact list"), and only some of the people on this list need to be sent copies of the RT News. Furthermore, it would be nice if various schools, etc, would make a single email address the place where they will receive the RT News. For example, Duke has "raycasting@duke.cs.duke.edu" as the address to which I should send the RT News. They also have individuals on the address list, but individual copies are not sent to them. Instead, the "raycasting" account they have remails the RT News to all people that are interested at Duke. In this way I can cut down on having issues sent out unnecessarily, of worrying about bounced mail, of maintaining a long mailing list (currently about 100 people), etc etc. To summarize, there are then a few different ways you can be listed. 1) Individual subscriber - You don't read comp.graphics and want to get the RT News. Your name is put on the subscriber list and the contact list. To subscribe, simply send me your name, email and snail mail addresses, and a one line summary (that I'll put next to your name) describing any special areas you're interested in (e.g. "parallelism, radiosity, filtering" might be one). You might also send me a few paragraphs about what you're up to nowadays, and I'll include this in the News. 2) Group subscriber - Like Duke. This way you have full control over who will automatically get an issue, and I won't have to change my subscriber list each time someone else wants to get the RT News. Some people have already switched over. I just received this: We went ahead and implemented the local alias. It's "raytrace", which you can reach as raytrace@cpsc.ucalgary.ca or calgary!raytrace. At the moment Dave Jevans and I (Bill Jones) are the only subscribers. 3) Contact list only - You read comp.graphics and so do not need to subscribe. However, you want to be on the list of people interested in ray tracing. Another advantage of the contact list is that people may send you mail - for instance, I wrote all the people on the list and invited them to come to a get-together for ray tracers at SIGGRAPH (more on this later). Everyone who is a subscriber is also automatically on the contact list, but not vice versa. You can also be listed as an individual on the contact list if you're a group subscriber. 4) The silent majority - You don't need to be on any list, and are happy just reading comp.graphics (or have hit the "n" key by now). Currently almost everyone on the contact list is also a subscriber. So, if you read comp.graphics fairly constantly and are on the subscriber list, please tell me to put you on only the contact list. Clear as mud? Good. I'll probably send the above to all people asking for subscriptions just to make sure they know what's what, so don't be offended if you get one. Whew! Well, with that done, I should mention that anyone can ask for a copy of the contact list. If you want to subscribe to the RT News, hardcopy edition, that's another coastline entirely - contact Andrew Glassner at glassner.pa@xerox.com for details, as he's the editor of that one. The email and hardcopy journals are mostly non-overlapping, so it's worth your while to get both if you're seriously interested in the subject. I can't afford to send out the back issues of the email RT News, but they are available via anonymous FTP from: cs.uoregon.edu - in /pub, also has lots of other ray tracing stuff, etc freedom.graphics.cornell.edu - in /pub, also has Xcu menu creator One other resource: I've been updating Paul Heckbert's ray tracing bibliography while he's been busy at grad school. If you would like the latest copy of this list, or have anything to add or change in it, just write me. I also will be posting it to the two ftp sites realsoonnow. ------------------------------------------------------------------------------- A SIGGRAPH Report, by Eric Haines Another SIGGRAPH has come and gone, and I had a good time. My only frustration was meeting many researchers for a minute and not getting to talk with them. I noticed that although the ray tracing session had but three papers, there were about nine others throughout the proceedings that used ray tracing techniques in various ways. Ray tracing (and ray casting) as a graphics tool has come into its own. A few more ray tracers are out on the market, such as "Sculpt 3D" by Byte by Byte for the Macintosh and Amiga and "LazerRays" by Lazerus. Hewlett Packard is now shipping radiosity and ray tracing software bundled in with every high-end graphics workstation. Intergraph has been getting a fair bit of airplay out of their new ray tracing package, though I haven't gotten details yet. Alias should be offering a ray tracer sometime soon. Ray tracing researchers got together informally for a "ray tracing roundtable" for an hour and some. Like last year, it was a large gathering, with around 50 people attending. We went around the group, with each person giving a brief introduction. I took an informal poll on a few questions, Andrew noted that the ray tracing book was out, and asked for contributions to "Graphics Gems" (more later), then we broke up and talked about this and that. Given the size of the gathering, it was a bit frustrating: there are all these people that I've wanted to meet and talk with in the same room, and after half an hour they're all gone and I've spoke with only a few. Basically, the roundtable meeting is too big for my tastes. One possibility that you all might consider is to invite people in your own special interest to a lunch or dinner. For example, I went to a pleasant "global illuminators" lunch this SIGGRAPH, where there were about twelve people - a good size. Oh, some nice books came out this SIGGRAPH. I'll plug the ray tracing book later. Others worth note (i.e. I bought them) are _Mathematical Elements for Computer Graphics, Second Edition_ by Rogers and Adams, which has been expanded to more than twice its original length, and _The RenderMan Companion_ by Steve Upstill, which looks like a nice book no matter what your feelings on RenderMan itself. I'm looking forward to the much expanded second edition of Foley & Van Dam's _Fundamentals of Interactive Computer Graphics_, which should be out early next year. ------------------------------------------------------------------------------- Ray Tracing Poll, from the roundtable discussion At the roundtable people were polled on a few questions. 1. What efficiency schemes have you used? Grids - 20 Octree/BSP - 26 (4 were specifically BSP) Bounding Volume Hierarchy - 22 Hybrid - 17 Greater than 3D (4D or 5D) - 13 Other - 5 (what were these, anyway?) 2. How many processors have you used? One processor - 21.1 Multiprocessor - 29.1 More than 10 processors - 21 More than 100 processors - 4 The most processors used was 1024 (2 people). 3. How long do you usually wait for a picture? Less than a minute - 1 Less than ten minutes - 6 Less than an hour - 13 Less than ten hours - 25 4. What is your favorite background color? UNC "Carolina Blue" - 12 Black - 15 ------------------------------------------------------------------------------- _An Introduction to Ray Tracing_, Announcement and Errata Well, the book is finally out. It is edited by Andrew Glassner, and sells for $49.95 from Academic Press. It includes sections by Andrew, Pat Hanrahan, Rob Cook, Paul Heckbert, Jim Arvo, Dave Kirk, and myself. The book is essentially the same as the 1988 SIGGRAPH Course Notes, with the addition of some figures and images and some minor corrections. Incidentally, if you have the book and find any glaring errors, please notify Andrew Glassner; enough copies sold at SIGGRAPH that another edition will be printed soon. Considering that the authors are scattered around the country, the book flows fairly well and covers most areas of ray tracing theory and practice. Also, there's finally a text to suggest when someone wants to know whether a point is inside a polygon (Sedgewick's _Algorithms_ didn't solve it efficiently). If you don't have a copy, buy a few and make us all fabulously wealthy beyond our wildest dreams (i.e. then I could afford the Sears' hibachi instead of the K-Mart version). Incidentally, the 1989 "Intro to RT Course Notes" included the book and some additional notes. The notes included reprints of classic articles, the code for the SPD package (God forbid that anyone have to type it in, though), and an article I whipped off called "Tracing Tricks", which I'll post sometime soon, maybe during a slow month. Some bugs have already been reported to me about my section, so I'll pass them on: From Tim O'Connor: If you'll flip to page 66 you'll note a little algorithm for ray/box testing. About halfway through you say: If T1 > Tnear, set T1 = Tnear If T2 > Tfar, set T2 = Tfar Then you never use T1, or T2 again in that loop. The example bears out my suspicion that one should actually "set Tnear = T1" and "set Tfar = T2". From Ehood Baratz <{world}!hpbbn!hputlaa!ehood>: In chapter 2 page 52 on formula (C9) it is written: If Pn * Rd < 0 (in other words, if Vd > 0) then .... I think it should be "if Vd < 0" because Pn*Rd is Vd (look at page 51 after (C4)). ------------------------------------------------------------------------------- _Graphics Gems_ Call for Contributions, by Andrew Glassner CONTRIBUTE TO A NEW BOOK FOR COMPUTER GRAPHICS PROGRAMMERS! Contributions are solicited for a new book, tentatively titled GRAPHICS GEMS. This book will be a collection of short notes by and for computer graphics programmers and researchers. The basic idea is to create a book similar to the CRC Mathematics Handbook, only tailored to the subject of computer graphics. The motivation for Graphics Gems comes from a desire to document and share the many techniques that are a necessary part of every graphics programmer's toolbox, yet don't appear in the standard literature. Each Gem represents a solution to a problem: not necessarily a research result, nor even a deep observation, but simply a good, practical technique for dealing with a typical computer graphics programming problem. A typical Gem may be a code fragment, a short analysis of an interesting problem, a bit of mathematics, a data structure, or a geometric relationship. Here are some appropriate topics for Gems - this list contains only a few suggestions for topics that might be covered by interesting Gems, and is far from complete: Two Dimensions: Fill, smooth, blur, dither, 2d plots, line drawing, curve drawing, bounding boxes, overlapping boxes, efficient bitblit (example: automatic selection of tick marks on a plot). Three Dimensions: Scan conversion, highlight detection, shading, isosurfaces, ray intersection, form factor calculation, visibility, texturing, transformations, deformations, smoothing, 3d plotting, parameterizations, surface subdivision, texturing functions, bounding boxes (example: fast shading formulae). Graphics: Colormap hacking, object manipulations, sampling, filtering, optics, interaction techniques, modelling primitives, efficient rendering, edge detection (example: reconstruction from stochastic sampling). General Math: Algebra, calculus, geometry (e.g. why normals don't move under the same transformations as surfaces). Programming: Numerical integration, root finding, root polishing, data structures (objects), data structures (programs), inner loops, interactive debugging, graphical debugging, color map hacking, over- and under-flow detection and correction, unusual functions (e.g. polynomial root-finding). Most Gems will be about 1 or 2 final printed pages (4 or 5 pages of typewritten, double-spaced manuscript), though if you choose to include source code the listings may run longer. Rough figures and equations will be professionally redrawn by the publisher. Each contributor will have a chance to review the final copy for his or her Gems before publication. Each Gem will be clearly identified with the name and affiliation of its contributor(s). If you have developed a nice solution to a problem that others might encounter, be it a data structure, an inner loop, or even an algebraic simplification that makes your programs shorter and more robust, then it would probably make a splendid Graphics Gem. Write it up and send it to the editor at the address below, either in hardcopy or electronic mail. Acceptable formats are plain text, nroff, TeX, MacWrite, and Microsoft Word (Macintosh). I would like to receive a rough draft of all Gems by November 1989. Contribute and share your favorite tricks and techniques with the rest of the community! Send your Graphics Gems to: Andrew Glassner Editor, Graphics Gems Xerox PARC 3333 Coyote Hill Road Palo Alto, CA 94304 USA email: glassner.pa@xerox.com phone: (415) 494 - 4467 ------------------------------------------------------------------------------- New People and Address Changes There were many new people at the roundtable at SIGGRAPH. In the interest of brevity, only new people who've sent an intro are listed. If any of you (or anyone else out there) would like to send in a paragraph or two of introduction, it will be printed here. You can always request the latest contact list from me. -------- We just received the 7 editions of "The Ray Tracing News" you posted recently at USENET. This is exactly the kind of information we need in our research project an rendering software. Not just the latest research news, but also discussion on the results of them. So PLEASE put us on your mailing list! Just let me describe our past and future work to justify the costs for you. We are a working group at the Institute for Interactive Graphic Systems at the University of Tuebingen (West Germany) and are part of the faculty of physics. The main future research aspect will go in direction of combining raytracing and radiosity. We come from the background of geometric modelling and graphics hardware (here Phong shading in realtime). I will start working on this project 4Q89 as my PhD. If you can give any additional information that might be interesting to us (including other research going on in this area) please let us know. Surface mail: Wilhelm-Schickard-Institut fuer Informatik Graphisch Interaktive Systeme z.Hd. Philipp Slusallek Auf der Morgenstelle 10 D-7400 Tuebingen Email : philipp@infotue.uucp Tel : x49 7071 296356 -------- (internet) zmel02@trc.amoco.com (usenet) uunet!apctrc!mlee (snail mail) Mark Lee Amoco Production Company Tulsa Research Center PO Box 3385 Tulsa, OK 74102 (phone) (918)-660-3556 or (918)-660-3000 for operator A short introduction. My interests lie in the areas of illumination models, faster ray tracing, photorealism, numerical and statistical methods. My real work is more in the area of rendering algorithms and scientific visualization. The areas that I enjoy working in, I pursue whenever I can squeeze it in. Incidentally, did you find a copy of the article by Levner, Tassinari, and Marini, "A Simple Method for Ray Tracing Bicubic Surfaces"? [no] Is this in a textbook or such? How could I find of copy of this paper? [Can anyone help? Has anyone seen it, and can at least summarize?] Some questions to post to the mailing list... Did the paper "The Ray Tracing Kernel" by Jim Arvo, Dave Kirk and Olin Lathrop ever get published? Does anyone have a copy of Blinn's notes from the Siggraph '84 tutorial notes on "The Mathematics of Computer Graphics" that they could send to me? [hey, I'd like one, too: I was a student volunteer at this course, and they ran out of course notes and I never got a copy.] -------- I am now doing a dissertation on realistic rendering for complex scenes, with extensions for nonisotropically scattering gasses. I am also part of a project that uses raytracing for visualization of volumes of scalar data. Peter Shirley University of Illinois at Urbana-Champaign shirley@cs.uiuc.edu {pur-ee,convex,inhp4}!uiucdcs!shirley 816 E. Oakland, #206 Urbana, IL 61801 (217) 328-6494 -------- Mike Sweeney - rendering, splines, object-oriented languages Softimage Inc. 3510 Blvd St. Laurent, Suite 214 Montreal, Canada H2X 2V2 (514) 845-1636 [write to Kaveh Kardan at larry.mcrcim.mcgill.edu!vedge!kaveh to reach Mike] Hello net-land, it's been a while. Eric says he wants an introduction so here goes.... I've been writing renderers for the last 6 years. The Waterloo CGL Raytracing Package was your basic naive ray tracer. It did contain an iterative solution to ray/bspline intersection, but I no longer believe in this approach - it's much faster to break the spline into triangles. My second attempt, the Alias renderer, war a raycaster. It was slow period. Then came Abel, where I started playing with octrees. The code was about twice as fast as any implementation of Kay/Kajiya slabs I could come up with, and at least ten times as fast as my implementation of Fujimoto's algorithm. After Abel folded, I wound up at Softimage. I added a modified Watkin's front end, and rewrote the tracer to make the maximum use of empty space. I've not tried to implement the Kirk/Arvo algorithm yet, but have an instinctive distrust of anything that mixes preprocessing with the rendering (the cost will go up with the sampling rate). What is the group's experience with this method? -------- # Jerry Quinn - PhD research in raytracing at Dartmouth # Dartmouth College # Department of Math & Comp Sci # Hanover, NH 03755 # (603) 646-2565 quinn@sunapee.dartmouth.edu I am a PhD student in computer science at Dartmouth and am in my second year. I'm currently interested in increasing efficiency in raytracing. I'm also looking at parallelism in RT, radiosity, and the combination of both. -------- I have taken a job at Princeton, and thought I'd send you my new address for the purposes of the RT News. Mark VandeWettering (markv@acm.princeton.edu) c/o Program in Applied and Computational Math Fine Hall Princeton University, Princeton NJ, 08544 Another question you might know off the top of your head: Alvy Ray Smith has written a tech memo on Volumetric Rendering at Pixar. Do you have his e-mail address, or otherwise know how I might request Pixar Tech Memos? [does anyone else know? - EAH] The ray tracing archive on skinner.cs.uoregon.edu still will remain there. I have permission from the higher-ups at the U of O to keep it there. If I lose that permissions at some future date, it will probably move to Princeton somewhere.... -------- Pat Hanrahan has also moved to Princeton, and is now at: hanrahan@princeton.edu -------- And one more for Princeton: alias marshall_levine mplevine@phoenix.princeton.edu [I asked about the ray tracing demo at SGI:] The ray-tracing demo that you saw on an IRIS at SIGGraph is called Flyray. It was written by Benjamin Garlick in June-August 1988. The underlying voxel ray-tracer was written by Paul Haeberli in July 1983. The demo is standard around here; it should be on every demo machine. I would guess that it would be in the /usr/src/cmd/demo directory on most demo machines, but it depends on that particular machine's configuration. It is easily accessible through Buttonfly, the SGI menu program. Buttonfly displays menus of demos on 3D buttons that twist, flip, and fly towards the screen when selected (with text on them!). You will probably find Flyray on Buttonfly under the SGI/CPU-Intensive button (it will be listed as Ray-Tracer or Flyray). If you have any questions or want a description of the demo, just let me know and I'll send you any information that I can dig up. While you're at SIGGraph, you should take a look at the newest version of Flight (By Rob Mace, one of the guys in my group) on the IRIS 4D computers. Take a look at the F-14. I'll let it be a surprise, and trust me, you'll be very surprised! -------- Please change my email address to palmer@ncsc.org (was palmer@ncifcrf.gov). Thomas C. Palmer North Carolina Supercomputing Center Cray Research, Inc. Phone: (919) 248-1117 PO Box 12732 Arpanet: palmer@ncsc.org 3021 Cornwallis Road Research Triangle Park, NC 27709 -------- Another address change: # Mark Reichert # Program of Computer Graphics # 120 Rand Hall # Cornell University # Ithaca, NY 14853 alias mark_reichert mcr@venus.graphics.cornell.edu ------------------------------------------------------------------------------- Bugs in MTV's Ray Tracer, by Eric Haines Craig Kolb mentioned that he was having problems with Mark VandeWettering's ray tracer. Since I've been touting it all this time (but having run it only once), I felt obligated to find the bugs. There were two: one was that the up vector was sometimes not perpendicular to the view vector, which results in the "balls" image having a "comin' at ya" kind of distortion (kind of interesting, but incorrect). The other was that the frustum width was affected by the distance to the hither, which it should not be. One result is that the "mountain" scene would get zoomed in on something fierce. Finally, I changed the statistics output a bit to give information that I like (e.g. the number of reflected and refracted rays actually shot are counted separately). Anyway, at least apply the fixes to main.c and the first part of screen.c. diff old/main.c new/main.c 109c112 < printf("number of rays cast: %-6d\n", nRays); --- > printf("number of eye rays: %-6d\n", nRays); diff old/screen.c new/screen.c 50d49 < VecNormalize(upvec) ; 66a66,72 > * Make sure the up vector is perpendicular to the view vector > */ > > VecCross(viewvec, leftvec, upvec); > VecNormalize(upvec); > > /* 71c77 < frustrumwidth = (view -> view_dist) * ((Flt) tan(view -> view_angle)) ; --- > frustrumwidth = ((Flt) tan(view -> view_angle)) ; 129c135 < Trace(0, 1.0, &ray, color); --- > Trace(0, 1.0, &ray, color, &nRays); 173c179 < Trace(0, 1.0, &ray, color); --- > Trace(0, 1.0, &ray, color, &nRays); 238c244 < Trace(0, 1.0, &ray, color); --- > Trace(0, 1.0, &ray, color, &nRays); diff old/shade.c new/shade.c 112d111 < nReflected ++ ; 115c114,115 < Trace(level + 1, surf -> surf_ks * weight, &tray, tcol); --- > Trace(level + 1, surf -> surf_ks * weight, &tray, tcol, > &nReflected); 120d119 < nRefracted ++ ; 125c124,125 < Trace(level + 1, surf -> surf_kt * weight, &tray, tcol) ; --- > Trace(level + 1, surf -> surf_kt * weight, &tray, tcol, > &nRefracted) ; diff old/trace.c new/trace.c 19c19 < Trace(level, weight, ray, color) --- > Trace(level, weight, ray, color, nr) 23a24 > int *nr ; 34c35 < nRays ++ ; --- > (*nr) ++ ; ------------------------------------------------------------------------------- Bug in SPD, from Pete Segal Pete Segal reported a particularly subtle bug in my Standard Procedural Databases package. Turns out a "w" component needs to be initialized. If you have a machine that initializes everything to 0, you'd never notice it. The patches to the README and lib.c files are below. I should be putting the latest and greatest version on cs.uoregon.edu soon. diff old/README new/README 4,5c4,5 < Version 2.5, as of 10/19/88 < address: 3D/Eye, Inc., 410 East Upland Road, Ithaca, NY 14850 --- > Version 2.6, as of 8/28/89 > address: 3D/Eye, Inc., 2359 N. Triphammer Rd, Ithaca, NY 14850 22a23,24 > Version 2.6 released August, 1989 - lib_output_cylcone fix (start_norm.w was > not initialized). 68a71,72 > > The SPD package is also available via anonymous FTP from cs.uoregon.edu. diff old/lib.c new/lib.c 5c5 < * Version: 2.2 (11/17/87) --- > * Version: 2.6 (8/28/89) 437a438 > start_norm.w = 0.0 ; ------------------------------------------------------------------------------- Solid Textures Tidbit, by Roman Kuchkuda One piece of research that you might mention in RTN: I had used procedural wood textures for a while and wondered whether you could use "real" wood textures. Through some connections at the UNC hospital I had a block of pine CT scanned. Sure enough, the grain showed up very well. The resulting pictures were more "interesting" than procedural texture. The structure is more complex than the procedural model. There were a few problems though: 1) There is a lot of data in the CT scans and memory paging slows down the ray tracing like crazy. 2) Reality doesn't look nearly as "real" as a neat clean procedural model of it does. The results were so mixed that I never tried to get this published anywhere. ------------------------------------------------------------------------------- Sundry Comments, by Jeff Goldsmith About the ray-tracing-as-a-sleazy-sales-gimmick idea: The whole point about my suggestion to include a ray tracer as part of a CG system is that it is, in fact, mostly useless, and most buyers don't know that. Thus, it works as a great gimmick, which is exactly "promising someone something that they think they want, but don't really." No one will use it after finding out how long it takes, so it doesn't have to have as many features as the rest of the system. Yes, this is a very cynical view, but sales is a non-technical problem, and (at least around here) expensive systems are usually purchased by people who know nothing about them, so it ought to be an effective technique with not a whole lot of resource expenditure. Besides, most CG programmers enjoy hacking ray tracers so you boost morale at the company at the same time. ...by the way, this is not entirely a joke, but... Euclidean distance calculation: Iterative approaches work great on this problem. A short summary (and code for one) is in Tom Duff's SIGGRAPH '84 Tutorial on Numerical Analysis (a terrific article, by the way, as is his spline piece in the same place) most of which he got from Moler and Morrison's "Replacing Square Roots by Pythagorean Sums" IBM Journal of Research and Development, 27/6, Nov. 1983. The method he describes has cubic convergence, so it works well to unroll the loop and do a set number of iterations. 4 iterations (2/, 4*, 2+) yield 62 digits of precision. ------------------------------------------------------------------------------- Texture Mapping Question, by Susan Spach What are good techniques for implementing texture mapping within raytracing? Is point sampling with a good sampling strategy most commonly used? Has mipmapping been extended to secondary rays? [I'm interested, too] ======== USENET cullings follow =============================================== Ray Traced Image Files, Prem Subramanyan Reply-To: prem@geomag.UUCP (Prem Subramanyan) Organization: Florida State University Computing Center We have quite a collection of rasterfiles of all sizes here at geomag. You can use the fbm package by Michael Mauldin to convert from Sun rasterfiles to GIF files. The main reason why I have chosen to keep them as rasterfiles, rather than convert them to GIF is that on the Sun the rasterfile viewers are neater. In any case. anonymous ftp to geomag.gly.fsu.edu (128.186.10.2) cd to pub/pics and download any pics you want. In the future, once I get the latest fbm package, I will post it there as well. We have a good collection of files ray-traced on the eta-10g with QRT by Steve Koren. The longest time taken (for blue.rst.Z) was 1 1/2 hrs. The small ones (640x400) went in usually under 15 minutes. In any case, they are quite interesting. ------------------------------------------------------------------------------- Image Collection, by Paul Raveling From: raveling@venera.isi.edu (Paul Raveling) Organization: USC-Information Sciences Institute With gobs of satisfaction, I'd like to announce the addition of some pictures of my own to the "Img" collection available on venera.isi.edu. Along with this go sincere thanks to Nic Lyons and HPLabs for the opportunity to digitize these photos. venera's pub directory now contains 2 compressed files to facilitate retrieval of images in this collection and of the imglib code. These are: pub/img_ls-RAlF.Z Directory listing of everything in the [~ftp/] images hierarchy pub/img.tar.Z Code for imglib and the various simple programs using it. The "root" directory, [~ftp/]images, and each of the four subdirectories containing images has its own README file with additional info. Credits for 2 images that weren't from my own pictures are: Window Rock: My wife spotted and captured the natural spiral pattern at Window Rock, Arizona. Solings: This is from the 1982 International Soling Association calendar. I used to own and race one of these, but wouldn't risk taking a camera aboard. Here's a subject summary of the new images in images/color_mapped: aspens Aspens in San Juan Mts, between Ouray & Silverton blue_tigers Blue Angels, in F11F Tigers ds_train Durango & Silverton narrow-gauge train elk An elk in Banff National Park ghost_house House in ghost town, somewhere between Ouray and Silverton graycard Kodak gray card, grayscale, and color patches halfdome Halfdome in polarized infrared light (Yosemite Nat'l Park) harvey Harvey, an African lion who lived at the L.A. Zoo high_line Durango & Silverton narrow gauge train on the high line model Model at one of Frank's photo day shows, probably in 1978 model_fullscale Model at one of Frank's photo day shows, probably in 1978 old497 Old 497: One of Durango & Silverton's narrow gauge steamers porcupine Porcupine @ ranger cabin, Mosquito Flats, Banff puff1 - puff2 Puff (the cat, not the dragon) san_juans San Juan Mountains, between Ouray and Silverton smurf1 - smurf4 Whitesmith, aka "The Smurf" [another cat] snake Non-digital snake (not an adder) solings Solings, from 1982 International Soling Association calendar stream Stream in San Juan Mountains, between Ouray and Silverton tbirds Thunderbirds window_rock Window Rock x-1e X-1E at NASA Ames Dryden Flight Research Center, Edwards AFB ------------------------------------------------------------------------------- MTV-Raytracer on ATARI ST - precision error report, by Dan Riley From: riley@batcomputer.tn.cornell.edu (Daniel S. Riley) Organization: Cornell Theory Center, Cornell University, Ithaca NY In article <1171@laura.UUCP> wagener@unidocv.UUCP (Roland Wagener) writes: >I have ported the MTV-Raytracer on the ATARI ST using the Turbo-C- >Compiler. The Program works fine and it uses about 3 hours CPU-Time >to create the Balls-Picture in 320x200 Resolution. >But there is a bug somewhere in the program. There are white spots in >all reflecting surfaces. This bug does not appear on a IBM-PC programmed >with Zortech-C++. But the PC needs 5 hours for a 200x200-Picture ... This sounds like a floating point precision problem. I've been playing with a number of ray tracers, including MTV, on my Amiga. I've seen white spots and other sorts of splotches if I use the Motorola ffp format floating point routines, which are single precision (32 bit) only. They go away if I use IEEE math libraries (all calculations done with 64 bit doubles). 3 hours cpu for a 320x200 picture on an 8 MHz 68000 sounds like single precision to me, but I don't know the ST or Turbo-C that well. I suppose there must be papers on controlling round-off errors in ray tracing algorithms, but none of the ray-tracers I've seen make any special efforts in that regard. Of course, all the ones I have source code to are meant to be clean and simple, not fast and convoluted...:-) -Dan Riley (riley@tcgould.tn.cornell.edu, cornell!batcomputer!riley) -Wilson Lab, Cornell U. ------------------------------------------------------------------------------- Question on Ray Tracing Bicubic Parametric Patches, by Robert Minsk From: ccoprrm@pyr.gatech.edu.UUCP (Robert E. Minsk) Organization: Georgia Institute of Technology Does anyone have a routine of know of any pointers to articles to find a intersection between a ray and a bicubic parametric patch besides a recursive subdivision algorithm? I am trying to speed things up a bit in my ray tracer. ------------------------------------------------------------------------------- END OF RTNEWS