A real-time systolic algorithm for on-the-fly hidden surface removal

Hidden surface removal for real-time realistic display of complex scenes requires intensive computation and justifies usage of parallelism to provide the needed response time. The authors present a systolic algorithm that identifies visible segments on a scanline with the "real-time" characteristic: visible segments are output on-the-fly as soon as segments are input to the systolic array. The proposed systolic architecture consists of a linear array of simple cells. The size of the systolic array is equal to the maximum number of input segments that are crossed by a vertical line. The correctness of the systolic algorithm is proven by first establishing the correctness of an initial version, which is then successfully transformed to more efficient versions, while preserving the properties for correctness