A space-optimal hidden surface removal algorithm for iso-oriented rectangles

DOI10.1142/S0129054120500240zbMATH Open1458.68268arXiv1109.0389OpenAlexW3080282701MaRDI QIDQ5859632FDOQ5859632

Athanasios K. Tsakalidis, A. Kosmatopoulos, Kostas Tsichlas

Publication date: 19 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: We investigate the problem of finding the visible pieces of a scene of objects from a specified viewpoint. In particular, we are interested in the design of an efficient hidden surface removal algorithm for a scene comprised of iso-oriented rectangles. We propose an algorithm where given a set of $n$ iso-oriented rectangles we report all visible surfaces in $O((n+k)logn)$ time and linear space, where $k$ is the number of surfaces reported. The previous best result by Bern, has the same time complexity but uses $O(nlogn)$ space.

Full work available at URL: https://arxiv.org/abs/1109.0389

Recommendations

• Hidden surface removal for rectangles
• Hidden line elimination for isooriented rectangles
• An optimal algorithm for reporting visible rectangles
• Space-optimal hidden line elimination for rectangles
• Generalized hidden surface removal

zbMATH Keywords

computational geometrycomputer graphicsiso-oriented rectangleshidden surface removal

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• New algorithms for special cases of the hidden line elimination problem
• Space-optimal hidden line elimination for rectangles
• Hidden line elimination for isooriented rectangles
• Hidden surface removal for rectangles

Cited In (7)

• Hidden line elimination for isooriented rectangles
• Hidden surface removal for rectangles
• Estimating the efficiency of a uniform-grid two-dimensional hashing algorithm for hidden line and surface removal in computer graphics
• Output-sensitive methods for rectilinear hidden surface removal
• Title not available (Why is that?)
• Space-optimal hidden line elimination for rectangles
• An optimal algorithm for reporting visible rectangles

This page was built for publication: A space-optimal hidden surface removal algorithm for iso-oriented rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859632)