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

DOI10.1142/S0129054120500240MaRDI QIDQ5859632zbMATH OpenOpenAlexFDO

Authors A. Kosmatopoulos, Kostas Tsichlas, Athanasios K. Tsakalidis

Publication date 19 April 2021

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

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

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)

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.

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

Cites work

• Hidden line elimination for isooriented rectangles
• Hidden surface removal for rectangles
• New algorithms for special cases of the hidden line elimination problem
• Space-optimal hidden line elimination 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
• scientific article; zbMATH DE number 177849 (Why is no real title available?)
• 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)