A systolic algorithm for hidden surface removal

S. R. Das, N. H. Vaidya, L. M. Patnaik, P. C. Mathias

Research output: Contribution to journalArticle

Abstract

With the advent of VLSI it has become possible to map parallel algorithms for compute-bound problems directly on silicon. Systolic architecture is very good candidate for VLSI implementation because of its regular and simple design, and regular communication pattern. In this paper, a systolic algorithm and corresponding systolic architecture, a linear systolic array, for the scanline-based hidden surface removal problem in three-dimensional computer graphics have been proposed. The algorithm is based on the concept of sample spans or intervals. The worst case time taken by the algorithm is O(n), n being the number of segments in a scanline. The time taken by the algorithm for a given scene depends on the scene itself, and on an average considerable improvement over the worst case behaviour is expected. A pipeline scheme for handling the I/O process has also been proposed which is suitable for VLSI implementation of the algorithm.

Original languageEnglish (US)
Pages (from-to)277-289
Number of pages13
JournalParallel Computing
Volume15
Issue number1-3
DOIs
StatePublished - Sep 1990

    Fingerprint

Keywords

  • VLSI implementation
  • hidden surface removal problem
  • simulation results
  • systolic algorithm
  • systolic architecture

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Cite this

Das, S. R., Vaidya, N. H., Patnaik, L. M., & Mathias, P. C. (1990). A systolic algorithm for hidden surface removal. Parallel Computing, 15(1-3), 277-289. https://doi.org/10.1016/0167-8191(90)90050-J