Path: utzoo!attcan!uunet!ncrlnk!ncrcae!hubcap!gatech!ncar!ames!vsi1!versatc!ritter
From: ritter@versatc.UUCP (Jack Ritter)
Newsgroups: comp.graphics
Subject: Re: Raytracing speedups....
Message-ID: <7839@versatc.UUCP>
Date: 17 Dec 88 00:27:31 GMT
References: <907@cmx.npac.syr.edu>
Organization: Versatec, Santa Clara, Ca. 95051
Lines: 64


In Article 2031 of comp.graphics,
Gill E. Fuchs writes:

>   The following paragraphs describe an idea of mine.  This idea describe
> 	a possible algorithm for improving speed for raytracing...

> 	But as you are reading world coordinate positions for objects using a
> 	4 X 4 transformation matrix, transform the object center plus any point
> 	along the border (radius for sphere) to screen coordinates.

> 	   As you begin to render an image and create rays for all pixels on
> 	the screen, you check to see if the current screen(x,y) coordinate that
> 	is being processed is in side any of the bounding boxes.


I came up with this idea in aug, '88. I posted it, and got a response.
Since my formulation was concise, I will include it here again, w/ respnse.
(Basically, Gill has added recursive boxing to the algorithm.)

**************************** My Aug posting*********************

A simple method for fast ray tracing has occurred to me,
and I haven't seen it in the literature, particularly
Procedural Elements for Computer Graphics.
It works for primary rays only.

Do once for each object: 
   compute its minimum 3D bounding box. Project
   the box's 8 corners unto pixel space. Surround the
   cluster of 8 pixel points with a minimum 2D bounding box.
   (a tighter bounding volume could be used).

To test a ray against an object, check if the pixel
through which the ray goes is in the object's 2D box.
If not, reject it.

It sure beats line-sphere minimum distance calculation.

*********************** the response**********************

Hi, I just read your posting on ray-object intersection and did not
get a chance to look and see if anyone else responded to this (which
for unbiased opinions is always best), so here is my response.

I am not sure whether your 8 pt 2-d bounding box test has been tried
or not.  It certainly is a novel idea worth persuing.  However, if you
have looked at most raytracing articles, there have been a variety of
attempt to reduce the number of "first" intersection calculations.  I
believe Weghorst actually goes as far as to use a first level
scan-conversion routine to solve the first intersection problem.  This
would be the fastest method.  The main problem with ray-tracing,
though, is the object intersections encountered at the later levels
when traversing the tree.  This is where the majority of time is spent
in this type algorithm.  Hope this was helpful.

			-Scott Whitman (slim@tut.cis.ohio-state.edu.ARPA)


-- 
       The ultimate realization: everything is everything. (I should know.)
   Jack Ritter, S/W Eng. Versatec, 2805 Bowers Av, Santa Clara, CA 95051
   Mail Stop 1-7.  (408)982-4332, or (408)988-2800 X 5743
   UUCP: {pyramid,mips,vsi1,arisia}!versatc!ritter