Space-Efficient Hidden Surface Removal

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 Θ(logn) while maintaining the running time.


slides
keywords: Computational Geometry, Data Structures, Terrains

Workshop or Poster (weakly reviewed)

Frank Kammer, Maarten Löffler, Rodrigo I. Silveira
Space-Efficient Hidden Surface Removal
MASSIVE'16
, 2016

Archived Publication (not reviewed)

Frank Kammer, Maarten Löffler, Rodrigo I. Silveira
Space-Efficient Hidden Surface Removal
1611.06915, 2016
http://arXiv.org/abs/1611.06915

back to list