Ray Tracing News

"Light Makes Right"

June 21, 1989

Volume 2, Number 4

Compiled by Eric Haines erich@acm.org . Opinions expressed are mine.

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.


Contents:

========Net News Cullings========

Introduction

First off, please note that I now have a second mail address:

        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


Hardcopy News

by Andrew Glassner

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


New (and Used?) People ----------------------

The Cornell Program of Computer Graphics computers have all changed their addresses. Any computer with the name "*.tn.cornell.edu" is now "*.graphics.cornell.edu".

____________

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


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]

back to contents


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.

back to contents

======== USENET cullings follow =================

Query: Dataflow architectures and Ray Tracing, by George Kyriazis (kyriazis@rpics)

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


Re: Pixar's noise function, by Jon Buller (bullerj@handel.colostate.edu.UUCP)

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


Re: DBW_render for SUN 3 ? by Tad Guy (tadguy@cs.odu.edu)

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


Re: Steel Colors, by Eugene Miya (eugene@eos.UUCP)

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


Dirty Little Tricks, by Jack Ritter (ritter@versatc.UUCP)

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


Obfuscated Ray Tracer, by George Kyriazis (kyriazis@turing.cs.rpi.edu)

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


Contents of FTP archives, skinner.cs.uoregon.edu, by Mark VandeWettering (markv@tillamook.cs.uoregon.edu)

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


Eric Haines / erich@acm.org