Interactive ray tracing with the visibility complex

Franklin S. Cho, David Forsyth

Research output: Contribution to journalArticle

Abstract

We describe a method of producing ray-traced images of 2D environments at interactive rates. The 2D environment consists of a set of disjoint, convex polygons. Our technique is based on the visibility complex [17,19] [Pocchiola M, Vegter G. Proc Int J Comput GEOM Applic 1996;6(3):279-308. Rivière S. Visibility computations in 2D polygonal scenes. PhD thesis, Univ. Joseph Fourier, Grenoble I, France], a data structure in a dual space where a face of the visibility complex corresponds to a contiguous set of rays in the primary space with the same forward and backward views. Sweeping the viewing ray around a viewpoint corresponds to walking along a trajectory on the visibility complex. Producing a ray-traced image is equivalent to walking along and maintaining a set of trajectories. Generating ray-traced images with the visibility complex is very efficient since it uses the coherence among the rays effectively. We have developed a new algorithm for the randomized incremental construction of the visibility complex. The advantage of using an incremental algorithm is that the history of the incremental construction yields an efficient ray-query data structure, which is required for casting secondary rays. The performance of our algorithm is analyzed and a comparison is made with the classical ray-tracing algorithm.

Original languageEnglish (US)
Pages (from-to)703-717
Number of pages15
JournalComputers and Graphics (Pergamon)
Volume23
Issue number5
DOIs
StatePublished - Oct 1999
Externally publishedYes

Fingerprint

Ray tracing
Visibility
Data structures
Trajectories
Casting

Keywords

  • Coherence
  • Interactive ray tracing
  • Line space
  • Visibility complex

ASJC Scopus subject areas

  • Engineering(all)
  • Human-Computer Interaction
  • Computer Graphics and Computer-Aided Design

Cite this

Interactive ray tracing with the visibility complex. / Cho, Franklin S.; Forsyth, David.

In: Computers and Graphics (Pergamon), Vol. 23, No. 5, 10.1999, p. 703-717.

Research output: Contribution to journalArticle

@article{0f868f7cac34420594b0d8f8f2589021,
title = "Interactive ray tracing with the visibility complex",
abstract = "We describe a method of producing ray-traced images of 2D environments at interactive rates. The 2D environment consists of a set of disjoint, convex polygons. Our technique is based on the visibility complex [17,19] [Pocchiola M, Vegter G. Proc Int J Comput GEOM Applic 1996;6(3):279-308. Rivi{\`e}re S. Visibility computations in 2D polygonal scenes. PhD thesis, Univ. Joseph Fourier, Grenoble I, France], a data structure in a dual space where a face of the visibility complex corresponds to a contiguous set of rays in the primary space with the same forward and backward views. Sweeping the viewing ray around a viewpoint corresponds to walking along a trajectory on the visibility complex. Producing a ray-traced image is equivalent to walking along and maintaining a set of trajectories. Generating ray-traced images with the visibility complex is very efficient since it uses the coherence among the rays effectively. We have developed a new algorithm for the randomized incremental construction of the visibility complex. The advantage of using an incremental algorithm is that the history of the incremental construction yields an efficient ray-query data structure, which is required for casting secondary rays. The performance of our algorithm is analyzed and a comparison is made with the classical ray-tracing algorithm.",
keywords = "Coherence, Interactive ray tracing, Line space, Visibility complex",
author = "Cho, {Franklin S.} and David Forsyth",
year = "1999",
month = "10",
doi = "10.1016/S0097-8493(99)00093-X",
language = "English (US)",
volume = "23",
pages = "703--717",
journal = "Computers and Graphics",
issn = "0097-8493",
publisher = "Elsevier Limited",
number = "5",

}

TY - JOUR

T1 - Interactive ray tracing with the visibility complex

AU - Cho, Franklin S.

AU - Forsyth, David

PY - 1999/10

Y1 - 1999/10

N2 - We describe a method of producing ray-traced images of 2D environments at interactive rates. The 2D environment consists of a set of disjoint, convex polygons. Our technique is based on the visibility complex [17,19] [Pocchiola M, Vegter G. Proc Int J Comput GEOM Applic 1996;6(3):279-308. Rivière S. Visibility computations in 2D polygonal scenes. PhD thesis, Univ. Joseph Fourier, Grenoble I, France], a data structure in a dual space where a face of the visibility complex corresponds to a contiguous set of rays in the primary space with the same forward and backward views. Sweeping the viewing ray around a viewpoint corresponds to walking along a trajectory on the visibility complex. Producing a ray-traced image is equivalent to walking along and maintaining a set of trajectories. Generating ray-traced images with the visibility complex is very efficient since it uses the coherence among the rays effectively. We have developed a new algorithm for the randomized incremental construction of the visibility complex. The advantage of using an incremental algorithm is that the history of the incremental construction yields an efficient ray-query data structure, which is required for casting secondary rays. The performance of our algorithm is analyzed and a comparison is made with the classical ray-tracing algorithm.

AB - We describe a method of producing ray-traced images of 2D environments at interactive rates. The 2D environment consists of a set of disjoint, convex polygons. Our technique is based on the visibility complex [17,19] [Pocchiola M, Vegter G. Proc Int J Comput GEOM Applic 1996;6(3):279-308. Rivière S. Visibility computations in 2D polygonal scenes. PhD thesis, Univ. Joseph Fourier, Grenoble I, France], a data structure in a dual space where a face of the visibility complex corresponds to a contiguous set of rays in the primary space with the same forward and backward views. Sweeping the viewing ray around a viewpoint corresponds to walking along a trajectory on the visibility complex. Producing a ray-traced image is equivalent to walking along and maintaining a set of trajectories. Generating ray-traced images with the visibility complex is very efficient since it uses the coherence among the rays effectively. We have developed a new algorithm for the randomized incremental construction of the visibility complex. The advantage of using an incremental algorithm is that the history of the incremental construction yields an efficient ray-query data structure, which is required for casting secondary rays. The performance of our algorithm is analyzed and a comparison is made with the classical ray-tracing algorithm.

KW - Coherence

KW - Interactive ray tracing

KW - Line space

KW - Visibility complex

UR - http://www.scopus.com/inward/record.url?scp=0003583080&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0003583080&partnerID=8YFLogxK

U2 - 10.1016/S0097-8493(99)00093-X

DO - 10.1016/S0097-8493(99)00093-X

M3 - Article

AN - SCOPUS:0003583080

VL - 23

SP - 703

EP - 717

JO - Computers and Graphics

JF - Computers and Graphics

SN - 0097-8493

IS - 5

ER -