Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!rutgers!clyde!cbatt!osu-eddie!osu-cgrg!spencer From: spencer@osu-cgrg.UUCP (Steve Spencer) Newsgroups: comp.graphics Subject: Re: ray tracing (Was Amiga ray tracer) Message-ID: <823@osu-cgrg.UUCP> Date: Tue, 28-Apr-87 11:33:01 EDT Article-I.D.: osu-cgrg.823 Posted: Tue Apr 28 11:33:01 1987 Date-Received: Thu, 30-Apr-87 03:30:58 EDT References: <1514@sphinx.uchicago.edu> <4947@hi.uucp> <829@bgsuvax.UUCP> Organization: Computer Graphics Research Group, Columbus OH Lines: 48 Summary: spatial subdivision In article <829@bgsuvax.UUCP>, ritzenth@bgsuvax.UUCP (Phil Ritzenthaler) writes: > In article <4947@hi.uucp>, josh@hi.uucp (Josh Siegel ) writes: > > I am going to throw out some more ideas. Maybe some great and new method > > could be generated right here... :-) > . > > Maybe I am in the wrong ballpark, but wasn't this already proposed? In > IEEE CG & A, April, 1986 a similar (but not quite) proposal was presented by > some gentlemen (one I recall was named Fujimoto). The system was call the > ARTS (Accelerated Ray Tracing System) System. It is now being put into > an application by Ray Tracing, INC. (address given if needed) . . . > Sorry, Josh. It's been done, though re-inventing the wheel shows original thought. Spatial subdivision has been proposed by more than one person or group. Look in IEEE CG&A, back SIGGRAPH proceedings... Basically, it falls into these categories: 1. a hierarchical subdivision scheme, usually an octree-like approach. this is quicker than... 2. an equal-sized spatial subdivision (break the "world" into NxNxN equal sized boxes. this method is easier to implement then #1, but it is slower. 3. the tried-and-true method of bounding boxes of bounding boxes... [Timothy Kay talked about a new (and interesting...) way to do this at last year's SIGGRAPH.] In general, all of these methods greatly reduce the time spent by ray-tracing programs, because you don't have to do ALL THOSE INTERSECTION CALCULATIONS !!!!! Fujimoto's program ran fast for two reasons: first, they used spatial subdivision. Second, their algorithm dropped into assembly language in places, for speed. Good luck. -- ...I'm growing older but not up... - Jimmy Buffett Stephen Spencer, Graduate Student The Computer Graphics Research Group The Ohio State University 1501 Neil Avenue, Columbus OH 43210 {decvax,ucbvax}!cbosg!osu-cgrg!spencer (uucp)