back to
contents
"Light Makes Right"
July 10, 1992
Volume 5, Number 1
Compiled by
All contents are copyright (c) 1991,1992, 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.
I've got a confirmed room in the Convention Center during the dead time between when the sessions end and the technical reception begins. Look for an announcement of the location wherever "Special Interest Groups" are listed (I'll probably also list it under "Birds of a Feather", if like last year they don't post where the SIG meetings are located (The difference between a "BOF" and a "SIG" meeting? All I know is I can reserve a room if it's a "SIG" meeting)).
Official time: 5:15-6:15 pm Thursday, July 30th
No guarantees about the shape of the table...
________
It's a bit embarrassing putting this issue together, reading the backlog of notes ending in phrases like "have a nice Xmas". What can I say, I've been busy... Culling through all this stuff has been pleasant. There are some nice new ideas and interesting research results. I've tried to minimize the endless stream of announcements about some of the new free software (geez, don't these people know the rest of us are trying to make money selling this stuff?!) by summarizing these in an article called "Ray Tracing Roundup".
By the way, if you're reading this on comp.graphics, don't ask to subscribe - "The RT News" is always posted to comp.graphics. If you think you missed an issue, check the princeton.edu archive site (assuming you have FTP).
There is a lot more stuff to wade through, a few articles I want to pass by the authors again, etc, but for now I thought the amount of material was enough to make an issue. Enjoy, and see you at SIGGRAPH.
back to
contents
I have become very involved in developing algorithms for ray tracing, especially in statistical analysis and "smart" ray-tree pruning and antialiasing. I am also working on a method of "on-demand modelling" where a ray tracer might not even compute an object's polygons unless its bounding volume is pierced. Thus, forests of millions of trees are possible with modest memory requirements: distant trees are never even synthesized. (This is one algorithm where true ray tracing is orders of magnitude faster than a Z buffer or scanline algorithm... a scary thought!) I have also written code for over 100 (!) Perlin-style solid textures as a commercial product.
________
Manoj Patel - stereo, motion blur Computer Science Department North Carolina State University Raleigh, N.C. 27695-8206 (919) 515-3271 e-mail: mp@adm.csc.ncsu.edu
I am a lowly graduate student at North Carolina State University. I am working on combining motion blur and stereo (using a modified version of Rayshade). My speciality is staying incredibly busy 24 hrs a day but getting very little done :-).
I would be interested in hearing from people that have implemented motion blur. I have been assuming that most people use supersampling or stochastic sampling (across about 8 - 24 time frames), but have few sources to back this up (i.e please tell me know what is done "in the real world").
________
Laurie Gerholz Unisys Corporation 3199 Pilot Knob Road, M.S. F2L09 Eagan, MN 55121 (612) 687-2913 vlad@moria.sp.unisys.com
My interests in computer graphics currently include ray tracing techniques, radiosity techniques, and methods of building scene models which can be rendered via ray tracing or radiosity. I am currently working on a ray tracing scene renderer which will run under Microsoft Windows. This is a part-time hobby effort, not at all related to my real job (too bad!).
________
Antonio Costa - ray tracing, visualization, modeling INESC - North Largo Mompilher 22 4100 Porto Portugal (351 2) 321006 ext. 329 alias antonio_costa a_costa@inescn.rccn.pt # alias antonio_costa acc@asterix.inescn.pt
I have developed my own extensible ray tracer in the past 2 years for U*ix, VMS, DOS and Transputers. I am very interested in texturing (2D and 3D) and better ray tracing... I am also doing some things in scientific visualization applied to medicine. I am looking for a subject to start my PhD work next year. [The ray tracer is at asterix.inescn.pt [192.35.246.17]. It does bicubic patches and other interesting things. -EAH]
________
Brian Corrie
I am moving to the land down under, to work on the Visualization project at the Australian National University in Canberra. Interests are the same as before, roughly, Realistic Rendering, Shading Languages, and Parallelization. They have some interesting hardware down there. I will be working on a 128 node Fujitsu AP1000, a MIMD parallel machine, parallelizing algorithms for visualization. My new email address is bcorrie@cs.anu.edu.au. G'day.
back to
contents
* Texturing: I had a smelly problem with the AutoCAD entity "polyface" (= a bunch of vertices and then a bunch of 3angles or 4angles referring to those by index) since AutoCAD don't know a THING about texturing, it naturally does not include texturing coordinates. And by default, RayTracker did texture EACH LITTLE POLYGON separately, yielding VERY ugly results.
What I *did* was simple, but (semi) effective: Look at ye normal vector. If Z component is largest, texture in XY space, if Y is largest, texture in XZ space, and if X is largest in YZ space! That created good results as long as the objects depicted were boxes and such, a brick texture was correctly oriented automatically on the faces and so on. Curved surfaces Weren't that good (I used the pre-smoothing normal, so each polygon had its own texturing at least, i.e. no change of texture-space over the polygon). But what the heck, it look quite alright, and actually, some of the funnier effects of the weird texturing on curved objects looked like some kind of inlaid material (like inlaid wood) or so where texture space just happened to swap. Perhaps you have thought of some similar criteria?
[Indeed I have - I independently invented this method a few years back, and I've found it useful since then. It's particularly good with textures like carpet or iron or suchlike: there is little distortion and you usually can't see the discontinuities when things flip from one "face" to another. Even when there is some "grain" to the texture, it usually looks pretty cool. - EAH]
Another idea I had was to average ALL NORMALS in any given polysurface, weighted by area, and that would give me a "normal" to the objects "most flat" orientation... then one would texture in the plane orthogonal to that normal... The problem is that one most often want the X direction of a texture to follow the horizon (not to get rotated textures)...
back to
contents
%A Michael Gigante %T Accelerated Ray Tracing Using Non-Uniform Grids %J Proc. of Ausgraph '90 %C Melbourne, Australia %D Sept. 1990 %P 157-63
- EAH]
As I made the claim that NUgrid would "just take care of the SPD balls example automatically", I thought I would followup on some results. These results are using rayshade 4.0.2 for which we have added NUgrid as well as the existing uniform grid. This model is exactly as generated by your SPD program (i.e. no hand tweaking to remove the ground plane from the uniform grid):
Resolution Grid Method NuGrid Method 8 7810.45 850.94 10 7083.62 647.86 12 7248.39 574.53 14 6477.42 518.00 16 5759.92 540.98 18 5000.04 532.22 20 4235.32 567.90 22 3407.94 558.84 24 2837.32 552.42 26 2544.04 537.30
note that NUgrid is far less sensitive to grid resolution and of course is significantly faster :-)
NUgrid doesn't always win as much, but it is always less sensitive to picking the "right" grid resolution.
[I would like to see how these results compare to two level gridding (i.e. complicated objects get their own grid - see next article). An automatic way to implement this is if a box contains more than so many items, nest a gridded box in it. This is one of David Jevans & Brian Wyvill's ideas in "Adaptive Voxel Subdivision for Ray Tracing," Proceedings of Graphics Interface '89, and has evidently been used by Alias Inc, to good effect. I wish some Rayshade hacker would go and implement this method (hint hint). - EAH]
[Mike wrote about some interesting new results he's found that's made NuGrid even faster; hopefully more about these in the next issue. - EAH]
back to
contents
In the mid eighties I did some experiments comparing a sequential ray traversal with a recursive ray traversal for an adaptive spatial subdivision (Excell). See also the discussion in the RTnews issues of March 26, 1988, Jim Arvo: Linear-time voxel walking for BSP and April 7, 1988, Erik Jansen: Re: Linear-time voxel walking for BSP. I did not found a clear difference in performance between the two methods (of course the Excell spatial directory is an efficient index, not requiring any tree traversal), as reported in the above mentioned issues of RTnews.
Nevertheless, papers are still appearing in conferences and journals that either prove that recursive traversal is performing worse than a newly proposed method or performing better in those cases where it is proposed as a 'new' method. This is reason enough to do a new comparison.
As part of a master's thesis project Wim de Leeuw first did some experiments with recursive traversal on an adaptive binary space subdivision, comparing it with the DDAOCT algorithm of Kelvin Sung (Eurographics'91). The DDAOCT did certainly not do better than the recursive method. Furthermore the DDAOCT method is very sensitive to the size of the hashtable.
Secondly, the recursive traversal/adaptive subdivision algorithm was implemented in Rayshade, a very fast ray tracer using a sequential grid traversal algorithm (see RayShade 4.0 and RayShade timings in RTnews Nov, 20, 1991). The uniform grid method of RayShade is very sensitive to the 'teapot in stadium' problem and therefore RayShade provides a two-level grid option: a grid for the whole scene and separate grids for complex (sub)objects. The adaptive subdivision/recursive ray traversal was implemented with only minor modifications to RayShade. The recursive traversal uses a stack and alternatively halfs the xmin-xmax, ymin-ymax, zmin-zmax ray intervals as described in RTnews April 7, 1988.
Here are the timings for the two/three methods (in seconds on a HP-700):
model grid grid/subgrid recursive/bsp
balls 942 156 366 gears 977 857 1155 mount 214 263 rings 307 299 441 teapot 154 171 tetra 39 84 tree 2246 134 278 conf.room 283 269
Conf. room is the room by Greg Ward that was converted from Radiance format to RayShade format.
As you see RayShade (with two-level grid) is indeed very fast, mainly because of the additional raybox test within each cell. The raybox test is not of much use in an adaptive subdivision because the cells are already tight enough.
Of course there are always ways to improve the recursive version by making larger changes to RayShade, for instance by inputting polygons not by their enclosing box but by their own extent, but that would not really change the picture, we think.
These have been our experiments so far. The code for the recursive ray traversal and the model data of the conference room can be obtained from us (fwj@duticg.tudelft.nl).
________
[I received this from Kelvin Sung (ksung@sherman.cs.uiuc.edu) in response. - EAH]
I hope I have pointed this out in comp.graphics, but in [the Eurographics '91] paper when I say "ARVO", I was referring to Glassner's Tree Coherence (Re: SIGGRAPH 90 Advance Ray Tracing Course Notes). It was my mistake. In that paper, I did not actually compare DDAOCT with Arvo's linear tree walking or Eric Jansen's recursive algorithm. I agree 100% with their claim. In fact, after realizing my mistake during the September Eurographics '91 conference, in November Peter Shirley and I implemented Arvo's linear tree walking algorithm and tested things out and we realized that linear tree walking is a better algorithm (independently from Jansen). We wrote up our experience as a Gem (which will appear in Graphics Gems III, as "Ray Tracing with the BSP Tree").
[Note that the code for Graphics Gems III is now available on princeton.edu in pub/Graphics. The book itself will be out at SIGGRAPH from Academic Press.]
back to
contents
From Dan:
I am rendering large protein structures with overlapping reflective spheres. 'Engridding' the primitives speeds the rendering considerably, as might be expected for a big conglomerate of 2000 spheres. My choice of grid size has been made mostly through trial-and-error, though.
So here's my question: Assuming a near-uniform density of primitives, what primitive/voxel ratio will result in optimal performance? Or does it vary a lot from one case to another? My trials (however limited) suggest a ratio of about 4 or 5 primitives/voxel. Does anyone have any suggestions?
From Marc:
That's about what I settled on a while back (again through trial and error), something like a 10x10x10 grid for 5000 spheres. It would sure be nice if Rayshade could compute an optimum grid size based on primitive distribution.
back to
contents
I just finished an undergraduate thesis in ray tracing. I implemented a ray tracer in C++ and compared a number of optimization strategies. I thought you might be interested in some of the results I ran into.
- Bounding volume hierarchies generated by the technique of Goldsmith and
Salmon yield huge speedups over naive ray tracing (obviously). I'd
guess 10-20X.
- You go slower if you combine with Snyder-Barr ray boxes because the ray
box rejection rate is small (45%) and you have to recompute the ray box
every time the ray hits a bounding volume (which is frequently when the
BVH was generated automatically).
- Kay-Kajiya BVH traversal reduces the number of intersections, but not by
much in my experience. In fact, only the Sphereflake image (modified
from the SPD) saw a big enough reduction for the priority queue to be
worthwhile. A 20% reduction in intersections resulted in a <4% speedup
over the naive traversal. In the other test images, naive traversal was
faster.
[I asked what "Snyder-Barr" boxes were in this context. -EAH]
Snyder-Barr boxes:
When you hit a bounding volume, enclose the ray's traversal of the bounding volume in a "ray box." This is an axis-aligned bounding box using the two points where the ray enters and exits the bounding box. An object cannot intersect the ray unless its bounding box intersects the ray box. If the bounding box for each object is precomputed, it costs you at most six comparisons to reject the intersection, or after six comparisons you have to do the intersection calculation after all. And since most ray boxes only enclose a small fraction of the bounding box's volume, the rejection rate should be high.
Also, if you find an intersection you can make the ray box smaller ("restrict" it?) because you know that a closer intersection isn't going to be found beyond the one you just found. This is done using the ray's direction cosines.
If you have a super-naive BVH (example: one root bounding volume), this works great. The ray hits the root, you enclose its traversal of the root bounding volume in a ray box. The ray box encloses a tiny fraction of the root bounding volume, so you get 95-99% rejection rate, i.e. almost all intersection calculations end after <=6 comparisons. The problem is that it doesn't reduce the number of intersection tests, just makes them a lot cheaper, so using a G-S hierarchy is much better. And when you combine the two, you hit so many bounding boxes (which requires you to compute the points where the ray enters and exits the bounding box, then do a bunch of comparisons so the ray box is defined by min/max vectors) that it's not worth the trouble.
back to
contents
TTDDD: these programs convert 3D objects in the binary TTDDD format into either OFF, NFF, Rayshade, or vort format. There is also a Postscript object viewer (very handy - I can quickly preview objects using GhostScript), and it also outputs Framemaker MIF files. These programs are SHAREWARE. Registered users also get code to automatically convert text strings into 3D objects using any TeX font. This package and many objects are available at wuarchive.wustl.edu, in /graphics/graphics/objects/TDDD. Some of the objects are excellent: one of my favorite test objects is the Star Wars "Imperial Scout Walker." Contact Glenn Lewis (glewis@pcocd2.intel.com).
There are a number of new VORT input files from Italy. (Contact Alessandro Villani (raytr@astrpi.difi.unipi.it)). They are available for anonymous ftp:
pub/contrib/artscenes/room.tar.Z on gondwana.ecr.mu.oz.au (128.250.1.63)
pub/graphics/room.tar.Z on munnari.oz.au (128.250.1.21)
The models are mainly objects in a room: clock, ashtray, bed, lights, television, etc. Contact Eric H. Echidna (echidna@ecr.mu.oz.au)
RayShade is now in version 4.0.6 at princeton.edu:pub/Graphics. There is an active, helpful mailing list for this group - contact rayshade-request@cs.princeton.edu to get put on it.
Inetray is a network version for running Rayshade 4.0. FTP it from maggia.ethz.ch (directory pub/inetray). It allows parallel calculation of rayshade pictures for multiprocessing machines and over a network of machines. You need SUN RPC 4.0 or newer. Contact Andreas Thurnherr (ant@ips.id.ethz.ch) for more information.
There is an X window fonts converter into Rayshade 3.0 polygons, by Ron Sass (sass@cps.msu.edu). Anonymous ftp from acs.cps.msu.edu in the file pub/sass/gentxt.c. There is also a tool for Rayshade animation here.
The code for a recursive ray traversal efficiency scheme for RayShade and the model data of Greg Ward's conference room can be obtained from Erik Jansen (fwj@duticg.tudelft.nl). Hopefully this will be made available via FTP some time soon. See the related article in this issue.
Radiance is going great guns. There's now even an Amiga port of Radiance 2.0. Check hobbes.lbl.gov (128.3.12.38) /pub/ports/amiga or osgiliath.id.dth.dk (129.142.65.24) /pub/amiga/graphics/Radiance. Contact Per Bojsen (bojsen@ithil.id.dth.dk).
The IRIT solid modeler 3.0 is now available at an ftp site near you, e.g. ftp.uu.net (192.48.96.2):/graphics/irit, among others. This is an X-based CSG modeller which now includes freeform surfaces, and it runs on a large number of platforms.
At asterix.inescn.pt [192.35.246.17] is a ray tracer by Antonio Costa. I haven't played with it, but it evidently renders bicubic patches and other interesting things.
POV (aka Son of DKBTrace, done by people on CompuServe) still seems to be in beta test or somesuch.
Studio Amiga is a 3D modelling and ray tracing specific BBS, (817) 467-3658. 24 hours, 105 Meg online.
The Utah Raster Toolkit version 3.1 should be out of testing some time after SIGGRAPH. There are a number of bug fixes and so on - worth getting if you use it. Harass Spencer Thomas for when it'll be out (spencer@med.umich.edu)
If you are interested in Greg Turk's work on reaction-diffusion textures (SIGGRAPH '91), he's placed C code for generating these in the anonymous ftp directory at UNC. Connect to ftp.cs.unc.edu and grab the files in the directory pub/reaction_diffusion.
Greg notes an implementation detail accidentally left out of the paper: The value of chemical "b" should not be allowed to go below zero. While I'm on the subject, I noticed a minor typo in the Witkin/Kass paper on the topic: the center term in equation four should be "-4 * a^2 - h^2 * b". Also, their reference #2 has incorrect page numbers - should be 363-385.
Graphics Gems III code is available via anonymous FTP at princeton.edu in /pub/Graphics/GraphicsGems/GemsIII. Have fun puzzling it out (since the book itself is not out quite yet). There are some nice bits, like Ben Trumbore's bounding volumes (I *think* I know what he's doing...) and Kelvin Sung's new BSP code.
back to
contents
The server is the official archive site for the Lightwave 3D mail-list.
Besides the above mentioned image-based files, the server contains many PD and Shareware graphics utilities for several computer platforms including Amiga, IBM and Macintosh.
Some samples include:
DKBTRACE - Raytracer for IBM, Amiga and Mac RAYSHADE - Raytracer for the Mac QRT - Raytracer for IBM, Amiga and Mac [...] Objects - Objects for Imagine, Videoscape, Lightwave and others Demos - ImageCels, Caligari, Autodesk 3D Studio and others
Plus much more! And many more to come!
The server resides on my BBS called "The Graphics BBS". The BBS is operational 24 hours a day 7 days a week at the phone number of +1 908/469-0049. It utilizes a Hayes V-Series 9600 V.42 modem. (soon to upgrade to a V.32 modem)
If you would like to submit objects, scenes or images to the server, please pack, uuencode and then mail the files to the address:
server@bobsbox.rent.com
For information on obtaining files from the server send a mail message to the address:
file-server@graphics.rent.com
with the following in the body of the message:
HELP /DIR
and a help file describing how to use the server and a complete directory listing will be sent to you via mail.
back to
contents
I actually use it since I do a lot of mathematical/parametric modelling using C code. Since I have an Amiga at home and a Sun at work, I can output rayshade objects and render them at work, or Imagine objects and render them at home; very convenient. In fact, I got started with parametric modelling about a year and a half ago by tearing apart your "tree" program you wrote for the SPD package; now I'm working on exploding objects, and breaking them in "reasonable" places when they are subjected to stress. Lots of fun! I also worked with Glenn to try to produce an algorithm to morph different objects into one another. It wasn't a dismal failure, but it is nothing I want to try to sell to ILM... I also enjoy playing with building new Perlin-style solid textures. That's ALWAYS a lot of fun.
back to
contents
Ok, here's what you do:
Check if rmajor > rminor.
If so, hit is OK as is.
If not, calculate the distance between the hit you got and torus center. We will be needing the distance SQUARED, so no need for a square root. Put the distance squared in variable SqrDist.
If rmajor < rminor && rmajor > 0
if SqrDist < (rminor*rminor - rmajor*rmajor)
then discard the hit, it's on the wrong surface.
If rmajor < rminor && rmajor < 0
if SqrDist > (rminor*rminor - rmajor*rmajor)
then discard the hit, it's on the wrong surface.
Voila!
________
Joe Cychosz (3ksnn64@ecn.purdue.edu) responds:
I did test the case where the torus was degenerate, however I did not consider the application sense of it not really being a wanted surface. I will study this further and incorporate your suggestion.
Also, not include in the GEM is the following code which compensates for the order of the roots being transposed. I didn't include it since it would make the GEM dependent on the behaviour of the root solver.
Insert after the call to SolveQuartic:
/* SolveQuartic returns root pairs in reversed order. */
if ( *nhits > 1 )
m = rhits[0]; u = rhits[1]; rhits[0] = u; rhits[1] = m;
if ( *nhits > 3 )
m = rhits[2]; u = rhits[3]; rhits[2] = u; rhits[3] = m;
back to
contents
I am after any info on the Taos parallel processor raytracing stuff.
The reason I sat up and paid attention when I read about Taos was only because of the way it handles code from a programmer's point of view.
Apparently it doesn't link the program at the compilation stage but rather downloads the objects as and when they are needed, and destroys them as they are finished with (how quickly depends on their priority). Also, if one branch calls an object which is already resident on another node rather than load dwon from the data store it loads in from the other node.
Also, the programmer doesn't need to allocate them to the nodes and ensure that all the node loads are balanced. Indeed Taos does this for the programmer to supposedly ensure optimum performance.
It can apparently do a 790x400 24bpp colour raytrace on 256 compound objects in under 15 minutes. And supposedly a 50x50 array of em can do real-time raytracing....
back to
contents
Next "bad" thing with standard Phong is the inability to get really shiny surfaces. Pumping up the specular exponent makes the shiny spot SMALLER, not (as it should) SHARPER. So it might look pretty shiny on a sphere, but use it on a cube, the chance of you ever SEEING that tiny little specular spot is very small, unless the light is positioned just right in respect to the viewer and some cube surface.
There is a nice and simple trick for this, used frequently by Pixar in their little movies: You simply threshold the specular light instead of feeding it directly to the output light. Let's assume we have a function similar to the Renderman (tm) function SmoothStep() that work like this:
Smoothstep(a,b,x)
if (x < a) return 0.0;
if (x > b) return 1.0;
if (x > a and x < b) return a smooth gradation between 0.0 and
1.0 (Pixar uses a hermite spline I think)
Then let our "all new" specular highlight be...
OLD specular formula: Ks * (cos b ^ Ke)
NEW specular formula: Ks * SmoothStep(0.4,0.5,cos b ^ Ke)
...where the numbers (here 0.4 and 0.5) could be anything you wish. This gives the surface a "glazed" appearance and may be useful modelling glass and similar.
back to
contents
if ( t < 0.0 ) return ( MISSED ) ;
if ( t < tfar ) {
/* hit near face, update normal */
It should be:
if ( t < tnear ) return ( MISSED ) ; <-- 0.0 to tnear
if ( t < tfar ) {
/* hit far face, update normal */ <-- near to far
Also, the text in Graphics Gems II has the same bug. The last sentence on page 249 should be:
"If the compute t is less than tnear, then the polyhedron is ..."
^
+--was "0"
back to
contents