Computing Visibility Subsets in an Orthogonal Polyhedron

Authors: Jefri Marzal, Hong Xie, Chun Che Fung

Abstract:

Visibility problems are central to many computational geometry applications. One of the typical visibility problems is computing the view from a given point. In this paper, a linear time procedure is proposed to compute the visibility subsets from a corner of a rectangular prism in an orthogonal polyhedron. The proposed algorithm could be useful to solve classic 3D problems.

Keywords: Visibility, rectangular prism, orthogonal polyhedron.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1338602

References:

[1] F. d. Durand, et al., "The 3D Visibility Complex," ACM Transactions on Graphics, vol. 21, pp. 176 - 206, 2002.
[2] M. N. Bygi and M. Ghodsi, "3D Visibility Graph," presented at the Computational Science and its Applications, Kuala Lampur, 2007.
[3] M. Pocchiola and G. Vegter, "Topologically sweeping visibility complexes via pseudotriangulations," Discrete & Computational Geometry, vol. 16, pp. 419–453, 1996.
[4] S. K. Ghosh and D. Mount, "An output sensitive algorithm for computing visibility graphs," SIAM Journal Computing, vol. 20, pp. 888-910, 1991.
[5] H. S. M. Coxeter, Regular polytopes. New York: Dover Publications, 1973.
[6] J. R. Rossignac and A. A. G. Requicha, "Construcitve Non-Regularized Geometry," Computer - Aided Design, vol. 23, pp. 21-32, 1991.
[7] T. Biedl and B. Genc, "Reconstructing orthogonal polyhedra from putative vertex sets," technical reports, 2007.
[8] K. Tang and T. C. Woo, "Algorithmic aspects of alternating sum of volumes. Part 1: Data structure and difference operation," Computer-Aided Design, vol. 23, pp. 357-366, June 1991.
[9] A. P. Tomas, et al., "On visibility problems in the plane - solving minimum vertex guard problems by successive approximation," in the 9th Int. Symp. on Artif. Intel. and Math., 2006.
[10] A. Aquilera and D. Ayala, "Solving point and plane vs orthogonal polyhedra using the extreme vertices model (EVM)," presented at the The Sixth International Conference in Central Europe on Computer Graphics and Visualization'98, 1998.
[11] R. Juan-Arinyo, "Domain extension of isothetic polyhedra with minimal CSG representation," Computer Graphics Forum, vol. 5, pp. 281-293, 1995.
[12] J. Marzal, et al., "Vertex Configurations and Their Relationship on Orthogonal Pseudo Polyhedra " World Academy of Science, Engineering and Technology pp. 1-8, 2011.