stephens@motcid.UUCP (Kurt Stephens) (03/08/91)
Most implementations (I've seen or heard or) of distributed ray
tracing, distribute the object database between multiple processors and
each processor computes a subset of the image.
Has any research been done on distributed ray tracers
which each processor handles the ray-object intersections for
subset of the database, while a master processor (or group of
master processors) computes the image, by sending messages to the
appropriate object processor, e.g. "intersect ray X with object Y"?
For the sake of discussion, what would be the
advantages/disadvantages of "slicing" the database rather than the
image?
Some Advantages:
1. Each object processor only needs a subset of the
object database
2. Each object processor would only need the intersection
routines, and not the entire ray tracer.
3. Because of #1 and #2, setup time in a massive scale
multiprocessor would be reduced.
Some Disadvantages:
1. Many object processors could be idle, waiting
for signals to process an intersection. In this case, "image slicing"
might be more efficent.
2. The master processor could be a bottleneck.
3. Inter-processor message I/O could be a bottleneck.
(millions of little Ethernet packets... ;^)
Any comments?
Kurt A. Stephens Foo::Foo(){return Foo();}
stephens@void.rtsg.mot.com "When in doubt, recurse."
--
Kurt A. Stephens Foo::Foo(){return Foo();}
stephens@void.rtsg.mot.com "When in doubt, recurse."stephens@motcid.UUCP (Kurt Stephens) (03/09/91)
stephens@motcid.UUCP (Kurt Stephens) writes: > Most implementations (I've seen or heard or) of distributed ray >tracing, distribute the object database between multiple processors and Ooops! I realized the improper terminology just after I sent the post... >each processor computes a subset of the image. > Has any research been done on distributed ray tracers >which each processor handles the ray-object intersections for >subset of the database, while a master processor (or group of >master processors) computes the image, by sending messages to the >appropriate object processor, e.g. "intersect ray X with object Y"? > For the sake of discussion, what would be the >advantages/disadvantages of "slicing" the database rather than the >image? > Some Advantages: > 1. Each object processor only needs a subset of the > object database > 2. Each object processor would only need the intersection >routines, and not the entire ray tracer. > 3. Because of #1 and #2, setup time in a massive scale >multiprocessor would be reduced. > Some Disadvantages: > 1. Many object processors could be idle, waiting >for signals to process an intersection. In this case, "image slicing" >might be more efficent. > 2. The master processor could be a bottleneck. > 3. Inter-processor message I/O could be a bottleneck. >(millions of little Ethernet packets... ;^) > Any comments? Nicholas Wilt (npw@eleazar.dartmouth.edu) writes: NW:I have seen netters allude to two competing techniques of parallel ray NW:tracing. Both seem to be targeted for groups of networked machines. NW:The scheme you propose requires machines to communicate during NW:computation; this is very different from telling each Sun on a network NW:"You do this part" and splicing together their results. Your proposal NW:is very feasible for massively parallel machines which have special NW:hardware for interprocessor communication, but even a high-speed network NW:may not have enough bandwidth to make your scheme feasible on a group NW:of networked machines. Jonathan Leech (uunet!mcnc.org!cs.unc.edu!leech) writes: JL: My idea was to split the database spatially using bounding volumes JL:ala Kay (not surprising since he worked in the same lab at the time JL::-), replicating the top levels of the bounding volume tree on each JL:node. Then the 'master processor' would just distribute blocks of JL:rays; each node would be responsible for two tasks, intersecting JL:primary rays against the global bounding volume tree and sending JL:requests for intersections with leaves of that tree, and satisfying JL:other node's requests for intersections with the leaf of the tree it JL:contained. Load balancing is accomplished by not sending blocks of JL:primary rays to the nodes doing a lot of the second task. As it turns JL:out, I was scooped before I got very far - see _The Visual Computer_ JL:about 2 years ago - but their implementation indicates the technique JL:does work. JL: I would avoid doing this on a network of workstations, which JL:usually have enough memory. This is more for MIMD machines like JL:hypercubes. You could use buffering strategies to cut down on JL:traffic, but why bother. -- Kurt A. Stephens Foo::Foo(){return Foo();} stephens@void.rtsg.mot.com "When in doubt, recurse."
woo@pioneer.arc.nasa.gov (Alex Woo RAA) (03/10/91)
======================================================================
Alex Woo, MS 227-6 | woo@ames.arc.nasa.gov
NASA Ames Research Center | NASAMAIL ACWOO
Moffett Field, CA 94035-1000| {seismo,topaz,lll-crg,ucbvax}!
Phone: (415) 604-6010 | ames!pioneer!woo
======================================================================
{hplabs,hao,att,decwrl,allegra,tektronix,menlo70}!ames!pioneer!woo
======================================================================erich@eye.com (Eric Haines) (03/11/91)
In article <6678@celery34.UUCP> stephens@motcid.UUCP (Kurt Stephens) writes: > > Most implementations (I've seen or heard or) of distributed ray >tracing, distribute the object database between multiple processors and >each processor computes a subset of the image. > Has any research been done on distributed ray tracers >which each processor handles the ray-object intersections for >subset of the database, while a master processor (or group of >master processors) computes the image, by sending messages to the >appropriate object processor, e.g. "intersect ray X with object Y"? Check out: %A John Salmon %A Jeffrey Goldsmith %T A Hypercube Ray-Tracer %J Proceedings of the Third Conference on Hypercube Computers and Applications %D 1988 They have an interesting method of taking a database which has been put in a hierarchical bounding box efficiency scheme and splitting up the hierarchy for efficient ray tracing. They also talk about image decomposition. %A Mark E. Dippe %A John Swensen %T An Adaptive Subdivision Algorithm and Parallel Architecture for Realistic Image Synthesis %J Computer Graphics (SIGGRAPH '84 Proceedings) %V 18 %N 3 %D July 1984 %P 149-158 %O also in Tutorial: Computer Graphics Hardware: Image Generation and Display, Computer Society Press, Washington, 1988, p. 285-290. They propose an algorithm for adaptive load distribution by splitting up the database into a grid of hexahedra and adjusting the boundaries of these hexahedra when bottlenecks in ray passing are detected. %A Keiji Nemoto %A Takao Omachi %T An Adaptive Subdivision by Sliding Boundary Surfaces for Fast Ray Tracing %J Proceedings of Graphics Interface '86 %I Canadian Information Processing Society %C Toronto, Ontario %D May 1986 %P 43-48 %Z adaptive subdivision algorithm on a parallel architecture These take Dippe & Swensen's ideas, but use regular boxes instead of hexahedra for efficiency. Hmmm, there are actually quite a few papers on this area of research. Give Tom Wilson's ray tracing abstracts a look. I just remembered, there's a nice overview of this topic. The following related references are from an article in the hardcopy Ray Tracing News (which I wish was reprinted somewhere else) by David Jevans: %A Hiroaki Kobayashi %A Tadao Nakamura %A Yoshiharu Shigei %T Parallel Processing of an Object Space for Image Synthesis Using Ray Tracing %J The Visual Computer %V 3 %N 1 %D February 1987 %P 13-22 %A Isaac D. Scherson %A Elisha Caspary %T Multiprocessing for Ray Tracing: a Hierarchical Self-balancing Approach %J The Visual Computer %V 4 %N 4 %D October 1988 %P 188-196 %A Andrew Pearce %T An Implementation of Ray Tracing Using Multiprocessor and Spatial Subdivision %R Master's Thesis %I University of Calgary, Dept. of Computer Science %D 1987 %A Hiroaki Kobayashi %A Satoshi Nishimura %A Hideyuki Kubota %A Tadao Nakamura %A Yoshiharu Shigei %T Load Balancing Strategies for a Parallel Ray-Tracing System Based on Constant Subdivision %J The Visual Computer %V 4 %N 4 %D October 1988 %P 197-209 %A Hiroaki Kobayashi %A Satoshi Nishimura %T Parallel Architecture for Fast Image Synthesis Under Dynamic Environments %B Proceedings of Computer Graphics International '89 %I Springer-Verlag %D 1989 [does anyone have the page numbers and editors of this last reference?] There are probably more I've missed. Eric Haines, erich@eye.com
jonas-y@isy.liu.se (Jonas Yngvesson) (03/12/91)
erich@eye.com (Eric Haines) writes: >%A Hiroaki Kobayashi >%A Satoshi Nishimura >%T Parallel Architecture for Fast Image Synthesis Under Dynamic Environments >%B Proceedings of Computer Graphics International '89 >%I Springer-Verlag >%D 1989 >[does anyone have the page numbers and editors of this last reference?] Hmm, that article doesn't exist. At least not in my copy. Maybe this one is the one intended: "Effective Parallel Processing for Synthesizing Continuous Images" by Hiroaki Kobayashi, Hideyuki Kubota, Susumu Horiguchi and Tadao Nakamura, pp 343-352, New Advances in Computer Graphics (Proceedings of Computer Graphics International '89), Springer-Verlag, 1989 In the same book (pp 507-522) is also: "Optimistic Multi-Processor Ray Tracing" by David Jevans --Jonas -- ------------------------------------------------------------------------------ J o n a s Y n g v e s s o n Dept. of Electrical Engineering jonas-y@isy.liu.se University of Linkoping, Sweden ...!uunet!isy.liu.se!jonas-y