erich@eye.com (Eric Haines) (03/01/91)
_ __ ______ _ __
' ) ) / ' ) )
/--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _
/ \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_</_(_(_/_/_)_
/ /|
' |/
"Light Makes Right"
March 1, 1990
Volume 4, Number 1
Compiled by Eric Haines, 3D/Eye Inc, 2359 Triphammer Rd, Ithaca, NY 14850
erich@eye.com or uupsi!eye!erich
All contents are US copyright (c) 1990 by the individual authors
Archive locations: anonymous FTP at weedeater.math.yale.edu [130.132.23.17],
/pub/RTNews, and others.
UUCP archive access: write Kory Hamzeh (quad.com!avatar!kory) for info.
Contents:
Introduction
New People, Address Changes, etc
Ray Tracing Abstract Collection, by Tom Wilson
Report on Lausanne Hardware Workshop, by Erik Jansen
New Version of SPD Now Available, by Eric Haines
Teapot Timings, by John Spackman
The Very First Point in Polygon Publication, by Chris Schoeneman
The Acne Problem, by Christophe Schlick
Shirley Thesis Available via Anonymous FTP, by Pete Shirley
Some Thoughts On Anti-aliasing, by Zap Anderssen, Eric Haines
New VORT Release, and the VORT Chess Set, by Eric H. Echnida, David Hook
Best (or at least Better) of RT News, by Tom Wilson
At Long Last, Rayshade v4.0 is Available for Beta-testing, by Craig Kolb
Parallel Ray Tracer, by Kory Hamzeh, Mike Muuss, Richard Webb
Distributed DKB, by Jonas Yngvesson
Quadrangle Tessellation, by Christophe Schlick
New Release of Radiance Software & Bug Fixes, by Greg Ward
Radiance Timings on a Stardent, by Eric Ost
RTSYSTEM Fast Ray Tracer, by Patrick Aalto
DKBTrace Beta Available, by David Buck
"Computer Graphics" 2nd Edition Corrections, Software, etc by Brown Emailer
Papers which are currently available from the Net via anon. FTP, J. Kouhia
======== USENET cullings follow ========
Ray-Cylinder Intersection Tutorial, by Mark VandeWettering
C++ Fractal and Ray Tracing Book, by Fractalman
Ray/Spline Intersection Reference, by Spencer Thomas
Superquadric Intersection, by Rick Speer, Michael B. Carter
Comments on Interval Arithmetic, by Mark VandeWettering, Don Mitchell
Platonic Solids, by Alan Paeth
Moon Problems, by Ken Musgrave, Pete Shirley
Ken gave another problem with rendering the moon:
Shadow Testing Simplification, by Tom Wilson
SIMD Parallel Ray Tracing, by George Kyriazis, Rick Speer
Rayscene Animator, by Jari K{hk|nen [sic]
SIPP 2.0 3d Rendering Package, by Jonas Yngvesson and Inge Wallin
3DDDA Comments, by John Spackman
Radiosity Implementation Available via FTP, by Sumant
Dirt, by Paul Crowley
Thomson Digital Images University Donation Program, by Michael Takayama
A Brief Summary of Ray Tracing Related Stuff, Angus Y. Montgomery
-------------------------------------------------------------------------------
Introduction
Well, it's been awhile. I've essentially fallen off the face of the earth,
with too much to do. So, it's time to throw something together during compile
& link time (pity my new machine does is much faster - it makes it harder to
get out an issue). As usual, the comp.graphics version does not have all the
comp.graphics cullings. If you want the full issue, pull it in via FTP from
weedeater.math.yale.edu or any other site which carries it.
My big fun for the week has been looking at my head: I finally received my
head database from the Visual Computing Group (415-688-7315) after getting my
head scanned in by their Cyberware scanner at SIGGRAPH. Quite a bargain:
around $40 for a 256x512 mesh of my head. There are lots of bad points in my
database: the top of my head is missing and my hair has a natty dredlock
look, but still it's pretty amazing, and a little data interpolation here and
there cleans up the dropout data points.
The data comes in a cylindrical coordinate system format, and VSG provides
source code for a number of programs and utilities to convert the data in
various ways. I've heard Spencer Thomas has rendered his face as an unrolled
cylinder, i.e. a height field. So, have others out there played with these
data sets much? Anybody want to trade heads?
-------------------------------------------------------------------------------
New People, Change of Addresses, etc
--------
Michael Cohen's email address is now mcohen@cs.utah.edu
Jim Arvo's email address is now arvo@graphics.cornell.edu
Peter Miller's email address is now pmiller@pdact.pd.necisa.oz.au
--------
Brian Corrie, University of Victoria, Victoria, B.C.
I am back from my trip down under, and have a new account here
at UVic.
My new address is bcorrie@csr.uvic.ca
One new area of interest. I like the idea of the shading language provided by
the RenderMan Interface. Do you know of anyone doing work in this area? I
want to make a shader compiler, along with a shader library that has some of
the pixar functions (noise..etc), that will compile a shader description into
a linkable module that a renderer can link to at compile time. Kind of a half
way step between interpreting the shader description and hard coding the
shader into the renderer itself. If I set up some binding rules then any
renderer that follows those rules will be able to link to any shader compiled
with the shader compiler. We can then pass around shader descriptions between
users. What do you think?
--------
# Patrick Flynn - geometry (solid and image), algorithmics, computer vision
# Department of Computer Science and Engineering
# University of Notre Dame
# Notre Dame, Indiana 46556
# (219) 239-8375
alias patrick_flynn flynn@cse.nd.edu
My interest in ray tracing was an itch that I couldn't scratch during 1989 and
much of 1990, while I was dissertating. I'm presently mapping subproblems
(like rendering) in model-based computer vision onto parallel architectures,
and developing a graphics course for seniors and grad students, with future
(unfocused) plans for an ongoing research program in graphics.
--------
# Jean-Philippe Thirion - coherency, interval arithmetic, data structure
# I.N.R.I.A.
# Domaine de Voluceau - Rocquencourt
# B.P. 105 - 78153 LE CHESNAY CEDEX
# FRANCE
# (33 1) 39 63 52 79
alias thirion thirion@bora.inria.fr
I worked from 1986 to 1990 for a PHD thesis at the L.I.E.N.S., Paris,
France, with Pr Claude Puech. First about data structures and hidden part
removal problems, then about the uses of coherency in order to improve ray
tracing. This work have lead to a PHD thesis about object space and ray
coherency for ray tracing (in french), and two research reports (in English):
- Tries, data structure based on binary representation for ray tracing
- Interval arithmetic for high resolution ray tracing
The first report have been published in Eurographics' 90. I am
writing now a third report about some enumeration problems on binary space
partitioning trees.
--------
Christophe Schlick
LaBRI
351, Cours de la Liberation
33405 TALENCE CEDEX --- FRANCE
Email: schlick@geocub.greco-prog.fr
I am currently working on my PhD thesis on "Realistic Image Synthesis". It
will include some classic topics as ray-tracing, radiosity, hydrid methods,
antialising and parallelization of those techniques.
--------
# Henry Kaufman
# Brown University graphics group
alias henry_kaufman hek@cs.brown.edu
I worked on an ARTS ray tracer (with the SEADS) data structure. Since the
details of their algorithm were not well described in their paper (in my
opinion), I had to figure out most of the algorithm myself. The part I found
interesting was "scan converting" my quadric surface primitives into the SEADS
voxels. I tried to implement Bresenham style scan converters, which turned
out to be fairly efficient. I just thought I'd mention it, even though you
are probably already familiar with the algorithms involved.
--------
# Nick Holliman - parallelism, CSG, spatial subdivision, ray tracing.
# School of Computer Studies,
# University of Leeds,
# Woodhouse Lane,
# Leeds, West Yorkshire, LS2 9JT.
# ENGLAND
# (0532) 335446
email: nick@uk.ac.leeds.dcs
I have just completed my PhD at Leeds and currently have an IBM research
fellowship at Leeds, working with the IBM UK Scientific Centre, Winchester.
My PhD work was the development of a parallel CSG ray tracer. This takes a
CSG model and creates a distributed octree using a parallel algorithm. It can
then ray trace the distributed octree and uses caching to avoid replicating
all the data on each processor. The system scales well making good use of up
128 T800 transputers (as many as I could find in one place) handling models of
up to 20,000 CSG primitives. We have recently extended this to support
parallel incremental update algorithms, so given a small change to the CSG
model the system updates the distributed octree and then updates the region of
image affected by the change. Current work is looking at increasing the model
size, improving the scalability and porting the system to other parallel
machines.
I would be keen to hear from anyone working on similar parallel algorithms and
if anyone is interested they are welcome to a copy of my thesis.
--------
Ning Zhang
I have written a Radiosity package and both input and output are based on the
NFF file format. Have you considered to have a similar benchmarking package
for comparing different Radiosity software and hardware? I think that would
be an interesting subject. [Any volunteers? - EAH]
----- Self description -----
# Ning Zhang - Radiosity, Raytracing, Image Compression
# School of Electrical Engineering
# The University of Sydney
# NSW 2006, Australia
# + 61 (02) 692 2962
alias ning_zhang nzhang@ee.su.oz.au
I have been in Germany for two year as a visiting scientist at the Computer
Graphics Center (ZGDV), Darmstadt. There I developed a Radiosity/Raytracing/
FastZBuffer package running on many platforms, including 386PC. Recently I
came to Australia as a visiting fellow at the Univ. of Sydney.
Email: nzhang@ee.su.OZ.AU
(In Germany, zhang@agd.fhg.de or zhang@zgdvda.uucp)
--------
Craig McNaughton
Interests - CSG, Animation, higher dimension, distortions
Address -
C/- Computer Science Department
University of Otago
PO Box 56
Dunedin
New Zealand
ph (+64) 3 4798488
I'm in the Graphics Research Group at Otago University, currently doing a
Masters. My main project at the moment is a general 4D CSG ray tracer, and
with luck, that will soon be extended to nD. Other current work include
getting the most out of 8 bit displays, and character animation with CSG
systems.
--------
# David B. Wecker - Author of DBW_Render, DIDDLY and other rendering tools
# Digital Equipment Corporation
# 1175 Chapel Hills Drive, CXN1/2
# Colorado Springs, CO 80920-3952
# (719) 260-2794
alias david_wecker wecker@child.enet.dec.com
If people want the current version of DBW (V2.0) for their Amiga, they should
contact:
William T. Baldridge
2650 Sherwood Lane
Pueblo, CO 81005
(BIX: WBALDRIDGE)
--------
David Tonnesen
Dept. of Computer Science
University of Toronto
Toronto, Ontario M5S 1A4
(416) 978-6986 and 978-6619
research: modeling and rendering
e-mail: davet@dgp.toronto.edu (UUCP/CSNET/ARPANET)
davet@dgp.utoronto (BITNET)
I am a Ph.D. student at the University of Toronto and interested in a variety
of graphic topics including ray tracing. Other areas I am interested in
include models of deformable models, global illumination models, models of
natural phenomena, physically based modeling, etc... Basically modeling and
rendering.
--------
Jim Rose, Visualization Research Asst.
Visualization Research Group
Utah Supercomputing Institute
rose@graph.usi.utah.edu
--------
Bruce Kahn - general concepts, portable packages, microcomputer based pkgs.
Data General Corp.
4400 Computer Dr.
MS D112
Westboro MA 01580
(508) 870-6488
bkahn@archive.webo.dg.com
-------------------------------------------------------------------------------
Ray Tracing Abstract Collection, by Tom Wilson (wilson@cs.ucf.edu)
[Tom has done the graphics community a great service in making available (for
free) all the ray tracing abstracts from articles he's collected. If you run
into a ray tracing article title which sounds interesting, you should check
here first to see if it's really what you want before wasting time tracking it
down. --EAH]
The next release of the collection of ray tracing abstracts are ready. I've
put them in several ftp sites (listed below). To get it, do the following:
get rtabs.shar.1.91.Z using binary mode. Uncompress it. Unshar it (sh
rtabs.1.91). Then read READ.ME. If you have any problems, send me e-mail.
The abstracts can be converted to two forms: Latex (preferred) or troff -me.
The filters I've included may help you write your own if you need something
else. I received no feedback concerning problems, so evidently it works for
those who tried it.
USA Sites:
weedeater.math.yale.edu (130.132.23.17) in directory pub/Papers
Craig Kolb <craig@weedeater.math.yale.edu>
karazm.math.uh.edu (132.170.108.2) in directory pub/Graphics
J. Eric Townsend <jet@karazm.math.uh.edu>
iear.arts.rpi.edu (128.113.6.10) in directory pub/graphics/ray
George Kyriazis <kyriazis@iear.arts.rpi.edu>
Australia Site:
gondwana.ecr.mu.oz.au (128.250.1.63) in directory pub/rtabs
Bernie Kirby <bernie@ecr.mu.oz.au>
Finland Site:
maeglin.mt.luth.se (130.240.0.25) in directory graphics/raytracing/Doc
Sven-Ove Westberg <sow@cad.luth.se>
Tom Wilson
Center for Parallel Computation
University of Central Florida
P.O. Box 25000
Orlando, FL 32816-0362
wilson@cs.ucf.edu
--------
Juhana Kouhia notes:
I have converted RT abstract to Postscript format - it's available from
nic.funet.fi pub/graphics/papers directory as wils90.1.ps.Z.
-------------------------------------------------------------------------------
Report on Lausanne Hardware Workshop, by Erik Jansen
There was a Hardware Workshop on the 2nd and 3rd of September in Lausanne.
Three papers on ray tracing are worth mentioning:
%A M-P Hebert
%A M.J. McNeill
%A B. Shah
%A R.L. Grimsdale
%A P.F. Lister
%T MARTI, A Multi-processor Architecture for Ray Tracing Images
%A D. Badouel
%A T. Priol
%T An Efficient Parallel Ray Tracing Scheme for Highly Parallel Architectures
%A Li-Sheng Shen
%A E. Deprettere
%A P. Dewilde
%T A new space partitioning Technique to Support a Highly Pipelined
%T Architecture for the Radiosity Method
The first paper discussed a load distribution based on an image space
partitioning. Additionally the scene was stored in an octree type of space
subdivision of which the first (top) n levels were duplicated over the
processors and stored in their local cache. The other levels of the database
were communicated when needed. Their figures (testpicture "gears") showed
that a local cache of 1/8 to 1/4 of the size of the total database is
sufficient to avoid communication bottle-necks. It was not clear from the
presentation whether these results also hold for more complex scenes.
The second paper discussed a virtual memory scheme that distributed the data
base over the processors in a way that 'ray coherence' is maintained as much
as possible. The left-over memory at the processors is used as a cache.
The third paper discussed a ray coherence scheme that was based on a
subdivision of a ray frustrum in sectors and a comparison of a probablistic
and deterministic method to determine the width (angle) of the sectors.
These papers will be published by Springer in "Advances in Computer Graphics
Hardware", vol. V. (ed. R. Grimsdale and A. Kaufman).
--------------------------------------------------------------------------
New Version of SPD Now Available, by Eric Haines
Version 3.0 of the Standard Procedural Databases is out. The major addition
is the teapot database. Other changes include being able to input a size
factor on the command line, changing mountain.c to mount.c (for IBM users),
and many changes and new statistics in the README file.
The teapot database is essentially that published in IEEE CG&A in Jan. 1987.
A checkerboard has been added underneath it to give it something to reflect &
cast a shadow upon. The checkerboard also reflects the subdivision amount of
the teapot patches, e.g. a 7x7 checkerboard means that each patch is
subdivided to 7x7x2 triangles. Degenerate (e.g. no area, 0 length normal)
polygons are either removed or corrected by the program. The bottom of the
teapot can optionally be removed.
The images for these databases and other information about them can be found
in "A Proposal for Standard Graphics Environments," IEEE Computer Graphics and
Applications, vol. 7, no. 11, November 1987, pp. 3-5. See IEEE CG&A, vol. 8,
no. 1, January 1988, p. 18 for the correct image of the tree database
(the only difference is that the sky is blue, not orange). The teapot
database was added later, and consists of a shiny teapot on a shiny
checkerboard.
The SPD package is available via anonymous FTP from:
weedeater.math.yale.edu [130.132.23.17]
irisa.fr [131.254.2.3]
among others. For those without FTP access, write to the netlib automatic
mailer: research!netlib and netlib@ornl.gov are the sites. Send a one line
message "send index" for more information, or "send haines from graphics" for
the latest version of the SPD package.
-------------------------------------------------------------------------------
Teapot Timings, by John Spackman
I enclose some timing figures for the SPD `teapot', ray-traced at
various degrees of tessellation. All images were rendered at 512x512 with two
light sources. The models were triangulated at a pre-processing stage to
support smooth shading with barycentric co-ordinates. I'm not sure whether
all other conditions were as documented in SPD, but the output looks right!
The host machine was a SUN SPARCStation IPC.
-------------------------------------------------------------------
SIZE FACTOR # TRIANGLES OCTTREE CONSTRUCTION RAY-TRACING
(SECS) (SECS)
-------------------------------------------------------------------
1 58 9.4 841.4
2 248 18.5 832.2
3 570 25.8 837.2
4 1024 35.7 844.8
5 1610 40.8 859.9
6 2328 50.4 864.2
7 3178 56.6 878.8
8 4160 66.5 900.7 (<-- 15 minutes)
9 5274 74.0 911.2
10 6520 81.6 922.7
11 7898 88.7 937.4
12 9408 95.0 954.7
-------------------------------------------------------------------------------
The Very First Point in Polygon Publication, by Chris Schoeneman
(nujy@vax5.ccs.cornell.edu)
A few months ago there was a discussion on point in polygon algorithms
(again), and one netter suggested perturbing vertices to avoid special cases
(using the Jordan curve theorem). This led me to the solution I eventually
found that you had already made.
Anyway, I just found the same solution in CACM, Aug. 1962, p. 434, and I
thought you might be interested to know.
The algorithm as given has an error in the if statement. It should
read:
if (y<=y[i] ...
not
if (y<y[i] ....
The author, M. Shimrat, doesn't check the horizontal bounds of the edge to
trivially accept or reject the intersection, but this, of course, isn't the
key to the solution.
So much for the patent. :-)
-------------------------------------------------------------------------------
The Acne Problem, by Christophe Schlick (schlick@geocub.greco-prog.fr)
What is Ray-Tracer Acne (RTA) ?
-----------------------------
As defined by Eric Haines in an early Ray-Tracing News, RTA is those black
dots that appear sometimes on a ray-traced image. RTA can result from two
different phenomena:
Case 1: When a ray intersects a surface S, some floating round-off can bring
the intersected point P inside the surface (Figure 1). So, when a reflected
ray or a light ray is shoot from P, it will intersect S and P will be in
shadow.
A common solution to this problem is to let some tolerance (T) for the inter-
section test: when an intersection point M is found, the distance D between
the origin of the ray and M is computed, and compared to T, the point is
rejected if D < T. The problem with that method is that T is an absolute
value, coded in the source code and sometimes not adapted for a specific
scene. A solution could be to scale T by the global diameter of the scene but
there will still be some scene for which it wouldn't work (for instance, a
scene will very big and very small sphere).
Case 2: This case can only appear when rendering an object composed of
polygons with interpolated normal vectors (Phong's method). This pathological
case was first described by Snyder & Barr at the SIGGRAPH 87 conference. When
a ray intersects a point P, the normal vector Np is interpolated from the
vertices normals thanks to the barycentric coordinates (Figure 2). Thus a
reflected ray or a light ray shot from P according to Np (direction Out in
Figure 2) can intersect another facet (Q on Figure 2).
Here the tolerance solution doesn't work because Q can be arbitrarily far from
P (it depends on the surface curvature and the size of facets). Thus Snyder &
Barr proposed to move P from the surface along Np by a certain distance D, and
to consider the new point P' as the intersection point from which other rays
are shot. Again, D is hard-coded and there would be some scenes for which D
is too high or too low.
Out
Out In Na \ Nb
\ / \ \ /
\ / \ \Q / Np
-------------- S \--------*-/ _/
\ / A B\ _/
* \/___________ In
P P\
\______Nc
C
Figure 1 Figure 2
The solution I propose is easy to implement, and robust whatever the scene.
If you examine Figure 1 and 2, you can see that, in the two case the error
comes from a sideness problem: a ray that is assumed to be outside S finds an
intersection that is inside S. In a ray-tracer, you are always carrying (in
the ray structure) a pointer to the media through which the ray is currently
traveling --- that pointer is needed for refraction. So when intersecting a
surface, you always know the current media. When you find a ray intersecting
a surface by the inside (negative cosine), the only thing to do is to test the
current media with the media inside the surface (checking the pointers). If
the two medias are different, there is a sideness problem and the point must
be rejected. That leads clearly to the following algorithm:
When a ray R traveling through a media M, with a directing [e.g. reflecting]
vector V hits a point P with a normal vector N on a surface S do
Begin
Compute Cos = -N.V (the cosine between the ray direction and normal vector)
If Cos > 0 /* R outside S */
then no problem
else /* R inside S */
if M != S then reject the point /* Sideness error */
else no problem
End
The cost of that method is a dot product between V and N. For reflection
rays, that dot product has to be done in the shading phase, so if you store
the result of the cosine in the ray structure, there will no extra cost. But
for light rays, the dot product is an extra cost. Compared to Snyder & Barr's
method, the cost is lower because moving a point along a normal vector needs a
linear combination (3 additions, 3 multiplications). For non-polygonalized
surfaces, the tolerance method is cheaper, but isn't robust.
Well, make your choice. And let me know your comments (and flames !)
--------
From Eric Haines:
Note that a third source of acne is from bump mapping - essentially it's
the same problem as in case 2, but this problem of the reflection ray passing
through the object can then happen to any object, not just polygons with a
normal per vertex.
Personally, I solve this problem by doing the check Christophe recommends,
i.e. check the dot product of the normal and the reflection ray. If the
reflection ray is bad, I solve this by adding some portion of the normal to
the reflection ray which puts the ray above the tangent plane at that point.
This can result in the reflections getting a bit squished on these bad pixels,
but this is much better than seeing black acne pixels.
Christophe's solution of rejecting intersections if the media does not
match is fine if you have well-behaved users, but our system assumes the user
can do whatever foolish thing he wants with surface definitions (my favorites
are us allowing different indices of refraction and different transmission
colors for front and back faces).
How do the rest of you solve this problem?
-------------------------------------------------------------------------------
Shirley Thesis Available via Anonymous FTP, by Pete Shirley
I have put a postscript copy of my thesis "Physically Based Lighting
Calculations for Computer Graphics" on anon ftp on cica.cica.indiana.edu
(129.79.20.22). I have broken the thing into several files and compressed
them. Each file, when uncompressed, should be a stand-alone postscript file.
The whole thing is about 180 pages long, so please don't kill any trees if you
don't really want it!
WARNING: The thesis files have many postscript figures in it. It is a real
printer hog. Please be thoughtful about printing and storing the thing.
I have also put several 24 bit ppm image files in compressed form. Don't
forget to set ftp in "binary" mode.
If you want this thesis and cannot get/print these files, please don't ask me
for alternate formats until after Dec. 15th. Thanks. It will also be
available as a U of Illinois tr (I don't know when).
The directory is pub/Thesis/Shirley.
Pete Shirley
Indiana U
shirley@cs.indiana.edu
"I didn't say it was good, just long!"
[This thesis is, among other things, a great survey of most every rendering
technique to date. "wine.ppm.Z" is an excellent image, even with the week+ of
computation. - EAH]
Thesis files:
ch1ch2.ps.Z (125K) Title page, etc.
Chapter 1 Introduction
Chapter 2 Basic Optics
ch3ch4.ps.Z (105K) Chapter 3 Global Illumination Problem Formulation
Chapter 4 Surface Reflection Models
ch5a.ps.Z (221K)
ch5b.ps.Z (247K) Chapter 5 Image Space Solution Methods
ch6a.ps.Z (261K)
ch6b.ps.Z (250K) Chapter 6 Zonal Solution Methods
ch7ch8ch9.ps.Z (123K) Chapter 7 Extensions to Basic Methods
Chapter 8 Implementation
Chapter 9 Conclusion
app.ps.Z (44K) Appendices
bib.ps.Z (30K) Bibliography
Picture files (ppm format, Makefile, seeppm.c viewing on SGI Iris.)
bump.ppm.Z (1.3M) 1024 by 768 camera effects, bump map, indirect lighting.
gal.ppm.Z (1.2M) 1024 by 768 solid textures, indirect lighting
dense.ppm.Z (.2M) 512 by 384 dense media(8 volume zones for indirect light)
sparse.ppm.Z (1.2M) 1024 by 768 sparse " " "
turb.ppm.Z (.3M) 512 by 384 uneven " " " "
lamp.ppm.Z (.8M) 1024 by 768 diffuse transmission, indirect lighting
wine.ppm.Z (1.1M) 1024 by 768 fresnel reflection, bw ray tracing
-------------------------------------------------------------------------------
Some Thoughts On Anti-aliasing, by Zap Anderssen, Eric Haines
From Zap:
About Anti-aliasing: The "standard" way of doing adaptive anti-a (refered to
as AA from now on, I'm lazy) is to check the color of last pixel and pixel
above or similar, and subdivide if they differ more than "this-n-that" from
eachother. Although you remember that I said once you should check what
OBJECT you hit (i.e. ignoring the color) and use that as subdiv criteria, and
you posted a mild flame that it wouldn't work on things like a patch mesh
since we spend useless time at all edges that are same all the same....
Well, since I think that all anti-aliasing for texturemapping should be done
in the texture mapping functions (for which I have a nasty trick involving the
angle to the normal vector of the surf and distance to screen e.t.c.) you
should only need extra rays at object edges.
But consider, what makes a surface change color abruptly? It's one of three
things:
* Shadow hits
* Texture map changes color
* Normal veccy moves a lot.
Ok, so here is my idea: You don't save the COLOR for last pixel, but the
normal vector. When this deviates more than this_n_that, you supersample.
Then you say "hey, sucker that doesn't work! Edges may be at different levels
or so but still have the same normal veccy" and to that I say, sure thang,
multiply the normal vector with the distance to the eye, and use that for a
criteria? Well, we lose the AA on the shadows, regrettably, but we get
another nice criteria.... Just a stupid idea, I know there are flaws, like
what happens if this Red surface is adjoining a blue one (i.e. color diff in
geometry rather than texture map?) This shouldn't be allowed ;-)
Seriously, there must be ways to fix this? I NEVER liked the idea of AA'ing
on the color diffs, since texturemaps may introduce heavy diffs even if no
extra rays are really needed....
Any Commentos?
--------
Oddly, I was just writing up my views on anti-aliasing yesterday,
though for different reasons. I agree, it would be nice to avoid subdivision
on texture mapped guys. Let's see, we have aliasing due to:
edges of objects
shadow boundaries
rapidly changing reflections/refractions or highlights
texture maps
So, we could do something like separate out these various factors and do tests
on each. The trick is that there's interaction between these things (shadows
and texture maps' effects get multiplied together: rapidly changing textures
in the dark don't matter) and that separating these out gives some weird
problems (say I say "if contributions absolute values vary by more than 10%",
and then I find that my highlight varies 5%, my reflection varies 7% and my
shadow varies %4, should I antialias? If yes, then why did I bother to
compute these fractional contributions. If no, then the color really is
varying a lot and should be supersampled). One advantage of separating stuff
out is for texture maps sampled with area methods (e.g. mipmapping) - if the
surface change ratio is separate from all the other ratios, then we could
simply say "ignore the surface change ratio" if we hit an area-sampled
textured object.
I don't have a good answer (yet?), but am interested to hear your ideas.
Using the normal is interesting, but it feels a bit removed from the problem:
on my "balls" (sphereflake) database, the normals change rapidly for the tiny
spheres, but say all the spheres just reflected things (no diffuse, no
highlights). Much of the spheres' reflections is the background color, which
doesn't change at all. So super-samples which merely also hit the background
in this case don't add anything, just waste time. By checking how much the
reflection color changed, instead, we could shoot less rays.
Variance on something like the normal might be worth tracking, as you point
out, but what if you're, say, viewing a surface which is in shadow? The
normal varies, but the shading doesn't (no light), so you waste effort.
Another interesting problem is anti-aliasing bump maps: do you really want to
do much blending, which would then smooth out the bumps?
-------------------------------------------------------------------------------
New VORT Release, and the VORT Chess Set, by Eric H. Echnida, David Hook
Eric H. Echidna (echidna@munnari.oz.au) writes:
Vort 2.0 is now 'officially' available from the following sites:
gondwana.ecr.mu.oz.au [128.250.1.63] pub/vort.tar.Z
munnari.oz.au [128.250.1.21] pub/graphics/vort.tar.Z
uunet.uu.net [192.48.96.2] graphics/vogle/vort.tar.Z
(uucp access as well ~ftp/graphics/vogle/vort.tar.Z
draci.cs.uow.edu.au [130.130.64.3] netlib/vort/*
Australian ACSnet sites may use fetchfile:
fetchfile -dgondwana.ecr.mu.oz pub/vort.tar.Z
or obtain it from the Australian Netlib at draci.cs.uow.oz
==================
VORT - a very ordinary rendering tool-kit. Version 2.0
VORT is a collection of tools and a library for the generation and
manipulation of images. It includes a ray tracer, pixel library, and
utilities for doing gamma correction, median cuts, etc...
The current distribution is described as follows:
art - a ray tracer for doing algebraic surfaces and CSG models. Art
supports the following primitives: polygons, offfiles, rings, disks,
torii, superquadrics, spheres, ellipsoids, boxes, cones, cylinders,
and algebraic surfaces. Tile patterns can be mapped onto all of the
above except algebraics, boxes, and offfiles. The following textures
are supported, bumpy, wave, marble, wood, ripple, fuzzy, stucco,
spotted, granite, and colorblend. The ray tracer uses an
acceleration technique based on the spatial kd-tree.
tools - some utilities for fiddling around with image files, and converting
between various formats. These include tools for converting nff files
to art format, and vort files to ppm format (and ppm to vort).
docs - various bits of doco on the tools
lib - the pixel library files - this has only been developed to the
point needed to read and write display files.
old - this contains a program for converting image files from 1.0
format to 1.1.
sun - a set of display programs for a sun workstation.
X11 - a set of display programs for a 256 color X machine.
iris - a display program for an Iris workstation.
pc - a set of display programs for a PC with VGA Extended Graphics.
movies - some C programs for generating some sample animations.
tutes - some C programs for generating some animations that demonstrate
the texturing.
text3d - some C routines that read in the hershey fonts provided with VOGLE
and use them to generate 3d text. Example input files are provided.
--------
There are several scenes and output images from the raytracer `art'
available on gondwana.ecr.mu.oz.au [128.250.1.63] in the directory pub/images.
These images are 8 bit sun rasterfiles and can be converted to other formats
using (for example) pbmplus.
There are also some simple 36 frame movies in the directories
pub/movies/* . These files are in VORT format and can be displayed with the
movie programs that come with VORT or can be converted to another format using
the vorttoppm program that comes with VORT.
--------
[Another package available & of interest:]
VOGLE 1.2 fixes some bugs and includes some speed ups from previous versions
of VOGLE. Specifically, all matrix stack manipulations are now 'done in
place' to save time.
VOGLE stands for "Very Ordinary Graphics Learning Environment".
VOGLE is a device portable 3D graphics library that is loosely based on the
Silicon Graphics Iris GL. VOGLE also supports 3D software text in the form of
Hershey vector fonts.
--------
David Hook notes:
> 'vort' package includes a chess set (it's the same one as the set at DEC).
There is a better chess set in pub/chess20.tar.Z on gondwana.ecr.mu.oz.au
(128.250.1.63) in the anonymous ftp area. These pieces were also done by the
same person (Randy Brown) who did the ones that are in VORT, but they are much
more detailed.
--------------------------------------------------------------------------
Best (or at least Better) of RT News, by Tom Wilson
I've scrunched all of the 1988 RTNews. I thought I would post to the net to
see if anyone else would want it. What I've removed is: names/addresses,
product reviews, reports on tracer bugs/fixes, and anything else that is
"out-dated." I've taken this approach since these programs probably no longer
have the bugs and errors. I don't know if many people are going to want the
scrunched versions, but I just wanted basic RT info to print and save. Some
of the issues weren't scrunched much (mainly the first few), but some are
about 1/3 the size (90,000 => 30,000 bytes).
Tom
wilson@cs.ucf.edu
-------------------------------------------------------------------------------
At Long Last, Rayshade v4.0 is Available for Beta-testing, by Craig Kolb
(kolb@yale.edu)
The distribution is available by anonymous ftp from weedeater.math.yale.edu
(130.132.23.17) in pub/rayshade.4.0 as either "rayshade.4.0.tar.Z" or the 16
compressed tar files in the subdirectory "kits@0".
Please direct comments, questions, configuration files, source code, and the
like to rayshade@weedeater.math.yale.edu. If you get semi-serious about using
rayshade, drop us a line and we'll add you to our mailing list.
Thanks to everybody who contributed to this and previous versions of rayshade,
and to those of you who are willing to provide feedback on this Beta release.
>From the README file:
------
This is the Beta release of rayshade version 4.0, a ray tracing program.
Rayshade reads a multi-line ASCII file describing a scene to be rendered
and produces a Utah Raster Toolkit "RLE" format file containing the
ray traced image.
Rayshade features:
Eleven primitives (blob, box, cone, cylinder, height field,
plane, polygon, sphere, torus, flat- and Phong-shaded triangle)
Aggregate objects
Constructive solid geometry
Point, directional, extended, spot, and quadrilateral light sources
Solid procedural texturing, bump mapping, and
2D "image" texture mapping
Antialiasing through adaptive supersampling or "jittered" sampling
Arbitrary linear transformations on objects and texture/bump maps.
Use of uniform spatial subdivision or hierarchy of bounding
volumes to speed rendering
Options to facilitate rendering of stereo pairs
This is Really and Truly a Beta release: No patches will be issued to upgrade
from this distribution and the 'official' release. The documentation is
spotty, and there is no proper 'man' page.
There are many differences between rayshade versions 3.0 and 4.0. In
particular, the input syntax has changed. Input files created for version 3.0
must be converted to version 4.0 syntax using the provided conversion utility
(rsconvert).
Rayshade v4.0 Beta has been tested on several different UNIX-based computers,
including: SGI 4D, IBM RS6000, Sun Sparcstation 1, Sun 3/160, DECstation,
Apollo DN10000. If your machine has a C compiler, enough memory (at least
2Mb), and runs something resembling UNIX, rayshade should be fairly easy to
port.
[...]
It is hoped that the 'official' release will include a library that provides a
C interface to the various ray tracing libraries. While there is currently no
documentation for the libraries, it should be easy for you to add your own
primitives, textures, aggregates, and light sources by looking at the code and
sending mail if you get stuck.
It is also hoped that the modular nature of the primitive, aggregate, texture,
and light source libraries will make it possible for people to write their own
code and to "swap" objects, textures, and the like over the net. The object
interfaces are far from perfect, but it is hoped that they provide a
reasonable balance between modularity and speed.
Additional rayshade goodies are available via anonymous ftp from
weedeater.math.yale.edu (130.132.23.17) in pub/rayshade.4.0. If you have
contributions of new objects, textures, input files, configuration files, or
images to make, feel free to send us email or to drop off a copy via ftp in
the "incoming" directory on weedeater.
-------------------------------------------------------------------------------
Parallel Ray Tracer, by Kory Hamzeh, Mike Muuss, Richard Webb
Parallel Raytracer Available, Kory Hamzeh (kory@avatar.avatar.com)
I wrote a parallel raytracer (named 'prt') a while back with the following
features:
- Runs on multiple heterogeneous machines networked together
using TCP/IP.
- Crude load balancing.
- Primitives:
- Polygons
- Spheres
- Hallow Sphere
- Cones
- Cylinders
- A object that can be expressed in a quadratic form
- Rings
- Shading:
- Gourard
- Phong
- Whitted
- Rendering:
- Simple: one ray per pixel
- Stochastic sampling (jitter)
- Instances of objects.
- Input format:
- An extension of nff. I have written a filter which
will convert NFF files to prt format.
- Output format:
- MTV format (24 bit).
Note that prt is a parallel raytracer which spawns off children over multiple
machines to distribute the work. I have only used it on five Sun
Sparcstations and have gotten excellent performance. I'm not aware of any
other public domain parallel raytracers other than VM_pRay (which, I believe,
runs only on a specific platform).
--------
Prt version 1.01 is now available from the following sites via
anonymous ftp:
apple.apple.com in /pub/ArchiveVol2/prt
iear.arts.rpi.edu in pub/graphics/ray/prt
If you have a copy of version 1.0, I would recommend that you get a copy of
the newer one. I will *not* post it again in alt.sources. If you can't ftp
it, send me mail and I will mail you a copy.
Version 1.01 had some minor bugs fixed and I included some info that I had
forgotten to put in the first set of docs.
--------
Michael John Muuss (mike@BRL.MIL) writes:
> [ lots of good stuff about BRL-CAD deleted ]
>
> While not "super sophisticated", the load balancing algorithm is
> non-trivial. It assigns pixel blocks of variable size. Three
> assignments are outstanding to each worker at any time, to
> pipeline against network delay. New assignment size is tuned,
> based upon measured past performance (weighted average with variable
> weighting, depending on circumstances).
and Kory responds:
Prt's load balancing is not as sophisticated as BRL-CAD's. Prt simply
multiplexes the scanlines across the different machines. The slowest machine
on the network will be the bottle neck.
When I get a chance, I would like to use the same techniques used in BRL-CAD.
I think that it is the best load balancing for a raytracer.
--------
Timings of PRT, by Richard Webb
Here is a snippet of a bug report I sent off to kory@avatar.com regarding his
"prt1.01" parallel ray tracer. Note that I ran these test on your NFF SPD
version 2.4. I'll grab v3.0 and re-run if you think it will make any
difference. I ran the test on a network of 25 Sun4's (both SparcStation1's
and 1+'s as well as a Solbourne and a few SunServers). Some machines finished
in about 1/2 of the elapsed time. The time is as reported by the PRT program.
TEST | TIME (mm:ss)
----------+--------------
balls | 10:32
gears | 16:49
mountain | 9:27
rings | 13:05
tetra | 0:59
tree | 4:05
It would be nice to have some texturing capability in NFF, but then I guess
that is somewhat too sophisticated for a "Neutral" format. The SIPP2.0 image
"isy90" marble teapot on a granite base looks very good except there are no
shadows. I hope someday we will have fast Renderman parallel "cookers"
generating nice compressed video sequences.
-------------------------------------------------------------------------------
Distributed DKB, by Jonas Yngvesson
DDKB (distributed dkb) has the same primitives, shading and input format as
DKB (for obvious reasons). This includes very nice support for solid
texturing.
Antialiasing differs slightly. DKB uses an adaptive jittered supersampling,
but in DDKB, each server only has access to one scanline at a time. This
means adaption is done in the x-direction only.
> - Output format:
> - MTV format (24 bit).
Here I have used a mix between the MTV-format an the QRT-format used in DKB.
An MTV-header is followed by the scanlines in QRT-format. Each line tagged
with its line number (this is because the lines are stored in the order they
are finished by the servers and must be sorted before display).
>Note that prt is a parallel raytracer which spawns off children over
>multiple machines to distribute the work. I have only used it on five
>Sun Sparcstations and have gotten excellent performance. I'm not aware
>of any other public domain parallel raytracers other than VM_pRay
>(which, I believe, runs only on a specific platform).
Yeah! We have tried DDKB running on 55 sparcstations (then we ran out of file
descriptors, perhaps we should use UDP instead of TCP). Pretty good
performance indeed. Unfortunately DKB is not a terribly fast tracer in itself
and I have no time to hack around in it.
I'm not very willing so send this thing out though. Partly because it is
still only a hack, and partly because I have not contacted David Buck and
asked what he thinks about the whole thing.
jonas-y@isy.liu.se
...!uunet!isy.liu.se!jonas-y
University of Linkoping, Sweden
-------------------------------------------------------------------------------
Quadrangle Tessellation, by Christophe Schlick
Why I believe that a quadrangle tessellation is better than a triangle one.
---------------------------------------------------------------------------
Tessellating objects using triangles has become a very popular method in the
ray-tracing world, at least since the classical paper of Snyder & Barr (SIG
87) The classical idea is to start from a parametric surface f(u,v) and
regularly sample the two parameters u and v. That gives a mesh composed of
quadrangles ABCD where A = f(u, v), B = f(u+du, v), C = f(u+du, v+dv) and D =
f(u, v+dv). Then the only thing to do is to cut the quadrangle into two
triangles ABC, CDA for instance.
D ------------- C
| _/\
| _/ \
| _/ \
| _/ \
| _/ \
| _/ \
|/ \
A -------------------- B
Using triangles instead of quadrangles has one main advantage: speed Indeed,
computing the intersection between a ray and a triangle, and getting the
barycentric coordinates (needed for interpolation) is simply a linear system
of two equations. An optimized algorithm would only take very few floating
point operations (about 8 multiplications after the ray/plane intersection)
But, using triangles instead of quadrangles has also several drawbacks:
First, there a two solutions to decompose a quadrangle into two triangles.
There is no absolute choice, and results will be very different when you take
ABC-CDA instead of DAB-BCD (especially if the curvature of the surface is
high).
But the main drawback of triangles is that the isoparametrics (u constant or v
constant) are not preserved (see figure). Thus every texture mapping (or
radiosity reading, if you use a radiosity first pass in your system) will be
deformed.
u=0 u=.5 u=1 u=0 u=.5 u=1
D ------------- C D ------------- C
| \ \ | | _/\
| { \ | | _/ \
| \ \ | |_/ \
| { \ | _/ \
| \ \ | _/ \ \
| { \ | _/ \ \
| \ \ |/ \ \
A -------------------- B A -------------------- B
u=0 u=.5 u=1 u=0 u=.5 u=1
Isoparametric u=.5 using 1 quadrangle and 2 triangles
"Three is bad, four is good" Dustin Hoffman (in RainMan)
But there is a drawback using quadrangles instead of triangles: speed Indeed,
computing the intersection and getting the (u,v) parameters of the
intersection point consists in solving a non-linear system of equations. And
there is a square root. Yerk! (see Haines' chapter in "Introduction to Ray
Tracing")
Fortunately the square root can be avoided in many cases! Tessellating
classical scenes will create a lot of very symphatic quadrangles: squares,
rectangles, parallelograms and trapezoids. For instance, tessellating a
surface of revolution (or more generally a surface created by sweeping a curve
around an axis, according to another curve) will create only trapezoids.
For squares, rectangles and parallelograms, (u,v) are given by a linear
system. For trapezoids, (u,v) are given by a system of one linear equation
and one non- linear equation. For all that cases, finding directly the
intersection between the ray and ONE quadrangle is LESS COSTLY than finding
the intersection between the ray and TWO triangles.
Another advantage of dealing with quadrangles vs triangles is the memory cost.
There are less primitives to create, to store, to transform, to put in
voxels...
Finally, never forget that for shadow rays, (u,v) are not needed. Thus using
a simple intersection test (Jordan test) will be faster, for the same result.
--------
reply from Eric Haines:
Just to be a devil's advocate, I thought I'd bring up some problems
with quadrilaterals versus triangles. I personally like quadrilaterals,
especially because of the strange shading artifacts from triangles. However,
we sometimes use triangles, such as in the situation where the quad mesh gives
quadrilaterals that are not totally planar (i.e. the four points don't lie in
a single plane). This is ill-defined, and so we must triangulate.
A more important time for triangulation is in animation. If you use
Gouraud interpolation for shading your primitives, triangles are rotation
invariant, while quadrilaterals are not. As such, if you make a film of some
object made of quadrilaterals rotating, you can see the quadrilateral shades
change over time.
--------
Christophe's reply:
Well, non planar quadrilaterals surely can be a problem. But when
rendering a scene there are so much approximations that are made (on the
illumination model, on the shading technique, on the normal vector
computation, ...) So, why should it not be allowed to do some approximation
about the geometry and replace a non planar polygon by a planar one?
The method I use is the following. When sampling your object along
the u and v coordinates, test about the "planarity" of the quadrangle. One
technique could be to compute the solid angle subtended by the 4 vertex normal
vectors. Another technique could be to compute the max distance from a vertex
to the "approximation plane" (AC x BD). When the solid angle or the max
distance is greater than a given tolerance, then subdivide the quadrangle
(quadtree-like scheme) until the tolerance is reached. Of course, every one
knows that patch cracking (as defined by Catmull) should occur. But
practically I you insure that two adjacent quadrangles are at neighboring
levels in the quadtree, cracking can not be visually detected. (I used that
trick intuitively though I saw recently a paper on it, can't remember
where...)
Concerning Gouraud shading, rotation invariance of triangles vs
quadrangles is not due to the number of vertex but to the fact that Gouraud
shading use an interpolation in screen space. I should avoid like the plague
every method that interpolates in screen space! Effects are well known:
perspective distorsion, rotation dependence, and so on... I really think that
screen space Gouraud & Phong shading would disappear soon, and be replaced by
their equivalent object space shading.
I haven't seen papers about that fact, but I'm sure that sure
techniques are already in use. The idea is to use a dicing technique (as in
the Reyes rendering system) to create micro-quadrangles by sampling a
quadrangle along u and v coordinates. The number of samples of the u
coordinate is proportional to the length of AB and CD edges (similarly for v
with BC and DA edges) The only thing to do is then to visit every micro-quad
vertex (double loop over u and v), interpolate incrementally either x, y, z,
r, g, b (Gouraud) or x, y, z, nx, ny, nz (Phong) and average samples that fall
in the same pixel.
The technique isn't more complicate as screen space interpolation, and
can be hardware coded as well (incremental scheme with integer arithmetic) The
ONLY advantage is Gouraud and Phong today, is that they are hardware coded so
outperforming every software algorithm. But it is perhaps time for chip
designer to realize that there are other --- and better --- shading methods
that support hardware implementation as well! For instance, when will we see
a chip that does incremental voxel traversal for ray tracing ?
--------
Eric's reply:
Interesting comments! We do similar things with non-planar
quadrilaterals, that is, we find if something is not flat by checking its
tolerance from some ideal plane for it. If the tolerance is noticeable, we
take special measures.
I agree that it would be nice if Gouraud shading was replaced with
something else. Renderman micro-facets is certainly one way to go. The trick
is, what if you are dealing with a surface that (a) does not have a natural
parameterization (that is, [u,v] values are not attached to it) or (b) the
surface has 5 or more vertices? It's not all that clear how to combine the
various vertex samples to get a proper shade. The problem is admittedly
ill-defined, but some answers look better than others. Doing a full weighted
average depending on the distance to all vertices from a given point on the
surface has been proposed, but this takes forever for complex polygons.
A voxel walker might be a nice hardware addition someday, but I think
the main problem with it is that it's very special purpose. Most hardware
manufacturers don't want to make highly specialized chips if the market is
small. Someday I suspect things will get fast enough that ray tracing becomes
popular because it's fairly quick to do - at this point, paradoxically, we'll
probably see specialized hardware that makes ray tracing much faster still.
However, right now I see companies like AT&T Pixel Machines getting little
business for their ray tracers - everyone likes the images, but few seem to
want to get involved making them for real!
-------------------------------------------------------------------------------
New Release of Radiance Software & Bug Fixes, by Greg Ward (gjward@lbl.gov)
I have just put together a new release of Radiance, 1.3. In addition to the
IES luminaire translator included separately on some tapes, 1.3 contains
several improvements, including faster runtimes for oconv with instances, a
driver for NeWS (and thus SGI's window system), better memory use on some
machines, fisheye views, and a translator for Architrion. I plan to release
more CAD translators, specifically one for DXF, in the near future.
The new tar file takes up over 36 Mbytes, because it includes compiled
versions for Sun-3, Sun-4, IRIS, DECstation and MacIntosh (running A/UX 2.0),
so you will need to send a large tape to get a copy. (Of course, you do not
need to load the binaries on your machine if you don't want them.) As before,
full C source code is provided for all programs.
Send your tapes to:
Greg Ward
Lighting Systems Research
Lawrence Berkeley Laboratory
1 Cyclotron Rd., 90-3111
Berkeley, CA 94720
--------
Thanks to an astute user, I have learned of a rather serious bug in the IES
luminaire data translator, ies2rad. It involves the improper conversion of
type B photometry, and some types of asymmetric fixtures.
Anyone who is currently using this program, or plans to use it in the future,
is advised to get the corrected source from me directly.
-------------------------------------------------------------------------------
Radiance Timings on a Stardent, by Eric Ost (emo@ogre.cica.indiana.edu)
Here is the most recent set of timings which resulted from running the
Radiance batch ray-tracer on tuna. Note that each rpict.* is a different
instance of the ray-tracer. The differences are
name compiled with
rpict.noO -- no optimizations selected
rpict.01 -- -O1, common sub-expression, etc., optimizations performed
rpict.O2 -- -O2, vectorization optimizations performed
rpict.O3 -- -O3, parallelization optimizations performed
Command:
rpict.X -vp 52.5 6 58 -vd .05 -.6 -.8 -vu 0 1 0 -vh 35 -vv 35 \
-av .1 .1 .1 -x 1000 -y 1000 scene.oct > scene.raw
System: Stardent Titan-3000
4 25MhZ R3000 processors
32 Mb main memory
file input read from NFS mounted file-system
file output written to a local-disk file-system
timing batch ray tracer rpict.noO
real 4:14.1
user 4:04.1
sys 8.5
timing batch ray tracer rpict.O1
real 4:14.4
user 4:04.4
sys 8.1
timing batch ray tracer rpict.O2
real 4:27.1
user 4:18.2
sys 6.8
timing batch ray tracer rpict.O3
real 4:15.4
user 16:37.5
sys 17.6
Simply optimized code does not seem to have much advantage over unoptimized
code. Vectorization appears to slow things down, but running on all 4
processors seems to recover nearly all of the real-time performance that was
lost. The fact that all of these results (per-processor) are fairly close
probably indicates that to obtain significant benefits from
vectorization/parallelization modification of the implementation itself is
required. A run-time subroutine/loop histogram obtained using 'prof' has
indicated several instances where in-lining code sequences may improve
performance; though, exactly how much improvement will be obtained remains to
be seen.
--------
Further information from Eric Ost:
Subject: Misc. Radiance 1.3 benchmarks
Program: rpict, version 1.3,
Date: February 22, 1991
This benchmark involves the example 1000x1000 picture described in
../ray/examples/textures as rendered from the associated makefile,
../ray/examples/textures/Makefile.
-----------------------------------------------------------------------------
(all times are in seconds)
System Real User System
-----------------------------------------------------------------------------
Sun-4/330 (ogre) 10:27.9 8:10.5 8.5
SGI Personal Iris (pico) 5:41.0 5:26.5 1.6
-IBM RS6000 model 320 (off-site) 4:19.2 4:13.9 0.3
+Stardent Titan-3000 (tuna) l 4:13.9 4:04.3 7.8
-IBM RS6000 model 540 (off-site) 2:50.3 2:45.2 0.2
*Stardent Titan-3000 (tuna) 1:52.2 1:45.7 4.8
-----------------------------------------------------------------------------
Legend:
+[Note: The entire image was rendered on 1 processor]
*[Note: Each processor renders 1/4 image, so this is the MAX of all timings.
The -x, -y, -vv, and -vh parameters were adjusted accordingly.]
-[Note: The IBM timings were performed by our IBM representative off-site.]
System Configurations:
Architecture Operating System RAM Processor #
-----------------------------------------------------------------------------
Sun-4/330 SunOS Release 4.0.3_CG9 24 MB 20 MhZ SPARC (1)
SGI Personal Iris IRIX System V Release 3.2 16 MB 20 MhZ R3000 (1)
Stardent Titan-3000 Unix System V Release 3.0 32 MB 25 MhZ R3000 (4)
IBM RS6000 model 320 Unix System V Release ? 16 MB 20 MhZ RS6000 (1)
IBM RS6000 model 540 Unix System V Release ? ?? MB 30 MhZ RS6000 (1)
-----------------------------------------------------------------------------
I would be happy to answer any questions pertaining to these timings. In no
way am I suggesting that these timings are the best possible for a given
architecture; rather, they were the ones I obtained and may or may not be
repeatable at another site. No special fine-tuning was done either to the
system or to Radiance before performing these timings. Each system was
relatively quiescent and therefore had a minimal load average.
-------------------------------------------------------------------------------
RTSYSTEM Fast Ray Tracer, by Patrick Aalto
The initial post:
I just finished a small demo I have been working on a couple of months. It
performs real-time ray-tracing and shading (a sort of mixture of them both) on
an IBM PC-compatible computer with VGA graphics. I find it pretty impressive
(although the environment is pretty simple: It has a planet, a moon and a
sun). It runs at 70 frames/second on my 80386/20 Mhz machine.
--------
This RTSYSTEM (Ray-Traced System) is a small demo that uses my new superfast
raytracing algorithms. It works on register-compatible VGA cards only, using
the non-standard 320x400x256 screen mode. This mode is highly suitable for
animation, since it features two separate video pages and lots of colors.
Nearly all common VGA-cards work quite well in this mode.
This demo shows a moon orbiting a planet. The viewer is on a distant moon of
the planet, and is looking 'up' towards the planet and the other moon. A
distant sun can also be seen from time to time. It is very easy to run this
demo; just type RTSYSTEM and it starts to run. After a second or two, a green
number will appear on the bottom- right corner of the screen. This number
tells you how many frames per second your computer is fast enough to draw. I
programmed this demo such, that it will just run at the maximum 70
frames/second on my 80386/20 Mhz computer. A slow VGA-card or a slower CPU
will not reach 70 frames/second, but even a 33 Mhz 80486 - machine will not
run faster than 70 frames/second, since this is the fastest hardware refresh
rate of a VGA display at this resolution. To quit the demo, just press the
ESC key.
The method of rendering shaded objects usually requires a lot of computation,
since the correct color value has to be computed separately for every single
screen pixel. The color value of a certain pixel depends on the amount of
light (and it's color) this pixel transmits towards the eye of a viewer.
Since each pixel represents some small portion of some physical object in the
3D image space, the transmitted light can be calculated based on the
properties of this physical object.
When light hits a smooth surface, a portion of it is reflected, and the rest
is transmitted into the object (if the object is even slightly transparent).
The direction of the reflected light is given by the Law of Reflection: the
angle of the reflection direction r, is equal to the angle of incidence , and
will be in the same plane as the incident vector v and a surface normal vector
N. Vector r can be determined using vector arithmetics:
r = v + 2Ncos = v - 2N(vN)
To calculate a dot product of two vectors requires normally 9 multiplications,
1 division and 1 square root. All this for every pixel in the object!! (The
planet in the middle of the screen has nearly 2800 pixels, by the way.) This
demo uses a highly sophisticated technique to calculate the color of a certain
pixel with only one table lookup and one addition per pixel! Everything is
also done using only integer values (16 and 32 bit), obviously.
Other new techniques in this demo include a 3D-modification of a well-known
Bresenham's circle algorithm to calculate all the X, Y and Z values of a ball
using only integer additions. (The standard method uses the ball equation
X+Y+Z=R, from which the values for Z-coordinates, for instance, can be
determined if all the other values are known. This includes a square root and
3 multiplications per every (X,Y) pair.)
Still another new technique is to apply trigonometrics to the 'ray-sphere
intersection' problem. This does not reduce the needed computations very
much, but gives correct results with much smaller intermediate results (VERY
important when dealing with only integer resolution).
It is interesting to note that even a standard 386 machine with a VGA-card can
perform simplified ray-tracing in realtime. All it takes is some
optimizations on the algorithms used.
An interesting thing is the optical effect called 'Mach band effect'. If you
look closely at the planet surface, you will notice all sorts of different
patterns on it, which change rapidly as the sun moves. These patterns are
merely an optical illusion, caused by the way the retina of our eyes function.
Since there are only 64 different shades of grey (from black to white)
available on a VGA display, the eye is sensitive enough to register the small
change between two neighboring pixels, thus creating a 'pattern' on the
screen.
Studying this demo you can also find out what 'anti-aliasing' means. Look at
the edge of the planet when it is fully lit. You will easily see the
'jaggies'. The planet edge does not appear to be smoothly round, but rather
can easily be seen to be just a collection of pixels. Now, look at the
day/night border on the planet. You will not see such jaggies here. This is
because this borderline is 'anti-aliased'. The transition from complete black
to complete white is gradual, and thus the eye can not detect individual
pixels.
My new game LineWars II will use some of these superfast rendering techniques.
It will come out sometime this year, I hope...
Patrick Aalto
Contact:
Internet: ap@tukki.jyu.fi (account about to expire soon..)
tkp72@jytko.jyu.fi
--------
I've been told that the demo I mentioned earlier can be found at
chyde.uwasa.fi (sorry, don't have the IP number here now) in the directory
PC/demo.
[This one caused a lot of traffic on the net. It's a cute demo, though there
aren't all that many rays traced, and a lot of tricks are done to avoid them.
I think this is just fine: why trace rays when you don't need to? But it
definitely got people excited when Patrick claimed "real time ray tracing".
--EAH]
-------------------------------------------------------------------------------
DKBTrace Beta Available, by David Buck (dbuck@ccs.carleton.ca)
I've placed a new version of DKBTrace onto alfred.ccs.carleton.ca
(134.117.1.1) for beta testing - and for those who just can't wait :-). The
source files and data files for DKBTrace version 2.10 can be obtained by
anonymous ftp from the above site. They are in directory
pub/dkbtrace/dkb2.10. No executables are available at this time.
Abstract:
DKBTrace is a freely-distributable raytrace program that renders quadric
shapes, CSG (Constructive Solid Geometry), and a handful of other primitive
shapes. Shadows, reflection, refraction, and transparency are also supported.
DKBTrace also allows you to define complex an interesting solid textures such
as wood, marble, "bozo", etc. The texturing facility has been greatly
enhanced in version 2.10.
NOTE: The data files for version 2.10 are NOT completely compatible with
previous versions. Old data files must be modified to run on the
new raytracer.
Please report any problems or questions to me at dbuck@ccs.carleton.ca.
I'm also starting up three mailing lists for people interested in the
following aspects of DKBTrace:
- General Questions and Problems with DKBTrace
- Porting DKBTrace to various platforms
- Writing a graphical user interface for DKBTrace
(note: I don't intend to write a graphical user interface, but
several people have expressed an interest, so I thought I
should at least maintain a mailing list for these people
so they can keep in touch).
If you want to be added to any (or all) of these mailing lists, please send me
an EMail message indicating which mailing lists you're interested in.
The final release of version 2.10 should be in one or two weeks. I will post
another announcement at that time.
-------------------------------------------------------------------------------
"Computer Graphics" 2nd Edition Corrections, Software, etc by the Brown
Automatic Mailer
Your e-mail addressed to
graphtext@cs.brown.edu
has been handled by an automatic "server" program that generated this response.
This server provides several services for readers of
"Computer Graphics: Principles and Practice", 2nd edition
by Foley, van Dam, Feiner, and Hughes
(Addison-Wesley, 1990)
ISBN 0-201-12110-7
There are several distinct "services" you can obtain from this server, each
identified by a unique keyword. To obtain the service, mail a message to
graphtext@cs.brown.edu containing the keyword (and only the keyword) in the
"Subject:" line. Only one service can be obtained per message.
Here are the services currently available, with the appropriate "Subject:"
lines shown:
--------
Subject: Help
The server sends you this helpful message in response.
If the server program seems to be broken somehow, send mail to
Dave Sklar (dfs@cs.brown.edu)
--------
Subject: Get-Text-Bug-List
Use this service to obtain a list of known "bugs" in the text.
--------
Subject: Report-Text-Bug
Use this service to report a bug in the text. The body of your
message should give the page and line number of the bug, and if
possible, indicate the necessary correction to be made.
Please check the "text-bug-list" before submitting a bug report so you
don't submit a duplicate bug report.
Please don't submit a bug report unless you are sure that there is
a bug in the text; this service is not for raising questions.
--------
Subject: Get-Text-Algorithms
Use this service to get instructions on how to obtain electronic
copies of many of the major algorithms (all in Pascal) presented
in the textbook.
--------
Subject: Software-Distribution
Use this service to get instructions on how to obtain SRGP and SPHIGS,
the software packages described in chapters 2 and 7.
These include information on all three versions:
1) UNIX/X11 (available via ftp)
2) Macintosh (available via ftp, except Pascal via floppy)
3) IBM-PC and compatibles (available via floppy)
--------
Subject: Get-Software-Bug-List
Use this service to obtain a list of known "bugs" in SRGP/SPHIGS.
This list does not include omissions and bugs that are
documented in the SRGP/SPHIGS reference manuals.
--------
Subject: Report-Software-Bug
Use this service to report a bug in the software or in the doc
associated with the software. If you can present a code fragment
that isolates the bug, all the better.
--------
At a later date, we will support services for the sharing of exercises
produced by instructors using the text, and for the submission of suggestions
for improvement of the text in later revisions.
-------------------------------------------------------------------------------
Papers which are currently available from the Net via anonymous FTP, J. Kouhia
--------------------------------------------------------------------
Last update January 28, 1991
Updates and mails to
Juhana Kouhia
kouhia@nic.funet.fi [128.214.6.100]
Put the new papers to
nic.funet.fi [128.214.6.100]
pub/graphics/papers/Incoming
%K KYRI90
%A George Kyriazis
%T A Study on Architectural Approaches for High Performance Graphics Systems
%I Rensselaer Design Research Center, Technical Report No: 90041
%D September 1990
%O weedeater.math.yale.edu [128.113.6.10] pub/Papers/kyri90.ps.Z
%O nic.funet.fi [128.214.6.100] pub/graphics/papers/kyri90.ps.Z
%K MUSG88
%A F. Kenton Musgrave
%T Grid Tracing: Fast Ray Tracing For Height Fields
%J Research Report YALEU/DCS/RR-639
%D July, 1988
%O weedeater.math.yale.edu [128.113.6.10] pub/Papers/musg88.ms.Z
%O nic.funet.fi [128.214.6.100] pub/graphics/papers/musg88.ps.Z
%K MUSG89a
%A F. Kenton Musgrave
%T Prisms and Rainbows: a Dispersion Model for Computer Graphics
%J Proceedings of the Graphics Interface '89 - Vision Interface '89
%I Canadian Information Processing Society
%C Toronto, Ontario
%P 227-234
%D June, 1989
%O weedeater.math.yale.edu [128.113.6.10] pub/Papers/musg89a.ms.Z
%O nic.funet.fi [128.214.6.100] pub/graphics/papers/musg89a.ps.Z
%K MUSG89b
%A F. Kenton Musgrave
%A Craig E. Kolb
%A Robert S. Mace
%T The Synthesis and Rendering of Eroded Fractal Terrains
%J Computer Graphics
(SIGGRAPH '89 Proceedings)
%V 23
%N 3
%D July 1989
%P 41-50
%Z info on efficiently ray tracing height fields
%K fractal, height fields
%O weedeater.math.yale.edu [128.113.6.10] pub/Papers/musg89b.ms.Z
%O nic.funet.fi [128.214.6.100] pub/graphics/papers/musg89b.ps.Z
%K MUUS??
%A M. J. Muuss
%T Excerpts from "Workstations, Networking, Distributed Graphics, and Parallel Processing"
%I BRL Internal Publication (???)
%D ?????
%O freedom.graphics.cornell.edu [128.84.247.85] pub/RTNews/Muuss.parallel.Z
%O nic.funet.fi [128.214.6.100] pub/graphics/papers/Muuss.parallel.ps.Z
%K MUUS??
%A M. J. Muuss
%A C. M. Kennedy
%T The BRL-CAD Benchmark Test
%I BRL Internal Publication (???)
%D ?????
%O freedom.graphics.cornell.edu [128.84.247.85] pub/RTNews/Muuss.benchmark.Z
%O nic.funet.fi [128.214.6.100] pub/graphics/papers/Muuss.benchmark.ps.Z
%K SHIR90a
%A Peter Shirley
%T Physically Based Lighting Calculations for Computer Graphics
%I Thesis
%D November 1990
%O weedeater.math.yale.edu [128.113.6.10] pub/Papers/shir90a/
%O nic.funet.fi [128.214.6.100] pub/graphics/shirley/
%K SHIR90b
%A Peter Shirley
%T Monte Carlo Method
%I Appendix from the SHIR90a
%D November 1990
%O nic.funet.fi [128.214.6.100] pub/graphics/papers/shir90b.ps.Z
%K WILS91
%A Tom Wilson
%T Ray Tracing Abstracts Survey
%D January 1991
%O weedeater.math.yale.edu [128.113.6.10] pub/Papers/wils91.1.shar.Z
%O nic.funet.fi [128.214.6.100] pub/graphics/papers/wils91.1.ps.Z
======== USENET cullings follow ===============================================
[culled - get the full issue via FTP -- see Introduction]
-------------------------------------------------------------------------------
END OF RTNEWS