×

An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains. (English) Zbl 0817.68084

Summary: We present an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly. For example, our results apply directly to terrain maps. A distinguishing feature of our algorithm is that its running time is sensitive to the actual size of the visible image, rather than the total number of intersections in the image plane which can be much larger than the visible image. The time complexity of this algorithm is \(O((k+n) \log^ 2n)\) where \(n\) and \(k\) are, respectively, the input and the output sizes. Thus, in a significant number of situations this will be faster than the worst case optimal algorithms which have running time of \(\Omega (n^ 2)\) irrespective of the output size.

MSC:

68W10 Parallel algorithms in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Sproull, R. F.; Sutherland, I. E.; Schumacker, R. A., A characterization of ten hidden-surface algorithms, Computing Surveys, 6, 1, 1-25 (1974) · Zbl 0287.68024
[2] McKenna, M., Worst-case optimal hidden-surface removal, ACM Transactions on Graphics, 19-28 (1987)
[3] Devai, F., Quadratic bounds for hidden line elimination, (Proc. \(2^{nd}\) Annual Symp. on Computational Geometry (1986)), 269-275
[4] Nurmi, O., A fast line-sweep algorithm for hidden line elimination, BIT, 25, 466-472 (1985)
[5] Schmitt, A., Time and space bounds for hidden line and hidden surface elimination algorithms, EURO-GRAPHICS, 43-56 (1981)
[6] Goodrich, M. T., A polygonal approach to hidden-line elimination, GVGIP: Graphical Models and Image Processing, 54, 1, 1-12 (1992)
[7] Bern, M., Hidden surface removal for rectangles, (Proceedings \(4^{th}\) ACM Symp. on Computational Geometry (1988)), 183-192
[8] Wright, T. J., A two-space solution to the hidden line problem for plotting functions of two variables, IEEE Trans. on Comput., c-32, 1, 28-33 (1972)
[9] Reif, J.; Sen, S., An efficient output-sensitive hidden-surface algorithm and its parallelization, (Proc. of the \(4^{th}\) ACM Symp. on Computational Geometry (1988)), 193-200
[10] Overmars, M.; Katz, M.; Sharir, M., Efficient hidden surface removal for objects with small union size, Computational Geometry: Theory and Applications, 2, 223-234 (1992) · Zbl 0774.68099
[11] Preparata, F.; Vitter, J., A simplified technique for hidden-line elimination in terrains, (Proc. of STAGS (1992)) · Zbl 0776.68113
[12] de Berg, M.; Halpern, D.; Overmars, M.; Snoeyink, J.; Krevald, M., Efficient ray-shooting and hidden surface removal, (Proc. \(7^{th}\) ACM Symp. on Computational Geometry (1991)), 21-30 · Zbl 0813.68160
[13] Overmars, M.; Sharir, M., Output-sensitive hidden surface removal, (Proc. \(30^{th}\) IEEE Symp. on Foundations of Computer Science (1989)), 598-603 · Zbl 0804.68146
[14] Guting, R. H.; Ottmann, T., New algorithms for special cases of the hidden-line elimination problem, Report 184 (1984)
[15] Chazelle, B.; Guibas, L., Visibility and intersection problems in plane geometry, (Proc. ACM Symp. on Computational Geometry (1985)), 135-146
[16] Lee, D. T.; Preparata, F. P., Location of a point in a planar subdivision and its applications, SIAM Journal of Comput., 6, 3, 594-606 (1977) · Zbl 0357.68034
[17] Cole, R.; Sharir, M., Visibility problems for polyhedral terrains, (Tech. Rept. No. 92 (1986), Courant Institute of Math. Sc)
[18] Chazelle, B., A theorem on polygon cutting with applications, (Proc. of IEEE FOCS (1982)), 339-349
[19] Mehlhorn, K., Data Structures and Algorithms, (Multidimensional Searching and Computational Geometry, Vol. 3 (1984)) · Zbl 0408.68055
[20] Overmars, M.; Leeuwen, J., Maintainence of configurations in space, Journal of Computer and System Sciences, 166-204 (1981)
[21] J. Reif and S. Sen, An efficient output-sensitive parallel algorithm for hidden-surface removal, (unpublished manuscript).; J. Reif and S. Sen, An efficient output-sensitive parallel algorithm for hidden-surface removal, (unpublished manuscript). · Zbl 0817.68084
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.