Multiprocessing architectures for parallel hidden surface removal algorithms

Abstract

Interactive computer graphics systems have become powerful tools for man-machine interaction, with wide-ranging applications. One particularly exciting and important area is the synthetic generation of realistic images of modeled solid objects. A major challenge in this domain is the hidden surface removal (HSR) process, which is essential for rendering visually accurate 2D representations of 3D objects. However, traditional HSR algorithms are computationally intensive, especially for moderately complex scenes. To address this, the dissertation explores the use of parallel processing techniques to accelerate the HSR process. It presents parallel algorithms designed for execution on multiprocessing systems, leveraging parallel sorting techniques and exploiting coherence in the object data to improve efficiency. Three classical HSR algorithms are considered:

Depth Sort Algorithm Scan Line Algorithm Warnock’s Area Subdivision Algorithm

A key insight is that polygon scan conversion is a common underlying operation in all three algorithms. Accordingly, the dissertation proposes three parallel polygon scan conversion algorithms, and compares their performance based on:

Execution time Speedup factor Processing power utilization

Performance evaluation is conducted through simulation, theoretical analysis, and experimental studies. A simulator named SIMPAR (Simulator for Multiprocessing Architectures) was developed in Pascal to assess the algorithms. The simulation results were validated through experiments on SHAMP, a shared memory multiprocessing system built using five Intel 16-bit single-board computers. Findings indicate that multiprocessing systems significantly reduce the time required for HSR. While coherence improves efficiency in sequential algorithms, it may reduce parallelism in parallel algorithms, potentially leading to performance degradation. The tools and methodologies developed in this work can also be applied to other parallel algorithm domains, such as image processing and graph-theoretic applications.