Enhanced Breadth-First Ray Tracing

Koji Nakamaru and Yoshio Ohno
Keio University

This paper appears in issue Volume 6, Number 4.
Purchase this issue from the akpeters.com web site.

Abstract

Breadth-first ray tracing that utilizes uniform spatial subdivision can render a large number of objects without breakdown. The original algorithm however has two major drawbacks: redundant data processing and limited grid resolution. We present several refinements for these drawbacks and realize fast and robust external ray tracing. We achieved speedups of roughly up to 4x for SPD scenes with up to 50 million objects, and up to 14x for pathological cases with 1 billion objects, all rendered on a PC with 256MB memory.

Author Information

Koji Nakamaru, Ohno Lab, Grad School of Comp Sci, Faculty of Science & Tech, Keio University, Yokohama 223-8522, Japan maru@on.cs.keio.ac.jp

Yoshio Ohno, Ohno Lab, Grad School of Comp Sci, Faculty of Science & Tech, Keio University, Yokohama 223-8522, Japan ohno@on.cs.keio.ac.jp

Supplements

The authors provide complete numerical results of their experiments: Detailed Report

Images

Rendered images for huge data. The view parameter is the only difference between ‘rings368m’ and ‘rings368’: the view frustum of ‘rings368m’ contains approximately 1,000,000 objects. (Click on a thumbnail to see the full-resolution image.)

mount14
#objects: 536,870,916
48.50GB

rings368
#objects: 1,000,787,041
86.77GB

rings368m
#objects: 1,000,787,041
86.77GB

BibTeX Entry

@article{NakamaruOhno01,
  author = "Koji Nakamaru and Yoshio Ohno",
  title = "Enhanced Breadth-First Ray Tracing",
  journal = "journal of graphics, gpu, and game tools",
  volume = "6",
  number = "4",
  pages = "13-28",
  year = "2001",
}