Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!ncar!boulder!speer
From: speer@boulder.Colorado.EDU (Rick Speer)
Newsgroups: comp.graphics
Subject: More Re:  A Ray Tracer Accelerator: ???
Keywords: bounding volumes
Message-ID: <30554@boulder.Colorado.EDU>
Date: 3 Dec 90 18:39:50 GMT
References: Articles 15386 and 15388 of comp.graphics
Sender: news@boulder.Colorado.EDU
Organization: University of Colorado, Boulder
Lines: 56
Nntp-Posting-Host: becks.colorado.edu
Originator: speer@becks.colorado.edu

Wilson@ucf-cs.UCF.EDU (tom wilson) writes about using what might
be called inscribing bounding volumes-

>Subject: A Ray Tracer Accelerator: ???
>Date: 14 Nov 90 02:01:57 GMT

>Out of nowhere, I have come up with a new (?) speedup (?) technique for
>shadow testing in ray tracing. I don't have the kind of code necessary to
>test it. It is kind of the inverse of a bounding volume:

                  [Many lines deleted]

As Mark VandeWettering noted in a followup, the gist of the idea is-

>[ Synopsis:  Tom suggests putting simple objects _inside_ complex ones. 
>  The idea is if the ray intersects the simple object, then it MUST 
>  intersect the simple one.  This is only good for shadow testing
>  obviously, since we would need the REAL intersection for view rays.]

I'd like to add my $0.02 and note that W. R. Franklin examined this idea
in a non-raytracing but similar context in the following paper-

  "3D Geometric Databases using Hierarchies of Inscribing Boxes",
  pp. 173-80 in Proceedings of "CMCCS '81" (this is what the Cana-
  dian conference now known as 'Graphics Interface' used to be call-
  ed; these volumes are available from the Canadian Information Pro-
  cessing Society, Toronto, if anyone's interested).

To be more specific, let me quote a bit from the paper's abstract-

  "Hierarchical tree structured databases are an efficient way
   of representing scenes with elaborate detail of varying scales.
   Storing a circumscribing box around each object is a well known
   method of testing whether the object intersects or obstructs any
   other objects. This paper proposes another aid: an inscribing box.
   The inbox is a polyhedron that is completely contained in the ob-
   ject. It should be as large as is easy to determine... The inbox
   speeds up visibility tests [in the following way:... ] [He con-
   cludes,] By combining inboxes and circumboxes, it is possible to
   calculate the visible surfaces of a hierarchical scene in time
   linear in the visible complexity of the scene..."

In his followup message, Mark goes on to note that this issue really
needs to be studied on test scenes using a probabilistic analysis. I
hope it wouldn't be too immodest of me to note that such an analysis
appears in the paper,

  "A Theoretical and Empirical Analysis of Coherent Ray-tracing",
  L. R. Speer, T. DeRose and B. Barsky, pp. 11-25 in the Proceed-
  ings of Graphics Interface '85, CIPS, Toronto, 1985.

------------------------------------------------------------------------------
| Rick Speer                 | "Can I try another world?" - From a guy trying|
| speer@anchor.colorado.edu  |  out the system at the VPL Research (virtual  |
|                            |  reality) booth at Siggraph '90.              |
------------------------------------------------------------------------------


Brought to you by Super Global Mega Corp .com