Space-Efficient Hidden Surface Removal

Abstract

We propose a space-efficient algorithm for hidden surface removal that combines one of the fastest previous algorithms for that problem with techniques based on bit manipulation. Such techniques had been successfully used in other settings, for example to reduce working space for several graph algorithms. However, bit manipulation is not usually employed in geometric algorithms because the standard model of computation (the real RAM) does not support it. For this reason, we first revisit our model of computation to have a reasonable theoretical framework. Under this framework we show how the use of a bit representation for the union of triangles, in combination with rank-select data structures, allows to implicitly compute the union of $n$ triangles with roughly $O(1)$ bits per union boundary vertex. This allows us to reduce the required working space by a factor $log n)$ while maintaining the running time.