back to
contents
"Light Makes Right"
January 21, 1997
Volume 10, Number 1
Compiled by
All contents are copyright (c) 1996,1997, all rights reserved by the individual authors
Archive locations: text version at
http://www.acm.org/tog/resources/RTNews/text/
HTML at
http://www.acm.org/tog/resources/RTNews/html/
You may also want to check out the Ray Tracing News issue guide and the ray tracing FAQ.
The first and second issues of the "journal of graphics tools" are out; visit http://www.acm.org/jgt for more info. I'm one of ten editors for this refereed journal, and I urge you all to consider submitting to it. Personally, I would like to see more short papers on specific, practical algorithms to perform various tasks. I believe most graphics programmers have a few tricks that have not made it into the literature for one reason or another. For example, if you've ever written an article for comp.graphics.algorithms explaining some technique, then you should consider contributing to jgt. Because of its focus on practical tools for graphics programmers, it is less formal that most other journals in computer graphics. Empirical proof (i.e. "as you can see, this works") and usability of algorithms is more important here than formal proofs.
ACM TOG, http://www.acm.org/tog, has actually caught up (its publishing schedule had once been more than a year behind) and is back on schedule, due to Andrew Glassner's fine whip hand and the suffering of numerous editorial board members (not including me, I've just been webslaving for it). Through the web site we have been able to offer additional materials for articles printed in TOG, such as MPEG movies showing algorithm behavior. We have also started to offer electronic versions of the latest TOG articles on an experimental basis. Late breaking news: Holly Rushmeier has taken over the Editor in Chief position for TOG, as Andrew has become busy with Microsoft's MSNBC TV channel.
I have recently added new resource links to ACM TOG's web pages. Under the "Resources" area you will find a number of interesting new programs, such as the GIMP (a free Photoshop-like program for Unix/Linux systems, with source code and plug-in interface). There are also links to other resources such as bibliographies (I was amazed to learn the Computational Geometry bibliography now has over 8000 entries), FAQs, links to on-line papers and tutorials, etc. If you know of other resources on the Net that deserve a link, please tell me. I am focussing on the better free resources directly useful to researchers and educators; for example, programs listed on the web page generally have source code available.
ACM TOG's site has also become the official home of two software resources, the Graphics Gems code and the Standard Procedural Databases package. I am the archivist for the Gems code, logging bug fixes and maintaining the errata. Craig Kolb has quietly and diligently provided a home for the Gems code base at Princeton for years now. His access to princeton.edu is becoming limited (he's now at Stanford) and he is also in danger of graduating, so I have moved the Gems code to http://www.acm.org/tog/GraphicsGems/. The Standard Procedural Databases code has also moved, to http://www.acm.org/tog/resources/SPD/. The SPD is code which produces various databases for testing ray tracer efficiency. Over the years Alexander Enzmann and others have added a wide variety of output formats (e.g. RenderMan, Wavefront OBJ, DXF) and translators. The latest release includes output into the VRML 2.0 and 3DMF file formats.
Also, I should note I've taken advantage of ACM's free membership benefit of having an email address from which I can forward. My new email address is erich@acm.org. This is actually handy; for example, I can forward mail to my free Juno email account during the Christmas vacation. See http://www.acm.org/account/ for details.
George Kyriazis is in Greece's army for a year, so I've taken over his duties as maintainer of WUArchive's graphics archive site (ftp or http://wuarchive.wustl.edu/graphics/graphics). "Benign neglect" has been my mantra so far, unfortunately. I would like to change this in the future, updating the site with newer graphics software and information. If you have resources such as code or papers you would like to see available at WUArchive, let me know. It's a free way to keep your works alive at a permanent site.
The computer graphics community has joined the "API of the Month" club. Here, you too can make up your own new API name; simply pick one from each column:
prefix suffix
------ ------
Direct VRML
Open X
Shock GL
Active Script
Java Movie
Cosmo Draw
Cyber Wave
Visual 3D
BTW and FYI, there's no doubt a good TIA (Three Initial Acronym) API generator could be made PDQ, IMO, given the existence of PCI, MMX, OLE, RDX, VFW, GDI, RSX, OCX, ICM, MFC, and AGP (and that's only a small taste of what just Microsoft and Intel have been up to). Actually, we're running out of acronyms: I just ran into two uses of STL (contest time: be the first to tell me what the two uses are and you win some random computer graphics CD laying on my desk).
In the same vein, here is a trademark alert: I recently noticed that the phrase "Old Number 5" is trademarked (I forget by who), so remember, when you use 5's, only use new ones. And don't forget that "the color Pink is a trademark of Owens-Corning Fiberglas Corp.".
Lastly, something I keep forgetting to mention: if you're a C coder, check out "Obfuscated C and Other Mysteries" by Don Libes, Wiley Books. I bought this on a lark with some book credit money I had, and it's one of the best things I ever got. The Obfuscated C contest winning programs are interesting, of course; I'm in awe of the program that solves differential equations and reverses code, and when applied to its own code creates a sort program, which when again applied to itself creates a Fibonacci sequence generator (no, I can't explain it better - check out http://reality.sgi.com/csp/ioccc/index.html for the Obfuscated C contest results, http://reality.sgi.com/csp/ioccc/1990/theorem.hint for the program description). However, some of the explanations of the code in these programs drag on. What's great about this book is all the "stuff they never taught you in school" techniques presented. There are some excellent pieces on allocating memory faster than malloc does, about efficient bit flag array creation and access, about signals, and many other topics which are useful for efficient and effective programming.
back to
contents
Name: Jim Roedder
Organization: McDonnell Douglas
Interests: acceleration methods, fast intersection tests for bi-cubic
patches
Methods Used: SEADS, hierarchical SEADS, Newton-Raphson for cubic surfaces
Phone: (314) 232-7083
E-mail: roedder@ws1777.mdc.com
Snail mail: Jim Roedder/MC 064-2263/PO Box 516/St Louis MO 63166
I have done ray tracing for about 7 years as a small fraction of my time. I apply RT to the calculation of radar cross section (electromagnetic scattering) for aircraft. I use the '3D billiards' techniques of ray tracing for tracking ray bounces on a geometrical model. My principal objects are parametric bicubic patches (PBCs) & flat facets. I use the point in polygon algorithm for general facets and the 3 planes algorithm for triangular facets. I use 2 dimensional Newton-Raphson for intersection tests on the PBCs and SEADS for geometry walk through. I optionally use 2 levels of SEADS for reducing memory requirements when memory is limited.
Since about 1989 I have used a technique for PBC tracing similar to Rick Turner's (RTNews Nov 18 '91) where I subdivide my PBCs. This technique yields SpeedIndeed. Normally, the volume of the bounding boxes encompassing the subdivisions is much less than the volume of a single bounding box containing the entire surface. Further, knowing which subdivision is being tested provides a better starting point to begin 2D Newton-Raphson.
With this logic, my ray tracer is only 3 to 6 times slower on curved surface geometry than on a comparable faceted model. This is measured on a geometry where the bounces are not between close neighbors. Staying with the original surfaces also increases my accuracy relative to triangulating. Are any RTNews readers getting better speeds than this? DOES ANYBODY HAVE FAST ASSEMBLY LANGUAGE for 4by4 matrix multiplies (either double or single precision) on the following machines:
Workstations: SG, HP, IBM RISC , Sun
Supercomputers: Intel Hypercube, Paragon
back to
contents
In "An introduction to ray-tracing" we can find this results from Heckbert's formulas:
|sqrt| / | * | + |
---------------------
n = n1 / n2 | | 1 | | |
c1 = -I.N | | | 3 | 2 |
c2 = sqrt(1 - n * n * (1 - c1 * c1)) | 1 | | 3 | 2 |
T = n * I + (n * c1 - c2) * N | | | 7 | 4 |
---------------------
| 1 | 1 | 13 | 8 |
We can do better:
Bec's method (?)
|sqrt| / | * | + |
---------------------
n = n1 / n2 | | 1 | | |
c1 = -I.N | | | 3 | 2 |
w = n * c1 | | | 1 | |
c2 = sqrt(1 + (w - n) * (w + n)) | 1 | | 1 | 3 |
T = n * I + (w - c2) * N | | | 6 | 4 |
---------------------
| 1 | 1 | 11 | 9 |
result: 2 * less, 1 + more
Any comments?
[I mentioned that on a few machines addition can be more expensive than multiplication. Xavier replied:]
I don't know if adds may be more expensive than multiplies, but if it's the case on some machines, one can write a simplier reformulation :
|sqrt| / | * | + |
---------------------
n = n1 / n2 | | 1 | | |
c1 = -I.N | | | 3 | 2 |
w = n * c1 | | | 1 | |
c2 = sqrt(1 + w * w - n * n) | 1 | | 2 | 2 |
T = n * I + (w - c2) * N | | | 6 | 4 |
---------------------
| 1 | 1 | 12 | 8 |
result: 1 * less and nothing more. Not so good as the previous one but there is no operation added.
____
[We also discussed light passing through colored transmitting objects and how to best control it. -EAH]
It appears that there is two ways for filtering colors.
1) the first solution is, as you say, filter by the color of the object and then the formula looks like this:
result_color = kt * light_color * object_color
Of course, if you don't want the filtering color you have to put the object_color to white.
2) the second solution is the one used by Softimage, for example. As kt goes to 1.0, the object disappears. So, even if you have defined the object as red, the object will be invisible and there will be no filtering effect at all.
result_color = kt * (kt * light_color + (1-kt) * object_color)
[A somewhat surprising formula, since there's a kt*kt term in there. -EAH]
An analogous problem appears with illumination models:
One use additive formulation, another (softimage) use multiplicative formulation:
result_color = local_color + ks * reflected_color + kt * refracted_color
result_color = (1-kt) * ((1-ks) * local_color + ks * reflected_color) +
kt * refracted_color
In the second solution, refraction is dominant.
I don't know what is better, but I think you are right. It's more easy to control the transparencies with the first solution: combining kt and the object's color. Maybe this is more difficult when the object is mapped because the object's color is given by the map and if you want a small color attenuation you have to transform all the map (to white)?
[Personally, I use a method between these two methods: things like diffuse and ambient and reflection get scaled by Kt, but the specular highlight does not. This makes it easier to control the highlight (which is a hack, anyway - you should really be reflecting the light source itself). -EAH]
By the way, when working on the special effects for the movie "The City of The Lost Children" a problem arose: When you compose a computer generated image on a real image you use a mask (alpha plane) for object occlusions. But what is the correct solution for mixing the object's shadows, too, and the reflection of that object on mirrors... We can do it all in a single image but we have never seen articles about such processes to know if we are wrong or right.
[I sort of understand this problem. Compositing is definitely a pain: for example, it's common to allow a texture map to act as a backdrop which fills the background. However, this backdrop has no physical location in the scene, so if you put a reflective or refractive object in the scene the map is not seen. Usually no big deal if you also just use the backdrop as a reflection/refraction map used when nothing else is hit, or perhaps actually give the texture a real location in space. -EAH]
____
Paul Heckbert (Paul.Heckbert@HOSTESS.GRAPHICS.CS.CMU.EDU) comments:
Yes, that is a nice little improvement. And I guess we would have to call it Bec's method!
As far as translucency, I suggest a formula like:
final_color = transparency*light_color + (1-transparency)*filter_color
where transparency = exp(-alpha*thickness)
and alpha is a parameter something like kt, controlling how much scattering there is, and thickness is the distance the ray travels through the transparent object.
I think you'll find formulas analogous to that in many computer graphics books.
back to
contents
I have another problem, again a useful result for ray tracing: what is the average cross-sectional area of the projection of a sphere vs. a bounding box around the sphere? In other words, given a sphere in a bounding box, what is the chance that an arbitrary ray (originating outside the bounding box) hitting the box will also hit the sphere?
The answer turns out to be the ratio between the sphere's surface area and the bounding box's area. In fact, surprisingly, the chance of hitting any convex object with a random ray is proportional to its surface area. Goldsmith & Salmon's automatic bounding volume hierarchy article was the first place I heard of this theorem, but I hadn't seen a proof, so I asked around.
________
From: Jim Arvo (arvo@cs.caltech.edu)
To answer your question, yes, the average projected area of a convex body is 1/4 its surface area. You can check out my SIGGRAPH course notes from 1990 for a (nearly) rigorous proof, or almost any book on geometric probability. I gave at least one reference to the theorem in my chapter of the ray tracing book. The 1990 course notes are not available on my web page yet, but they will be as soon as I find the file!!! I'm such a pack rat I know I have it somewhere!
[And indeed he found it, check out http://www.cs.caltech.edu/~arvo/papers.html and get the "Ray Tracing with Meta-Hierarchies" paper. There are other great ray tracing (and other) papers here which have appeared only in course notes or hard to find proceedings, e.g. "The Ray Tracing Kernel" and "Backward Ray Tracing". -EAH]
________
It turned out that the first entry I received won:
From: Han-Wen Nienhuys (hanwen@stack.nl) http://www.stack.nl/~hanwen
I'm not sure this is what you want, but the expectancy of the area of a projection of any convex object compared to the area of its surface is a fixed ratio. The ratio can be easily calculated, take a sphere:
projection: pi R^2 object area: 4 pi R^2
ratio: 1/4
The area of the boundingbox is 6*(2*R)^2, =24*R^2 and the expected area of the projection is 24*R^2/4=6R^2, so the ratio of sphereprojection vs. cubeprojection is pi/6.
I am just doing this from the top of my head. Last year's Dutch University Mathematics Competition had a similar question (expected area of an isotropic projection of a cube).
The answer suggested partitioning the convex object in triangles and then proving the theorem for arbitrary triangles.
The idea is this (let ExpArea be the expected area of a projection along a isotropically distributed direction, and "f" is the ratio we are trying to find):
1. For any triangle T.
ExpArea(T) = f * Area(T)
f does not depend on T.
2. For any convex polytope (made of triangles T_i)
P = Union_i T_i
So ExpArea(P) = ExpArea(Union T_i) = Sum_i ExpArea(T_i) = Sum_i f*Area(T_i) = f * Area(Union_i T_i) = f * Area(P)
(maybe I am losing a factor 2 somewhere, because a convex set has back and/or front side. It doesn't matter, any factors will be absorbed in f)
3. If C is a convex object, it can be approximated by a triangularization P, so
ExpArea(C) = ExpArea(P) = f*Area(P) = f * Area(C)
~ ~
The triangles can be made smaller, and the approximations (~) will be better. In the limit,
ExpArea(C) = f * Area(C)
for any convex C. f is fixed (does not depend on C)
4. f can be easily calculated: A sphere is (radius 1) is convex,
ExpArea(Sphere) = pi Area (Sphere) = 4 * pi
So f is 1/4
5. Area(BoundingCube) = 4 * 6 = 24, So ExpArea(BoundingCube) = 1/4 * 24 = 6
ExpArea(Sphere) / ExpArea(BoundingCube) = pi / 6
I know that this is only a so-so proof (if it is worth the name), step 1 and especially step 3 would involve some advanced math, but this is how you would prove it elegantly.
The result also generalizes to lower (2) and higher dimensions.
________
In case you didn't follow that, here's a talk through:
To state this a little more loosely, step one says that an arbitrary triangle and its average projected area have a constant ratio. This could use a little more proof, as he says, but here's an intuitive way to know that this is true. First, this is definitely true for the class of all equilateral triangles - there is some answer to what the average projected area is for some one equilateral triangle, and scaling up this equilateral triangle to a different size won't change the ratio "f" between the new area and new average projected area. So, now make an arbitrary triangle out of a million tiny equilateral triangles; sure, the edges won't be perfect (add another billion tiny triangles, then, i.e. take it to the limit) but the point is that the ratio "f" for equilateral triangles then applies to arbitrary triangles (or any 2D figure, in fact). So, now we informally know step 1 is true, that "f" is a constant.
Step 2 says that a convex object made of polygons will have a constant "f" ratio, too, same as in step 1. This is because from any angle, no part of the object covers another forward facing part of the object (it's convex). So, you can sum up all the triangles' areas since they do not interfere with each other.
Step 3 is sort of like my step 1 informal proof: it says that any convex object (e.g. curved) can be tessellated into triangles, something I think we all believe.
Step 4 is the clever part: a sphere is a convex object, and the nice thing about a sphere is that its projected area is the same from any direction. So now we simply work backward through the steps. For a sphere the projected area vs. the surface area is 1/4th, so "f" must be 1/4, and since we proved this "f" is constant we now know that it holds for all convex objects, so we can compute the answer to the problem in Step 5. If this proof seems bass-ackwards to you, check Arvo's paper for a formal integration of the projected area of an arbitrary triangle. I personally like the (looser) proof as is, since we never had to even integrate to prove it.
Note that the value of 1/4th is for a convex 3D object. The ratio is 1/2 for an arbitrary 2D figure's average projected area to its actual area (because we do not compute its actual area by adding its front area to its backface area), if both sides of the 2D figure are visible (i.e. no culling).
This result is handy for all sorts of things. Goldsmith and Salmon use it to compute a cost function for the relative chances of hitting a bounding volume, so helping them to optimize their hierarchy. Or, say you want to test a graphics rasterizer by tossing arbitrarily oriented polygons on the screen which will cover an average of 50 pixels each. By this theorem you know that (using a parallel projection) the triangles need to cover 100 pixels when viewed straight on.
________
And the "all mimsy were the borogoves" comment of the day on this problem...
From: Ken Musgrave (musgrave@seas.gwu.edu)
Just got back from a visit to Pixar, where Ronen remarked that they were having a conversation recently, the conclusion of which was "there's very little volume of a 48-dimensional sphere in a unit bounding box." Think about it: as the dimension D goes to infinity, the sphere's volume goes to zero. "All those corners to cut off," Ronen credited someone (I forget whom) with noting.
back to
contents
________
Internet Raytracing Competition
The Internet Raytracing Competition is an open competition held every two months. Participants may use any 3D rendering program.
http://www.povray.org/irtc
[This is kinda fun, and overwhelming in the number of entries submitted, e.g. I see about 110 images in the latest contest. You can vote on the entries; something to do while waiting for compiles to finish. Many images have "how I did it" information attached. -EAH]
________
POV-Ray Mirrors
This is a list of known mirrors of ftp.povray.org and ways you can access the mirrored files.
ftp or http://wuarchive.wustl.edu/graphics/graphics/mirrors/ftp.povray.org
ftp://ftp.shu.ac.uk/pub/computing/packages/raytrace/ftp.povray.org
ftp or http://www.hensa.ac.uk/ftp/mirrors/povray
ftp or http://ftp.nectec.or.th/pub/mirrors/ray-tracing
ftp://ftp.etsimo.uniovi.es/pub/raytrace
NB: not all sites carry all files. For example, etsimo does not carry the competition, mirrors, images or Hall-Of-Fame. The shu UK mirror, as far as I know, only carries a subset also.
________
Errata for "Principles of Digital Image Synthesis"
You can find the errata listing on the web at:
http://www.research.microsoft.com/research/graphics/glassner/work/projects/pdis/errata.htm
Thanks to all the bug-spotters on the To: line!
-Andrew Glassner (glassner@microsoft.com)
________
It is my pleasure to announce that my PhD dissertation is now available on the net. The dissertation is entitled:
It's all about global illumination models, Monte Carlo methods, variance reduction techniques, path tracing, light tracing and bidirectional path tracing. You can find the abstract, an overview of the chapters, the table of contents, the colour images and the dissertation itself at:
http://www.cs.kuleuven.ac.be/~ericl/thesis/
Even if you're not interested in the text you can just have a look at the pretty pictures. Enjoy! Kind regards,
Eric Lafortune
________
RayTraced Evolution
For info about RTEvol (RayTraced Evolution), a free package for procedural-modelling using Lindenmeyer-grammars and interpreted C-like macros/functions, look at this URL:
http://www.rz.tu-ilmenau.de/~juhu/GX/RTEvol/
Primarily I use this package to test some raytracing-acceleration techniques, but now it expands to a fully programmable system. It is an ideal tool for quick generation of test-scenes.
Have fun,
--JuHu (cn1@irz301.inf.tu-dresden.de)
________
Pete Shirley's moved to Utah, and his useful page has moved with him:
http://www.cs.utah.edu/~shirley
This page includes a focussed link list for Monte Carlo rendering techniques and a list of computer graphics related periodicals and conferences.
________
Grammar of Ornament now on CD ROM
I love the Dover book "The Grammar of Ornament" by Owen Jones. So I was happy to find that this book is now available on CD ROM; see
http://www.dimagin.com
This CD ROM is a labor of love; the creator, Stephen Hubbard, says it took 5 man years, $65K, and 3 girl friends to make.
________
Flatland now on the Web
While I'm on the topic of classics, the classic volume "Flatland" has been put on the web by Tom Banchoff, check out:
http://www.geom.umn.edu/~banchoff/Flatland/
You might also want to look at the projects Banchoff has been involved with (he's well-known for his visualizations related to topology, 4D spaces, etc):
http://www.geom.umn.edu/~banchoff/projects.html
________
ZRend
[ZRend is also mentioned in RTNv7n5; it is part of the Graphics Gems V distribution, and it has been improved since then by the author. -EAH]
The key features of this program are:
(a) Reads a variant of the standard Neutral File Format (NFF) as input (b) Outputs a 24 bit color TARGA file (c) Uses accurate fixpoint arithmetic in all its calculations (d) Works on X windows environment. We have tested it on Sun Sparc machines. (e) High Performance. The renderer has almost realtime performance.
This software is available through the Web and via anonymous ftp. The software includes sample files, including the teapot. We would appreciate any feedback you can give us on this software. We are quite impressed by the quality of the images produced. Enjoy the use of this utility!
http://www.cerc.wvu.edu/public_domain_sw.html
- Raghu Karinthi (raghu@cs.wvu.edu)
________
Application Challenges to Computational Geometry
This tech. report is now available at:
http://graphics.lcs.mit.edu/~seth/pubs/taskforce/techrep.html
- Seth Teller
[it's a report on the challenge of applying computational geometry to practical problems, among other things. Also check out http://www.cs.duke.edu/~jeffe/compgeom/ for comments on this report and for many other computational geometry resource links. -EAH]
back to
contents
%A Andrew Woo %A Andrew Pearce %A Marc Ouellette %T It's Really Not a Rendering Bug, You See... %J IEEE Computer Graphics and Applications %V 16 %N 5 %D Sept. 1996 %P 21-25
I found this is also on the web at http://ada.computer.org:80/pubs/cg&a/articles/g50021.pdf - very nice! See http://ada.computer.org:80/pubs/cg&a/backissu.htm for other IEEE CG&A back issues and articles/abstracts available online.
If you render, read this one. They point out many common bugs you'll run across. I had already run into many of these bugs, but a few were new ones I hadn't hit yet - it's great to get a warning of what to watch out for, sort of an "FBI's Most Wanted" list of rogues. Their "poor texture interpolation" bug (where a textured quadrilateral with one short side is badly rendered if split into two triangles) actually has an interesting limiting case: a tessellation of a cone. A good textured cone tessellation needs to have quadrilaterals for the faces, not triangles: at the cone tip you need two vertices, with the XYZ locations identical but the normals and texture coordinates different. Systems which show textures by splitting up quads into triangles and rendering these will improperly display such quadrilaterals.
____
%A Krzysztof S. Klimaszewski %A Thomas W. Sederberg %T Faster Ray Tracing Using Adaptive Grids %J IEEE Computer Graphics and Applications %V 17 %N 1 %D Jan/Feb 1997 %P 42-51
The short summary is: automatic bounding volume hierarchy with grids at each level. To make this scheme more profitable the authors discuss methods of merging bounding volumes and of nesting grids directly within voxels. It's nice to see some serious ray tracing efficiency research still being done, and the techniques and results are interesting and well-presented. Even if you just use grids, their section on setting the resolution of grids is a nice take-away (the gist is an idea I've heard of before, but I don't recall seeing in print: instead of giving a box of dimensions of say 1,4,9 a constant grid resolution along each axis, instead scale the resolutions proportionally with the box's dimensions. Timing results are given showing this to be a better method.)
____
%A Frederic Cazals %A George Drettakis %A Claude Puech %T Filtering, Clustering and Hierarchy Construction: a New Solution for Ray Tracing Complex Scenes %J Computer Graphics Forum (Eurographics '95) %V 14 %N 3 %C Maastricht, Netherlands %D 1995 %P C371-C382
This one's available on-line at http://flamingo.stanford.edu/~cazals/xfc_research.html. It's got some interesting ideas on forming efficient access structures. Specifically, it uses techniques such as histogramming and filtering of the object sizes to split up and then cluster objects of differing scales in order to efficiently ray trace scenes. I enjoyed it because it's a new way of thinking about the problem.
back to
contents
You make a great point about the fickleness of genetic algorithms. One problem is that if you the human need to judge each image, you have to see all these garbage tests. Using some automatic quality selection algorithm instead will prune for you, so while the generation effort is still wasted, it's automatic and you just let things cook a bit longer. But as we said, the quality of texture is more a human subjective thing. We need to stay in the loop! Here a fast CPU is still good for fast updates so the human can make their choices faster I guess...
But a more promising method of using genetic algorithms is to limit their scope. By feeding in a set of very complex primitives, simple combinations can make new and impressive surfaces using only simple combinations. Consider the impossibility of making a fractal noise cloudy surface with a genetic algorithm that can do only + - / *, if, and floor. It just wouldn't happen, though those operations are sufficient. But when it has noise() as a primitive, magic can happen!
So I see a way in which say a limited number of complex primitives (say two fractal noises, a sawtooth, and a radial ramp) and a limited number of simple operations (+-/* if.. sin,) get mixed together, with rules to prevent super-concatenation. 3*noise(x)+x+noise(sawtooth(x)) is fine, but sawtooth(noise(x+4*sin(noise(radial(x+1))))) is not. Maybe even limit it to simple binomial combinations.
The idea of this is that by limiting the genetic forms, you can limit the complexity of the textures (keeping them efficient) and you also limit the number of changes that can occur during a mutation or breeding. You give up some of the rich number of possible surfaces you might get by surprise, but the extra control may be reasonable. Have you used Kai's Power Tools texture explorer? It seems to have only a very few base algorithms, with only a few controls, though they also use a large selection of spline color maps. It's not overly complex, yet people play with it for hours.
Another aspect of genetic algorithms is perhaps more interesting. Forget changing the ALGORITHM, take any current man-made texture. Nearly all are driven by a list of parameters like "turbulence value" or "scale size", etc. What set of parameters looks best? Answer: jiggle a test test of parameters some way and let the user pick images until these parameters get set to some local user maximum happiness value. I mention this a bit in the postscript of my chapter in the texturing book. There's something to this. I don't know just how to do it yet. But it'd be very useful, both for end user as well as for developer.
[and here's another interesting bit from another note from Steve. -EAH]
My main idea is that the algorithm for choosing the new parameters is not obvious, and depending on the application it may even vary. So I may write a METAalgorithm which basically has a bunch of methods to try. It tries them all and notices which ones tend to make better pictures (as scored by the user). Then it starts using those selection methods more often. This can happen adaptively even as the user plays around. Maybe at first the user is just exploring, looking for many different types of appearances, until he finds a cool one he wants to refine. Suddenly his goals change; he wants one that's "like THAT but better", as opposed to "something cool not like these". Anyway, just a long-deferred project. I haven't thought about it for a year or so.
back to
contents
Basically I've compiled a list of reasons why would one use raytracing at all. Here it goes:
I doubt these (or other) reasons will ever push scanline based renderers like 3DS out of the picture.
Real world animation (visualization, games, ...) will always need faster results even with god knows how fast machines, academic research will without a doubt move to global methods like path tracing and particle tracing.
There is no easy (cheap) way to avoid aliasing in raytracing. This is going to be a dominating factor when raytracing moves (and it will, I'm sure) into mainstream production software. In production, quality is very important.
[Incidentally, check out Blue Sky Productions, http://www.blueskyprod.com/, for a company which uses pure ray tracing for production work. -EAH]
back to
contents
...a neat sampling scheme specifically for soft shadows. If a pixel is in shadow but its neighbor is not, both are sampled even more. If one of the pixels is in PARTIAL shadow, its neighbors are also sampled more. Pass #1 basically uses a single sample per pixel, but it identifies any shadow boundaries. The recursive "fill" algorithm used in pass #2 helps a lot since it works very hard on the soft areas but doesn't fire much more in solid light or solid dark regions. It worked surprisingly well. I meant to do the same for depth of field, but it was trickier and I never got around it. However, I really find the shadow "area growth" sampling to work exceedingly well; looking at a grey scale image of the number of samples taken for each pixel, the soft shadow regions are easily noticed.
This is good; you only do the horrible soft shadow work where the shadow really is soft.
back to
contents
As discussed in RTNv8n2, this "soft reflection" idea can actually be used in object space (instead of image space, as above). Microcosm (reviewed in RTNv7n5) (now called Megahedron, and available from Syndesis http://www.syndesis.com) actually implements this technique.
back to
contents
"Radiosity" is a computer graphics technique that enables you to synthesize photorealistic images. Whereas ray tracing techniques excel in the rendition of point light sources, specular reflections, and refraction effects, radiosity methods accurately model area light sources, diffuse reflections, color bleeding between surfaces, and detailed shading within shadows. They are in a sense complementary approaches to photorealistic rendering.
Folklore had it that you needed a graphics workstation with gigabytes of RAM or even a supercomputer to do radiosity rendering. This is no longer true: You can use your personal desktop computer -- a '386 IBM-PC with a math coprocessor, 4 MB of RAM, and a 256-color SVGA display will do nicely -- to experiment with radiosity methods. A 66-MHz '486DX machine will render a simple scene (540 polygons) in less than three minutes. A more complex scene with 2,700 polygons can be rendered in a little over six minutes.
Commercial radiosity renderers are slowly making their way into the marketplace. Take a look, for example, at the incomparable Lightscape Visualization system (http://www.lightscape.com) to see what is available now for Windows NT. (Other interesting sites on the Web for commercial radiosity renderers are http://www.bentley.com/products/masterpiece/ -- download the Microstation MasterPiece Technical Profile -- and the Italian http://www.atma.it/. [also Lightworks, http://www.lightwork.com/products/rad_over.htm. -EAH])
In the meantime, you can download HELIOS to experiment with the possibilities of radiosity rendering using MS-Windows 3.1 or Windows 95. The Web site is:
http://www.ledalite.com/software/software.htm
where you will find a demonstration version of HELIOS Version 1.03A (144 KB) and the complete C++ development package (700 KB), including four different executable versions of HELIOS, fully- commented C++ source code (over 12,700 lines), make files for Microsoft Visual C++ 1.5 and Borland C++ 4.5, online help files, two demonstration environments, demo images, and more.
(While you are perusing our Web site, you might want to look at http://www.ledalite.com/library-/ledapub.htm -- we have an eclectic variety of academic papers and articles on computer graphics and related topics available online for downloading.)
The HELIOS development package is *not* in the public domain. It is copyrighted material that may be freely copied, redistributed, and/or modified for personal, non-commercial use ONLY, provided the copyright notice is included with all source code files.
HELIOS was first developed in:
Ashdown, I. 1994. Radiosity: A Programmer's Perspective.
New York, NY: John Wiley & Sons, Inc. Softcover, 498 pages, 12 color
plates. http://www.wiley.com.
ISBN 0-471-30444-1 (without diskette) $39.95 US
ISBN 0-471-30488-3 (with 3.5-inch MS-DOS diskette) $54.95 US
[brief review and table of contents in RTNv7n3. -EAH]
This book provides a detailed explanation of radiosity theory and its associated algorithms (no knowledge of higher mathematics required!) More important, it also includes complete, fully documented, and compiler-independent C++ source code (over 7,500 lines) for HELIOS Version 1.00A, a fully-functional radiosity- based rendering program for MS-Windows 3.1, Windows 95, and Windows NT.
The radiosity-related code presented in the book is identical to that now offered online. If you want to fully understand how HELIOS (and radiosity) works, you more or less need to buy the book.
back to
contents
Carlo Sequin's group at UC Berkeley has done some good work in the area of culling scenes using cells and portals, the URL for his home page with related links is:
http://HTTP.CS.Berkeley.EDU/~sequin/
A good reference for this technical area is:
S. J. Teller and C. H. Sequin,
``Visibility Preprocessing for Interactive Walkthroughs,''
Proc. ACM SIGGRAPH'91,
Las Vegas, Aug. 1991, and
Computer Graphics,
Vol 25, No 4, pp 61-69, (1991).
Seth Teller is now at MIT, and here is the URL for his PhD Thesis which is focused on the cells and portals culling area:
http://graphics.lcs.mit.edu/~seth/pubs/pubs.html
David Leubke at UNC has implemented a cell-based culling system for Performer, see his URL at:
http://www.cs.unc.edu/~luebke/publications.html
back to
contents
Two books I've worked on last year are Keith Rule's "3D Graphic File Formats: A Programmers Reference", Addison-Wesley (see http://www.europa.com/~keithr/) and and Bridget Testa Mintz' "Graphical Treasures of the Internet", Academic Press (http://www.apnet.com/). I've also done some editing for parts of Rob Glidden's "Graphics Programming with Direct3D: Techniques and Concepts," Addison-Wesley.
"3D Graphic File Formats" is about the only book in its field. Murray and vanRyper's "Encyclopedia of Graphics File Formats" is about the only book that comes close at this point, and their volume is primarily about image file formats. Rule's book discusses VRML 1.0, DXF, 3DS, Wavefront OBJ, TrueSpace, WTK-NFF, POV-Ray 2.2, and RAW formats. For most readers Rule provides something no other book does: a working program for reading and writing each of these 3D formats and translating from one to another. It is written in C++, with a Windows framework to read/view/write models, along with an OCX custom control. The CD ROM also includes over 100 models not normally found on the web and trial versions of TriSpectives and TrueSpace. The best thing about the book: the DXF format is explained in English, not tech-ese. Credit for this accomplishment is shared by Rule and Zap Andersson, who has worked with the format for years.
Some limitations of the book should be mentioned. First, the software converts basic geometry, but currently does not support translations of surface vertex normals (i.e. any smoothing information is lost when moving between formats) or texture coordinates. It also does not have a serious polygon tessellator. So, you may have to get a professional translation program (Syndesis' InterChange, Okino's Polytrans, etc), for higher quality translations. Also, the book is not meant to be the final word on each specification; much of the book is dedicated to explaining how the software works, not how the format works. However, given the page limitations, this book is quite a feat. It is more than adequate for those who want to get under the hood and understand various 3D file formats, and for those who want to convert from their own file formats to others. Adding new format readers and writers is a fairly straightforward process; usually one of the formats Rule covers is similar to what you want to add, so that code can simply be regrooved to read in the new format.
Mintz' "Graphical Treasures of the Internet" is on the non-technical end of the spectrum. While a fair bit of the book is dedicated to explaining to beginners many of the basics of Internet, commercial services, and non-commercial alternatives (and I would bet that almost no one has tried all the resources she covers), there is also a fair bit of meat about other topics. There are interviews with a number of well-known computer graphics and Internet people and many different perspectives are presented. Personally, I found the chapter on copyright and software patents particularly interesting; it was something I felt confident passing on to our company lawyer for his own edification. There is also information here found nowhere else. For example, she presents a history of the comp.graphics.* hierarchy back as far as could be done. Mintz is an engineer turned professional writer, and it shows: this book is both well-written and well-informed.
Glidden's "Graphics Programming with Direct3D", from Addison-Wesley (http://www.aw.com/) is a pleasure to read, which is surprising given that the topic sounds dry as can be. His book talks about the place of 3D in the marketplace, motion capture, how to manage multi-user spaces, and other interesting topics which do not directly bear on the topic of Direct3D. The author is a long-time technical reporter on computer graphics and related topics, so his prose is readable and he can't resist commenting on many aspects of the field. He gives a great top-level view of various areas of the field, along with solid advice on Direct3D, e.g. whether to go with retained mode vs. immediate mode. There is also some information on 3D file formats such as DirectX, DXF, and 3DS, on the basics of 3D vector math, and on the fundamentals of graphics PC hardware. Given that the Direct3D API is still in flux (e.g. today I read how a new command, DrawTriangle, was just added to it), it means to me that this book actually could have a longer life-span than could be expected, as Glidden's discussions on more than just the nitty-gritty of using D3D will last well beyond the next beta release.
Many other books came out during 1996, of course. API books were a noticeable trend, witness "3D with HOOPS" by William Leier and Jim Merry, Addison-Wesley, with a CD-ROM with a personal version of the HOOPS library for the Mac, Unix, and Windows. Such software used to cost hundreds, if not thousands, of dollars for a single person license, but in the new market for mind-share prices have dropped. Same story for "Learn 3D Graphics Programming on the PC" by Richard Ferraro, Addison-Wesley, which is essentially a nicely done explanation of 3D graphics using the RenderWare API and includes a personal copy on CD-ROM - again, a few years ago a personal copy of this software would cost you about $1000.
Certainly of note is "Jim Blinn's Corner", from Morgan Kaufmann Publishers (http://www.mkp.com/). Finally, many of Blinn's IEEE CG&A column articles are assembled in one place. I personally wish they had just gone for it and published all 45 of his columns to date, but having these 20 in one place saves me a lot of flipping through old issues of CG&A. In case you've been missing out on this column, think "Graphics Gems" meets "Programming Pearls". Each chapter is around 10 pages long and focusses on a particular topic, like "How Many Ways Can You Draw A Circle?", "Subpixelic Particles", and "Backface Culling Snags". There is a lot of useful "here's what I think is the best/fastest/cleanest way to do this" type of advice. If you're a graphics programmer, why you don't have this book I cannot imagine.
What else is new? Well, there's a second edition of Murray & vanRyper's "Encyclopedia of Graphics File Formats", from O'Reilly, (http://www.ora.com/), which has bulked out a bit more with information on new formats like PNG and more on 3D file formats like 3DS. I still consider this primarily a 2D file format book (esp. now that Rule's book is out), but it's definitely the first place I look for information on such formats. Other than that, hmmm, I haven't gone wild buying new books this year I guess. There are a ton of new books on specific topics (e.g. I'd guess around 50+ on just VRML itself), but nothing else pops out at me as of general interest - if you know anything good I've missed, let me know!
Another book of note is Watkins & Mallette's "Stereogram Programming Techniques", from Charles River Media (http://www.charlesriver.com/). I beat this topic to death in RTNv8n1, reviewing two books in the process, so I have to admit that I've only skimmed through this new volume (the fad's past, right? Stereogram pictures are destined to be remembered as the black light posters of the 90's). This new entry in the field looks pretty good: it stresses the theory and programming behind the technique, and there's no hidden agenda to sell you any additional software. This book is considerably longer that the other two books I reviewed (it's about 450 pages), and so can take its time in presenting theory, code listings, etc. The stress is put on stereo pairs, SIRDS, and SIS (i.e. there are no text stereograms). All in all, it looks good, and also points the reader at other articles and resources.
For more book recommendations, try Brian Hook's page:
http://www.wksoftware.com/publications/3dbooks.html
Tastes vary, and I disagree with a few of his reviews, but the great thing for me was to hear about some books I've never even run across. Such a list gives you a chance to get some titles to page through at the bookstore and see if they look worthwhile (Also, there are some interesting HTML pages on Direct3D and OpenGL under the "publications" category at this site, if you're in to such things).
back to
contents