Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-lcc!styx!ames!ucbcad!ucbvax!cbatt!osu-eddie!elwell
From: elwell@osu-eddie.UUCP (Clayton Elwell)
Newsgroups: comp.graphics
Subject: Re: ray tracing (Was Amiga ray tracer)
Message-ID: <3483@osu-eddie.UUCP>
Date: Fri, 1-May-87 12:10:03 EDT
Article-I.D.: osu-eddi.3483
Posted: Fri May  1 12:10:03 1987
Date-Received: Sun, 3-May-87 01:24:20 EDT
References: <1514@sphinx.uchicago.edu> <4947@hi.uucp> <829@bgsuvax.UUCP> <823@osu-cgrg.UUCP> <21416@styx.UUCP>
Sender: news@osu-eddie.UUCP
Reply-To: elwell@osu-eddie.UUCP (Clayton Elwell)
Organization: The Ohio State University, CIS Dept.
Lines: 42

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?  Is it true for all cases?  How did you
>conclude that one scheme was faster than the other?  Does the hierarchical
>subdivision scheme take advantage of integer arithmetic to trace rays?
>
>John Carlson
>ARPA: carlson@lll-tis-b.arpa
>UUCP: lll-crg!styx!carlson

I have observed the implementation of a ray tracer that uses scheme #1 (octree
subdivision).  It was written by Andrew Glassner while he was at Case Western
Reserve University.  I believe he had an article about it in IEEE CG&A a year
or so ago (I can go look it up if necessary).

His scheme subdivided the scene into an octree such that each cell had less
than a certain number of objects.  Since the cell boundaries were parallel to
the coordinate planes (in object space, of course), and the program kept track
of the size of the smallest cell, a ray could be propagated from one cell to
the next in only a few calculations.  He tested it against a naive ray tracer
(one that tested each ray against every object), and it showed a significant
improvement.  As I remember, the naive tracer ran in exponential time (by
number of objects), and the octree encoded tracer ran in sublinear time (by
number of objects).

This is discussed in detail in his article in IEE CG&A mentioned above.


-=-


							Clayton Elwell
The meek are getting ready...			Elwell@Ohio-State.ARPA
					   ...!cbosgd!osu-eddie!elwell