Computation of the axial view of a set of isothetic parallelepipeds

ABSTRACT

We present a new technique to display a scene of three-dimensional isothetic parallelepipeds (3D-rectangles), viewed from infinity along one of the coordinate axes (axial view). In this situation, there always exists a topological sorting of the 3D-rectangles based on the relation of occlusion (a dominance relation). The arising total order is used to generate the axial view, where the two-dimensional view of each 3D-rectangle is incrementally added, starting from the closest 3D-rectangle. The proposed scene-sensitive algorithm runs in time O(N log2N + d log N), where N is the number of 3D-rectangles and d is the number of edges of the display. This improves over the previously best known technique based on the same approach.

REFERENCES

• 1: M. Bern, Hidden surface removal for rectangles, Proceedings of the fourth annual symposium on Computational geometry, p.183-192, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73412]
• 2: F Devai, Quadratic bounds for hidden line elimination, Proceedings of the second annual symposium on Computational geometry, p.269-275, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10544]
• 3: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 4: EDELSBRUNNER, S., OVERMARS, M. H., AND WOOD, D. Graphics in flatland. In Advances in Computing Research. Vol. 1: Computational Geometry, F. P. Preparata, Ed., JAI Press, Greenwich, Conn., 1983, 35-39.
• 5: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.124-133, July 1980
• 6: O. Fries , K. Mehlhorn , St. Näher, Dynamization of geometric data structures, Proceedings of the first annual symposium on Computational geometry, p.168-176, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323256]
• 7: Ralf Hartmut Güting , Thomas Ottmann, New algorithms for special cases of the hidden line elimination problem, Computer Vision, Graphics, and Image Processing, v.40 n.2, p.188-204, November 1, 1987 [doi>10.1016/S0734-189X(87)80114-7]
• 8: GOODRICH, M.T. A polygonal approach to hidden-line elimination. In Proceedings of the 25th Allerton Conference on Communication, Control, and Computing (Allerton, Ill., Oct. 1987). University of Illinois Press, 1987.
• 9: GUIBAS, L. J., AND YAO, F. F. Translating a set of rectangles. In Advances in Computing Research, Vol. 1: Computational Geometry, F. P. Preparata, Ed., JAI Press, Greenwich, Conn., 1983, 61-77.
• 10: Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987 [doi>10.1145/27625.27627]
• 11: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 12: Otto Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT, v.25 n.3, p.466-472, 1985 [doi>10.1007/BF01935366]
• 13: Mark H. Overmars, Range searching in a set of line segments, Proceedings of the first annual symposium on Computational geometry, p.177-185, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323257]
• 14: Thomas Ottmann , Peter Widmayer, Solving Visibility Problems by Using Skeleton Structures, Proceedings of the Mathematical Foundations of Computer Science 1984, p.459-470, September 03-07, 1984
• 15: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 16: J. H. Reif , S. Sen, An efficient output-sensitive hidden surface removal algorithm and its parallelization, Proceedings of the fourth annual symposium on Computational geometry, p.193-200, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73413]
• 17: SCHUMACKER, R. A., BRAND, B., GIGILLAND, M., AND SHARP, M. Study for applying computergenerated images to visual simulation. Tech. Rep. TR AFHL-TR-69-14, USAF Human Resources Lab., 1969.
• 18: SCHMITT, A. Time and space bounds for hidden line and hidden surface computation. In Proceedings of Eurographics '81. North-Holland, Amsterdam, 1981, 43-56.
• 19: S. Sechrest , D. P. Greenberg, A Visible Polygon Reconstruction Algorithm, ACM Transactions on Graphics (TOG), v.1 n.1, p.25-42, Jan. 1982 [doi>10.1145/357290.357294]
• 20: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• 21: VAN EMDE BOAS, P., KAAS, a., AND ZILJSTRA, E. Design and implementation of an efficient priority queue. Math. Syst. Theor. 10 (1977), 99-127.
• 22: YAO, F.F. On the priority approach to hidden surface algorithm. In Proceedings of the 21st IEEE Symposium on Foundations of Computer Science (Syracuse, N.Y., 1980). IEEE, New York, 1980, 301-307.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

General Terms:
Algorithms, Design