speer@boulder.Colorado.EDU (Rick Speer) (12/04/90)
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. | ------------------------------------------------------------------------------