Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!shirley
From: shirley@iuvax.cs.indiana.edu (peter shirley)
Newsgroups: comp.graphics
Subject: Re: Where to publish ray tracing algorithm?
Message-ID: <57800@iuvax.cs.indiana.edu>
Date: 10 Sep 90 18:01:34 GMT
References: <1145@mti.mti.com> <1150@mti.mti.com> <6147@titcce.cc.titech.ac.jp>
Organization: Indiana University, Bloomington
Lines: 41

mohta@necom830.cc.titech.ac.jp (Masataka Ohta) writes:

>In article <1150@mti.mti.com> adrian@mti.UUCP (Adrian McCarthy) writes:

>>Rather than using recursive or hierarchical
>>spatial subdivision techniques to reduce ray-object intersection tests
>>(which are of O(log n) algorithms)

>Can you prove it? I think (but can't prove) hierarchical spatial
>subdivision is only O(n**(1/3)).


>I already published an O(1) ray tracing algorithm (See "An introduction
>to RAY TRACING" edited by Andrew S. Glassner, Academic Press, 6.3 The Ray
>Coherence Algorithm, page 232-234, or, "Computer Graphics 1987 (Proc.
>of CG International '87)", page 303-314, Ray Coherence Theorem and
>constant time ray tracing algorithm).

>						Masataka Ohta


Kaplan also has claimed a constant time algorithm.  I don't believe that
his is consyant time-- it (like an octree) is a divide and conquer
search, so it will AT BEST be O(logN)  (it takes O(logN) time to travel
down the hieght of a tree).

I don't really see how we can even say what the big-O of a ray intersection
is without precisely stating what rays are allowed on what geometry.
For example, suppose I set up N epsilon radius spheres in random locations
within a cube, where epsilon is small.  In the typical case a ray might
come close to many spheres.  If an octree is used, the candidate sets
of many leaves might be checked (worse than O(logN)).  If all of the spheres
have the same center, how can any scheme get a candidate set for a ray
through ythe center that doesn't include all spheres?  This would be 
O(NlogN) for an octree and O(N) optimally.  How would your method be O(1)?
It seems that often we have good algorithm behavior in practice with
pathological cases giving terrible big-Os.  Perhaps we can bound the set
of scenes somehow?

Pete Shirley
shirley@cs.indiana.edu