Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!lll-lcc!styx!ptsfa!ihnp4!cbatt!osu-eddie!osu-cgrg!spencer From: spencer@osu-cgrg.UUCP (Steve Spencer) Newsgroups: comp.graphics Subject: Re: ray tracing (Was Amiga ray tracer) Message-ID: <824@osu-cgrg.UUCP> Date: Fri, 1-May-87 10:40:10 EDT Article-I.D.: osu-cgrg.824 Posted: Fri May 1 10:40:10 1987 Date-Received: Sun, 3-May-87 01:14:22 EDT References: <1514@sphinx.uchicago.edu> <4947@hi.uucp> <829@bgsuvax.UUCP> <21416@styx.UUCP> Organization: Computer Graphics Research Group, Columbus OH Lines: 59 In article <21416@styx.UUCP>, carlson@styx.UUCP (John Carlson) writes: > In article <823@osu-cgrg.UUCP> spencer@osu-cgrg.UUCP (Steve Spencer) writes: > >Basically, it falls into these categories: > > 1. a hierarchical subdivision scheme, usually an octree-like approach. > > this is quicker than... > > 2. an equal-sized spatial subdivision (break the "world" into NxNxN > > equal sized boxes. > > this method is easier to implement then #1, but it is slower. > > This is news to me (and I am trying to catch up). > Do you have empirical or experimental data to show this? Not that I have actual numbers right here with me, but I seem to remember a slightly quicker runtime for octree-based subdivision versus the SEADS (equal-sized subdivision) method. Intuitively, it would make sense that the hierarchical approach would be faster, because the subdivisions are more proportional to the scene's complexity in a given area (greater subdivision where there's more stuff, less subdivision where there's a lot of empty space.) > Is it true for all cases? No. There are "scenes" (groupings of lights and objects) which, based upon their placement, would be faster with one method than with the other. For example, imagine defining a scene with nine spheres: eight of them at the corners of a cube 100 units on a side, and the ninth in the center. The SEADS approach would be a dog here, compared to the octree approach, for most combinations of [criteria for octree subdivision] and [number of "voxels" in which to subdivide the scene space]. On the other hand, the octree approach may bog down with a scene which was constructed with many objects clustered near the center of the scene space, because traversing the octree can be time-consuming when the octree is deep. Here, the SEADS approach would, at least in concept, be better. > How did you conclude that one scheme was faster than the other? Comparing timings of scenes. > Does the hierarchical subdivision scheme take advantage of integer > arithmetic to trace rays? It can, though ours doesn't. (I didn't write that module but am fairly certain of my answer.) Both the hierarchical subdivision and the SEADS method could utilize integer arithmetic. > > John Carlson > ARPA: carlson@lll-tis-b.arpa > UUCP: lll-crg!styx!carlson Hope this helped. -- ...I'm growing older but not up... - Jimmy Buffett Stephen Spencer, Graduate Student The Computer Graphics Research Group The Ohio State University 1501 Neil Avenue, Columbus OH 43210 {decvax,ucbvax}!cbosg!osu-cgrg!spencer (uucp)