## 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 *Θ*(log*n*) while maintaining the running time.

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

back to list