_ __ ______ _ __
' ) ) / ' ) )
/--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _
/ \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_ 4 and < infinity.
Last issue's puzzle was: You have a cube and you select at random three
(different) corners. What is the chance that the triangle formed by these
corners is acute (all angle < 90 degrees)? is a right triangle (has one
angle == 90 degrees)?
A quick answer is this (from Spike Hughes): there are 8*7*6 possible
triangles, and divide by 3*2 since we do not care about the order of the
vertices. This gives 56 unique triangles formed. Of these, 6 have right
angles at a given corner: the 3 cube-edge/cube-edge pairs and the 3
edge/perpendicular-face-diagonal pairs. Each triangle can have at most one
right angle, so with 6 right triangles at a given corner, then 6*8=48
triangles must be right triangles. So 48 of 56, i.e. 6 of 7 triangles formed
are right triangles. This leaves a 1 in 7 chance that a random triangle is
acute. No obtuse triangles are possible, interestingly enough. Other ways of
thinking about this problem include proving that acute triangles must be
formed entirely of cube face diagonals, and using dot products of 0 between
edges to rule out right triangles.
----------------------------------------------------------------------------
Ray Tracing Roundup
I've been compiling useful formulas and equations in a single document for
people involved in global illumination research. It now has 34 pages and 86
items listed:
http://www.graphics.cornell.edu/~phil/GI/
- Phil Dutre (phil@Graphics.Cornell.edu)
[This thing's amazing, go grab it. -EAH]
-------
3D Object Intersection page
A page giving references a wide variety of 3D object intersection references
is now available:
http://www.realtimerendering.com/int/
Also at this site is my personal list of frequently used graphics related
web sites:
http://www.realtimerendering.com/portal/
It's geared towards real-time rendering, but has much that applies to
graphics in general.
--------
Optimizing Ray-Triangle Intersection
If you're interested in optimized ray-triangle intersection code and
statistics, then take a look at:
http://www.ce.chalmers.se/staff/tomasm/raytri/
I have optimized my and Trumbore's code from journal of graphics tools, and
tried it on three different machines and with different percentages of
triangle hits. The code is also available at the above mentioned site. Let
me know if you have any suggestions for improvements.
-- Tomas Moller (tompa@acm.org)
--------
Graphics Gems Repository update
The Gems repository has been expanded in two ways. New pages have been
added:
http://www.acm.org/tog/GraphicsGems/category.html - by category
http://www.acm.org/tog/GraphicsGems/authors.html - by author
http://www.acm.org/tog/GraphicsGems/gems.html - in book order
In addition, each of these pages has direct links to the relevant code for
each gem.
--------
Non-Photorealistic Rendering
Craig Reynolds maintains an excellent annotated links collection on the
subject of NPR:
http://www.red3d.com/cwr/npr/
--------
SIGGRAPH has the beginnings of a corrigenda (i.e. corrections) site for
SIGGRAPH proceedings:
http://www.siggraph.org/publications/corrigendum.html
If you know of an error in a SIGGRAPH article, please let Stephen Spencer
(spencer@siggraph.org) know.
This year's SIGGRAPH papers are listed and online versions linked from:
http://www.cs.brown.edu/~tor/sig2000.html
--------
A mailing list dedicated to realtime raytracing now exists:
You can join this community by going to:
http://www.onelist.com/subscribe/realtime_raytracing
Or you can join by sending email to:
realtime_raytracing-subscribe@onelist.com
The archives are at:
http://www.egroups.com/group/realtime_raytracing
This list has had some interesting discussions (see some later in this
issue), though traffic has died down in recent months. Many of the
subscribers are into the demo scene (see
http://www.acm.org/tog/resources/RTNews/demos/overview.htm).
--------
The Best Efficiency Scheme (BES) Project has its own page at:
http://www.cgg.cvut.cz/GOLEM/bes.html
The WWW page contains updated version of the project proposal, more than 200
possible scenes in VRML'97 format of different complexity, and technical
report describing the first results of the project (testing on 30 SPD scenes
X 12 acceleration data structures X 4 methods of shooting rays).
By the way, we are still looking for large scale scenes (over 500,000
primitives).
-- Vlastimil Havran (havran@fel.cvut.cz)
--------
A software tool for interactive visualization of spatial data structures was
designed to verify the correctness of implementations. Several static images
from that visualization are available at:
http://www.cgg.cvut.cz/~havran/vis/visualization.html
-- Vlastimil Havran (havran@fel.cvut.cz)
[This is pretty interesting to look at, in fact. -EAH]
--------
Art of Illusion
Art of Illusion is a free, open source 3D modelling and rendering studio. It
is written entirely in Java, and should be usable on any Java Virtual
Machine which is compatible with JDK 1.1 or later.
The current version is 0.4, released May 3, 2000. This is still a fairly
early version, and some basic functionality is still missing. It is
progressing quickly, however, and already has a number of advanced features
including a powerful raytracer, a flexible and easy to use triangle mesh
editor, and the ability to automatically generate smooth, organic shapes
from triangle meshes.
http://drizzle.stanford.edu/~peastman/aoi.html
-- Peter Eastman (peastman@drizzle.stanford.edu)
[Peter also notes that this package has a triangulator in it: "The routine
is Line.convertToTriangleMesh. I can't guarantee that it's the best
algorithm, but it seems to work pretty well. Also, it will deal fine with
concave polygons, but will sometime have trouble with self-intersecting
ones."]
--------
Real-Time Volumetric Rendering
We did some volumetric rendering with raytracing and then "mixed" that with
a normal 3d scene (the scene was drawn using 3d acceleration).
Fair enough, it looks a bit blurry but it does give the impression of flying
through 3d clouds.
Oh you can download the demo from http://www.incognita-hq.com if you're
curious. it's called platipus (needs a "multimedia" machine with dx7, ram,
the whole lot).
In the demo there's also my (now pretty old) rt engine, which is not too
bad.
-- angel sastre (icg_reboot@bigfoot.com)
[Also, source code is available at the site.]
--------
Year Three (1998/1999) results of the Internet Raytracing Competition are
now available on CD ROM. The quality of some of the winning entries is
impressive:
http://www.irtc.org
--------
The global illumination bibliography now resides on:
http://www.helios32.com/
as well as other related resources. There's also an image of the very first
radiosity image ever computed (made with hand-cranked calculators). See
http://www.helios32.com/resources.htm#History
--------
Some interesting BIBTEX entries of lesser known papers can be found at:
Ray tracing: http://www.cgg.cvut.cz/~havran/Bib/rtmame.bib
Visibility: http://www.cgg.cvut.cz/~havran/Bib/vismame.bib
Rendering: http://www.cgg.cvut.cz/~havran/Bib/renmame.bib
The lists are being regularly updated with new papers as they appear.
-- Vlastimil Havran (havran@fel.cvut.cz)
--------
An extensive annotated collection of links to procedural texture synthesis
is available at:
http://www.threedgraphics.com/texsynth/
--------
The PVMPOV patch gives POV-Ray the ability to distribute a rendering across
multiple Unix platforms:
http://www-mddsp.enel.ucalgary.ca/People/adilger/povray/pvmpov.html
There is also a beta Win32 version at:
http://netlib2.cs.utk.edu/pvm3/win32/
--------
A nice summary of free L-system software out there is at:
http://www.cpsc.ucalgary.ca/projects/bmv/software.html
--------
A pleasant page covering free and shareware modeling software:
http://www.mech.ed.ac.uk/~dom/3d/3d.html
--------
John Morris' lecture notes for his data structures class are nicely done,
covering the basics of this subject. Worth a look at:
http://swww.ee.uwa.edu.au/~plsd210/ds/
--------
The mental ray specifications are interesting to read from a standpoint of
looking at what features are part of a commercial ray tracing renderer:
http://www.mental.com/p207.html
--------
In response to several requests, we have made available measured skin BRDF
data from the 1999 EGWR paper,
"Image-Based BRDF Measurement Including Human Skin", by Steve Marschner,
myself, Eric Lafortune, Ken Torrance, and Don Greenberg.
Data are in gzipped tar archives, each with a lot of binary data files
containing raw BRDF samples in red, green, and blue channels. Data on the
spectral response of the camera and the spectral balance of the source are
included, and two of the three data sets include coefficients for rendering
with the multi-lobe representation of Lafortune et al. (SIGGRAPH 97).
The URL is http://www.graphics.cornell.edu/online/measurements/
Have fun.
-- Stephen H. Westin (westin@graphics.cornell.edu)
--------
The Mops is a free open source modeler for Unix (Linux, IRIX) systems and
(sort-of) Windows. Check it out at:
http://www.informatik.uni-rostock.de/~rschultz/mops/
--------
A great site for information on implicit surfaces is:
http://implicit.eecs.wsu.edu/
On a related note, Jules Bloomenthal's very useful implicit surface
polygonizer article from Graphics Gems IV is now also available at his site:
http://www.unchainedgeometry.com/jbloom/papers/index.html
--------
GraphicsJungle
At:
http://www.cpsc.ucalgary.ca/Redirect/GJ/index.html
is the Jungle project, run by Przemyslaw Prusinkiewicz and Brian Wyvill. It
is focussed on modeling, animating and rendering blobbies. The software can
be found at:
http://www.cpsc.ucalgary.ca/~jungle/software/jspdoc/index.html
for SGI and Linux systems.
--------
Robert Schneiders maintains an overwhelmingly large annotated links site on
mesh generation:
http://www-users.informatik.rwth-aachen.de/~roberts/meshgeneration.html
--------
The NURBS++ Package is source under GPL for manipulating and evaluating
NURBS curves and surfaces. It includes an OpenGL-based editor, and can
output POV-Ray, RIB, or VRML files. It's at:
http://yukon.genie.uottawa.ca/~lavoie/software/nurbs/feature.shtml
--------
A few useful resources are at:
http://www.cs.utexas.edu/users/atc/downloads.html
A.T. Campbell, III's page. These include a small Java raytracer, a fairly
complete BSP tree library, and other things.
--------
The POV-Ray SuperPatch is an unofficial collection of extensions to POV-Ray:
http://www.geocities.com/Athens/Academy/8764/spovraydjgpp.html#superpatch
Extensions include parametric surfaces, isosurfaces, splines, sphere sweeps,
new pigment mappings, rational bezier surfaces, new mesh type, slope
dependent textures, variable reflections, light groups, spherical/toroidal/
(etc)/ warps, and unicode text.
--------
For a rundown of tools for POV-Ray, and other open source modeling and
rendering software (as well as some nice images), see:
http://www.linuxgazette.com/issue53/gx/baptista/2.html
--------
ParPov is a library for reading POV-Ray files. The first application of this
library is Pov2Rib, a (surprise) POV to RenderMan RIB format converter. Open
source at:
http://www9.informatik.uni-erlangen.de/~cnvogelg/pov2rib/index.html
The quality of the conversion looks to be quite high, see:
http://www9.informatik.uni-erlangen.de/~cnvogelg/pov2rib/examples.html
for comparison images.
--------
A basic particle system animator for POV-Ray (with source) is available at:
http://www.sbox.tu-graz.ac.at/home/a/ahi/particle-system.html
--------
Hugo Elias' "The good-looking textured light-sourced bouncy fun smart and
stretchy page" has some nicely done tutorials on Perlin noise, clouds,
physically based animation, and many other tidbits:
http://freespace.virgin.net/hugo.elias/
--------
OpenDX
Based on IBM's Visualization Data Explorer, this is an open source
visualization package:
http://www.opendx.org/
--------
Graphics Course Notes
By Steve Seitz, Paul Heckbert, Andy Witkin, Joel Welling, the notes at:
http://www.cs.cmu.edu/afs/cs/academic/class/15462/web/notes/notes.html
have some interesting tidbits in them. For example, in the Ray Casting
section there is a clear explanation of barycentric coordinates, and a cute
geometric proof of the formula for the area of a triangle (I haven't seen it
before).
--------
The Graphics Muse columns in the Linux Gazette has all sorts of tidbits:
http://www.linuxgazette.com/issue46/gm.html
and see the bottom of the page for links to previous issues.
--------
For some pleasing images of fractal terrain, see:
http://www.fractalworlds.com
--------
Information on IGES, STEP, and other CAD related formats is available at:
http://www.cadcamcenter.com/cadcam/toc.htm
There are also links to other resources of interest to CAD programmers.
----------------------------------------------------------------------------
BART: A Benchmark for Animated Ray Tracing, by Jonas Lext
(lext@ce.chalmers.se), Ulf Assarsson (uffe@ce.chalmers.se), and
Tomas Moller (tompa@acm.org)
[The authors have come up with a useful new benchmark for measuring ray
tracer performance. For static testing, these scenes address a problem the
SPD/NFF benchmarks had: realistic environments. Little research has been
done for ray tracing efficiency schemes including the fourth dimension,
time. Given the growing interest in real-time ray tracing, I see this as an
area ripe for some interesting work. For example, Reinhard, Smits, and
Hansen just published a clever "modulo" grid scheme at the Eurographics
Rendering Workshop this year; see the "Recent Papers" article at the end of
this issue. - EAH]
Description of BART
-------------------
Abstract: Due to the advent of ray tracing at interactive speeds and because
there is an absence of a way to measure and compare performance and quality
of ray traced scenes that are animated, we present an organized way to do
this fairly and accurately in this proposal for BART: A Benchmark for
Animated Ray Tracing. This is a suite of test scenes, placed in the public
domain, designed to stress ray tracing algorithms, where both the camera and
objects are animated parametrically. Equally important, BART is also a set
of rules on how to measure performance of the rendering. We also propose how
to measure and compare the error in the rendered images when some kind of
approximation algorithm has been used.
Informal description: We were and still are interested in efficient
algorithms for computer graphics. In this case we focused on ray tracing
algorithms for animated scenes. The main reason for this is that real-time
or interactive ray tracing is quite possible to do on multiprocessor
computers. So, to be able to compare different acceleration schemes, we set
out to compile a suite of test scenes for this. We currently have three
scenes described below that we have put into the public domain. Each scene
was designed to stress ray tracing algorithms in general. In order for the
user of BART to make a fast implementation, we provide a simple C-parser for
the file format (it takes about half a day to implement), and some animation
code. The benchmark may also be used to: 1) compare algorithms using polygon
rendering hardware (e.g., OpenGL), 2) compare global illumination and
radiosity algorithms, 3) compare motion blur algorithms, but was not
designed specifically for these areas of interest.
The BART benchmarks are at http://www.ce.chalmers.se/BART/.
----------------------------------------------------------------------------
Global Illumination Test Scenes, by Brian Smits (bes@cs.utah.edu) and
Henrik Wann Jensen (henrik@graphics.stanford.edu)
Henrik Wann Jensen and I have designed a set of scenes for testing energy
transport. Our main goal was simplicity, both for the scenes, and for the
type of transport tested by each scene. We wanted a set of very simple
scenes that would exercise different aspects of rendering algorithms and
make it fairly obvious when something wasn't working correctly. They range
from the fairly simple (direct illumination without occluders) to the fairly
challenging (reflection of a caustic from a secondary luminaire). We would
appreciate any feedback you have.
Global Illumination Test Scenes
-------------------------------
University of Utah Technical Report UUCS-00-013
Abstract:
The global illumination community has discussed having a database of scenes
that could be used to compare and validate different global illumination
algorithms. We present a set of test scenes for global illumination
algorithms and propose that they be the beginning of such a database. These
scenes are designed to be as simple as possible and still test a particular
aspect of energy transport. The scenes are available on a web site in a
variety of formats, along with images and pixel radiance data. We feel that
the simplicity and availability of the models will make it easier for the
community to use them, and that the field will benefit from a standard set
of scenes. Additionally, we discuss classes of models with analytic
solutions.
Tech Report:
http://www.cs.utah.edu/~bes/papers/scenes/
Scene Repository:
http://www.cs.utah.edu/~bes/graphics/scenes/
----------------------------------------------------------------------------
Realtime Techniques for Ray Tracing, by Ádám Nagy (nadam@freemail.hu),
Eric Haines, Russel Simmons (russ@paypal.com), Paul Kahler
(phkahler@oakland.edu), Factory (factory@free.net.au), and
Bruno Schödlbauer (bschoedlbauer@gmx.net)
[from the realtime raytracing email list, see the Ray Tracing Roundup in
this issue. It starts on one topic, evolves to another, and ends with a web
site. -EAH]
Ádám Nagy writes:
For intersecting decisions I always use 2 kind of 'Intersection'
calculation:
- First is for rays with 1 fixed point. This is true for eye rays, and
shadow rays also. This is much simpler for all primitives, because I
precalculate coefficients which only depends on the fixed point of the ray,
and the primitive.
- Second is the general intersection calculation, which I use only at
reflections and refractions.
With a lot of light sources the number of shadow rays + number of eye rays
can be so great that this kind of optimization is important.
I use basically sphere hierarchy, but for eye rays in addition I use another
special optimization: I divide the screen into sectors (16*16) pixels: for
all the sectors I precalculate its own sphere hierarchy which it intersects:
I don't have to go through all the hierarchy for all the pixels.
I use adaptive techniques: I do full raytracing for some gridpoints on the
screen, and for other pixels I do some heuristics (determined from the
neighbor pixel infos) to save costly full hierarchy 'Intersect' calls. I am
interested what kind of heuristics other guys are using.
My engine is a little bit slow because it is still in C++, but now I am in
the middle of rewriting the important part to PIII Streaming SIMD based
assembly code, I'm sure it will help a lot in terms of speed.
My basic idea regarding pIII Streaming SIMD is to maintain an 'Intersecting
job queue', and I try to solve 4 intersect job in parallel fully using the
PIII Streaming SIMD extensions. Does anyone have experience regarding to
optimizing to PIII, or optimizing to Athlon?
Does anyone have experience in doing some part of ray tracing using integers
instead of floating point?
Do you know better way than hierarchical spheres, and other kind of
optimization techniques?
--------
Ádám Nagy later adds:
I am trying to experiment with more complex heuristics, and I am interested
in others' ideas about it. Here I show a very basic one, which is already
implemented in my engine:
Let's do a classic raytracing for every fourth pixel (I put 1 where I do
raytracing.)
10101010
00000000
10101010
00000000
10101010
Let's also store the trace information for those pixel. What does this mean?
If for a pixel the eye ray intersected object A, and for the two
lightsources the shadow rays intersected object B and object C, and the
reflection ray intersected object D, we can store: A(BC)D. After it for the
remaining pixels we can check its four neighbors, and if all the neighbors
have the same stored structure, than we can simply assume that structure for
that pixel without doing any intersecting calculation. In this case the only
problem is that we sometimes miss some one-pixel objects, but these are not
important (sometimes it is better not to show 1 pixel objects!)
----
Eric Haines replies:
That's an interesting approach, of knowing in advance what the ray tree is
and shooting the rays only at those objects. Have you compared shooting the
rays for the other 3 neighbors vs. just interpolating the already computed
shade across the four corners? Interpolation would be bad if there are
textures or a sharp specular highlight, I guess, but otherwise might be
fine.
----
Ádám Nagy replies:
Actually, the best approach seems to make a compromise: I do not interpolate
the pixel color directly, but I am not shooting the ray to the object: I am
interpolating the normal vector (to enable shooting refraction rays...), the
shade without texture, and the texture coordinates, and I multiply the
texture color with interpolated shade: The textures look fine!
----
Russel Simmons responds:
You don't really need to interpolate the normal vector. I believe the
'standard' approach for grid-based raytracing (and the technique that I use
in my engine) is just to treat rays that have been reflected no differently
from other rays. In other words, your grid-interpolator routine knows
nothing of rays being reflected rays or not; it merely interpolates shade,
u, v, across the block. The higher-level tracing routines handle
reflections. In addition to shade, u, v, I also store an id for each block.
The id is essentially a surface id used to determine which texture to use,
and also whether or not a block can be interpolated. If the 4 id's at the
corners don't match, I don't interpolate the texture. Now, in the case of
reflections, it would be possible to have 3 corners of a block hit object A,
but the last corner hit object B, get reflected, finally hitting object A.
Even though all 4 corners have the same surface id (of object A) we don't
want to interpolate across (because there is an edge between object A and B
in there somewhere). So to solve this problem you can flip some high bits
in the id value if the surface is hit via a reflection - then the id's won't
match. Also, if you want to not interpolate across shadow boundaries (you
might want to subdivide) then a decent hack is to have a high bit in the id
values represent in/out of shadow.
Getting back to normal vectors.. interpolating them like you say may have
some advantages, but in my experience the method described above works and
looks great.
----
Paul Kahler notes:
I find the following pattern works really well:
00100010001
00000000000
10001000100
00000000000
00100010001
It's every 8th pixel, but my perception is that it's no worse than the 2x2
method you mentioned. That varies with texture, of course. At one point I
did tests with a single object and found a disturbing amount of time being
spent comparing colors of pixels and interpolating (I just tested color to
see if more rays were needed, and interpolated just color) than tracing
rays. I came up with a couple of great macros to compare and interpolate
colors that cut the time way down - they're like MMX, but in C.
----
Factory responds to Paul's note:
I assume that interpolates along triangles, as opposed to being along
parallelograms, i.e.
00111110001
01233321000
12345432100
01233321000
00111110001
and not..
11111110001
23333321000
12345432100
01233333210
00111111111
> I came up with a couple of great macros to compare and interpolate
> colors that cut the time way down - they're like MMX, but in C.
Hmm, looks like a nasty thing to optimize, I'd prolly try and make special
case renderers for the four different rows that need to be rendered.
Another thing bad about that approach is that it prolly wouldn't lend itself
to super sampling, but OTOH, I reckon it would look rather kewl if one was
to do it with fairly large triangles.. (at least in a demo).
----
Paul replies:
No, actually if I follow your notation correctly it's:
231323132
343434343 Where the 2's are the average of 4 1's
132313231 The 3's are the average of a 2 and a 1
343434343 And the 4's I forgot how they work ;-)
231323132 probably just an average of 2 pixels (hmm which ones..)
Looking at this little diagram makes me think I'm not even averaging the
best choices of pixels. OTOH I don't do weighted averages. Also, if the
threshold for deciding to shoot more rays is low enough it doesn't mater how
you interpolate. BTW, I'm doing this in windows with a default size of
512x384, so the pixels are small and the artifacts are not too bad. Shadows
tend to look low-res because the outline of the shadow doesn't always
trigger enough additional rays, but at higher speeds you still don't notice.
The key is to always shoot rays along an objects edge. With solid colors,
just about any interpolation will do for the interior.
----
Bruno Schödlbauer also responds to Paul's comments:
One thing you might try is not to interpolate, but instead to trace one
frame every odd pixel, and next frame every even pixel. For every pixel not
traced use the values of the previous frame. It probably looks strange with
few frames per second, but with many frames one shouldn't notice it.
----
Paul ends on this note:
I just posted 3 small (72K) programs demonstrating my RTRT progress. Also
available is an explanation of how I do my pixel interpolation - see the
page describing DRE linked from the RTRT page
(http://www.oakland.edu/~phkahler/rtrt/dre.html). All found at:
http://www.oakland.edu/~phkahler
Choose the Realtime Raytracing link. BTW, these are Windoze programs and
should run on 95,98, or NT unless there is some MFC dll version issue (I've
seen some problems before).
You'll notice that my focus is not on getting the best possible performance
on a particular scene, but on making a very high performance ray tracer that
can be used for all sorts of things. Comments are welcome of course.
----------------------------------------------------------------------------
Fastest Way to Generate Eye Rays in Ray Tracing, by Samuel Paik
(paik@webnexus.com)
[I'm sure I've seen this written up somewhere before, but can't seem to find
it. This is the method I use, and I believe once Paul Heckbert also
mentioned using something like it. I suspect it's been discovered by many
others - time to have it written down somewhere. // Searching around,
I finally found the reference, the poorly named (my fault) "Ray
Transformation", by Kendall Bennett, RTNv6n1. Still, it's worth repeating.
-EAH]
Nicolas Delalondre wrote:
> What is the fastest way to generate eye rays? (I don't want to apply a
> matrix to each vertex of the scene)
Fastest? There typically is no single fastest way to do anything in
computing. Also, it seems highly unlikely that a single matrix-vector
multiply is a major cost in your ray tracer.
However, try this:
Take the eye point and the projection plane and transform them into world
space. Now simply march along the projection plane for each pixel, this
gets you one point and the eye point is another for an eye ray. Viola! If
your model & view transforms are nice (exercise to the student to determine
what those conditions are...) then you can march along the projection plane
for the cost of a single vector addition, and generating the eye ray costs
another vector addition (if you need a normalized eye ray, that costs a
little extra).
----------------------------------------------------------------------------
On Transforming Planes, by Steve Hollasch (stevehol@microsoft.com)
[From netnews. It's still a common error to transform normals by the
rotation matrix, instead of its inverse transpose. You can often get away
with this, see http://www.gignews.com/realtime020100.htm, and this topic was
covered way back in RTNews1a. That said, I like Steve's little proof of how
the matrix and its inverse cancel out. -EAH]
Here's my take on transforming planes that should make everything clear.
If you represent points as column vectors (that is, translation components
in the last column of a 4x4 matrix), then you transform a point by
performing the matrix multiply M P = P', where M is the transformation
matrix and P is the column-vector point. Given a plane Q, you'd transform
by the same matrix by performing the matrix multiply Q M* = Q', where M* is
the inverse of matrix M, and Q is a row vector [A B C D], where the plane is
defined by Ax + By + Cz + D = 0.
Also note that Q M* = M*t Qt, where M*t is the transpose of M*, and Qt
is the column vector form of Q. This is useful if your matrix multiply
routine is geared to doing column-vector style multiplication.
If your system uses row-vectors to represent points, then just flip all
of the matrix equations I've written above: P' = P M, Q' = M* Q = Qt M*t.
For a quick proof, consider that you want the plane equation Ax+By+Cz+D
= 0 to hold true both before and after a transform. That is, for all
points P that lie on the plane Q, then all of the transformed points P'
should lie on the transformed plane Q':
[1] (Q') (P') = Q P (it's an exercise to the reader to prove that
the matrix product of the row vector Q and the column vector P expresses the
plane equation Ax+By+Cz+D=0)
[2] (Q M*) (M P) = Q P (Q' = transform Q, and P' = transform P)
[3] Q (M* M) P = Q P (Associative law for matrix multiplication)
[4] Q P = Q P (M* M = Identity)
Q.E.D.
----------------------------------------------------------------------------
Intersecting a Ray and a Triangle with Plücker Coordinates, by
Ray Jones (rjones@pobox.com)
Testing for ray-triangle intersections with Plücker coordinates [1,2] has
the benefit of being simple, reasonably efficient, and concise. Its main
competitors are based on ray-plane intersection combined with barycentric
tests. Various people have asserted to me that these methods are better
because, as side effects of the intersection test, they give:
a) the point of intersection
b) the barycentric coordinates of the intersection
both of which are often needed for further computations.
However, the Plücker intersection test can also be used to generate the
barycentric coordinates. Paraphrasing from [1], given the Plücker
coordinate R of a ray through points P0,P1 and the Plücker coordinates
E0,E1,E2 for the edges of a triangle (A,B,C), the intersection test checks
the signs of the permuted inner products of R and each of E0,E1,E2. If the
signs agree, then the ray intersects the triangle.
The permuted inner product of the Plücker coordinates of two lines, P0->P1
and Q0->Q1, is related to the volume of the tetrahedron formed by
(P0,P1,Q0,Q1). The volume of this tetrahedron (within a constant scale) is
given by the determinant |P0 P1 Q0 Q1|:
| P0.x P0.y P0.z 1 |
| P1.x P1.y P1.z 1 |
| Q0.x Q0.y Q0.z 1 |
| Q1.x Q1.y Q1.z 1 |
The Plücker coordinates of the line P0->P1 are the determinants of the six
2x2 sub-matrices of:
( P0.x P0.y P0.z 1 )
( P1.x P1.y P1.z 1 )
The connection between the Plücker coordinates and the volume determinant is
easy to see, and it can be shown that the permuted inner product is
equivalent to |P0 P1 Q0 Q1| [3]. (I have assumed that the w coordinates for
the points are 1, for reasons explained below.)
Getting back to the triangle intersection test, given the ray P0->P1, any
point P2 on the ray, and an edge Q0->Q1 of the triangle (A,B,C), it can also
be shown that the volume of the tetrahedron (P0,P1,Q0,Q1) is proportional
to:
- The magnitude of (P0-P1)
- The dot product of (P0-P1) and the normal of (Q0,Q1,P2)
- The area of the triangle (Q0,Q1,P2)
The first factor above is the same for each edge. If we assume (without
loss of generality) that P2 is in the plane of the triangle (A,B,C), then
the second factor is also the same for each edge, since then the normal of
(Q0,Q1,P2) is the same as that of (A,B,C).
Therefore, the volume of the three tetrahedra, and by extension the Plücker
inner products of the edges and the ray, are proportional to the areas of
the triangles (A,B,P2), (B,C,P2) and (C,A,P2). If P2 is in the plane of
(A,B,C), then these are the subtriangles that define the barycentric
coordinates of P2. Since the other two factors are the same for each edge,
the Plücker intersection test gives (directly) the unnormalized
(homogeneous) barycentric coordinates of the ray-plane intersection point.
There is one caveat: although the Plücker coordinates are homogeneous, for
the equivalence to hold true, the Plücker coordinates of the edges of the
triangle cannot be scaled independently.
(Another benefit to using the Plücker intersection test is explained by
Amanatides and Choi[4], where tests are performed only once per edge and
shared by adjacent triangles.)
[1] http://www.acm.org/tog/resources/RTNews/html/rtnv10n3.html#art11
[2] http://www.acm.org/tog/resources/RTNews/html/rtnv11n1.html#art3
[3] My thanks to Pat Hanrahan, who explained the equivalence of the
tetrahedral volume and Plücker inner product as well as the
connection to barycentric coordinates after I had found it by
other (less clear) means. He knew of this connection well before
I noticed it.
[4] http://www.cs.yorku.ca/~amana/research/mesh.pdf
John Amanatides, Kia Choi "Ray Tracing Triangular Meshes",
Proceedings of the Eighth Western Computer Graphics Symposium
April 1997, pp 43-52.
----------------------------------------------------------------------------
Volumetric Rendering, by Paul Kahler (phkahler@oakland.edu)
[From the realtime raytracing list.]
I just thought I'd mention that I tried some very limited RT volume
rendering. I used an oct-tree (however you spell that) and treated it as
nested bounding *spheres*. A single sphere is circumscribed around the top
level cube in the tree. Then 8 smaller spheres are circumscribed around the
8 subcubes. This pattern is repeated down to the smallest size sphere/cube
to be used.
There really aren't any cubes or spheres defined. Only the orientation of
the entire hierarchy. Each node in the tree has just 8 pointers to its
children (NULL if an octant is empty). The bottom level objects have color
information instead of pointers. You can use the recursive structure to do
really fast intersection tests on the spheres. The ultimate may be to
project the ray onto a plane perpendicular to the ray with the bounding
sphere at the origin. The intersection test is then checking if the point is
inside a circle, and subsequent tests of the children are just a matter of
moving that point around the plane (via 8 vectors projected onto the plane).
I never got as far as the plane projection, but I did do a recursive
intersection test and used one of 8 different orders to test the child
octants depending on the ray direction (not optimal, but never used the
worst-case order). I was able to trace a solid block of 64x64x64 balls at
1fps or so. There was a LOT of aliasing going on because I was using the
normal vector of each ball where the ray hit rather than some type of
"surface normal" involving the overall surface geometry.
My conclusion was that each voxel should have a single normal vector
associated with it (I've used this before in a non-RT voxel renderer
http://www.oakland.edu/~phkahler) and with more optimization you could get
good performance and large voxel counts. I've decided to put that aside
until several gigabytes of ram are available and I have more time. RAM usage
can be minimized if you can re-use even the smallest subtrees but a complex
scene will still require a lot of storage and it will be static (those
blades of voxel grass will not blow in the wind).
----------------------------------------------------------------------------
Recent Papers, summarized by Eric Haines and Vlastimil Havran
(havran@fel.cvut.cz)
This section is a collection of notices of some recent papers related to ray
tracing and global illumination. Please feel free to send me other relevant
abstracts to publish here.
Vlastimil Havran writes:
Several papers on ray tracing appeared at
WSCG'2000(http://wscg.zcu.cz/wscg2000/wscg_2000_program.htm),
SCCG'2000(http://www.dcs.fmph.uniba.sk/~sccg/2000/program.htm), and
EGWR'2000(http://www.fee.vutbr.cz/egrw2000/program.html), that could be of
interest. I've selected only those closely related to ray tracing (many more
of them are related to general rendering, particularly to global
illumination):
Wilkie,A., Tobler,R.F., Purgathofer,W.: Raytracing of Dispersion Effects in
Transparent Materials (Austria)
http://wscg.zcu.cz/wscg2000/Papers_2000/W7.pdf.gz
Havran,V., Dachs,L., ra,J.: VIS-RT: A Visualization System for RT Spatial
Data Structures (Czech Republic)
http://wscg.zcu.cz/wscg2000/Papers_2000/X77.ps.gz
Revelles,J., Urena,C., Lastra,M.: An Efficient Parametric Algorithm for
Octree Traversal (Spain) http://wscg.zcu.cz/wscg2000/Papers_2000/X31.pdf
Poitou,O., Bermes,S., Lecussan,B.: Laziness, a Way to Improve Distributed
Computation of the Ray Tracing Algorithm
http://wscg.zcu.cz/wscg2000/Papers_2000/T29.ps.gz
EGWR'2000:
Dynamic Acceleration Structures for Interactive Ray Tracing, Erik Reinhard,
Brian Smits, Chuck Hansen
Direct Ray Tracing of Displacement Mapped Triangles, Brian Smits, Peter
Shirley, Michael Stark
Ray Tracing Point Sampled Geometry, Gernot Schaufler, Henrik Jensen
Tapestry: A Dynamic Mesh-based Display Representation for Interactive
Rendering, Maryann Simmons
--------
What follows are abstracts which I (Eric) have collected from email, etc;
by no means is it a comprehensive list.
Reinhard, E., Smits, B., and Hansen, C., "Dynamic Acceleration Structures
for Interactive Ray Tracing," in Proceedings Eurographics Workshop on
Rendering, (Brno, Chzech Republic), June 2000.
My own explanation: The idea of this paper is that as objects move outside
the grid efficiency structure, they are (cheaply) reinserted into the grid
itself, with a little resulting inefficiency. How is this possible? The grid
is treated as a structure that repeats, filling space: now any object can be
put into the grid, using the grid resolution as a modulus. In other words,
something moving out through the left face of the grid "enters" the right
face, and its larger location in the world is also noted. By doing so, the
whole grid does not have to be recomputed each frame; rather, just the
moving objects are deleted and reinserted. Only if the ray traveling through
this grid matches the larger location of the object is the object tested for
intersection. Paper available at http://www.cs.utah.edu/~reinhard/egwr/
--------
"Interval methods for ray casting implicit surfaces with affine arithmetic,"
Affonso de Cusatis Junior, Luiz Henrique de Figueiredo, Marcelo Gattass,
Proceedings of SIBGRAPI'99, p. 65-71. IEEE Computer Press.
Abstract: We study the performance of affine arithmetic as a replacement for
interval arithmetic in interval methods for ray casting implicit surfaces.
Affine arithmetic is a variant of interval arithmetic designed to handle the
dependency problem, and which has improved several interval algorithms in
computer graphics.
Full text, color images and other links available at http://www.tecgraf.puc-
rio.br/~lhf/sib99/
--------
"Hierarchical and Stochastic Algorithms for Radiosity", Philippe Bekaert,
K.U. Leuven, PhD Dissertation, 1999.
The radiosity method is a physically based method to compute the
illumination in a virtual environment with diffuse (matte) surfaces. It
allows to generate very realistic images of such environments by computer,
and it is suitable for quantitative predictions of the illumination.
In the radiosity method, a number of simplifying assumptions are made that
can however lead to certain image artifacts. In this dissertation, the
numerical error introduced by these assumptions is analyzed. The analysis
allows to propose new algorithms in which this error, the discretization
error, is efficiently controlled during the computations by means of
hierarchical refinement.
The radiosity method also requires the solution of very large non-sparse
systems of linear equations (about 100,000 equations is common). Moreover,
the coefficients of these systems are non-trivial four-dimensional
integrals. The main part of this dissertation is devoted to an in-depth
study of how the Monte Carlo method can be applied in this context.
The Monte Carlo method is suitable for reliable computation of the
coefficients of the systems of equations. It also leads to algorithms that
do not require explicit computation and storage of these coefficients. A
systematic overview of such algorithms is presented. Previously proposed
algorithms of this type are compared and some new algorithms are developed.
Next, the application of several variance-reduction techniques is described,
and the use of low-discrepancy sampling in this context is discussed.
Finally, new ways to incorporate higher-order radiosity approximations and
hierarchical refinement are proposed.
The resulting Monte Carlo radiosity algorithms do not only appear to be more
reliable, but also often lead more rapidly to usable images than their
deterministic counterparts. They require significantly less computer
storage, and they are more user friendly. It is expected that these
algorithms will stimulate the use of the radiosity method in a wide spectrum
of applications.
Overview and thesis at:
http://www.cs.kuleuven.ac.be/cwis/research/graphics/CGRG.PUBLICATIONS/PHBPHD
--------
"Incoming First-shot for Non-Diffuse Global Illumination," Szirmay-Kalos
Laszlo, Mateu Sbert, Roel Martinez, Robert Tobler, Spring Conference of
Computer Graphics, Budmerice, 2000
Abstract:
This paper presents a method that can replace the small and medium size
lightsources by their effect in non-diffuse global illumination algorithms.
Incoming first-shot is a generalization of a preprocessing technique called
the first-shot that was developed for speeding up global diffuse radiosity
algorithms. In order to reduce the prohibitive memory requirements of the
original first-shot when it is applied to non-diffuse scenes in a direct
manner, the proposed new method computes and stores only the incoming
radiance generated by the lightsources and the reflected radiance is
obtained from the incoming radiance on-the-fly taking into account the local
BRDF and whether or not the actual viewing direction is in a highlight.
Since the radiance function of the reflection is smoother and flatter than
the original lightsource function, this replacement makes the integrand of
the rendering equation have significantly smaller variation, which can speed
up global illumination algorithms. The paper also discusses how the first-
shot technique can be built into a stochastic iteration algorithm using ray-
bundles, and provides run-time statistics.
Paper at: http://www.fsz.bme.hu/~szirmay/puba.html
--------
"3D Visibility, analysis and applications", by Fredo Durand, PhD
Dissertation, Universite Joseph Fourier, Grenoble
This thesis deals with 3D visibility, and also contains a huge survey of
visibility techniques in different fields such as graphics, vision or
robotics.
Abstract: Visibility problems are central to many computer graphics
applications. The most common examples include hidden-part removal for view
computation, shadow boundaries, mutual visibility of pairs of points, etc.
In this document, we first present a theoretical study of 3D visibility
properties in the space of light rays. We group rays that see the same
object; this defines the 3D visibility complex. The boundaries of these
groups of rays correspond to the visual events of the scene (limits of
shadows, disappearance of an object when the viewpoint is moved, etc.). We
simplify this structure into a graph in line-space which we call the
visibility skeleton. Visual events are the arcs of this graph, and our
construction algorithm avoids the intricate treatment of the corresponding
1D sets of lines. We simply compute the extremities (lines with 0 degrees of
freedom) of these sets, and we topologically deduce the visual events using
a catalogue of adjacencies. Our implementation shows that the skeleton is
more general, more efficient and more robust than previous techniques.
Applied to lighting simulation, the visibility skeleton permits more
accurate and more rapid simulations. We have also developed an occlusion
culling preprocess for the display of very complex scenes. We compute the
set of potentially visible objects with respect to a volumetric region. In
this context, our method is the first which handles the cumulative occlusion
due to multiple blockers. Our occlusion tests are performed in planes using
extended projections, which makes them simple, efficient and robust. In the
second part of the document, we present a vast survey of work related to
visibility in various domains.
Available at http://graphics.lcs.mit.edu/~fredo/THESE/
----------------------------------------------------------------------------
END OF RTNEWS