Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!mit-eddie!uw-beaver!ubc-vision!fornax!chapman
From: chapman@fornax.uucp (John Chapman)
Newsgroups: comp.graphics
Subject: Re: ray tracing (Was Amiga ray tracer)
Message-ID: <276@fornax.uucp>
Date: Sat, 2-May-87 15:52:14 EDT
Article-I.D.: fornax.276
Posted: Sat May  2 15:52:14 1987
Date-Received: Wed, 6-May-87 04:48:27 EDT
References: <1514@sphinx.uchicago.edu> <4947@hi.uucp> <829@bgsuvax.UUCP> <823@osu-cgrg.UUCP> <21416@styx.UUCP> <3483@osu-eddie.UUCP>
Organization: School of Computing Science, SFU, Burnaby, B.C. Canada
Lines: 19

.
.
.
> 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).

The naive ray tracing alg. tests a ray against every object in the scene.
The time for a single ray is O(n) when there are n objects. If you render
a scene with an m by m raster and a single ray/pixel the time is then
O(n*m*m).
 

*** REPLACE THIS LINE WITH YOUR MESSAGE ***
-- 
{watmath,seismo,uw-beaver}!ubc-vision!fornax!sfulccr!chapman
                   or  ...!ubc-vision!sfucmpt!chapman