Making the DDA run: two-dimensional ray traversal using runs and runs of runs

Author

Stephenson, Peter ; Litow, Bruce

Author_Institution

Fraunhofer Center for Res. in Comput. Graphics, Providence, RI, USA

fYear

2001

fDate

2001

Firstpage

177

Lastpage

183

Abstract

Iterative algorithms based on runs, and runs of runs are presented to calculate the cells of the two-dimensional lattice intersected by a line of real slope and intercept. The technique is applied to the problem of traversing a ray through a two-dimensional grid. Using runs or runs of runs provides a significant improvement in the efficiency of ray traversal for all but very short path lengths when compared to the DDA algorithm implemented using floating or fixed point arithmetic

Keywords

computational geometry; data visualisation; iterative methods; ray tracing; DDA algorithm; DDA run; digital geometry; fixed point arithmetic; floating point arithmetic; intercept; iterative algorithms; line digitisation; ray tracing; ray traversal; real slope; runs of runs; two-dimensional grid; two-dimensional lattice; two-dimensional ray traversal; very short path lengths; volume visualisation; Arithmetic; Biomedical imaging; Computer graphics; Computer vision; Geometry; Information technology; Iterative algorithms; Lattices; Ray tracing; Visualization;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Science Conference, 2001. ACSC 2001. Proceedings. 24th Australasian

Conference_Location

Gold Coast, Qld.

ISSN

1530-0900

Print_ISBN

0-7695-0963-0

Type

conf

DOI

10.1109/ACSC.2001.906640

Filename

906640