_ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_ karazm.math.uh.edu (132.170.108.2) in directory pub/Graphics J. Eric Townsend iear.arts.rpi.edu (128.113.6.10) in directory pub/graphics/ray George Kyriazis Australia Site: gondwana.ecr.mu.oz.au (128.250.1.63) in directory pub/rtabs Bernie Kirby Finland Site: maeglin.mt.luth.se (130.240.0.25) in directory graphics/raytracing/Doc Sven-Ove Westberg 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 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 =============================================== Ray-Cylinder Intersection Tutorial, by Mark VandeWettering >I am trying to do ray tracing of light through a >cylinder coming at different angle to the axis >of the cylinder. Could some one give me some >pointers? Ray cylinder intersection is (conceptually) just as easy as hitting a sphere. Most of the problems come from clipping the cylinder so it isn't infinite. I can think of several ways to do this, but first let me mention that you should consult Introduction to Ray Tracing edited by Andrew Glassner. Articles by Pat Hanrahan and Eric Haines go over most of this stuff. It's easiest to imagine a unit cylinder formed by rotating the line x = 1 in the xy plane about the y axis. The formula for this cylinder is x^2 + z^2 = 1. If your ray is of the form P + t D, with P and D three tuples, you can insert the components into the original formula and come up with: (px + t dx)^2 + (pz + t dz)^2 - 1 = 0 or px^2 + 2 t dx px + (t dx)^2 + pz^2 + 2 t dz pz + (t dz)^2 or (px^2 + pz^2) + 2 t (dx px + dz pz) + t^2 (dx^2 + dz^2) which you can then solve using the quadratic formula. If there are no roots, then there is no intersection. If there are roots, then these give two t values along the ray. Figure out those points using P + t D. Now, clipping. We wanted to have a finite cylinder, say within the cube two units on a side centered at the origin. Well, gosh, ignore any intersections that occur outside this box. Then take the closest one. Now, to intersect with an arbitrary cylinder, work up a world transformation matrix that transforms points into the objects coordinate system. Transform the ray origin and direction, and voila. You do need to be careful to rescale t appropriately, but it's really not all that hard. You might instead want to implement general quadrics as a primitive, or choose any one of a number of different ways of doing the above. Homogeneous coordinates might make this simpler actually.... Hmmm.... And there is a geometric argument that can also be used to derive algorithms like this. Think about it. It shouldn't be that difficult. ------------------------------------------------------------------------------- C++ Fractal and Ray Tracing Book, by Fractalman There's a very nice book called 'Fractal Programming and Ray Tracing with C++'by Roger T. Stevens and published by M&T Books. The book comes with a disk of sample programs for Zortech C++ but can be modified to be used with Turbo C++. The text is very easy to understand and you only need some rudimentary knowledge of C and computer graphics. ------------------------------------------------------------------------------- Ray/Spline Intersection Reference, by Spencer Thomas >Can someone please tell me where I can find an algorithm for >finding the intersection of a ray and a Bezier and/or B-Spline >patch. You might look at Lischinski and Gonczarowski, "Improved techniques for ray tracing parametric surfaces," Visual Computer, Vol 6, No 3, June 1990, pp 134-152. Besides having an interesting technique, they refer to most of the other relevant work. ------------------------------------------------------------------------------- Superquadric Intersection, by Rick Speer, Michael B. Carter Here's some material that may be of assistance. The following paper- "An Introduction to Ray Tracing", by Roman Kuchkuda, pp. 1039-60 in Theoretical Foundations of Computer Graphics and CAD, R. A. Earnshaw, Ed., Springer-Verlag, 1988. is a good introduction to the tracing of superquadrics. In addition to the usual overview material it gives actual source code, in C. This paper- "Robust Ray Tracing with Interval Arithmetic", by Don Mitchell, pp. 68-74 in the Proceedings of Graphics Interface '90, Canadian Infor- mation Processing Society (Toronto), 1990. focuses in particular on root-finding when intersecting a ray with an implicit surface. Mathematical and pictorial examples of tracing super- quadrics are given, along with data on the time-cost of intersections (when run on a SPARCstation). There's also some discussion of using the method for CSG. Finally, this thesis- "Implementation of a Ray-Tracing Algorithm for Rendering Superquadric Solids", Bruce Edwards, Masters Thesis and Technical Report TR-82018, Rensselaer Polytechnic Institute (Troy, NY), December 1982. probably goes into more detail than either of the papers mentioned above. [Actually, it doesn't: there's one page on intersecting superquadrics, which says something like "use Newton's Method" and gives a reference number, which turns out to be a "private conversation with Alan Barr". --EAH] -------- >From Michael B. Carter: I was just digging through my literature and finally came up with the reference that was stuck in the back of my mind. I cannot vouch for the speed of this method, but here's the ref. Kalra, Devendra, and Alan H. Barr, "Guaranteed Ray Intersections with Implicit Surfaces," Computer Graphics, Vol. 23, No. 3, July 1989. This method uses Lipschitz conditions to intersect ANY implicit surface. It always finds the closest (or subsequent) intersection points -- even in badly behaved functions. There are also some really neat pictures of blended objects in the paper. ------------------------------------------------------------------------------- Comments on Interval Arithmetic, by Mark VandeWettering, Don Mitchell First some comments by Mark: >> "Robust Ray Tracing with Interval Arithmetic", by Don Mitchell, pp. >> 68-74 in the Proceedings of Graphics Interface '90, Canadian Infor- >> mation Processing Society (Toronto), 1990. [Rick Speer] > > Interesting paper, though I admit to not having tried its method yet. >Looks like a great general method for superquadrics and whole families of >surfaces. My favorite paper of this proceedings. [Eric Haines] Very interesting paper, but I believe that the convergence of the method is quite slow, even slower than bisection. I coded up a version of it for the MTV raytracer, and was testing it out when it was clear it was converging VERY slowly. If anyone has some hints, or wants to discuss this further, send me some email. The reason I was interested in this scheme is that it would allow you to trace non-linear rays (rays could be generalized to space curves) which would allow more generic transformations of objects (ala Al Barr). You can use geometrical properties of the superquadric to figure out intersections. There can be at most two intersections in any octant of the superquad, so a primitive method would be to handle each octant separately and then use some favorite numerical method (Newtons or bisection) to home in on the roots. -------- Don Mitchell responds: The interval-arithmetic algorithm is a root-isolation algorithm. It gets used in combination with root-refinement (something much faster than bisection and much safer than Newton's method, hopefully). The speed of convergence depends a lot on how you are refining intersections. If you are just performing the interval algorithm until it converges to a root, that would be very slow and not really a proper application of the method. For a benchmark image containing a number of 4th degree algebraic surfaces, the interval method was about three times slower than a specialized polynomial solver (e.g., Sturm sequences). Its hard to compare its run time on transcendental surfaces, since I don't know any other way except Kalra's Lipschitz method (described in SIGGRAPH 89). I think interval arithmetic is more straightforward than the Lipschitz methods, particularly for surfaces with singular gradients (like concave superquadrics). It does not require an off-line human calculation to derive Lipschitz conditions. There are also a lot of improvements that I didn't mention (or implemented later). For example, there are faster interval multiply algorithms than the one I gave. You can do the root isolation algorithm with (F, dF/dt) instead of (F, grad F). There are also ways of using the derivative intervals to narrow the function intervals with the mean-value theorem. Like a lot of techniques, there is a long journey between theory and implementation. ------------------------------------------------------------------------------- Platonic Solids, by Alan Paeth Coordinates for these and for their four-dimensional analogs were published by HSM Coxeter, first in 1948 in _Regular Polytopes_, pg. 52-53 (Methuen, London) and again in subsequent revisions; any/all are highly recommended reading. The table for (quasi) regular 3D polyhedra is transcribed below. I've posted this a few times already; perhaps a "frequently asked" entry is in order. PLATONIC SOLIDS (regular and quasi-regular variety, Kepler-Poinset star solids omitted) The orientations minimize the number of distinct coordinates, thereby revealing both symmetry groups and embedding (eg, tetrahedron in cube in dodecahedron). Consequently, the latter is depicted resting on an edge (Z taken as up/down). SOLID VERTEX COORDINATES ----------- ---------------------------------- Tetrahedron ( 1, 1, 1), ( 1, -1, -1), ( -1, 1, -1), ( -1, -1, 1) Cube (+-1,+-1,+-1) Octahedron (+-1, 0, 0), ( 0,+-1, 0), ( 0, 0,+-1) Cubeoctahedron ( 0,+-1,+-1), (+-1, 0,+-1), (+-1,+-1, 0) Icosahedron ( 0,+-p,+-1), (+-1, 0,+-p), (+-p,+-1, 0) Dodecahedron ( 0,+-i,+-p), (+-p, 0,+-i), (+-i,+-p, 0), (+-1,+-1,+-1) Icosidodecahedron(+-2, 0, 0), ( 0,+-2, 0), ( 0, 0,+-2), ... (+-p,+-i,+-1), (+-1,+-p,+-i), (+-i,+-1,+-p) with golden mean: p = (sqrt(5)+1)/2; i = (sqrt(5)-1)/2 = 1/p = p-1 -------- The poster wanted a circumscribing (unit) sphere. Just pick a vertex and calculate its length (to the origin) and you have R, that sphere's radius. Normalize (divide all coordinates by R) and the solids are contained by a unit sphere. Alan Paeth Computer Graphics Laboratory University of Waterloo ------------------------------------------------------------------------------- Moon Problems, by Ken Musgrave et al > Am I correct in a vague memory I seem to have, that the (Earth's) moon is >supposedly a near-ideal Lambertian reflector? > > There's something fishy here, methinks. The moon is not lambertian. If it were, then a full moon would be bright at the center of the disk, and fade into black at the edges. Instead, a full moon is a fairly uniformly colored disk. If you assume the lambertian surface has a scattering probability kcos(theta), you might guess that the moon is just k (scatters in all directions above the surface with equal probabilities). I think this will work for a simple model. pete PS-- I saw some angular reflectance curves in some book I can't find. I think it was a heat transfer text. The actual function was pretty funky. -------- Alain Fournier responds: As this is one of my favorite trick question about reflection, I'll bite. Consider the moon when full (that is the sun -the light source- is in the same direction as the observer -the eye. It is pretty obvious that it appears essentially as a disk, that is the reflected light is about of same luminance all over the visible part of the moon (I ignore the effect of the surface details such as the maria). That shows that it is neither a specular reflector (the center would be a lot brighter than the periphery, nor a diffuse reflector (the center would be somewhat brighter than the periphery (try this on your favorite renderer, a perfectly diffuse white sphere illuminated from the direction of the eye). So what's going on. Well, as most of the computer graphics types (us) ignore, the world is not all between totally diffuse and totally specular, there are surfaces outside of this. In the case of the moon, it so happens that a Phong model (using the expression loosely) with an exponent of 0.5 for the cosine of the angle normal/light gives the right appearance of a disk at full moon. I can find exact references back in my office, if anybody is interested. Credit where credit is due: Bob Woodham, of UBC, first pointed that out to me, and has worked on the subject of models for the surface reflectance of the moon (and other objects in the solar system). -------- Doug McDonald replies: Remember that the moon has hills and valleys. The hills near the terminator are what one sees, and the actual surface is seen at an angle much less than 90 degrees. The actual surface itself is sort of Lambertian. At least when I actually examined some small (~5 cm) size pieces of the Moon in a lab they looked rather Lambertian. On the spot reports agree. The word "fractal" comes to mind. -------- Paul Heckbert writes: As others have mentioned, the moon and other dusty surfaces are not Lambertian. Blinn, in the paper cited below, says they follow the Hapke-Irvine illumination model more closely. %A James F. Blinn %T Light Reflection Functions for Simulation of Clouds and Dusty Surfaces %J Computer Graphics (SIGGRAPH '82 Proceedings) %V 16 %N 3 %D July 1982 %P 21-29 %K shading %Z Hapke-Irvine illumination model ------------------------------------- Ken gave another problem with rendering the moon: > A very wide-angle view of a scene (i.e., a landscape), with a sphere >(i.e., a moon) in an extreme corner of the image, sports one very distorted >sphere in the image, when rendered using the standard virtual-screen model >for ray tracing. (See the cover of Jan. '89 IEEE CG&A for an example.) > > Seems that this is a version of the sphere-to-plane mapping problem, and >therefore inadmissible to a non-distorting solution. > > Can anyone out there prove this conjecture right or wrong, or demonstrate >some nice workaround? > Yes, this distortion is due to sphere-to-plane mapping. Actually, the volume defined by the rays joining every point on the sphere to the center of projection will be a cone. Now an intersection of this cone with a plane will invariably result in an ellipse. So EVERY sphere, should look like an ellipsoid in a ray-traced image which uses this model. But the distortion is prominent only for spheres located in extreme corner of the scene. I also encountered the same problem and would be interested in any method or projection-model which circumvents this problem. If the pin-hole camera model is not a good model for the human eye-brain system then is there any other model which is more accurate? Dilip Khandekar -------- A solution I can see is to have each pixel, instead of having a calculated position on a viewing plane, have each instead with a calculated horizontal and vertical angle from the center. Knowing the angles, one can easily construct a vector of the appropriate angles to represent this pixel's ray. I have not actually implemented this, but it is obvious that this would work, as when a conventional method is used and the viewing plane is located far from the eye point, the near-spherical approximation of the plane is good enough to remove most any distortion. The reason why a conventional camera does well is due to the same phenomenon -- it takes a spherical "bunch" of rays and maps them to the film plane. If I ever get my present thesis out of the way, I will attempt to implement this in my version of DBW_Render. Prem Subrahmanyam [If I understand this correctly, the idea is doing equal angle spacing of rays, instead of equal increments on the image plane. I gave this suggestion to Ken, then quickly tried it out & found it lacking, as it distorts straight lines into curves and I forget what else. See the next entry. --EAH] -------- This rings a bell in my mind, since I once by mistake in my raytracer did a purely 'angular' perspective model, i.e. the x axis of the display was really the angle of the ray in the ground plane, and the 'y' coordinate was the angle from that plane... the image looked.... different.... well, anybody implemented some kind of 'different' perspective model? Ideally, you would hook up the user's face to the screen via a telescopic pole, and pull it via pneumatic cylinders to the correct viewing distance, and the rendering equation should of course not project onto a plane, but onto a slightly curved ditto (i.e. a computer monitor). Now we would hear no more whining about perspective distorsion.... ;-) No, seriously, anybody tried twiddling with it? I did (by mistake) in my tracer but, well.... nah, not good... And the problem is, also, that these twiddlings are only easy to do in raytracers, since linear-things (polygon's and such) may get non-linear sides when you twiddle (har har for you Z-buffalos ;-) Zap Anderssen -------- You might like to experiment with mimicking the distorting effect of camera lenses. Lenses which behave like renderers are very expensive, and are called something like `flat-plane lenses' (surprise). Ordinary lenses exhibit distortion (it's called that in optics books). Positive distortion makes flat squares look like pillowcases, negative makes them look weird. A way to model positive distortion is to move points in the picture closer to the center. A point that starts off at (r, theta) on the image plane in polar co-ordinates would move to (r', theta) where, in two popular approximations: r' = r (1 - C * r * r) r' = r * cos (C * r) for appropriate (small) constants C. Of course, I was working with images. In a ray-tracer, you would distort the directions of the rays by using the inverse transformation to splay the rays from the camera outwards. NO guarantees that it will fix the problem, but it is not a million miles away from this discussion.... Ian D. Kemmish -------- If the distorsion is too large, look for conformal mappings. A conformal mapping would transform _small_ circles to circles. The most general conformal mapping from the sphere to the plane is a stereographic projection followed by an analytic transformation of the complex plane. Read the Shaum book on complex variables, do all the problems and start tinkering :-). Pierre Asselin, R&D, Applied Magnetics Corp. -------- Pictures generated with a standard perspective camera model only look "normal" if the viewing angle used during rendering matches the angle at which you view the picture. If you use a horizontal view angle of theta during perspective rendering, and view the pictures on a monitor of width w, then if you view the screen at a distance of d = w/2*cot(theta/2), the picture will not look distorted. Here's a little table for a w=14" screen: telephoto about normal wide angle view angle (degrees), theta : 10 50 90 recommended viewing distance, d : 80" 15" 7" The same argument applies in photography: shoot a photograph with a standard (50mm focal length) lens, print it at 8x10" size, say, and it will look pretty normal when viewed at a distance of about one foot. If you shoot a picture with a wide angle lens (24mm, say) and print it at 8x10, you will perceive "perspective distortion" if you view it at a distance of a foot, but it will look much less distorted if you hold it close to your face, so that your viewing angle matches the view angle captured by the lens. The argument also applies in projection of movies and slides: there is only one point in a movie theater from which a viewer will see the same image as that seen by the camera (i.e. same angle of view). Theater geometry and the lenses used for shooting and projection are usually chosen to put that "ideal viewer position" near the middle of the theater, I imagine. Assuming perfect filming and projection and one eye closed, viewers at this ideal position will not see any distortion artifacts of the projection -- that is, they will not be able to tell the difference between a projected film and a window into a 3-D scene. Viewers not at the ideal viewing position, such as those in the first row, will see the familiar artifacts of perspective "distortion" that will easily allow them to distinguish between a projected image and a real 3-D scene. Another interesting observation about projections is that you can project onto ANY shape screen you like (planar, spherical, cube corner, curtain, human torso, ...) and there will be no artifacts of the projection if the projection lens matches the shooting lens, the viewer is right at the projector, and the surfaces are properly finished. --- Related question: is there a formula relating camera lens focal length and angle of view? (I would guess that such a relationship would not be theoretical, but would be based on practicalities, and would vary from manufacturer to manufacturer) Paul Heckbert -------- In reply to Paul Heckbert: Focal length and angular field are independent. For example, you can have a 50mm focal length lens which is a "standard" lens for 35mm photography, or a 50mm wide angle lens for a larger film format. There are some applications (enlarging?) where it is sometimes recommended to use a wide angle lens from a larger film format in place of a standard lens to assure better field uniformity. For a family of lenses designed for a given film size, then of course there will be a relationship between focal length and field of view, since economics dictate that the field of view should be no larger than necessary. Note that the field does not have a sharply defined size, but that the intensity drops off continuously at the margins of the field (vignetting). Jeff Mulligan -------- In response to Paul's related question: The relationship is fairly straightforward as I understand it. Think pyramid where the width and length of the base are defined by the image dimensions and the height is given by the focal length. The formula for the angle is simply: angle = 2 * atan(film_size/2 / focal_length) For 35mm film, whose image dimensions are 34mm by 23mm (approx.), the view angles for a standard 50mm lens are 37.6 by 25.9 degrees. Greg Ward -------- If Ken is rendering an outdoor picture at night with the moon in it, then it is probably a very wide angle picture, and you are absolutely correct that the answer is "stick you face closer to the screen and it will look ok." You state: >there is only one point in a movie theater from which a viewer will see the >same image as that seen by the camera (i.e. same angle of view). Theater >geometry and the lenses used for shooting and projection are usually >chosen to put that "ideal viewer position" near the middle of the >theater, I imagine. You don't have to imagine. You are exactly right. I remember this from filmmaking books I read in high school. A 35mm movie camera uses 50mm lenses as the "normal" lens. A 35mm film projector uses a 100mm lens so the picture looks right when you are seated half way between the projector and the screen. (I don't remember the numbers for "Panavision" or other wide screen systems.) Use of telephoto or wide angle lenses in the camera produces some distortion to the viewer at the center of the theater. This is something very important to film directors. All films are done this way. They understand it. I have never heard this issue mentioned in the context of computer graphics. Maybe no one knows this? As to your question: >is there a formula relating camera lens focal length and angle of view? Such a formula is simple, if the lens has no distortion, and the size and shape of the film is known. Where distortion is distortion in the strict optical aberration sense. Any optical system is subject to several aberrations to varying degrees. These are: spherical abberation coma astigmatism curvature of field distortion longitudinal chromatic aberration lateral chromatic aberration Distortion is non-uniform magnification across the field of view. Magnification usually varies slightly as the angle off the optical axis varies. This gives rise to "barrel" (negative) or "pincushion" (positive) distortion. Named, for what the image of a square looks like when subjected to said distortion. For camera lenses, you can safely assume the distortion is very small except for wide angle lenses (which is probably the case you were interested in). I expect that lens manufacturers would be reluctant to release the actual numbers describing their lens's performance, since most people couldn't tell the difference anyway. For a lens focused at infinity and flat film, fov = 2 * atan ( film_width / ( 2 * focal_length ) ) The only difference between a distortionless lens and an ideal pinhole camera with respect to field of view is that if the lens is focused at a finite distance, replace focal_length in the above formula with: 1/(1/focal_length - 1/object_distance) which is the lens to image (film) distance. Chuck Grant -------- >Related question: is there a formula relating camera lens >focal length and angle of view? The way this is done for a rectilinear lens (everything one ever encounters short of optics with high distortions or a fisheye) is based on the size of the image formed. In an "ideal" lens -- a pin-hole is a nice first approximation -- the field is as large as you want -- the negative or film holder or other physical limitation defines the "field stop". In a more complex lens the diameter of some internal element might serve to define the field stop -- a 50mm lens for a 35mm SLR would probably not be able to produce a ~250 mm image circle if mounted on a large format camera's lens board. If if could it would make a tremendous wide angle! If the linear field F is given, then you can use the dimensionless relation: 2 tan(A/2) = F/EFL to solve for angular field A or effective focal length. This says (for instance) that a conventional SLR with 43 mm film diagonal (35 mm film is 24 mm x 36 mm; hypot(24,36)~=43) will cover a reasonable, mildly wide-angle 53 degree (diagonally) angular field with a 43 mm lens installed. Alan Paeth -------- So using the (theoretical! yay!) relation angle = 2 * atan(film_size/2 / focal_length) with 35mm film format, which I'm taking to be 34mm wide by 24mm high (Greg Ward's numbers; Alan Paeth's numbers differ slightly: 24x36), we get the following correspondence for some common lens focal lengths: focal length (mm) 24 35 50 80 200 horizontal angle (deg) 70.6 51.8 37.6 24.0 9.72 vertical angle (deg) 51.2 36.4 25.9 16.4 6.58 Paul Heckbert ------------------------------------------------------------------------------- Shadow Testing Simplification, by Tom Wilson Out of nowhere, I have come up with a new (?) speedup (?) technique for shadow testing in ray tracing. I don't have the kind of code necessary to test it. It is kind of the inverse of a bounding volume: Consider an expensive-to-intersect object (and for this example, a convex solid. I'll generalize later). Now typically a bounding volume tells you when a ray misses the object or parts of the objects (for hierarchies). Eventually you have to intersect the object itself (I'm assuming the object hasn't been broken down into polygons or whatever). Now what would be good is a volume that, if intersected, would tell you the object is hit without intersecting the object at all (of course it won't always work). Suppose for this example we have a bloboid sphere or a megafaced convex polyhedron and we put a sphere inside the object such that the entire sphere is enclosed in the real object. Now if a ray hits the sphere, it definitely hits the object. If the ray misses the sphere, it may still hit the object somewhere between the bounding volume and the "inner tube" volume. Now this scheme is ideal for shadow testing, since where the object is hit by the ray is usually irrelevant. A "normal" ray needs the intersection point, so this scheme may not help much (I don't know). ::::::::::::: An ugly (and pretty bad) 2D example: : 000 : : 00 00 : 0's define the sphere inside the object :'s : 0 *--: : 0 0 -:-- : 0 0 : ---- : 0 0 : ----< Shadow ray that hits at * ::: 00 00 : :::000 : :::::: The object could really be any type of object (not just convex) provided a sufficient inner tube volume can be constructed. It's really the same problem as the bounding volume: the better the bounding volume (inner tube) the more rays that are culled as misses (hits). Is it feasible? I don't know. I don't have any complicated-objects code in my tracer, so I can't test yet (without writing the code first obviously). Perhaps someone who has the type of setup necessary can incorporate this and find out (for that matter, has anyone already done it?). If it's a good scheme, maybe I should change my thesis 8-) (I really just wanted to get into the next issue of the RT News). Please give some feedback. -------- Reply from Mark VandeWettering: My guess is that while this would work, it is not necessarily a good thing to do. Whether it is an actual speedup is basically a result of how often you hit the internal bound versus how often you hit the object. As a crude guess, we might imagine that the probability of hitting an object is roughly proportional to its surface area. Further suppose that our complex object has surface area = A, and for the sake of argument, spherical. As a typical example of our inner bound, lets assume it is a sphere as well, but with radius 10% smaller. (This seems pretty tight, I bet you could not do much better for real objects). If the object has unit radius, its surface area is 4*Pi. Our "unbounding sphere" has surface area .81 * 4 * Pi. So, we can assume for this argument that 81% of all rays that penetrate the object will penetrate the inner volume. Examining the costs: 81% of the time: we just intersect the cheap volume 19% of the time: we need to intersect BOTH volumes to determine whether or not the object intersects the ray. To generalize: let C(cheap) be the cost of intersecting the cheap volume C(object) be the cost of intersecting the real object p be the probability of a ray which hits the object hitting the inner cheap bounding volume. Then, this scheme is a potential speedup if p C(cheap) + (1-p) * (C(cheap) + C(object)) < C(object) Is this a speedup? I dunno. One scene in Eric Haines' SPD data base includes a large gear with 144 edges. The polygon intersection routine I use is linear in the number of edges for a polygon. The majority of rays fall within a disc which probably accounts for 90% or more of the total area of the face. I am pretty sure that a scheme like you suggest would be useful for this case. But in general? I dunno. It really depends on the probability p. For most objects, my guess is you might be able to get p = 0.5, which would make the inequality something like C(cheap) + 0.5 * C(object) < C(object) or C(cheap) < 0.5 * C(object) which actually does seem to make it attractive. In general, if the ratio of C(cheap)/C(object) = r, then we can solve for the percentage of inner bounding volumes we need to make this scheme profitable. p C(cheap) + (1-p) C(cheap) + (1-p) C(object) < C(object) p C(cheap) + C(cheap) - p C(cheap) + C(object) - p C(object) < C(object) C(cheap) + C(object) - p C(object) < C(object) - p C(object) < -C (cheap) p > r What this means, if the ratio of speed from cheap to expensive is 1/10, then we need to have probability greater than 10% to achieve a speedup. Hmmm. This probably bears looking into. Any comments? -------- John Gregor comments: Well, to add another data point, the Wavefront software has both a "trace object" and a "shadow object" associated with each object being rendered. The trace object is the object used in reflections. Usually, these objects are left undefined, or point to a lower complexity, but similarly shaped, object. Since shadows and objects appearing as reflections are typically small and are there to provide visual cues and since Wavefront's running time is decidedly non-linear to number of polygons in the scene, this is a win. Also, you can achieve some neat tricks using this. You can have an object cast a shadow from a completely different object (e.g. a kitten casting a lion's shadow) or appearing as something else in mirrors. Using the same object with a different offset or scale can lead to some pretty neat effects occasionally also. -------- Rick Speer writes: I'd like to add my $0.02 and note that W. R. Franklin examined this idea in a non-raytracing but similar context in the following paper- "3D Geometric Databases using Hierarchies of Inscribing Boxes", pp. 173-80 in Proceedings of "CMCCS '81" (this is what the Canadian conference now known as 'Graphics Interface' used to be called; these volumes are available from the Canadian Information Processing Society, Toronto, if anyone's interested). To be more specific, let me quote a bit from the paper's abstract- "Hierarchical tree structured databases are an efficient way of representing scenes with elaborate detail of varying scales. Storing a circumscribing box around each object is a well known method of testing whether the object intersects or obstructs any other objects. This paper proposes another aid: an inscribing box. The inbox is a polyhedron that is completely contained in the ob- ject. It should be as large as is easy to determine... The inbox speeds up visibility tests [in the following way:... ] [He concludes,] By combining inboxes and circumboxes, it is possible to calculate the visible surfaces of a hierarchical scene in time linear in the visible complexity of the scene..." In his followup message, Mark goes on to note that this issue really needs to be studied on test scenes using a probabilistic analysis. I hope it wouldn't be too immodest of me to note that such an analysis appears in the paper, "A Theoretical and Empirical Analysis of Coherent Ray-tracing", L. R. Speer, T. DeRose and B. Barsky, pp. 11-25 in the Proceed- ings of Graphics Interface '85, CIPS, Toronto, 1985. ------------------------------------------------------------------------------- SIMD Parallel Ray Tracing, by George Kyriazis, Rick Speer In article <9308@mirsa.inria.fr> kjartan@puce.inria.fr (Kjartan Emilson) writes: > >Does anybody have an algorithm for a massively parallel raytracer, >which could for example run on a Connection Machine, i.e a machine >with a 'single instruction - many data' architecture ? > The ray-tracing algorithm is usually parallelized ray-at-a-time, which makes it suitable for MIMD machines. If you want to run it on an SIMD you have a problem, since you have to advance all rays at the same time, then filter out which rays do not need a second reflection, and trace the second level, etc. I believe that Scott Whitman (at uiuc?) has written a ray-tracer for a SIMD machine. I don't remember any details. Pick up the SIGGraph proceedings for either '88 or '89 (don't remember which one) on ray-tracing or parallel computer architectures for computer graphics and you are going to see his name there. -------- Rick Speer writes: A fair amount of literature is beginning to appear on this subject. The references below should get you started. "3D Image Synthesis on the Connection Machine", Franklin C. Crow, Gary Demos, Jim Hardy, John McLaughlin and Karl Sims, pp. 254-69 in Parallel Processing for Computer Vision and Display, P. M. Dew, T. R. Heywood and R. A. Earnshaw, Eds., Addison-Wesley, 1989. "Ray Tracing on a Connection Machine", H. C. Delaney, pp. 659-67 in the Proceedings of the 1988 International Conference on Super- computing, ACM, July, 1988. "Ray-tracing Parallelization on a SIMD/SPMD Machine", PhD. Thesis, Marie-Claire Forgue, Laboratoire de Signaux et Systemes, Universite de Nice, Nice, France, September, 1988. "Distributed Ray Tracing Using an SIMD Processor Array", A N. S. Williams, B. F. Buxton and H. Buxton, pp. 703-25 in Theoretical Foundations of Computer Graphics and CAD, R. A. Earnshaw, Ed., Springer-Verlag, 1988. ------------------------------------------------------------------------------- Rayscene Animator, by Jari K{hk|nen [sic] Thanks to all people who voted for Rayscene. It's now available from tolsun.oulu.fi. Version is 1.3, which the first published version of Rayscene so docs are not perfect. But we are working on it... The stuff is in directory /pub/rayscene. Directory also contains two ani- mations for PC and animation player (Autodesk Animator AAPLAY.EXE). Those animations were made with Rayscene and DKB-raytracer. Enjoy. Also stuff for Amiga should be available soon. More information from hole@rieska.oulu.fi or oldfox@rieska.oulu.fi -------- There are a few animation demos, made with the "Rayscene" animation utility FTPable from tolsun.oulu.fi (128.214.5.6) in the directory /pub/rayscene/anim.PC (for "Autodesk Animator" on the PC) and in /pub/rayscene/anim.amiga (for "Movie" on the Amiga). Here is a short description of the animation files: PC-stuff: aaplay.lzh Autodesk Animator animation player, freely distributable rdice.lzh One mirrored die rounding over chess board 2dice.lzh Two dice ... movdice.lzh same as above, but viewpoint moves bouncing.lzh Mirrored ball bouncing over chess board 2balls.lzh Two mirrored, color-changing balls moving over wavy surface. Animation data files created with Rayscene's soon-released utili- ty, "Sin". Data file and array file by Panu Hassi. This animation (Amiga version) can also be found from anim.amiga NOTE: When Sin is released with Rayscene version 1.31, datafile and arrayfile are included (and explained too.) vortdemo.lzh Combination of three different animations:cylinder, mech and Chess. These animations are usually distributed with VORT-tracer. NOTE: No Rayscene used. Just for fun...and there seems to be a request for raytraced animations... Amiga: At the moment, only 2balls is available. There's going to be more... Rayscene was released only a few weeks ago, so there are going to be more animations here. Email me for more information. NOTICE: Rayscene is now available from iear.arts.rpi.edu also. (Directory /pub/graphics/ray/rayscene). Animations are available only from tolsun... P.S. DKBTracer was used for rendering. ------------------------------------------------------------------------------- SIPP 2.0 3d Rendering Package, by Jonas Yngvesson and Inge Wallin We just posted the source code to sipp 2.0 in comp.sources.misc. It may be a while before it appears due to moderation, though. Here is an excerpt from the README file: ******************************************************************* sipp 2.0 -- 3d rendering package by Jonas Yngvesson jonas-y@isy.liu.se Inge Wallin ingwa@isy.liu.se Linkoping Institute of Technology Sweden ******************************************************************* This is the beta-test release of version 2.0 of SIPP, the SImple Polygon Processor. SIPP is a library for creating 3-dimensional scenes and rendering them using a scan-line z-buffer algorithm. A scene is built up of objects which can be transformed with rotation, translation and scaling. The objects form hierarchies where each object can have arbitrarily many subobjects and subsurfaces. A surface is a number of connected polygons which are rendered with Phong interpolation of the surface normals. The library has an internal database for the objects that is to be rendered. Objects can be installed in, and removed from, this database at any time. The library also provides 3-dimensional texture mapping with automatic interpolation of texture coordinates. Simple anti-aliasing is performed through double oversampling. A scene can be illuminated by an arbitrary number of light sources. A basic shading algorithm is provided with the library, but the user can also use his own shading algorithms for each surface to produce special effects. Images are produced in the Portable Pixmap format (ppm) for which many utilities exist. ------------------------------------------------------------------------------- 3DDDA Comments, by John Spackman 3d-dda's are prone to many special cases, especially when line slopes approach zero (so the the inverse line slope, generally used as the increment a la ARTS) approaches infinity. A more numerically stable & hence more robust generalization of Bresenham's algorithm to 3D, which navigates ALL the voxels intersected by the ray is described in `Scene Decompositions for Accelerated Ray Tracing', John Spackman, PhD Thesis The University of Bath, UK, 1990. Available as Bath Computer Science Technical Report 90/33 Copies can be ordered from Angela Coburn at JANET: `amc@uk.ac.bath.maths' or ARPA: `amc%maths.bath.ac.uk@nsfnet-relay.ac.uk'. Any surface mail should be addressed to:- Angla Coburn Mathematical Sciences The University of Bath Claverton Down Bath AVON BA2 7AY UK However, uniform spatial division is generally wasteful in memory costs, being non-adaptive. I prefer octtrees - the above thesis describes an incremental ray navigation of octtrees & techniques for octtree construction (& indeed for building Uniform grids). - `My way's better than everyone elses' :-) ------------------------------------------------------------------------------- Radiosity Implementation Available via FTP, by Sumant (sumant@shakti.ernet.in) I have carried out some Radiosity implementations as part of the investigation into light equilibrium based rendering methods for my doctoral work. To test the implementation, I have used a very simplified scene modeler, BOX. BOX supports only box as the modeling primitive and translation and scaling as the modeling transformation. I am looking for some good planar surface model data. Interested netters may please send me data with the data format. I will try to provide the input interface for the sent data formats. The implementation is available at our FTP site (pub/Rad.0.1.tar.Z at sbs.ncst.ernet.in ip# 144.16.1.21). In case of any difficulty in getting from the FTP site, please send me mail on sumant@shakti.ernet.in. I will send the UUENCODED compressed tar file. The system has been tested both on SUN and VAX is expected to run on any UNIX platform. Further, I invite comments and suggestions from the interested users. sumant(sumant@shakti.ernet.in) national centre for software technology,bombay,india ------------------------------------------------------------------------------- Dirt, by Paul Crowley I've been thinking about this one, and dirt is a nightmare of the first order. No, I'm not talking about my personal hygiene... I was in the kitchen (this _does_ have CG content, bear with me) and I thought "Wouldn't this be a nice interesting scene to try and render. The reflection of the marble back wall against the taps, the kettle, the shadows from the fluorescent strip lights, the cups... fun". Then I looked at the dirt. It was a pretty clean kitchen, as kitchens go. There was no mould on the plates, as there is in the kitchen at home (it's my flatmates fault. I eat out now as a survival precaution). But, for example, there was a whole _variety_ of crumbs on the floor. Breadcrumbs, little bits of onion peel, poppy seeds, a discarded match... anyone looking for photorealism would have to come up with a description of each of these. Or the dirt on the iron - you couldn't just throw some "turbulence" function at this or fractals because the dirt on irons isn't uniform - you'd have to go into the physics of how dirt forms on irons. I'm not sure if that physics is even fully understood. There were little pencil marks on the cupboard doors where the carpenters marked them - if you had been rendering it, would you have remembered those? A dribble of water down one side of a cup. A blue stain on the carpet whose cause is a mystery to me. The trouble with dirt is that it's a result of the history of those objects, and not a static thing. That chip in the sideboard is in _that_ position because your flatmate was trying to get a cold sausage out of the fridge, but she was blind drunk and accidentally drove a waterpipe into it while heading for the ground at high speed. You going to write a simulation of that? Will you remember to include the little bit of sweater that got caught in the chip last Tuesday? Photorealism is _really_ hard. \/ o\ Paul Crowley aipdc@uk.ac.ed.castle /\__/ Trust me, I know what I'm doing. ------------------------------------------------------------------------------- Thomson Digital Images University Donation Program, by Michael Takayama (tak@tce.com) Thomson Digital Images (TDI) America is offering a special donation program to qualified educational facilities in the U.S. and Canada interested in 3D computer graphics/animation for Industrial Design, Scientific Visualization, and Animation. TDI Explore v2.3 software is a high-end workstation-based package including sophisticated 3D modeling, animation, and rendering capabilities. Some features of the software include NURBS modeling, inverse- kinematics animation, particle-system animation, interactive 3D texture editing, fast scan-line rendering and ray-tracing. TDI is a world leader in the high-end 3D graphics/animation market with an installed base of more than 450 systems. ******************************************************************************* UNIVERSITY DONATION PROGRAM --------------------------- If you have ever thought about working with 3D, now is the time. TDI America will donate the EXPLORE software to universities and colleges in the United States and Canada to give students access to the newest developments in the world of 3D computer animation and graphics. There are certain criteria which must be adhered to in order for a college/ university to be a successful candidate for this program: 1. EXPLORE must be used for research or educational projects. 2. The software must be made available to a minimum of 10 students per year. 3. The software must not be used for commercial purposes without the express written permission of TDI America. 4. The school must appoint one person who will act as the direct contact with TDI America. 5. A software maintenance agreement and a software license agreement must be signed and returned to TDI America. Because our university donation program provides software free of charge, the only costs involved are for maintenance (which includes a one year warranty, telephone support and free upgrades) and training. TDI runs on the full range of Silicon Graphics workstations and the IBM RISC 6000. The Silicon Graphics hardware can be ordered from TDI at our educational discount prices for your convenience. To demonstrate your interest in our university donation program, please send me a letter indicating your intended use of the software, what workstation(s) you have or would like to purchase, and your time frame. I will be happy to put together a price proposal for you, to arrange for a demo, and to discuss with you the applications of our software for your school. I look forward to speaking with you about EXPLORE and our donation program. Sincerely, Karen Lazar Director, University Donation Program TDI America ******************************************************************************* For more information, contact: Karen Lazar Director, University Donation Program TDI America 1270 Avenue of the Americas Suite 508 New York, NY 10020 TEL: 212/247-1950 FAX: 212/247-1957 ******************************************************************************* Michael Takayama email: tak@tce.com Technical Support Manager TDI America -------- >Great initiative. Any ideas to make the donation valid outside USA and Canada, >like making it worldwide? Whom should I contact to get this information? TDI America has made this donation offer available only to educational facilities in the United States and Canada. For those of you located elsewhere in North or South America, you can ask if the program can be made available to you. Contact: Karen Lazar [etc...] For those of you located in Europe, you can try contacting the TDI home office in Paris, France. I believe that they have a similar program available in Europe. Contact: Thomson Digital Image 22 rue Hegesippe-Moreau 75018 Paris FRANCE TEL: 33-1-43-87-58-58 FAX: 33-1-43-87-61-11 ------------------------------------------------------------------------------- A Brief Summary of Ray Tracing Related Stuff, Angus Y. Montgomery (angus@godzilla.cgl.rmit.oz.au) I have found (been given/know of) these raytracers (rt's), 3d object file formats, and object file databases (db's). If you know of other non-trivial rt's available please let me know asap. NOTE: before madly ftp-ing in these rt's and stuff, check out eric (erich@acm.org) haines' rt-related ftp site list for a site near _you_. his list is fairly comprehensive and up to date, and is what i used to find most of the following. x : before the source means that it is a duplicate of the most up-to-date i have downloaded. xx : dated compared to another. * this is the _source_ site - the rt from there couldn't be any fresher rt : (a.k.a and de-acronymation) my source. >>>rts(ftp and by request): art : (a rt, VORT) *|munnari.oz.au brl : (ballistic research lab) more info at hanauma.stanford.edu dbw : (dist render, distpro, d.b.wecker) hanauma.stanford.edu x|munnari.oz.au drt : (distance rt, rayman) iear.arts.rpi.edu dkb : (d.k.buck) iear.arts.rpi.edu 2.01 (or .10 ?) xx|cs.uoregon.edu (*alfred) mtv : x|iear.arts.rpi.edu *|cs.uoregon.edu uses nff ohta : iear.arts.rpi.edu xx|cs.uoregon.edu pray : (vm_pray) cs.uoregon.edu (*irisa) prt : (parallel) from comp.graphics/Kory Hamzeh qrt : (quik) iear.arts.rpi.edu xx|cs.uoregon.edu rad : from Ning Zhang. radiance : from Greg Ward ray : ucsd.edu v3.0 runs off nff :is this an earlier mtv? rayshade : xx|iear.arts.rpi.edu cs.uoregon.edu v3.0 (*weedeater) rpi : (Kyriazis, pxm, vmpxm, gk aargh!) do differ, but in essence the same *|iear.arts.rpi.edu v2.0 x|cs.uoregon.edu xx|ucsd.edu >>>object databases: NFF : (neutral file format) gondwana.ecr.mu.oz.au OFF : (object file format) gondwana.ecr.mu.oz.au poly : polyhedra db spd v3 : (standard procedural db) cs.uoregon.edu produces NFF >>>other formats: AutoCAD : cad $ GDS things file : (thf) cad IGES : (initial graphics exchange standard) architron : (arch) cad imagine : amiga $ irender : (slp) sgi $ renderman : pixar's rtk : (rt kernel) $ turbo silver : amiga $ videoscape3D : amiga >>>(not what i wanted : trivial or limited) fritz good micro : (uray, DBW_uray) a smaller version of dbw mini : (paul) mintrace : (shortest) nonfinished obfus ps >>>(not rts) rayscene wave ------------------------------------------------------------------------------- END OF RTNEWS