Hidden surface removal for c-oriented polyhedra

DOI10.1016/0925-7721(92)90007-FMaRDI QIDQ1194308zbMATH OpenOpenAlexFDO

Authors Mark H. Overmars, Mark de Berg

Publication date 27 September 1992

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(92)90007-f

zbMATH Keywords

\(c\)-oriented polyhedrahidden surface removaloutput-sensitive algorithms

Mathematics Subject Classification ID

Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

An output-sensitive hidden surface removal algorithm that can deal with cyclic overlap among the objects is given. The method works for any set of polyhedra whose faces have a constant number of different orientations. Let \(n\) be the total number of edges of the polyhedra and \(k\) the complexity of the visibility map. The time complexity of \(O((n+k)\log n)\) improves earlier results on that line. The basic method also works for intersecting polyhedra and for polyhedra, where the number of different orientations of the edges is not bounded. Further results are given and open questions are discussed.

Recommendations

• Dynamic output-sensitive hidden surface removal for c-oriented polyhedra
• Repetitive hidden-surface-removal for polyhedral scenes
• A simple output-sensitive algorithm for hidden surface removal
• An improved technique for output-sensitive hidden surface removal
• An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains

Cites work

• A simple output-sensitive algorithm for hidden surface removal
• Adding range restriction capability to dynamic data structures
• An improved technique for output-sensitive hidden surface removal
• Computation of the axial view of a set of isothetic parallelepipeds
• Efficient ray shooting and hidden surface removal
• Fractional cascading. I: A data structuring technique
• Hidden surface removal for rectangles
• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 177563 (Why is no real title available?)
• scientific article; zbMATH DE number 177849 (Why is no real title available?)
• scientific article; zbMATH DE number 3451445 (Why is no real title available?)
• New algorithms for special cases of the hidden line elimination problem
• Output-sensitive generation of the perspective view of isothetic parallelepipeds
• Visibility of disjoint polygons

Cited in

(13)

• Hidden-surface removal in polyhedral cross-sections
• Visualization algorithm for CSG polyhedral solids
• Dynamic output-sensitive hidden surface removal for c-oriented polyhedra
• Efficient ray shooting and hidden surface removal
• On fat partitioning, fat covering and the union size of polygons
• An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains
• Generalized hidden surface removal
• Computing the visibility map of fat objects
• On circularly-hidden surface removal.
• THE OBJECT COMPLEXITY MODEL FOR HIDDEN-SURFACE REMOVAL
• Repetitive Hidden Surface Removal for Polyhedra
• Translating polygons with applications to hidden surface removal
• Repetitive hidden-surface-removal for polyhedral scenes

This page was built for publication: Hidden surface removal for \(c\)-oriented polyhedra

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