Borland Programmer's Resource

home *** CD-ROM | disk | FTP | other *** search

/ Borland Programmer's Resource / Borland_Programmers_Resource_CD_1995.iso / code / graphics / rtnews / rtnv3n1 < prev next >

Wrap

Text File | 1995-05-19 | 52.6 KB | 1,189 lines

_ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_</_(_(_/_/_)_ / /| ' |/ "Light Makes Right" January 2, 1990 Volume 3, Number 1 Compiled by Eric Haines, 3D/Eye Inc, 2359 Triphammer Rd, Ithaca, NY 14850 NOTE ADDRESS CHANGE: wrath.cs.cornell.edu!eye!erich [distributed by Michael Cohen <m-cohen@cs.utah.edu>, but send contributions and subscriptions requests to Eric Haines] All contents are US copyright (c) 1989,1990 by the individual authors Archive locations: anonymous FTP at cs.uoregon.edu (128.223.4.1) and at freedom.graphics.cornell.edu (128.84.247.85), /pub/RTNews Other sites: uunet.uu.net:/graphics Contents: Introduction New People Archive Site for Ray Tracing News, by Kory Hamzeh Ks + T > 1, by Craig Kolb and Eric Haines Quartic Roots, and "Intro to RT" Errata, by Larry Gritz and Eric Haines More on Quartics, by Larry Spence Question: Kay and Kajiya Slabs for Arbitrary Quadrics? by Thomas C. Palmer Ambient Term, by Pierre Poulin Book Reviews on Hierarchical Data Structures of Hanan Samet, by A. T. Campbell, III Comparison of Kolb, Haines, and MTV Ray Tracers, Part I, by Eric Haines Raytracer Performance of MTV, by Steve Lamont BRL-CAD Ray Tracer Timings, by Gavin Bell BRL-CAD Benchmarking and Parallelism, by Mike Muuss ======== USENET cullings follow ======== Rayshade Patches Available, by Craig Kolb Research and Timings from IRISA, by Didier Badouel Concerning Smart Pixels, by John S. Watson Input Files for DBW Render, by Tad Guy Intersection with Rotated Cubic Curve Reference, by Richard Bartels Needed: Quartz surface characteristics, by Mike Macgirvin Solution to Smallest Sphere Enclosing a Set of Points, by Tom Shermer True Integration of Linear/Area Lights, by Kevin Picott ------------------------------------------------------------------------------- Introduction This issue's focus is on timings from various people using a wide selection of hardware and software. Much of the delay in getting out this issue was my desire to finish up my own timing tests of MTV's, Kolb's, and my own ray tracers on the same machine. I hope some of you will find this information of use. Another feature of this issue is a pair of book reviews. One of the purposes of the RT News is to provide people with sources of information relevant to ray tracing. So, I would like to see more reviews, or even just brief descriptions of articles and books that you come across. Keeping up to date in this field is going to take more time as the years go by, so please do pass on any good finds you may have. Also, if you're an author, please feel free to send a copy of the abstract here for publication. This service is already provided to a certain extent by SIGGRAPH for thesis work. However, even a duplication of their efforts is worthwhile, since an electronic version is much easier to search and manipulate. Finally, ------------------------------------------------------------------------------- New People # Kory Hamzeh # 6640 Nevada Ave. # Canoga Park, Ca 91303 # Email: UUCP: avatar!kory or ..!uunet!psivax!quad1!avatar!kory # INTERNET: avatar!kory@quad.com alias kory_hamzeh quad.com!avatar!kory I'm not professionally involved in ray tracing. Just personally fascinated by it. I have written a couple of ray tracers (who hasn't yet?) and I'm in the midst of designing a 24 bit frame buffer. Since I don't do this on a professional level, I lack some of the resources required to develop real products. I maintain a archive site with a lot of graphics related items (including Ray Tracing News). If you need to access the archive (anonymous uucp only) please send me mail. -------- # # Steve Lamont, sciViGuy - parallelism # NCSC, # Box 12732, # Research Triangle Park, NC 27709 alias steve_lamont cornell!spl%mcnc.org -------- # Bob Kozdemba - novice tracer, futures, also radiosity # Hewlett-Packard Co. # 7641 Henry Clay Blvd. # Liverpool, NY 14450 # (315-451-1820 x265) alias bob_kozdemba hpfcla!hpfcse!hpurvmc!koz I work for HP in Syracuse, NY as a systems engineer. I will be attending SU starting in Jan. `89 working toward my BS with a focus in computer graphics. My job responsibilities are to provide technical support to customers and sales in the areas of Starbase graphics and X Windows. Lately I have been experimenting with HP's SBRR product [radiosity and ray tracing part of the HP graphics package] and trying to keep abreast of futures in graphics. I have written an extremely primitive ray tracer and I am looking for ideas on how to implement reflections and transparency. -------- # Robert Goldberg # Queens College of CUNY # Comp. Sci. Dep't # 65-34 Kissena Blvd. # Flushing, N.Y. 11367-0904 # Work : 3d Modeling algorithms, with appl. to graphics and image processing # Phone: Work - (718) 520-5100 alias robert_goldberg rrg@acf8.nyu.edu -------- # John Olsen - refraction, radiosity, antialiasing, stereo images. # Hewlett-Packard, Mail Stop 73 # 3404 E. Harmony Road # Ft Collins, CO 80525 # (303) 229-6746 # email: olsen@hq.HP.COM, hplabs!hpfcdq!olsen alias john_olsen hpfcdq.hp.com!olsen Currently, I've been spending some time tinkering with the DBWrender ray tracer making it produce 24 bit/pixel QRT-format images. I like the QRT output format, but I like some of the features of DBWrender, such as antialiasing and fading to a background color. I've thought about writing my own ray tracer with all the features I want, but so far I've resisted this evil temptation, and only looked for fancier ones already done by others who could not resist the temptation. :^) I've just installed an alias for a local ray tracing news distribution. You can send it to raylist@hpfcjo.HP.COM (or if you can't reach, try something like hplabs!hpfcdq!hpfcjo!raylist). -------- # Andrew Hunt, andrew@erm.oz # Earth Resource Mapping, 130 Hay St, Subiaco, Western Australia 6008 # Phone: +61 9 388 2900 Fax: +61 9 388 2901 # ACSnet: andrew@erm.oz alias andrew_hunt uunet!munnari!erm.erm.oz.au!andrew In 1987 I implemented a "Three Dimensional Digital Differential Analyser" (3D-DDA) algorithm, along the lines of Fujimoto and Iwata`s, and used it to speed up a raytracing system under development at the Computer Science Department at Curtin University of Technology. Recently I have got a bit busy developing commercial image processing software to devote much time to Ray Tracing. Sometime during 1990 I plan to try to port our Ray Tracing system to a Transputer based platform. -------- # Nick Beadman - Distributed Ray Tracing, Efficiency # School of Information Systems # University of East Anglia # Norwich # Norfolk # United Kingdom alias nick_beadman cmp7112@sys.uea.ac.uk At the moment I'm trying to implement a distributed ray tracer on 8 t800s on a meiko computing surface using C, with little success I should add. It all part of a big third year computing project worth a sixth of my degree. -------- # Peter Miller - algorithms, realism # 18 Daintree Cr # Kaleen ACT 2617 # AUSTRALIA # CONTACT LIST ONLY: subscription through melbourne #Phone: +61-62-514611 (W) # +61-62-415117 (H) # UUCP {uunet,mcvax,ukc}!munnari!neccan.oz!pmiller # ARPA pmiller%neccan.oz@uunet.uu.net # CSNET pmiller%neccan.oz@australia # ACSnet pmiller@neccanm.oz alias peter_miller cornell!uunet!munnari!neccan.necisa.oz.au!peter I have been interested in ray tracing since 1984, when I wrote a ray tracer before I knew it was called ray tracing! Since then I have been reading journals and tinkering with my ray tracer. The last 3 years were spent marooned off the net, with very poor graphics output devices; so while some work was done on the ray tracer, I now have a lot of catching up to do. -------- # Mike J. McNeill # VLSI and Graphics Research Group, # EAPS II, # University of Sussex, # Falmer, BRIGHTON, East Sussex, BN1 9Qt # TEL: +44 273 606755 x 2617 # EMAIL: (JANET) mikejm@syma.sussex.ac.uk | (UUCP) ...mcsun!ukc!syma!mikejm alias mike_mcneill mike@syma.sussex.ac.uk I am currently researching into parallelising the RT algorithm on a multiprocessor architecture. I'm using object space subdivision using a fast octree traversal algorithm. At the moment I'm simulating the architecture using C via TCP/IP protocols on a distributed Apollo network. Interested in all aspects of speed-up, parallel architectures, coherency and radiosity - dare I mention animation and Linda? Also does anyone know of a modelling package for use on the Apollos? ------------------------------------------------------------------------------- Archive Site for Ray Tracing News, by Kory Hamzeh Avatar is an archive site which archives Ray Tracing News, comp.source.unix, comp.sources.misc, and other goodies. Archived files can be access by any one using anonymous uucp file transfers. A list of all files in the archive can be found in avatar!/usr/archive/index. Note that this file is quite large (about 40K). If you are only interested in the graphics related archives, snarf the file avatar!/usr/archive/comp/graphics/gfx_index. All Ray Tracing News Archives (except for the first few) are stored in /usr/archive/comp/graphics directory. They are named in the following fashion: RTNewsvXXiYY.Z Where XX is the volume number, YY is the issue number. Note that all files (except index and gfx_index) are compressed. Before trying to access avatar, your L.sys file (or Systems file, depending on which flavor of UUCP you have) must be edited to contain the following info: # # L.sys entry for avatar. # # NOTE: 'BREAK' tells uucico to send a break on the line. This keyword # may vary from one flavor of UUCP to another. Contact your system # administrator if your not sure. # # 1200 baud avatar Any ACU 1200 18188847503 "" BREAK "" BREAK ogin: anonuucp # # 2400 baud avatar Any ACU 2400 18188847503 "" BREAK ogin: anonuucp # # 19200 baud (PEP mode) for Telebit Trailblazers only avatar Any ACU 19200 18188847503 ogin:-\n-ogin: anonuucp After the previous lines are entered in you L.sys file, you may use the following command to get the index file: uucp avatar!/usr/archive/index /usr/spool/uucppublic/index This command will grab the file from avatar and put it in your /usr/spool/uucppublic directory using the name index. For example, to get Ray Tracing News Volume 2, Issue 5, execute the following command: uucp avatar!/usr/archive/comp/graphics/RTNewsv02i05.Z /tmp/RTnewsv02i05.Z NOTE that some shells (like csh) use the "!" as an escape character, so use a "\" before the "!". If you experience problems getting to any of the files, I can be reached via e-mail at: UUCP: avatar!kory or ..!uunet!psivax!quad1!avatar!kory INTERNET: avatar!kory@quad.com soon to be kory@avatar.avatar.com Enjoy, Kory Hamzeh ------------------------------------------------------------------------------- Ks + T > 1, by Craig Kolb and Eric Haines From: Craig Kolb <craig@weedeater.math.yale.edu> While adding adaptive tree pruning to rayshade (and discovering a bug), I came across a question I've had regarding the SPD for a while. Some objects have Ks + T > 1. How can this be? For example, the spheres in "mountain" have Ks = .9 and T = .9. Unless I'm completely out to lunch (which is possible), ths means that subsequent specularly reflected rays are weighted by .9, and that transmitted rays are also weighted by .9. This leads to "glowing" objects pretty quickly. What's wrong in the above description? Be warned that in "nff2shade.awk", I set the "specular reflectance" to be min(Ks, 1. - T). -------- My reply: Actually, true enough, Ks + T > 1 does occur in the SPD stuff. I use T in a funny way, since I was trying to make databases that would display both using hidden surface and ray tracing algorithms. Hmmm, how to explain? Well, imagine you have a glass ball: under the hidden surface system (without transparency), you'd like the ball to appear opaque, and so a high Kd is in order. Now if the thing's transparent, you don't want Kd to be high. So what I do is lower Kd and Ks by ( 1 - T ). An admittedly weird shading model, which I've now changed a bit (i.e. reflectance and transmittance are now entirely separate). So, your solution of turning down the reflectance is fine. I should add that I didn't really explain all this as it's irrelevant for timings (all we care about is what rays get generated, not the final color), but I agree, it would be nicer to get a good resulting picture as a check. I'll change that in the next update of SPD, actually... thanks for pointing it out! -------- Craig's reply: Ah, I get it. I brought it up because it does make a difference timing-wise if you're using adaptive tree pruning. Although you say in the SPD stuff that pruning shouldn't be used, Mark's raytracer currently has no option to turn it off. I was comparing pruned vs. pruned, and noticed that I had many fewer reflected rays, since my reflectance for the transparent gears was .05 rather than .95. ------------------------------------------------------------------------------- Quartic Roots, and "Intro to RT" Errata, by Larry Gritz (vax5.cit.cornell.edu!cfwy) I was trying to find the solution to a quartic equation to solve a ray-torus intersection test. I've gotten lots of replies, but generally fall into one of two categories: either solve the quartic equation (I forget the reference now, but I'll send you either a reference or the formula if you want [It's in the _CRC Standard Math Tables_ book - EAH]), or by some iterative method. Everybody says (and I have confirmed this experimentally) that solving the equation is very numerically unstable. I have chosen to use the Laguerre method from Press, et. al. _Numerical Recipes in C_, which is slow, but seems to work, and finds all roots without needing to specify brackets for the roots. (An advantage since although I can bracket all possible real roots with the bounding box test that I already do, I'm not really sure how many roots lie within the brackets.) What actually turns out to be a bigger problem is that I got the quartic coefficients from the SIGGRAPH '88 Ray Tracing Course Notes (on page 3-14 of Pat Hanrahan's section). [Larry and I thrashed this out over a number of passes (boy, I wish I had access to Mathematica or somesuch), and came out with the following corrected equation set for those on page 93 of _An Introduction to Ray Tracing_: a4 & a3 - Pat's are OK. a2 = 2(x1^2+y1^2+z1^2)((x0^2+y0^2+z0^2)-(a^2+b^2)) + 4 * (x0x1+y0y1+z0z1)^2 + 4a^2z1^2 a1 = 4 * (x0x1+y0y1+z0z1)((x0^2+y0^2+z0^2)-(a^2+b^2)) + 8a^2 * z0 * z1 a0 = ((x0^2+y0^2+z0^2)-(a^2+b^2))^2 - 4a^2(b^2-z^2) - EAH] ------------------------------------------------------------------------------- More on Quartics, by Larry Spence From: larry@csccat.UUCP Newsgroups: comp.graphics Subject: Re: Solution to quartic eqn? >I didn't ask the question, but thanks for your input. However, Ferrari's >theorem yields a fast and very accurate answer. ^^^^ Are you sure about this? If it's the same closed-form solution that you find in the CRC books, etc., doesn't it use trig functions and cube roots? Seems to me there was a paper by Kajiya in the early '80s on numerical ray tracing, and there have been several in the last few years. My advice would be to go look at SIGGRAPH proceedings from 1981 on. Certainly, a closed form solution like the one suggested wouldn't take advantage of any coherence in the problem, unless you wrote all the trig stuff yourself. [Comments, anyone? I never saw any replies. - EAH] ------------------------------------------------------------------------------- Question: Kay and Kajiya Slabs for Arbitrary Quadrics? by Thomas C. Palmer <palmer@mcnc.org> Here's a question regarding slabs for arbitrary quadrics. Kay & Kajiya '86 discusses computing slabs for polygons and implicit surfaces. The method for implicit surfaces using Lagrange multipliers and gives an example using spheres. This is easy and works quite nicely for canonical (i.e. centered and axis aligned) quadrics. K&K handle object rotations and translations during the slab computation. What about quadrics that have been transformed by some arbitrary matrix prior to input and look like this: ax^2 + 2bxy + 2cxz + 2dxw + ey^2 + 2fyz + 2gyw + hz^2 + 2izw + jw^2 = 0 ? The xy, xz, and yz terms prevent a simple solution via Lagrange multipliers. Has anyone done this? How do you handle quadric bounding planes? Note that K&K cheated for the tree branchs in the tree models. Each cylinder has endpoint capping spheres so the cylinder's extent is just the combined extent of the two spheres. Thanks for your help - -Tom Thomas C. Palmer North Carolina Supercomputing Center Cray Research, Inc. Phone: (919) 248-1117 PO Box 12732 Arpanet: palmer@ncsc.org 3021 Cornwallis Road Research Triangle Park, NC 27709 ------------------------------------------------------------------------------- Ambient Term, by Pierre Poulin (poulin@dgp.toronto.edu) I just read your Tracing tricks in the latest Ray Tracing News. Thanks for passing that on to us, this was very interesting. One trick you mentioned was to put a light source at the eye position in order to eliminate the ambient term. This is a simple trick I did not know. However, you noted that highlights appears as artifacts. Since you know that this light does not need any shadow rays, you could use only the diffuse intensity created by this light to approximate the ambient term, hence creating no undesirable highlights. I know, this is very easy and everyone probably knows that. But just in case you would not have thought about it, I wanted to indicate it to you. I just hope I am not the 10,000th to tell you :^) -------- My reply: I'm glad to hear that you enjoyed the "Tracing Tricks" article - sometimes I worry that I'm just publishing ideas that everyone already knows. I've tried having the ambient light have no highlight, and it's sort of interesting, but the lack of highlight can look a little strange for those objects where there really would be a highlight (it sort of makes them look less shiny, though it also depends upon the other lights in the scene). Nonetheless, turning it off is definitely worth exploring. You're the first person to comment on this, actually. Thanks for taking the time to write, and do keep in touch. ------------------------------------------------------------------------------- Book Reviews on Hierarchical Data Structures of Hanan Samet, by A. T. Campbell, III (atc@cs.utexas.edu) "The Design and Analysis of Spatial Data Structures", and "Applications of Spatial Data Structures", by Hanan Samet, Addison-Wesley, 1990. Reviewed by A. T. Campbell, III This two-volume series of books is one man's effort to provide a guide to the study of hierarchical data structures. The topic has extensive influence on many fields, particularly computer graphics, image processing, and computational geometry. Hanan Samet is a well-established expert in the field, with literally dozens of publications. As a computer graphics researcher, I eagerly anticipated the books' publication. A close examination of both volumes leads to one conclusion: the books are extremely worthwhile. The integration of diverse material is remarkable. Comprehensive research results throughout the spectrum of science are drawn together seamlessly. Samet has really done a thorough job of pulling together literature from a vast collection of conferences and journals, both major and minor. The level of explanation is good. Samet has obviously read all of his references thoroughly. The descriptions of algorithms reflect an understanding of what is really going on. Even algorithms mentioned briefly are given a good essential description. Numerous topics are covered. Algorithms for such problems as proximity-searching, efficient storage of image and volume data, constructive solid geometry, data structure conversion, hidden surface removal, and ray-tracing fill the books. Pseudo-ALGOL code examples present detailed explanations of how to build and traverse many of the data structures. Ray-tracing enthusiasts in particular will enjoy a detailed description of how to trace a path through an octree. There are, however, a few problems with the presentation. Despite the ambitious titles of the volumes, there is nowhere near as much theory or practical advice as one might expect. The emphasis is instead on explaining literally everything at an understandable level. While this makes the books a wonderful introduction to all sorts of stuff, the reader still needs guidance in choosing what techniques to actually use. The title of the first volume, "The Design and Analysis of Spatial Data Structures", obviously invokes comparison with the classic text "The Design and Analysis of Computer Algorithms", by Aho, Hopcroft, and Ullman. However, Samet's approach differs greatly from that of Aho et al. While the data structures are described and discussed in detail, the analysis is not very formal. Theorems and proofs, as well as detailed algorithm analysis, are not much in evidence. A more appropriate title might simply be "An Introduction to Spatial Data Structures". The second book, "Applications of Spatial Data Structures", covers basically every research result in hierarchical algorithms, major or minor. It is exceptionally good at explaining techniques succinctly. The depth is not sufficient enough to implement the techniques without referring to the original papers, however. Additionally, the reader is given no good feel for which results should actually be used. If a technique is commonly used in industry or never used because of impracticality, Samet never says so. The reader who expects a "cookbook" solution to his problem will be disappointed. The books are primarily of use for two purposes. First, they provide a good introduction to those aspects of computational geometry and image processing which are most likely to be of interest to a person working in graphics. Second, they provide a very complete guidebook to the literature. I would suggest that researchers and practitioners have these volumes on their reference shelves. Due to the sheer volume of material presented, I would not recommend them for use as course textbooks. ------------------------------------------------------------------------------- Comparison of Kolb, Haines, and MTV Ray Tracers, Part I, by Eric Haines I decided to compare the MTV ray tracer, the Kolb "rayshade" software, and my own modified "SBRR" ray tracing package to see the efficiency of each. My goal was to see what sort of performance was obtained by each ray tracer and note the strengths and weaknesses of each. This first section of the report marks the state of current results, consisting of timings from the "gprof" command for each package, using the Standard Procedural Database (SPD) package. All three packages were run on an HP 350 workstation with a floating point accelerator board. The compiler options were "-g -G +ffpa" (debug, profile, with special floating-point only compile), using HP-UX 6.5. The three ray tracers were selected from all the existing packages by having the following properties: (1) Each could handle all the primitives in the SPD package, and (2) each had some automatic efficiency scheme. Other packages do not support all the primitives (e.g. DBW does not have cylinders, cones, or n-sided polygons), or do not have automatic efficiency generation (e.g. QRT lets you explicitly create bounding boxes, but has no way for this to happen automatically). The MTV ray tracer was created by Mark VandeWettering, and uses the Kay/Kajiya hierarchy approach (i.e. sorting objects along X/Y/Z and splitting each group, recursively). To make it conform to the requirements of the SPD tests, "minweight" was set to 0.0 in order to disable tree pruning a la Hall's method. Craig Kolb's "rayshade" ray tracer uses a 22x22x22 grid on all scenes. Because of the use of grids (i.e. 3DDDA), it was found to be sensitive to the background polygons used in the SPD package. In four of the SPD scenes (balls, gears, rings, and tree) there is a "ground" polygon. The "rayshade" software allows some user intervention in how the database is structured. It was found that faster timings (sometimes strikingly quicker) could be obtained by leaving this background polygon out of the grid structure. Changing the database in this manner is forbidden by the SPD tests, but both sets of results are presented because of the difference in timings. The SBRR package is not public domain, but rather is part of the graphics software in all HP workstations using the Turbo-SRX graphics accelerator. It uses the Goldsmith and Salmon automatic bounding volume hierarchy method. It should also be noted that this package is full featured, which has a corresponding slowdown effect when intersection computations are performed. For example, polygons can be single or double sided, with different materials, colors per vertex, normals per vertex, and other combinations available. Since the package has a "hardware assist" by using the graphics engine as an item buffer (see Weghorst and Hooper), timings are given both with and without this assist. The times without are the fairer of the two for comparison. Without further ado, here are the timings: MTV Basic ----- ----- balls 12604 gears 38123 mount 9307 rings 24286 tetra 1081 tree 8056 Kolb Basic Modified ----- ----- -------- balls 14871 3224 gears 12601 11449 mount 2989 2989 (i.e. same - no modification needed) rings 8348 8103 tetra 836 836 (i.e. same - no modification needed) tree 18957 2505 SBRR Basic Item Bfr ----- ----- -------- balls 5027 4126 gears 13561 12776 mount 5440 3749 rings 11044 10446 tetra 1187 457 tree 3229 2719 So, considering the MTV ray tracer as 1.00, here are the relative performance times of each tracer - (MTV time / RT time) - i.e. higher is faster, and can be thought of as how many times faster it is: SPD MTV-Base Kolb-Bas Kolb-Mod SBRR-Bas SBRR-Bfr ----- -------- -------- -------- -------- -------- balls 1.00 0.85 3.91 1.40 3.05 gears 1.00 3.02 3.32 2.81 3.33 mount 1.00 3.11 <--same 1.71 2.48 rings 1.00 2.91 3.00 2.20 2.32 tetra 1.00 1.29 <--same 0.91 2.37 tree 1.00 0.42 3.22 2.50 2.96 Some interesting phenomena are revealed by the statistics. The "tetra" database is pretty much the same absolute speed for everyone. However, given the performance for other scenes, it is noteworthy that MTV performs relatively faster on this than others. I've noticed this, too, when trying Kay/Kajiya myself - this scheme just soars on tetra, though I am not sure why. Perhaps it is the smallness and regularity of the objects, which would go well with Kay/Kajiya's assumption that using the centroid of these is reasonable. For other databases one can imagine better hierarchies that those constructed by Kay/Kajiya. For example, with mount, the four spheres above the fractal mountain should be in their own cluster just off the top of the hierarchy tree. The "tetra" scene is a strange test in that most (around 81%) of the scene is background, so what we tend to test here is affected more by how fast one can traverse a scene, set up rays, shade, and store values in a file. It will take further analysis to see where the time is spent. The Kolb ray tracer is interesting in how much its efficiency scheme is affected by the geometry of the scene. The "teapot in a football stadium" effect I've written about previously hits grid efficiency schemes with a vengeance. For example, moving the ground polygon from the grid subdivision to outside of it makes rayshade perform 4.6 times faster for balls, and 7.7 times faster for tree! The point is that grids perform best when the scene is relatively "compact". The large ground polygons in these scenes cause the entire grid to get larger in two directions, and so make many more objects fall inside but a few grid squares, thereby ruining much of the efficiency of the grid. Comparing Kolb to MTV, we see that overall Kolb is faster. Kolb does worse on balls and tree using the unmodified database, but otherwise outperforms MTV, being about twice as fast. When the ground polygon is taken out of the grid subdivision, Kolb is more than 3 times faster for all cases except tetra. Comparing SBRR and MTV shows SBRR to be faster for most cases, with MTV being slightly faster for tetra. Overall SBRR is almost twice as fast with its basic performance, and about 2.75 times faster when the item buffer is used. Comparing SBRR and Kolb is a bit tricky, since there are two tests of each. Taking the basic tests in each, Kolb and SBRR are comparable: Kolb outperforms SBRR in four cases, and SBRR outperforms Kolb in two (and for one of those, tree, it is almost 6 times faster). SBRR has some things to learn from Kolb (which is why I'm doing all this, anyway), as Kolb's modified database results point towards the fact that faster performance is possible. So, on the basis of pure raw timings, Kolb and SBRR without modifications or accelerators are of comparable speed. With user intervention into the database structure, Kolb can become noticeably faster. It should also be noted that Kolb uses a default of 22x22x22 grid cells, which is under user control and so could be tuned to further improve performance. Actually, this is an interesting open question: what heuristics can be used to determine a reasonable grid size for a scene? Also, is there a reasonable way to determine if such performance destroyers such as ground polygons are present automatically, and so remove them from the grid subdivision itself? David Jevans' and Brian Wyvill's work on nested grid subdivisions ("Adaptive Voxel Subdivision for Ray Tracing", Proceedings of Graphics Interface '89, p. 164-172) might lead to a less variable performance and to greater overall speed. Craig and I have discussed this, but unfortunately he has no time to try this out - perhaps someone out there can experiment and compare results. As mentioned, this is research in progress. My next step will be to analyze the statistics generated by each program and see where time is spent. ------------------------------------------------------------------------------- Raytracer Performance of MTV, by Steve Lamont > Could you pass on your timings on ray tracer performance on various > machines and any thoughts or experiences you want to share about the subject? The parallelization was done in a brute force manner, forking processes and dividing the work by the number of processes. The parent process remains behind and reads the scanlines in a round robin fashion from pipes. There is no communication from the parent to the child processes once the forking has been done; the ray tracing routines simply march down the scan lines. This approach works well on a homogeneous architecture where all processes run at approximately the same speed and no process "dries up" or runs out of work to do. This works well for single frames. However, my approach for a large animation is to simply parcel out work on a frame per processor basis. I've built the MTV raytracer on the Cray, the IRIS, and the Ardent Titan... and here are some preliminary results on a 128 x 128 test image (the balls image with reflections but no refractions, 3 light sources, 11 primitives (16 with bounding volumes) processes (CPU seconds) Machine 1 4 Notes Y-MP/8-432 4.0 1.0 -hopt,intrinsics,vector IRIS (4D/240)* 8.2 2.1 -O2 (MIPS R3000/3010) Titan (P2) 30.0 7.7 -O3 (MIPS R2000 + prop. vector/fp unit) Titan (P3) 7.2 --- Run by vendor. (MIPS R3000/3010 + proprietary vector unit) Wall clock times improved by a factor of 2.5 to 3, which squares pretty well with Amdahl's law as extended for small parallel architectures. These are *preliminary* results with respect to the Titan -- we've only had it for a couple of weeks. On none of the machines did MTV vectorize in any way to speak of. In fact, turning off vectorization improves performance for several "short vector" loops; e.g., loops of vector length 3. Timings were done on a fairly heavily loaded Cray and an empty IRIS and Titan. The Cray is a Y-MP with four processors (upgradable to 8, hence the 8-4) and 32 mWords of central memory. There is also a 128 mWord SSD (Solid-state storage device). We also have 40 gBytes of rotating storage (a combination of DS-40s and DD-49s). [*] Actually, this machine is a CDC Cyber 910-624 but the only difference between it and a "genuine" Silicon Graphics IRIS 4D/240 is the color of its box and the binding on the manuals. [Disclaimer: These comments are solely the responsibility of the author and no endorsement by the North Carolina Supercomputing Center should be inferred] Steve Lamont, sciViGuy EMail: spl@ncsc.org NCSC, Box 12732, Research Triangle Park, NC 27709 ------------------------------------------------------------------------------- BRL-CAD Ray Tracer Timings, by Gavin Bell (gavin@krypton.sgi.com) These results are third-hand; I can vouch for the accuracy of our machine's results, but the BRL people may have more recent results to share. The only experience I have with ray-tracing timing on our machines is with a simple, interactive ( :-> ) ray-tracer demo called 'flyray'. I modified it to be fully parallelized; it uses one CPU to display a real-time display of the scene being ray-traced (complete with rays shooting into and bouncing around the scene), and the other N-1 CPUs to compute ray-object intersections (these results are shown in a separate window). As for timing... runs REAL fast on an 8 CPU system. What follows is a form letter I've been sending to people who asked for ray-tracing timings. ------------------------ This is a response to all of those people who asked me for the BRL-CAD ray-tracing benchmark results. I'm surprised at how many of you there are! First, a little bit about myself. I work in Technical Marketing, the 'Demos and Benchmarks' group here at Silicon Graphics. I'm not usually involved in benchmarks; I work mainly on our demos. The rest of this text comes directly from a 'SGI Benchmark Summary' prepared by one of our Marketing people. The numbers are communicated to him by the software engineer who did the benchmark. These benchmark summaries are communicated to salespeople in a weekly newsletter as soon as the results come in. Other summaries done include: 'INDUSTRY STANDARD': Dhrystones, Digital Review Labs, Linpack, Livermore Fortran Kernals, MUSBUS, Whetstones. OTHERS: LES50 (computational fluid dynamics), Moldflow (finite element analysis), Molecular Dynamics, Nord, UFLA, GROMOS (all computational chemistry). If you want more information on any of these benchmarks, please see a SGI sales rep-- I can't keep typing in all of these numbers!! Also, please remember that these benchmarks were done for a specific customer, who was interested in a specific machine, so most of them were not benchmarked on our whole product line (the 'Industry Standard' benchmarks, however, are usually run on all of our products). APPLICATION BENCHMARK NAME CUSTOMER ----------- -------------- -------- Rendering BRL-CAD 3.7 US Army Ballistic Research Lab LANGUAGE SUMMARY DATE -------- ------------ C 9/5/89 DESCRIPTION ----------- The BRL-CAD benchmark is a part of the US Army Ballistic Research Laboratory's BRL-CAD package. The core of the BRL-CAD benchmark is a ray-tracing program which consists of about 150,000 lines of C code. Computations are performed in double precision floating point. Five separate data bases are input to the ray tracing program, resulting in six performance ratings (one for each, plus a total which is the mean of the other five) . When rendered, each data base will produce a 512x512x24 bit color shaded image. The images are of increasing complexity, and are identified as 'Moss', 'World', 'Star', 'Bldg' and 'M35'. RESULTS ------- The result of this benchmark is reported as rays traced per second, and referred to as Ray Tracing Figure of Merit (RTFM). Higher numbers indicate better performance. The code was parallelized by inserting user directives to create multiple processes to trace rays. RESULTS FOR SGI MACHINES: Note: The actual report has nice graphs here. Machine RTFM ------------------- 1x16 (4D/80) 714 2x16 (4D/120) 1358 4x25 (4D/240) 5034 8x25 (4D/280) 7434 Note: NxMM numbers refer to the number of processors in the machine (N) running at MM MHZ. COMPETITIVE RESULTS: Machine # Processors RTFM Relative Performance -------------------------------------------------- Vax 780 1 77 1.0 Sun3 1 88 1.1 Convex C120 1 163 3.6 Sun4 1 435 5.6 SGI 4D/120S 2 1358 17.5 Alliant FX/80 8 2783 33.6 SGI 4D/240S 4 4456 70.4 Cray X-MP/48 4 7217 116.1 SGI 4D/280 8 7434 119.7 ANALYSIS -------- The BRL-CAD benchmark exhibits excellent speedup as processors are added. This is due to the coarse granularity inherent in the ray tracing problem being solved. Each ray is processed independently, with no data dependencies among the rays. This means that multiple processors can each work on separate rays simultaneously, with minimal need for synchronization among processors. While the code is highly parallelizable, it is not efficiently vectorizable because of short vector lengths. The combination of these two characteristics explain the phenomenal performance of Silicon Graphics machines relative to vector machines like Cray and Alliant. The characteristics of this benchmark that lead to high performance by the Silicon Graphics machines are common to all ray tracing applications. -------- Here is another note from Gavin: My only experience with the BRL ray-tracer came when I was at Princeton University - I installed it on Silicon Graphics machines there for the Graphics Lab. That was two years ago; as far as I could tell, it didn't use octrees or any other space-partitioning algorithm. I used a ray-tracer written at Princeton (the precursor of what is now Craig Kolb's rayshade program; Craig and I had the same thesis advisor) which did do octrees; it was infinitely faster than the BRL beast. ------------------------------------------------------------------------------- BRL-CAD Benchmarking and Parallelism, by Mike Muuss (mike@BRL.MIL) I'm sort of on vacation right now, so I'm going to cop out and just send you the TROFF input for several things that I have handy about how we benchmark ray-tracing in the BRL-CAD Package. The first one is our benchmark summary paper. The second one is a portion of a paper that I wrote called ``Workstations, Networking, Distributed Graphics, and Parallel Processing''. You may publish and/or redistribute both documents as you wish. Note that the United States Government holds the "copyright", ie, it is not permissible to copyright this material. [These papers are rather lengthy, so I won't include them in this issue. If you would like copies, look at the archive sites for Muuss.benchmrk and Muuss.parallel, or write me. - EAH] ======== USENET cullings follow =============================================== Rayshade Patches Available, by Craig Kolb From: craig@weedeater.math.yale.edu Newsgroups: comp.graphics Organization: Math Department, Yale University Patches 1-3 for rayshade v3.0 are available via anonymous ftp from weedeater.math.yale.edu (new address: 130.132.23.17) in directory pub/rayshade.3.0/patches. The patches fix several minor bugs, clean up the documentation, and provide new features. Several people have expressed an interest in 'trading' rayshade input files. If you have an interesting input file that you'd like to share, feel free to deposit it in the "incoming" directory on weedeater or send it to me via email. I will make these files available in the pub/Rayinput directory on weedeater. Rayshade is supposedly "on the verge" of appearing in comp.sources.unix, patches and all. ------------------------------------------------------------------------------- Research and Timings from IRISA, by Didier Badouel From: badouel@irisa.irisa.fr Newsgroups: comp.graphics Organization: IRISA, Rennes (Fr) We have a parallel raytracer (called PRay) at IRISA which as MTV uses NFF description databases. This raytracer has been implemented on an iPSC/2, on a SEQUENT BALANCE and also on serial computers (SUN3, GOULD NP1) to make better comparisons. I give you the various synthesis times for the well known 'Teapot' database. The image has been rendering with a 512X512 resolution with 3 light sources. Results are as follows : #PEs Time (in sec.) ________________________________________ SUN3: 8877 (~ 2h27mn) ________________________________________ GOULD NP1: 1642 (~ 27mn) ________________________________________ SEQUENT BALANCE 1 37121 (~ 10h18mn) 2 18567 3 12381 4 9285 5 7431 6 6197 7 5311 8 4656 9 4138 (~ 1h9mn) ________________________________________ iPSC/2 1 6294 (~ 1h45mn) 2 3332 4 1700 8 860 16 440 32 224 64 119 (~ 2mn) ________________________________________ The code running on the iPSC/2 emulates a virtual shared memory over the local PEs. The database is not duplicated but all the local memories are used. The remaining memory after loading code and data is used as a cache to speed up low global accesses. ----- In order to benchmark our parallel raytracer running on an iPSC/2, which use Eric Haines' NFF file format as input, we would like to know if other people have a parallel raytracer using these databases in order to make some comparisons. One of our goals is to render the largest possible database. For the moment, we have rendered the 'tetra10' database: - the database contains more than 1 million polygons (1048576 polygons) - the size of the database with its 'object access structure' (a grid) is 140 MO. - the synthesis time is 526 seconds on the iPSC/2 with 64 nodes and 4 MO node memory. - however, on account of using NFF text file format, reading the input is very slow (more than 3 hours for 'tetra10') when using YACC and LEX. Furthermore, our iPSC/2 configuration does not have I/O node system. ________________________________________________________________ Didier BADOUEL badouel@irisa.fr INRIA / IRISA Phone : +33 99 36 20 00 Campus Universitaire de Beaulieu Fax : 99 38 38 32 35042 RENNES CEDEX - FRANCE Telex : UNIRISA 950 473F ________________________________________________________________ ------------------------------------------------------------------------------- Concerning Smart Pixels, by John S. Watson From: watson@ames.arc.nasa.gov (John S. Watson) Newsgroups: comp.graphics Organization: NASA - Ames Research Center In article <207400033@s.cs.uiuc.edu> mccaugh@s.cs.uiuc.edu writes: > > Does anyone know of a system with "smart" pixels? Once upon a time I wrote a ray tracer in which the pixels used heuristics to determine their sampling rate. Since the reason for doing it was to speed things up, the heuristic had to be simpler than casting a ray( s, if sub-sampling). I used difference in previous pixels values, with a little randomness tossed in. So pixels changing quickly were sampled every frames, while pixels that were hardly ever changing were sampled only once every 10 frames. The results: much faster, but with a graininess on the edges of moving objects. I needed to make the pixels more aware of what was happening with its neighbors. Never got around to doing that. Another problem is big pictures have lots of pixels ... 512x512 = 0.25 million. To be smart you must have a memory. To save memory, I combined the above with an Area-of-Interest/Variable Acuity (AOIVA) Ray Tracer. Hope this helps, John S. Watson, Civil Servant from Hell ARPA: watson@ames.arc.nasa.gov NASA Ames Research Center UUCP: ...!ames!watson Any opinions expressed herein are, like, solely the responsibility of the, like, author and do not, like, represent the opinions of NASA or the U.S. Government. ------------------------------------------------------------------------------- Input Files for DBW Render, by Tad Guy From: tadguy@cs.odu.edu (Tad Guy) Newsgroups: comp.graphics Organization: Old Dominion University, Norfolk, VA In article <6475@pt.cs.cmu.edu> te07@edrc.cmu.edu (Thomas Epperly) writes: I was wondering if anyone had any neat input files for DBW_Render available for anonymous ftp. xanth.cs.odu.edu as /amiga/dbw.zoo. If you have a network of, say, sun workstations, you might as well get /amiga/distpro.zoo, which will allow to distribute the computations over many machines. ------------------------------------------------------------------------------- Intersection with Rotated Cubic Curve Reference, by Richard Bartels From: rhbartels@watcgl.waterloo.edu Newsgroups: comp.graphics Organization: U. of Waterloo, Ontario In article <1445@tukki.jyu.fi> toivanen@tukki.jyu.fi (Jari Toivanen) writes: : :I would like to know is there any simple and effective solution to :following problem: : : [intersecting a ray with a rotated cubic curve] : :Jari Toivanen Segments are for worms ;-) :University of Jyvaskyla, Finland Internet: toivanen@tukki.jyu.fi Look at the article: Ray Tracing Objects Defined By Sweeping Planar Cubic Splines Jarke J. van Wijk ACM Transactions on Graphics Vol. 3, No. 3, July, 1984, pp. 223-237 I believe that the author subsequently wrote a whole book on the subject. [Incidentally, this article also has a method for quickly intersecting a tight fitting bounding volume around such curves. I've found this test useful for use as a torus bounding volume. Also, does anyone know of the existence and the name of the book Richard mentions? - EAH] ------------------------------------------------------------------------------- Needed: Quartz surface characteristics, by Mike Macgirvin From: mike@relgyro.stanford.edu Newsgroups: comp.graphics Organization: Stanford Relativity Gyro Experiment (GP-B) I am in need of the surface characteristics for fused quartz. Ambient, diffuse and specular color characteristics, Phong coefficent, reflectance, and transparency. I have the index of refraction (Well, I have to average it, c'est la vie). I have attempted to derive these experimentally, but find the resulting traced image lacking in many ways, and a simulation visualization I am working on requires accuracy. I am using Kolb's 'rayshade' if it affects your responses. Please respond via e-mail if possible. ------------------------------------------------------------------------------- Solution to Smallest Sphere Enclosing a Set of Points, by Tom Shermer From: shermer@cs.sfu.ca Newsgroups: comp.graphics Organization: School of Computing Science, SFU, Burnaby, B.C. Canada >I need the solution for the following problem: >find the smallest sphere that encloses a set of given points, in both >2-D and 3-D (or even n-D, if you like). > This problem can be solved in linear time (in any fixed dimension) by the technique of prune-and-search (sometimes called ``Megiddo's Technique''), either directly or by first converting the problem to a linear program. The most relevant reference (for 2d & 3d) is: Linear-time Algorithms for Linear Programming in R^3 and Related Problems, Nimrod Megiddo, SIAM J. Comput, v. 12, No. 4, Nov 1983, pp. 759-776. Other related references: Linear time algorithms for two- and three- variable linear programs, M.E. Dyer, SIAM J. Comput, v. 13, 1984, 31-45. On a multidimensional search technique and its application to the Euclidean one-center problem, M. E. Dyer, Dept. Math and Stats TR, Teesside Polytechnic, Middlesbrough, Cleveland TS1 3BA, UK, 1984. Linear programming in linear time when the dimension is fixed, N. Megiddo, JACM 31, 1984, 114-127 The weighted Euclidean 1-center problem, N. Megiddo, Mathematics of Operations Research 8, 1983, 498-504 On the Ball Spanned by Balls N. Megiddo, manuscript (this may have appeared in the literature by now) ------------------------------------------------------------------------------- True Integration of Linear/Area Lights, by Kevin Picott From: kpicott@alias.UUCP Newsgroups: comp.graphics Organization: Alias Research Inc. Has anyone seen any work done on evaluating the diffuse and specular illumination produced by linear and/or area lights? I have checked all the standard sources and all information I find gets to the point where the integration is set up and then a little hand waving is performed accompanied by the magical words "numerically integrated". This works but is too slow for my purposes. Does anyone know of any work done in different directions (ie faster evaluation) ? -------- Thanks to all who replied to my query about linear and area lights. In the area of linear lights, two papers on analytical solutions were found. The first, by John Amanatides and Pierre Poulin has been submitted to Eurographics '90 and I'll hopefully get a look at that soon. The second, "Shading Models for Point and Linear Sources", ACM TOGS, 4(2), April 1985, pp. 124-146. by T. Nishita, I. Okamura, E. Nakamae, proposes an analytic solution to the diffuse component, but only under certain circumstances. The latter unfortunately reduces to numerical integration in the majority of cases where spline surfaces are involved, although a method of optimization is given that reduces computation time for the numerical integration. This method would seem to be suited to lighting parallel and perpendicular to the illuminated surfaces. There was also a paper entitled "A Comprehensive Light-Source Description for Computer Graphics", IEEE CG&A, July 1984, by Channing P. Verbeck and Donald P. Greenberg that approximates both linear and area light sources as a series of point sources. This is a compromise to numerical integration, but is still computationally expensive. In summary, the analytical solution to linear sources exists and is calculable, at least for the diffuse component. The specular component exists, but direct calculation is almost expensive as numerical integration. As far as area light sources are concerned... no analytical solutions were found. In fact, from the work examined I was left with the impression that even if the solution existed it would not be very useful from a light illumination point of view (ie non-radiosity). (Comments?) -- Kevin Picott aka Socrates aka kpicott%alias@csri.toronto.edu Alias Research Inc. R+D Toronto, Ontario... like, downtown ------------------------------------------------------------------------------- END OF RTNEWS