Ray Tracing News

"Light Makes Right"

January 6, 1989

Volume 2, Number 1

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

All contents are copyright (c) 1988,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:


Introduction

Well, this has been a busy time around here. First of all, note my change of address (it's in the header). We've moved to a larger building with much better environmental controls (i.e. we don't have to cool the machines in the winter by opening the windows). In the meantime I've been trying to actually finish a product and maybe even make some money from it. There's also those SIGGRAPH deadlines on January 10th.... Busy times, so excuse the long delay in getting this issue out.

The other great struggle has been to try to get my new Cornell account to talk with the outside world. DEC's EUNICE operating system has foiled me so far, so this issue is being distributed by Michael Cohen, who's now at the University of Utah. Many thanks, Michael.

Due to the length between issues, my cullings from USENET have accumulated into an enormous amount of material. As such, the condensed version of these will be split between this and the next issue. This issue contains what I felt was the best of the supersampling discussion. If this material is old hat, please write and tell us of your experiences with supersampling: what algorithm do you use? are you satisfied with it? what kind of filtering is used, and what are your subdivision criteria?

This issue is the first one that has a "Volume X, Number Y" in the header. This has been added partly for ease of reference, but also (more importantly) for avoiding dropouts. If you get "Number 1", then "Number 3", you know you've missed something (probably due to email failure). At the end of this issue is a list of all the past issues. If you are missing any, please write and I'll send them on.

back to contents


New Members

From: David Jevans (hpfcla!jevans@cpsc.UCalgary.CA)

I can be reached at the U of Calgary. I work days at Jade Simulations International, ph # 403-282-5711.

My interests in ray tracing are in multi-process (networks of SUNS, BBN Butterfly, and Transputers) ray tracing, space subdivision, and ray tracing functionally defined iso-surfaces.

I am working on optimistic multi-processor ray tracing and combining adaptive and voxel spatial subdivision techniques. I have implemented a parallel ray tracer on the University of Calgary's BBN Butterfly. My ray tracers handle a variety of object types including polygons, spline surfaces, and functionally defined iso-surfaces. My latest projects are using TimeWarp to speed up multi-processor ray tracing, adding a texture language, frame coherence for ray tracing animation, and developing the ray tracing answer to radiosity.

David Jevans, U of Calgary Computer Science, Calgary AB T2N 1N4 Canada uucp: ...{ubc-cs,utai,alberta}!calgary!jevans

________

# Subrata Dasgupta - raycasting of free-form surfaces, surface representations
# Duke University
# Dept. of Computer Science
# Durham, NC 27706
# (919)-684-5110
alias subrata_dasgupta sdg@cs.duke.edu

I am relatively new the field of ray tracing. I am involved in the design of a raycasting system based on the original design by Gershon Kedem and John Ellis [Proc. 1984 Int'l conference on Computer Design]. The original design uses Constructive Solid Geometry for building up a complex object out of simple primitives like cones, cylinders, and spheres. The main drawback of such a system is that representing an object with cubic or higher order surfaces require numerous quadratic primitives and even then is at best an approximation to the original surface.

The raycasting machine uses an array of parallel rays and intersects them with primitives. The applications of such a machine are potentially large like: modeling surfaces for NC machines, calculating volume and moment of inertia, finding fast surface intersections, to name just a few. At present there are 2 working models of the raycasting machine, one of which is in the Dept. of Mechanical Engg. at Cornell. The other one is our experimental m/c which is located at the U. of N. Carolina at Chapel Hill (The operative word in this sentence is "located" :-) ). Although my input may not be very frequent at the beginning I will be an avid reader of the raycasting news. Thanks for inviting me in.

________

From: Darwin G. Thielman (hpfcla!thielman@cs.duke.edu)
Subject: Duke ray casting group

# Darwin Thielman - Writing software to control the raycasting machine at Duke
# Duke University
# Computer Science Dept.
# Durham, NC. 27706
# (919) 684-3048 x246
alias darwin_thielman thielman@duke.cs.duke.edu

At Duke we have designed a system that does ray casting on many primitives in parallel. This is achieved with 2 types of processors, a primitive classifier (PC) and a combine classifier (CC). The PC's solve systems of quadratic equations and the CC's combine these results.

I am the system software person, I am writing micro code for an Adage 3000 machine. The micro code is responsible for controlling the ray casting board and creating images from the output of the board.

In addition the following people also work on the ray casting system at Duke.

Gershon Kedem
John Ellis
Subrata Dasgupta
Jack Briner
Ricardo Pantazis
Sanjay Vishin

Also at UNC Chapel Hill there is a eng. who is working on the hardware design of the system he is Tom Lyerly.

Since I do not want to attempt to explain what each one of these people is doing (with the possibility of getting it wrong) I will not try. All of the above people will have access to the RTN and if any of them are interested they may respond. Also If anyone want to get a hold of any of them just send me a message and I will forward it to the proper person.

We also have one of our boards at Cornell, there is a group there that is working on solid modeling, and hopes to use our hardware. If you want you can contact Rich Marisa (607) 255-7636 for more information on what they are doing. His mail address is marisa@oak.cadif.cornell.edu. Also I have talked to him and if you want to see a demo of our system he would be glad to show it to you.

If you have any questions or comments please feel free to contact me.

                                        Darwin Thielman

________

From: Steven Stadnicki (hpfcla!stadnism@clutx.clarkson.edu)

Steven Stadnicki - shadowing from reflected light sources, tracing atomic orbitals, massively parallel ray tracing 212 Reynolds Dormitory Clarkson University Potsdam, NY 13676 (315) 268-4079 stadnism@clutx.clarkson.edu

Right now, I'm working on writing a simple ray tracer to implement my reflected shadowing model (see the E-mail version of RTNews, Nov. 4), and then I'll be trying a few texture models. (Texture mapping on to atoms... the marble P-orbital!)

________

From: hpfcla!sunrock!kodak!supra!reichert@Sun.COM (Mark Reichert x25948) Subject: RT News intro

#
# Mark Reichert - diffuse interreflections
# Work:
# Eastman Kodak Company
# Advanced Systems Group
# Building 69
# Rochester, NY 14650
# 716-722-5948
#
# Home:
# 45 Clay Ave.
# Rochester, NY 14613
# 716-647-6025
#
I am currently interested in global illumination simulation using ray
tracing with auxiliary data structures for holding illuminance values.

I am also interested in ray tracing from the lights into the environment - maybe just a few bounces, then storing illuminance as above.

What I would really like is a ray tracer (or whatever) that would do a nice job of modeling triangular glass prisms.

alias mark_reichert hpfcrs!hpfcla!hplabs!sun!sunrock!kodak!supra!reichert

back to contents


Multiprocessor Visualization of Parametric Surfaces

From: Markku Tamminen (hpfcla!mit%hutcs.hut.fi@CUNYVM.CUNY.EDU)

I obtained the Ray-Tracing News from Panu Rekola, and sent the message below to some people on your distribution list interested in related matters.

I have done research in geometric data structures and algorithms in 1981-84. A practical result was the EXCELL spatial index (like an octree with binary subdivision, together with a directory allowing access by address computation).

My present interests are described below.

Charles Woodward has developed a new and efficient method for ray-tracing parametric surfaces using subdivision for finding the ray/patch intersection.

============================================================================

I am putting together a project proposal with the abstract below. I would be interested in obtaining references to any new work you have done in ray-tracing and hardware, and later in an exchange of ideas. I will send an acknowledgement to any message I get, so if you don't see one something has gone wrong. (Email has often been very unreliable.)

Looking forward to hearing something from you,

        Markku Tamminen
        Helsinki University of Technology
        Laboratory of Information Processing Science
        02150 ESPOO 15, FINLAND
        Tel: 358-0-4513248 (messages: 4513229, home: 710317)
        Telex: 125161 HTKK SF
        Telefax:        358-0-465077
        ARPANET:        mit%hutcs.uucp%fingate.bitnet@cunyvm.cuny.edu
        INTERNET:       mit@hutcs.hut.fi
        BITNET:         mit%hutcs.uucp@fingate
        UUCP:           mcvax!hutcs!mit

       Multiprocessor visualization of parametric surfaces
                        Project proposal

               Markku Tamminen (mit@hutcs.hut.fi)
               Charles Woodward (cwd@hutcs.hut.fi)
                Helsinki University of Technology
          Laboratory of Information Processing Science
              Otakaari 1 A, SF-02150 Espoo, Finland

ABSTRACT

The proposed research aims at an efficient system architecture and improved algorithms for realistic visualization of complex scenes described by parametric surfaces.

The key components of such a system are a spatial index and a surface patch intersector. For both very efficient uniproces- sor solutions have been developed by the authors at the Hel- sinki University of Technology. However, to obtain sufficient speed, at least the latter should be based on a specialized ar- chitecture.

We propose obtaining a balanced complete system by gradually as- cending what we call a specialization hierarchy. At its bottom are solutions based on multiprocessors or networks of independent computing units (transputers). In this case an important research problem is how to avoid duplicating the data base in the proses- sors. At the top of the hierarchy are specialized processors im- plemented in VLSI.

The research will produce general insight into the possibilities of utilizing concurrency and specialized processors in geometric search and computation.

PREVIOUS WORK

M. Mantyla and M. Tamminen , ``Localized Set Operations for Solid Modeling ,'' Computer Graphics , vol. 17, no. 3, pp. 279-289 , 1983.

M. Tamminen , The EXCELL Method for Efficient Geometric Access to Data , Acta Polytechnica Scandinavica, Ma 34 , 1981.

Markku Tamminen, Olli Karonen , and Martti Mantyla, ``Ray- Casting and Block Model Conversion Using a Spatial Index,'' Computer Aided Design, vol. 16, pp. 203 - 208, 1984.

C. Woodward, ``Skinning Techniques for Interactive B-Spline Surface Interpolation,'' Computer-Aided Design, vol. 20, no. 8, pp. 441-451, 1988.

C. Woodward, ``Ray Tracing Parametric Surfaces By Subdivision in Viewing Plane,'' to Appear in Proc. Theory and Practice of Geometric Modelling, ed. W. Strasser, Springer-Verlag, 1989.

________

[a later message from Markku Tamminen:]

I thought I'd send this summary of responses as feedback, because some answers may not have found their way through the network. I think mit@hutcs.hut.fi might be the safest address to use for me.

Our project has not yet started - I have just applied for funding with the proposal whose abstract I sent to you. Also, I am a software person, but hope to get somebody hardware-oriented involved in the project. We will be using transputers to start with, but so far I have just made some small experiments with them.

Our ray/patch intersection method is based on subdivision. It is a new method developed by Charles Woodward, and quite a bit more efficient than Whitted's original one. However, it takes 3 ms for a complete ray/patch intersection on a SUN4. Thus, we'd like to develop a specialized processor for this task - the algorithm is well suited for that.

Our spatial index is EXCELL, which I originally published in 1981, and whose 3D application was described in SIGGRAPH'83 by Martti Mantyla and me. I have lately tuned it quite a bit for ray-tracing, and we are very satisfied with its performance. (EXCELL uses octree-like, but binary, subdivision. It has a directory, which is an array providing direct access by address computation, and a data part, which corresponds to the leaf cells of an octree. Binary subdivision leads to fewer leaf-cells than 8-way. There is an overflow criterion that decides when subdivision will be discontinued.)

We have obtained best results when we store in the spatial index for each patch the bounding box of its control points, and further cut it with a "slab" defined by two planes parallel to a "mean normal" of the patch. Using this method we have to perform, on the average, less than 2 complete patch/ray intersection tests.

Our method has not been as efficient as that of subdividing the patches to all the way to triangles. However, as much less storage is required, we consider our technique more suited for distributed architectures.

In the proposed project we want to look both into developing a specialized (co)processor for the ray/patch intersection task and into distributing the whole computation on several processors. I think that the most difficult research problem is the partitioning of the data base in a loosely coupled system. In our case the ray/patch intersection task is so time consuming that it would help (to begin with) to keep the ray/database traversal on the workstation and jost distribute the intersection task to other processors.

Some questions:

    Does anybody know of HW work in the ray/patch intersection area; e.g.,
    as a continuation of Pulleyblank & Kapenga's article in CG&A?

    Does anybody know of somebody working with transputers in ray-tracing? (We
    do know of the INMOS ray-tracing demo.)

    How enthusiastic are you about the approach of using digital signal
    processors? What other off-the shelf processors would be specially suited
    as a basis for a ray-tracing coprocessor?

    What would be the specific computation to offload to a coprocessor?

I don't know what more to write now about our project. Below is a short summary of the responses I got:

    From: kyriazis@yy.cicg.rpi.edu (George Kyriazis)

Works with pixel machine, and will transport RPI's ray-tracer to it. Main problem: duplication of code and data.

    From: jeff@CitIago.Bitnet (Jeff Goldsmith)

Has implemented ray-tracer with distributed database on hypercube. Communication between parts of database by RPC. With 128 processors 50% utilization. (Ref: 3rd Hypercube Concurrent Computation Proc.) A proposal to build custom silicon for intersection testing. In this case the rest of the system could reside on a ordinary PC or workstation.

    From: gray@rhea.cray.com (Gray Lorig)

"Your abstract sounds interesting."

    From: Frederik Jansen (JANSEN@ibm.com)

Mike Henderson at Yorktown Heights is working on ray/patch intersection problem (software approach).

    From: Mark VandeWettering (markv@drizzle.cs.uoregon.edu)

"As to HW implementation, my advice is NOT to take the path that I took, but to implement one simple primitive: a bilinear interpolated triangular patch." "Take a look at AT&T's 12 DSP chip raytracing board." Would like to experiment with implementing an accelerator based on Motorola DSP56001.

    From: tim%ducat.caltech.edu@Hamlet.Bitnet (Tim Kay)

"I am interested how fast a *single* general purpose processor can raytrace when it is assisted by a raytracing coprocessor of some sort. there seems to be tremendous potential for adding a small amount of raytracing HW to graphics work stations." "I am quite capable of ray tracing over our TCP/IP network."

    From: priol@tokaido.irisa.fr

"I work on ray-tracing on a MIMD computer like the Hypercube." Partitions scene boundary as suggested by Cleary. To do it well sub-samples image before parallel execution. With 30-40 processors 50% efficiency. Part of work published in Eurographics'88.

    From: toc@wisdom.TN.CORNELL.EDU (Timothy F. O'Connor)

"Abstract sounds interesting. My main interest is in radiosity approach."

    From: Russ Tuck (tuck@cs.unc.edu)

"My work is summarized in hardcopy RTnews vol.2, no. 2, June '88, "Interactive SIMD Ray Tracing."

That's it for now. I hope there has been some interest in this multi-feedback. I'll get more meat of my own in the messages when our new work starts.

Thanks to you all! / Markku

back to contents


Miscellany

From: hpfcla!subramn@cs.utexas.edu
Subject: Ray Tracing articles.

I would like you to bring this to the attention of the RT news group (if you consider it appropriate).

There are lots of conference proceedings and journals other than SIGGRAPH & CG&A which contain ray tracing articles. At least, here, at our university we don't get all those journals (for example, the Visual Computer) due to budget constraints. It would be nice for someone to post relevant articles on ray tracing so that all of us will be aware of the work going on in ray tracing every where. For instance, I have found several articles in the Visual Computer that were relevant to what I was doing after being pointed at by someone else. If these can be listed by someone who gets these journals, then it would make it easier to get access to these articles.

K.R.Subramanian
Dept. of Computer Sciences
The University of Texas at Austin
Austin, Tx-78712.
subramn@cs.utexas.edu
{uunet}!cs.utexas.edu!subramn

________

[My two cents: we don't get "Visual Computer" around here, either. I've been helping to keep Paul Heckbert's "Ray Tracing Bibliography" up to date and would like to obtain relevant references (preferably in REFER format) for next year's copy for use in SIGGRAPH course notes. See SIGGRAPH '88 notes from the "Introduction to Ray Tracing" course for the current version to see the state of our reference list. - Eric]

________________________________________

From: "David F. Rogers" (hpfcla!dfr@USNA.MIL)
Subject:  Transforming normals

Was skimming the back issues of the RT News and your memo on transforming normals caught my eye. Another way of looking at the problem is to recall that a polygonal volume is made up of planes that divide space into two parts. The columns of the volume matrix are formed from the coefficients of the plane equations. Transforming a volume matrix requires that you premultiply by the inverse of the manipulation matrix. The components of a normal are the first three coefficients of the plane equation. Hence the same idea should apply. (see PECG Sec. 4-3 on Robert's algorithm pp 211-213). Surprising what you can learn from Roberts' algorithm yet most people discount it.

________________________________________

>From: stadnism@clutx.clarkson.edu (Steven Stadnicki,212 Reynolds,2684079,5186432664)
Subject: Some new thoughts on how to do caustics, mirrored reflection, etc.
[source: comp.graphics]

Here's a new idea I came up with to do caustics, etc. by ray tracing: from your point on some surface, shoot out some number (say ~100) in "random" directions (I would probably use a jittered uniform distribution on the sphere). For each light source, keep track of all rays that come within some "distance" (some angle) from the light source. Then, for each of these rays, try getting closer to the light source using some sort of Newton-type iteration method... for example, to do mirrored reflection:

           \|/
           -o-   Light source
           /|\
                               |
                +---+          | M
                | O |          | i
                | b |          | r
                | j |          | r
                | e |          | o
                | c |          | r
                | t |          |
----------------+---+--X-------+

>From point X, shoot out rays in the ~100 "random" directions mentioned above;
say one of them comes within 0.05 radians of the light source. Do some sort of
update procedure on the ray to see if it keeps getting closer to the light
source; if it does, then you have a solution to the "mirrored reflection"
problem, and you can shade X properly. This procedure will work for curved
mirrors as well as planar ones (unlike the previous idea I mentioned), and will
also handle caustics well. It seems obvious to me that there will be bad cases
for the method, and it is certainly computationally expensive, but it looks
like a useful method. Any comments?

                                         Steven Stadnicki
                                         Clarkson University
                                         stadnism@clutx.clarkson.edu
                                         stadnism@clutx.bitnet

________________________________________

>From: jms@antares.UUCP (joe smith)
Organization: Tymnet QSATS, San Jose CA
Subject: Re: Ray Tracing Novice Needs Your Help
[source: comp.graphics]

In article (2399@ssc-vax.UUCP) dmg@ssc-vax.UUCP (David Geary) writes:
> What I'd really like is to have the source in C to a *simple*
>ray-tracer - one that I could port to my Amiga without too much
>difficulty.
>~ David Geary, Boeing Aerospace, ~

My standard answer to this question when it comes up is to locate the May/June 1987 issue of Amiga World. It's the one that has the ray-traced robot juggler on the cover. The article "Graphic Scene Simulations" is a great overview of the subject, and it includes the program listing in C. (Well, most of the program. Details such as inputting the coordinates of all the objects are omitted.)

________________________________________

From: hpfcla!sunrock!kodak!supra!reichert@Sun.COM (Mark Reichert x25948) Subject: A call for vectors.....

Imagine a unit sphere centered at the origin.

Imagine a vector, the "reference vector", from the origin to any point on the surface of this sphere.

I would like to create n vectors which will evenly sample the surface of our sphere, within some given angle about that "reference vector".

I need to be able to jitter these vectors in such a way that no two vectors in a given bunch could be the same.

This appears to be a job for spherical coordinates, but I can't seem to find a formula that can treat the surface of a sphere as a "uniform" 2D surface (ie. no bunching up at the poles).

I desire these vectors for generating soft shadows from spherical light sources, and for diffuse illumination guessing.

I have something now which is empirical and slow - neither of which trait I find very desirable.

I will have a need for these vectors often, and seldom will either the angle or the number of vectors needed be the same across consecutive requests.

Can anyone help me?

________________________________________

>From: hoops@watsnew.waterloo.edu (HOOPS Workshop)
Subject: Needing Ray Tracing Research Topic
[source: comp.graphics]

As a System Design Engineeering undergrad at University of Waterloo, I am responsible for preparing a 'workshop' paper each term. I am fascinated with ray tracing graphics, but what I really need is a good application that I can work into a workable research topic that can be completed in 1 or 2 terms.

If anyone in netland can offer any information on an implementation of ray tracing graphics for my workshop please email me.

Thanks in advance folks,

Tracey Bernath
System Design Engineering
University of Waterloo
Waterloo, Ontario, Canada

              hoops@watsnew.uwaterloo.ca
 Bitnet:      hoops@water.bitnet
 CSNet:       hoops@watsnew.waterloo.edu
 uucp:        {utai,uunet}!watmath!watsnew!hoops

back to contents


Supersampling Discussion

[A flurry of activity arose when someone asked about doing supersampling in a ray tracer. Below are some of the more interesting and useful replies. - Eric]

_________________________________

>From: jevans@cpsc.ucalgary.ca (David Jevans)
[source: comp.graphics]
Summary: blech

In article (5548@thorin.cs.unc.edu), brown@tyler.cs.unc.edu (Lurch) writes:
> In article (5263@cbmvax.UUCP) steveb@cbmvax.UUCP (Steve Beats) writes:
> >In article (1351@umbc3.UMD.EDU) bodarky@umbc3.UMD.EDU (Scott Bodarky) writes:
> >If you sample the scene using one pixel per ray, you will get
> >pretty severe aliasing at high contrast boundaries. One trick is to sample
> >at twice the vertical and horizontal resolution (yielding 4 rays per pixel)
> >and average the resultant intensities. This is a pretty effective method
> >of anti-aliasing.

> From what I understand, the way to achieve 4 rays per pixel is to sample at
> vertical resolution +1, horizontal resolution +1, and treat each ray as a
> 'corner' of each pixel, and average those values. This is super cheap compared
> to sampling at twice vertical and horizontal.

Blech! Super-sampling, as suggested in the first article, works ok but is very slow and 4 rays/pixel is not enough for high quality images. Simply rendering vres+1 by hres+1 doesn't gain you anything. All you end up doing is blurring the image. This is VERY unpleasant and makes an image look out of focus.

Aliasing is an artifact of regular under-sampling. Most people adaptively super-sample in areas where it is needed (edges, textures, small objects). Super-sampling in a regular pattern often requires more than 16 rays per anti-aliased pixel to get acceptable results. A great improvement comes from filtering your rays instead of simply averaging them. Even better is to fire super-sample rays according to some distribution (eg. Poisson) and then filter them.

Check SIGGRAPH proceedings from about 84 - 87 for relevant articles and pointers to articles. Changing a ray tracer from simple super-sampling to adaptive super-sampling can be done in less time than it takes to render an image, and will save you HUGE amounts of time in the future. Filtering and distributing rays takes more work, but the results are good.

David Jevans, U of Calgary Computer Science, Calgary AB T2N 1N4 Canada uucp: ...{ubc-cs,utai,alberta}!calgary!jevans

________________________________________

>From: awpaeth@watcgl.waterloo.edu (Alan Wm Paeth)
Subject: Re: raytracing in || (supersampling speedup)
[source: comp.graphics]

In article (5548@thorin.cs.unc.edu) brown@tyler.UUCP (Lurch) writes:
>
>From what I understand, the way to achieve 4 rays per pixel is to sample at
>vertical resolution +1, horizontal resolution +1, and treat each ray as a
>'corner' of each pixel, and average those values. This is super cheap compared
>to sampling at twice vertical and horizontal.

This reuses rays, but since the number of parent rays and number of output pixels match, this has to be the same as low-pass filtering the output produced by a raytracer which casts the same number of rays (one per pixel).

The technique used by Sweeney in 1984 (while here at Waterloo) compares the four pixel-corner rays and if they are not in close agreement subdivides the pixel. The recursion terminates either when the rays from the subpixel's corners are in close agreement or when some max depth is reached. The subpixel values are averaged to form the parent pixel intensity (though a more general convolution could be used in gathering up the subpieces).

This approach means that the subpixel averaging takes place adaptively in regions of pixel complexity, as opposed to globally filtering the entire output raster (which the poster's approach does implicitly).

The addition can be quite useful. For instance, a scene of flat shaded polygons renders in virtually the same time as a "one ray per pixel" implementation, with some slight overhead well spent in properly anti-aliasing the polygon edges -- no time is wasted on the solid areas.

   /Alan Paeth
   Computer Graphics Laboratory
   University of Waterloo

________________________________________

>From: andreww@dgp.toronto.edu (Andrew Chung How Woo)
Subject: anti-aliasing
[source: comp.graphics]

With all these discussions about anti-aliasing for ray tracing, I thought I would get into the fun also.

As suggested by many people, adaptive sampling is a good way to start dealing with anti-aliasing (suggested by Whitted). For another quick hack on top of adaptive sampling, you can add jitter (suggested by Cook). The jitter factor can be controlled by the recursive depth of the adaptive sampling. This combination tends to achieve decent quality.

Another method which nobody has mentioned is "stratified sampling". This is also a rather simple method. Basically, the pixel is divided into a N-size grid. You have a random number generator to sample a ray at (x,y) of the grid. Then shoot another ray, making sure that the row x and column y are discarded from further sampling, etc. Repeat this for N rays. Note, however, no sharing of point sampling information is available here.

Andrew Woo

________________________________________

>From: loren@pixar.UUCP (Loren Carpenter)
Subject: Re: anti-aliasing
[source: comp.graphics]

[This is in response to Andrew Woo's article - Eric]

Rob Cook did this too. He didn't call it "stratified sampling", though. The idea is suggested by the solutions to the "8 queens problem". You want N sample points, no 2 of which are in the same column, and no 2 of which are in the same row. Then you jitter on top of that....

p.s. You better not use the same pattern for each pixel...

                        Loren Carpenter
                        ...!{ucbvax,sun}!pixar!loren

________________________________________

[By the way, what kind of adaptive supersampling have people been using? We've had fairly good results with the simple "check four corners" algorithm and box filtering the values generated. We find that for complex scenes an adaptive algorithm (which shoots 5 more rays if the subdivision criteria is met) shoots about 25% more rays overall (a result that Linda Roy also obtained with her ray-tracer). What the subdivision criteria are affects this, of course. We've been using 0.1 as the maximum ratio of R,G, or B channels of the four pixel corners. How have you fared, and what kinds of filtering have you tried? - Eric]

back to contents


Distributed Ray Tracer Available

>From: kyriazis@rpics (George Kyriazis)
[source: comp.graphics]

During the last week I put myself together and managed to pull out a second version of my ray tracer (the old one was under the subject: "Another simple ray tracer available"). Tis one includes most of the options described in R. Cook's paper on Distributed ray tracing.

Capabilities of the ray tracer are:
        Gloss (blurred reflection)
        Translucency (blurred refraction)
        Penumbras (area light sources)
        Motion Blur
        Phong illumination model with one light source
        Spheres and squares
        Field of view and arbitrary position of the camera

The ray tracer has been tested on a SUN 3 and SUN 4. I have it available under anonymous ftp on life.pawl.rpi.edu (128.113.10.2) in the directory pub/ray under the name ray.2.0.shar. There are some older version there if you want to take a look at them. If you can't ftp there send me mail and I'll send you a copy. I also have a version for the AT&T Pixel Machine (for the few that have access to one!).

No speed improvements have been made yet, but I hope I will have Goldsmith's algorithm running on it soon. I know that my file format is not standard, but people can try to write their own routine to read the file. It's pretty easy.

Hope you have fun!

  George Kyriazis
  kyriazis@turing.cs.rpi.edu
  kyriazis@ss0.cicg.rpi.edu

back to contents


Ray Tracing Program for 3b1

>From: sid@chinet.UUCP (Sid Grange)
Subject: v05i046: ray tracing program for 3b1
[source: comp.sources.misc]
Posting-number: Volume 5, Issue 46
Archive-name: tracer

[This was posted to comp.sources.misc. I include some of the documentation so you can get a feel for it. Nothing special, but it might be fun if you have a 3b1 (it's supposed to work on other UNIX systems, too). - Eric]

NAME
     tracer- run a simple ray tracing procedure

DESCRIPTION
     Tracer is a program developed originally to study how
     ray tracing works, and was later modified to the present state
     to make it more compatible for animated film production.

     It is capable of depicting a number of balls (up to 150)
     and a plane that is covered with a tiling of any bitmapped picture.

PROGRAM NOTES
     This program generates a file containing a header with x and y sizes,
     followed by the data in 8-bit greyscale, one pixel to a character, in
     scanlines.
     There are two necessary input files: ball data, and a pattern bitmap.
     The tiling bitmap can be digitized data, it must be in the form of
     scan lines no longer than 512 bytes followed by newlines.

back to contents


Map Archive

>From: crum@lipari.usc.edu (Gary L. Crum)
Subject: DB:ADD SITE panarea.usc.edu (Internet archive for maps)
[source: comp.archive, and ftp]

An Internet archive for maps of geographic-scale maps has been set up, starting with data from the United States Geological Survey (USGS) National Cartographic Information Center (NCIC), specifically a map of terrain in USGS Digital Elevation Model (DEM) format.

The archive is on host panarea.usc.edu [128.125.3.54], in anonymous FTP directory pub/map. Gary Crum (crum@cse.usc.edu) is maintainer.

The pub/map directory is writable by anonymous ftp. Approximately 50M bytes are available for the map archive as of this writing.

NOTES:

* Files ending in the .Z extension have been compressed with the "compress" program available on comp.sources archives such as j.cc.purdue.edu. They should be transferred using the "binary" mode of ftp to UNIX systems. Send mail to the maintainer to request format changes (e.g., to uuencoded form split into small pieces).

* Some maps, e.g., DEM files from USGS, contain long lines which have been observed to cause problems transferring with some FTP implementations. In particular, a version of the CMU TCP/IP package for VAX/VMS did not support these long lines.

* Source code for UNIX tools that manipulate ANSI labeled tapes and VMS tapes is available as pub/ansitape.tar.Z on the map archive host.

_________________

Index for Map Archive on Internet Host panarea.usc.edu [128.125.3.54].
version of Mon Nov 14 09:41:10 PST 1988

NOTE: This INDEX is descriptive to only the directory level in many cases.

-rw-r--r--  1 crum      1090600 May 26 09:33 dem/MAP.N0009338
-rw-r--r--  1 crum       278140 Nov 11 14:16 dem/MAP.N0009338.Z
        Digital Elevation Model 7.5 minute quad (see dem/README).
        Ft. Douglas quadrangle, including part of Salt Lake City, UT.
        Southeast corner has coordinates 40.75 N 111.75 W

drwxrwxrwx 2 crum 512 Nov 1 19:23 terrain-old-format/MAP.37N112W drwxrwxrwx 2 crum 512 Nov 1 19:23 terrain-old-format/MAP.37N119W drwxrwxrwx 2 crum 512 Nov 1 19:24 terrain-old-format/MAP.38N119W USGS NCIC terrain maps in "old" format before DEM was introduced. Files in these directories ending in extensions .[a-s] should be concatenated together after transfer.

-rw-rw-rw- 1 45 777251 Nov 11 11:10 world-digitized/world-digitized.tar.Z drwxrwxr-x 7 crum 512 Nov 11 10:56 world-digitized/extracted The "extracted" directory is produced from the tar file. From world-digitized/expanded/doc/read.me : The World Digitized is a collection of more than 100,000 points of latitude and longitude. When connected together, these co-ordinates form outlines of the entire world's coastlands, islands, lakes, and national boundaries in surprising detail.

drwxrwxrwx 2 crum 1024 Nov 12 19:10 dlg/35N86W Digital Line Graph of area with top-left coordinates 35 N 86 W. See dlg/README. From roskos@ida.org (Eric Roskos).

back to contents


Index of Back Issues, by Eric Haines

This is a list of all back issues of the RT News, email edition. I'm retroactively giving these issues numbers for quick reference purposes. Topics are fully listed in the first issue in which they are discussed, and follow-up material is listed in braces {}. I've tried to summarize the main topics covered, not the individual articles.

[Volume 0, August-December 1987] - Standard Procedural Databases, Spline Surface Intersection, Abnormal Normals

[Volume 1, Number 1,] 1/15/88 - Solid Modelling with Faceted Primitives, What's Wrong [and Right] with Octrees, Top Ten Hit Parade of Computer Graphics Books, Comparison of Efficiency Schemes, Subspaces and Simulated Annealing.

[Volume 1, Number 2,] 2/15/88 - Dore'

[Volume 1, Number 3,] 3/1/88 - {comments on Octrees, Simulated Annealing}, Efficiency Tricks, More Book Recommendations, Octree Bug Alert

[Volume 1, Number 4,] 3/8/88 - Surface Acne, Goldsmith/Salmon Hierarchy Building, {more Efficiency Tricks}, Voxel/Quadric Primitive Overlap Determination

[Volume 1, Number 5,] 3/26/88 - {more on Efficiency, Voxel/Quadric}, Linear Time Voxel Walking for Octrees, more Efficiency Tricks, Puzzle, PECG Correction

[Volume 1, Number 6,] 4/6/88 - {more on Linear Time Voxel Walking}, Thoughts on the Theory of RT Efficiency, Automatic Creation of Object Hierarchies (Goldsmith/Salmon), Image Archive, Espresso Database Archive

[Volume 1, Number 7,] 6/20/88 - RenderMan & Dore', Commercial Ray Tracing Software, Benchmarks

[Volume 1, Number 8,] 9/5/88 - SIGGRAPH '88 RT Roundtable Summary, {more Commercial Software}, Typo in "Intro to RT" Course Notes, Vectorizing Ray-Object Intersections, Teapot Database Archive, Mark VandeWettering's Ray Tracer Archive, DBW Render, George Kyriazis Ray Tracer Archive, Hartman/Heckbert PostScript Ray Tracer (source),

[Volume 1, Number 9,] 9/11/88 - {much more on MTV's Ray Tracer and utilities}, Archive for Ray Tracers and databases (SPD, teapot), Sorting on Shadow Rays for Kay/Kajiya, {more on Vectorizing Ray-Object Intersection}, {more on George Kyriazis' Ray Tracer}, Bitmaps Library

[Volume 1, Number 10,] 10/3/88 - Bitmap Utilities, {more on Kay/Kajiya}, Wood Texture Archive, Screen Bounding Boxes, Efficient Polygon Intersection, Bug in Heckbert Ray Tracer (?), {more on MTV's Ray Tracer and utilities}, Neutral File Format (NFF)

[Volume 1, Number 11,] 11/4/88 - Ray/Triangle Intersection with Barycentric Coordinates, Normal Transformation, {more on Screen Bounding Boxes}, {comments on NFF}, Ray Tracing and Applications, {more on Kay/Kajiya and eye rays}, {more on Wood Textures}, Virtual Lighting, Parallel Ray Tracing, RenderMan, On-Line Computer Graphics References Archive, Current Mailing List

back to contents


Eric Haines / erich@acm.org