"Light Makes Right"
June 21, 1989
Volume 2, Number 4
Compiled by
All contents are copyright (c) 1989, all rights reserved by the individual authors
Archive locations: anonymous FTP at
ftp://ftp-graphics.stanford.edu/pub/Graphics/RTNews/,
wuarchive.wustl.edu:/graphics/graphics/RTNews, and many others.
You may also want to check out the Ray Tracing News issue guide and the ray tracing FAQ.
eye!erich@wrath.cs.cornell.edu
This is a lot more direct than hopping the HP network through Palo Alto and Colorado just to get to Ithaca. We have the connection courtesy of the Computer Science Dept at Cornell, and they have asked us to try to keep our traffic down. So, please don't be a funny guy and send me image files or somesuch.
I just noticed that Andrew and I are out of sync: his hardcopy version is on Volume 4, and I'm on Volume 3. One excuse is that the first year of the email edition is labeled "Volume 0", since it wasn't even called "The Ray Tracing News" at that point. An alternate excuse is that I program in "C", and so start from 0. Anyway, until maybe the new year, I'll stick with the current scheme (hey, no one even noticed that last issue was misnumbered (and corrected on the USENET copy)).
back to contents
The latest issue of the hardcopy Ray Tracing News (Volume 3, Number 1, May 1989) goes into the mail today, 31 May. Everyone who is on the softcopy mailing list should receive a copy. If you don't get a copy in a week or two, please let me know (glassner.pa@xerox.com). It would help if you include your physical mailing address, so I can at least confirm that your issue was intended to go to the right place.
Contributions are now being solicited for Vol. 4, No. 2. Start working on those articles!
back to contents
____________
Stuart Green - multiprocessor systems for realistic image synthesis Department of Computer Science University of Bristol Queen's Building University Walk Bristol. BS8 1TR ENGLAND. green@uk.ac.bristol.compsci
I am working on multiprocessor implementations of algorithms for realistic image synthesis. So far, this has been restricted to straightforward ray tracing, but I hope to look at enhanced ray tracing algorithms and radiosity. I've implemented a ray tracer on a network of Inmos Transputers which uses mechanisms for distributing both computation and the model data amongst the processors in a distributed memory MIMD system.
____________
Craig Kolb (and Ken Musgrave)
My primary interests include modeling natural phenomena, realistic image synthesis, and animation.
I can be reached at: Dept. of Mathematics Yale University P.O. Box 2155 Yale Station New Haven, CT 06520-2155 (203) 432-7053
alias craig_kolb craig@weedeater.math.yale.edu alias ken_musgrave musgrave-forest@yale.edu
...I've just started looking into ray/spline intersection. We do a lot of heightfield-tracing 'round here, and in the past have rendered them using a triangle tessellation. I'm giving splines a shot in order to render some pictures of eroded terrain for our SIGGRAPH talk. I notice that you list spline intersection among your primary interests. What sort of methods have you investigated? At the moment I've implemented (what I assume is) the standard Newton's method in tandem with a DDA-based cell traversal scheme (as per our SIGGRAPH paper). Although this works, it's not exactly blindingly fast... Do you know of any 'interesting' references?
____________
Kaveh Kardan Visual Edge Software Ltd. 3870 Cote Vertu Montreal, Quebec H4R 1V4 (514)332-6430 larry.mcrim.mcgill.edu!vedge!kaveh
I graduated with a BS in Math from MIT in 1985, did some work in molecular graphics at the Xerox Research Centre of Canada (XRCC), wrote the renderer at Neo-Visuals (now known as SAS Canada) -- which included a raytracer --, and the animation stuff at Softimage. I'm currently working at Visual Edge on the UIMX package: an X Windows user interface design system.
Regarding the Softimage raytracer: it was written by Mike Sweeney (who used to be at Abel, and who did "Crater Lake" at Waterloo).
I will also be acting as a mail forwarder for Mike, as Softimage is not on any networks. So in effect, you should probably include Mike in the mailing list as well, with my address -- or somehow let people know that he can be reached tc/o me.
If I may make some comments about the stuff I have read so far in the back issues:
====================
Jeff Goldsmith writes:
> 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.
back to contents
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]
back to contents
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.
back to contents
======== USENET cullings follow =================
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...
back to contents
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
back to contents
Newsgroups: comp.graphics 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 (ofer@gandalf.berkeley.edu) 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
back to contents
Newsgroups: comp.graphics 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.
back to contents
Newsgroups: comp.graphics 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.
back to contents
Newsgroups: comp.graphics 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 <math.h> #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<s2?s1:s2;}main(){D z,zz;int i,ii;F(A(y ,0);y<24;y-=listen(3,0)){F(x-=x;x<40;x++){F(z=!close(y+3),A(i,0);i<*m*(y>-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");}}
back to contents
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.]
back to contents