Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!decwrl!sun-barr!ccut!titcca!cc.titech.ac.jp!necom830!mohta
From: mohta@necom830.cc.titech.ac.jp (Masataka Ohta)
Newsgroups: comp.graphics
Subject: Re: Where to publish ray tracing algorithm?
Message-ID: <6147@titcce.cc.titech.ac.jp>
Date: 10 Sep 90 15:31:29 GMT
References: <1145@mti.mti.com> <1150@mti.mti.com>
Sender: news@cc.titech.ac.jp
Organization: Tokyo Institute of Technology
Lines: 29

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

>many instances can use a surface map for
>a single bouding volume as a lookup table to immediately determine a small
>subset of objects to test (which is truly of O(1)). (Small subset here is
>roughly equivalent to the set of objects in the smallest volume in a
>comparable hierarchical scheme.)

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

Judging from the above brief description of your algorithm, it may be
similar or identical to mine.

>It's *not* general,

Hmmm, mine is general.

						Masataka Ohta