A Fast Voxel Tracing Algorithm and Hardware Implementation

Peikai ZHENG; Shanjun ZHANG; Tsuyoshi YAMAMOTO; Yoshinao AOKI

A Fast Voxel Tracing Algorithm and Hardware Implementation

Peikai ZHENG, Shanjun ZHANG, Tsuyoshi YAMAMOTO, Yoshinao AOKI

Full Text Views

0

Cite this

Summary :

Voxel representation of solid object is a well known model that is widely used in CAD, robots, computer graphics, and medical image processing. Efficient algorithms for the tracing in voxel model are of great importance. A fast hardware oriented voxel tracing algorithm (called LCDDA) is proposed and implemented. All the voxels pierced by a given ray are generated incrementaly. To meve from a voxel to the next one only three fixed point additions and comparisons, which can be done using 3 parallel pipelines, and a ROM access are required. It takes 0.2 microseconds to do this under 5 MHz clock on a personal computer, which is 103 times faster than Fujimoto's and 1339 times than Glassner's algorithm on a workstation. As an application of this, time consuming ray tracing process is performed by this hardware implemented algorithm on a personal computer. Also, an active intersection table (AIT) is introduced to avoid multiple intersection of a ray and the same object. The high speed of these methods have been proved by experimental results.

Publication: IEICE TRANSACTIONS on Information Vol.E74-D No.9 pp.2951-2959

Publication Date: 1991/09/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Image Processing, Computer Graphics and Pattern Recognition

Authors

Peikai ZHENG
Shanjun ZHANG
Tsuyoshi YAMAMOTO
Yoshinao AOKI

Keyword

Cite this

Copy

Peikai ZHENG, Shanjun ZHANG, Tsuyoshi YAMAMOTO, Yoshinao AOKI, "A Fast Voxel Tracing Algorithm and Hardware Implementation" in IEICE TRANSACTIONS on Information, vol. E74-D, no. 9, pp. 2951-2959, September 1991, doi: .
Abstract: Voxel representation of solid object is a well known model that is widely used in CAD, robots, computer graphics, and medical image processing. Efficient algorithms for the tracing in voxel model are of great importance. A fast hardware oriented voxel tracing algorithm (called LCDDA) is proposed and implemented. All the voxels pierced by a given ray are generated incrementaly. To meve from a voxel to the next one only three fixed point additions and comparisons, which can be done using 3 parallel pipelines, and a ROM access are required. It takes 0.2 microseconds to do this under 5 MHz clock on a personal computer, which is 103 times faster than Fujimoto's and 1339 times than Glassner's algorithm on a workstation. As an application of this, time consuming ray tracing process is performed by this hardware implemented algorithm on a personal computer. Also, an active intersection table (AIT) is introduced to avoid multiple intersection of a ray and the same object. The high speed of these methods have been proved by experimental results.
URL: https://global.ieice.org/en_transactions/information/10.1587/e74-d_9_2951/_p

Copy

@ARTICLE{e74-d_9_2951,
author={Peikai ZHENG, Shanjun ZHANG, Tsuyoshi YAMAMOTO, Yoshinao AOKI, },
journal={IEICE TRANSACTIONS on Information},
title={A Fast Voxel Tracing Algorithm and Hardware Implementation},
year={1991},
volume={E74-D},
number={9},
pages={2951-2959},
abstract={Voxel representation of solid object is a well known model that is widely used in CAD, robots, computer graphics, and medical image processing. Efficient algorithms for the tracing in voxel model are of great importance. A fast hardware oriented voxel tracing algorithm (called LCDDA) is proposed and implemented. All the voxels pierced by a given ray are generated incrementaly. To meve from a voxel to the next one only three fixed point additions and comparisons, which can be done using 3 parallel pipelines, and a ROM access are required. It takes 0.2 microseconds to do this under 5 MHz clock on a personal computer, which is 103 times faster than Fujimoto's and 1339 times than Glassner's algorithm on a workstation. As an application of this, time consuming ray tracing process is performed by this hardware implemented algorithm on a personal computer. Also, an active intersection table (AIT) is introduced to avoid multiple intersection of a ray and the same object. The high speed of these methods have been proved by experimental results.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - A Fast Voxel Tracing Algorithm and Hardware Implementation
T2 - IEICE TRANSACTIONS on Information
SP - 2951
EP - 2959
AU - Peikai ZHENG
AU - Shanjun ZHANG
AU - Tsuyoshi YAMAMOTO
AU - Yoshinao AOKI
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E74-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 1991
AB - Voxel representation of solid object is a well known model that is widely used in CAD, robots, computer graphics, and medical image processing. Efficient algorithms for the tracing in voxel model are of great importance. A fast hardware oriented voxel tracing algorithm (called LCDDA) is proposed and implemented. All the voxels pierced by a given ray are generated incrementaly. To meve from a voxel to the next one only three fixed point additions and comparisons, which can be done using 3 parallel pipelines, and a ROM access are required. It takes 0.2 microseconds to do this under 5 MHz clock on a personal computer, which is 103 times faster than Fujimoto's and 1339 times than Glassner's algorithm on a workstation. As an application of this, time consuming ray tracing process is performed by this hardware implemented algorithm on a personal computer. Also, an active intersection table (AIT) is introduced to avoid multiple intersection of a ray and the same object. The high speed of these methods have been proved by experimental results.
ER -