Interactive ray tracing with the visibility complex

Franklin S. Cho, David Forsyth

Research output: Contribution to journalArticlepeer-review


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)
Issue number5
StatePublished - Oct 1999
Externally publishedYes


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

ASJC Scopus subject areas

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


Dive into the research topics of 'Interactive ray tracing with the visibility complex'. Together they form a unique fingerprint.

Cite this