Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!tut.cis.ohio-state.edu!mailrus!cornell!vax5!cnsy From: cnsy@vax5.CIT.CORNELL.EDU Newsgroups: comp.graphics Subject: Ray Tracing News, Volume 2, Number 4 Message-ID: <18845@vax5.CIT.CORNELL.EDU> Date: 21 Jun 89 20:12:28 GMT Sender: news@vax5.CIT.CORNELL.EDU Reply-To: wrath.cs.cornell.edu!eye!erich Organization: 3D/Eye Inc Lines: 364 In order to keep my name off the "Ten Most Posted" list, I'm trimming these USENET posted issues of USENET cullings, since it's a waste to echo what I like of what's been posted in the past month or so. If you want to get this stuff, go to the skinner.cs.uoregon.edu FTP site and grab the whole issue. If you can't FTP, I can't help you much - your best bet is to read this newsgroup! _ __ ______ _ __ ' ) ) / ' ) ) /--' __. __ , --/ __ __. _. o ____ _, / / _ , , , _ / \_(_/|_/ (_/_ (_/ / (_(_/|_(__<_/ / <_(_)_ / (_ I don't get it. Why doesn't every CG Software vendor supply a >ray tracer. It's definitely the easiest renderer to write. Yes, >they are slo-o-o-o-o-o-w, but they sound glitzy and (I bet) would >stimulate sales, even if buyers never used them. Having worked at two CG Software companies, I know firsthand how the "to do" list grows faster than you can possibly implement features (no matter how many programmers you have -- c.f."The Mythical Man-Month"). Jeff is right that ray tracing sounds glitzy, and, yes, it is another factor to toss into the sales pitch -- but it is not at all clear that it is worth the effort. Most (if not all) ray tracers assume either infinite rendering time or infinite disk space. In the real world (a 68020 and a 144Meg disk) this is not the case. The raytracer I wrote at Neo Visuals was written in Fortran -- ergo no dynamic memory allocation -- so I had to work on optimizing it without significantly increasing the memory used. This mostly involved intelligently choosing when to fire rays. The renderer performs a Watkins-style rendering, and fires secondary rays from a pixel only if the surface at that pixel needs to be raytraced. Memory constraints prevented me from using any spatial subdivision methods. Yes, ray traced images are great sales tools. They are also sometimes not entirely honest -- novice users ("I want a system to animate Star Wars quality images, about ten minutes of animation a day on my XT") are not aware of the expense of raytracing, and very few salesmen go out of their way to point this out. However, these same users, unsure of the technology, put together a list of buzzwords (amongst them "raytracing") and go out to find that piece of software which has the most features on their list. Hence I coined the phrase "buzzword compatible" while at Neo-Visuals (and also "polygons for polygons sake" -- but that's another story). I have also seen demos, animations, and pictures at trade shows, presented by hardware and software vendors, which were extremely and deliberately misleading. A very common example is to show nice animation that was not really created with your software product. The animation having been typically created by special programs and add-ons. An obvious example was Abel, marketing their "Generation 2" software with "Sexy Robot", "Gold", "Hawaiian Punch", etc. I only mention Abel because they are no longer in business -- I don't want to mention any names of existing companies. I hadn't intended this to be a flame. But that sums up why not all software vendors bother with raytracing, and how it can be abused if not handled carefully. ==================== On Steve Upstill's remarks on the Renderman standard: Disclaimer: I have not read the Renderman specs, and have spoken to people who liked it and people who didn't. I would like to say that while I was at Neo-Visuals, Tom Porter and Pat Hanrahan did indeed drop by to ask us about our needs, and to ensure that the interface would be compatible with our system. As I recall, we asked that the interface be able of handling arbitrary polygons (n vertices, concave, etc). As I recall, I was playing devil's advocate at the meeting, questioning whether rendering had settled down enough to be standardized. So yes, at least Neo-Visuals did get to have a say and contribute to the interface. I spoke to one rendering person at Siggraph who didn't appreciate the way Pixar had handed down the interface and said "thou shalt enjoy." Well the alternative would be a PHIGS-like process: years spent in committees trying to hash out a compromise which will in all likelihood be obsolete before the ink is dry. In fact, two hardware vendors decided to take matters into their own hands and came up with PHIGS+. Yes, the interface is probably partly a marketing initiative by Pixar. Why would they do it otherwise? Why should they do it otherwise? I would guess that Pixar hopes to have the standard adopted, then come out with a board which will do Renderman rendering faster than anyone else's software. This seems a natural progression. More and more rendering features have been appearing in hardware -- 2D, 3D, flat shaded, Gouraud, and now Phong and texture maps. It is very probable that in a few years, "renderers" will be hardware, except for experimental, research, and prototype ones. ----------------------------------------------------------------------------- Minimum Bounding Sphere, continued ---------------------------------- by Jack Ritter, {ames,apple,sun,pyramid}!versatc!ritter I noticed in "The Ray Tracing News" an answer to my query about minimum bounding spheres. The answer following my question assumes there are 3 points. (Search for "Ray Traced Bounding Spheres"). This is wrong; I meant n points in 3 space. Since then, Lyle Rains, Wolfgang Someone and I have arrived at a fast way to find a tight bounding sphere for n points in 3 space: 1) Make 1 pass through pts. Find these 6 pts: pt with min x, max x, min/max y, min/max z. Pick the pair with the widest dimensional span. This describes the diameter of the initial bounding sphere. If the pts are anywhere near uniform, this sphere will contain most pts. 2) Make 2nd pass through pts: for each pt still outside current sphere, update current sphere to the larger sphere passing through the pt on 1 side, and the back side of the old sphere on the other side. Each new sphere will (barely) contain its previous pts, plus the new pt, and probably some new outsiders as well. Step 2 should need to be done only a small fraction of total num pts. The following is code (untested as far as I know) to increment sp: typedef double Ordinate; typedef double Distance; typedef struct { Ordinate x; Ordinate y; Ordinate z; } Point; typedef struct { Point center; Distance radius; } Sphere; Distance separation(pa, pb) Point *pa; Point *pb; { Distance delta_x, delta_y, delta_z; delta_x = pa->x - pb->x; delta_y = pa->y - pb->y; delta_z = pa->z - pb->z; return (sqrt(delta_x * delta_x + delta_y * delta_y + delta_z * delta_z)); } Sphere *new_sphere(s, p) Sphere *s; Point *p; { Distance old_to_p; Distance old_to_new; old_to_p = separation(&s->center, p); if (old_to_p > s->radius) { /* could test vs r**2 here */ s->radius = (s->radius + old_to_p) / 2.0; old_to_new = old_to_p - s->radius; s->center.x = (s->radius * s->center.x + old_to_new * p->x) / old_to_p; s->center.y = (s->radius * s->center.y + old_to_new * p->y) / old_to_p; s->center.z = (s->radius * s->center.z + old_to_new * p->z) / old_to_p; } return (s); } Jack Ritter, S/W Eng. Versatec, 2710 Walsh Av, Santa Clara, CA 95051 Mail Stop 1-7. (408)982-4332, or (408)988-2800 X 5743 UUCP: {ames,apple,sun,pyramid}!versatc!ritter [This looks to be a good quick algorithm giving a near-optimal solution. Has anyone come up with an absolutely optimal solution? The "three point" solution (in last issue) gives us a tool to do a brute force search of all triplets, but this is insufficient to solve the problem. For example, a tetrahedron's bounding sphere cannot be found by just searching all the triplets, as all such spheres would leave out the fourth point. - EAH] ----------------------------------------------------------------------------- Comments on "A Review of Multi-Computer Ray-Tracing" --------------------------------------------------- by Thierry Priol I read with a great interest in the hardcopy "Ray Tracing News (May 1989)" "A Review of Multi-Computer Ray-Tracing". But, D.A.J. Jevans said that our work presented in CGI "may even serve to cloud the important issues in multi-computer ray-tracing"! I do not agree with this remark. The presentation at CGI describes only a first step in using multi-processor ray tracing algorithms. It is true that there were no interesting results in this paper. D.A.J. Jevans also said that a hypercube architecture is hardware specific. I do not agree. This kind of architecture represents a great part of distributed memory architectures. Our algorithm is not specific for this topology and can work on a SYMULT-2010 which uses a mesh topology. However, I agree when he said that our algorithm provides little in the way of new algorithms, since we used Cleary's algorithm. But we think that for the moment, the main problem is not to create new algorithms but to make experiments with some algorithms presented by several authors because most of them have been simulated but not implemented. Our experiments show that many problems due to distributed computing (not only load and memory balancing) were not solved by the authors. At present, our algorithm has been modified to take into account load balancing and we have several results not yet published. These new results may give some important conclusions about the Cleary approach (processor-volume association). We are working now on a new algorithm based on a global memory on distributed memory architectures! For my mind it is the best solution to obtain load and memory balancing. The ray coherence property is a means to have a sort of locality when data is read in the global memory (best use of caches). We are very interested (D. Badouel, K. Bouatouch and myself) in submitting to the "Ray-tracing News" a short paper which summarizes our work in parallel ray-tracing algorithm for distributed memory architecture. This contribution should present two ray tracing algorithms with associated results. This work has not been yet published outside France. ======== USENET cullings follow =============================================== {deleted from USENET edition, since all of these articles were on USENET}