### 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 language | English (US) |
---|---|

Pages (from-to) | 277-289 |

Number of pages | 13 |

Journal | Parallel Computing |

Volume | 15 |

Issue number | 1-3 |

DOIs | |

State | Published - 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

*Parallel Computing*,

*15*(1-3), 277-289. https://doi.org/10.1016/0167-8191(90)90050-J