Visibility-ordering meshed polyhedra

ABSTRACT

A visibility-ordering of a set of objects from some viewpoint is an ordering such that if object a obstructs object b, then b precedes a in the ordering. An algorithm is presented that generates a visibility-ordering of an acyclic convex set of meshed convex polyhedra. This algorithm takes time linear in the size of the mesh. Modifications to this algorithm and/or preprocessing techniques are described that permit nonconvex cells nonconvex meshes (meshes with cavities and/or voids), meshes with cycles, and sets of disconnected meshes to be ordered. Visibility-ordering of polyhedra is applicable to scientific visualization, particularly direct volume rendering. It is shown how the ordering algorithms can be used for domain decomposition of finite element meshes for parallel processing, and how the data structures used by these algorithms can be used to solve the spatial point location problem. The effects of cyclically obstructing polyhedra are discussed and methods for their elimination are described, including the use of the Delaunay triangulation. Methods for converting nonconvex meshes into convex meshes are described.

REFERENCES

• 1: BAKER, T J. Three dimensional mesh generation by triangulation of arbitrary point sets. Am. Inst. Aero. Astro. Rep. AIAA-87-1124, 1987.
• 2: B^kF.R, T J. Shape reconstruction and volume meshing for complex solids. Int. J. Numer. Methods Eng. 32, 4 (1991), 665 675.
• 3: Loren Carpenter, The A -buffer, an antialiased hidden surface method, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.103-108, July 1984
• 4: Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
• 5: Bernard Chazelle, How to search history, Information and Control, v.64 n.1-3, p.77-99, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80045-0]
• 6: B. Chazelle , L. Palios, Triangulating a non-convex polytype, Proceedings of the fifth annual symposium on Computational geometry, p.393-400, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73876]
• 7: Robert A. Drebin , Loren Carpenter , Pat Hanrahan, Volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.65-74, Aug. 1988
• 8: A. M. Day, The implementation of an algorithm to find the convex hull of a set of three-dimensional points, ACM Transactions on Graphics (TOG), v.9 n.1, p.105-132, Jan. 1990 [doi>10.1145/77635.77640]
• 9: DEt,At~x^',', B. Sur la sphere vide. lzv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennvka Nauk 7 (1934), 793-800.
• 10: H. Edelsbrunner , N. R. Shah, Incremental topological flipping works for regular triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.43-52, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142688]
• 11: Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
• 12: H. Edelsbrunner , F. P. Preparata , D. B. West, Tetrahedrizing point sets in three dimensions, Journal of Symbolic Computation, v.10 n.3-4, p.335-347, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80068-5]
• 13: EI)~:l.snUt!NN~;~4, H. An acyclicity theorem for cell complexes in d dimensions. Combinatorica I0, 3 (1990), 251-260.
• 14: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 15: Fmv'~)Eit, G., G~}Rt)t)N, D., ^xD RFYN{mnS, R.A. Back-to-front display of voxel-based objects. IEEE Comput. Graph. Appl. 5, 1 (Jan. 1985), 52-60.
• 16: 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
• 17: Chris Goad, Special purpose automatic programming for hidden surface elimination, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.167-178, July 1982
• 18: Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103472]
• 19: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 20: R. B. Haber , B. Lucas , N. Collins, A data model for scientific visualization with provisions for regular and irregular grids, Proceedings of the 2nd conference on Visualization '91, October 22-25, 1991, San Diego, California
• 21: Barry Joe, Construction of three-dimensional Delaunay triangulations using local transformations, Computer Aided Geometric Design, v.8 n.2, p.123-142, May 1991 [doi>10.1016/0167-8396(91)90038-D]
• 22: K~:NNO.~, S. R. A vectorized Delaunay triangulation scheme for nonconvex domains with automatic nodal point generation. Am. Inst. Aero. Astro. Rep. AIAA-88-0314 (1988).
• 23: KOYAMADA, K. Volume visualization for the unstructured grid data. In SPIE/SPSE Extracting Meaning from Complex Data Conference Proceedings, Vol. 1259 (1990), 14-25.
• 24: Michael J. Laszlo, Techniques for visualizing 3-dimensional manifolds, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
• 25: David Laur , Pat Hanrahan, Hierarchical splatting: a progressive refinement algorithm for volume rendering, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.285-288, July 1991
• 26: LEE, C. Regular triangulations of convex polytopes. In Applied Geometry and Discrete Mathematics: The Victor Klee Festschrifi. P. Gritzmann and B. Sturmfels, Eds., American Mathematical Society, Providence, R.I., 1991.
• 27: Nelson Max , Pat Hanrahan , Roger Crawfis, Area and volume coherence for efficient visualization of 3D scalar functions, Proceedings of the 1990 workshop on Volume visualization, p.27-33, December 10-11, 1990, San Diego, California, United States
• 28: MES~IKAT, S., RUPPERT, J., AND LI, H. Three-dimensional unstructured grid generation based on Delaunay tetrahedrization. In Proceedings Third International Conference Numerical Grid Generation (June 1991), 841-851.
• 29: M/JCKE, E.P. Ph.D. thesis, in preparation. Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign, 1991.
• 30: NACKMAN, L. R., AND SRINIVASAN, V. Point placement for Delaunay triangulation of polygonal domains. In Proceedings Third Canadian Conference Computational Geometry (Aug. 1991), 37-40.
• 31: M. S. Paterson , F. F. Yao, Binary partitions with applications to hidden surface removal and solid modelling, Proceedings of the fifth annual symposium on Computational geometry, p.23-32, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73836]
• 32: PERgON~ET, A. Some present fully automatic mesh generators. In Proceedings Int. Symposium on Numerical Methods in Engineering (1989), 129-136.
• 33: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 34: Franco P. Preparata , Roberto Tamassia, Efficient point location in a convex spatial cell-complex, SIAM Journal on Computing, v.21 n.2, p.267-280, April 1992 [doi>10.1137/0221020]
• 35: Harald Rosenberger, Degeneracy control in geometric programs, University of Illinois at Urbana-Champaign, Champaign, IL, 1990
• 36: SCHSNHARDT, E. Uber die Zerlegung von Dreieckspolyedern in Tetraeder. Math. Ann. 98 (1928), 309-312.
• 37: Peter Shirley , Allan Tuchman, A polygonal approximation to direct scalar volume rendering, Proceedings of the 1990 workshop on Volume visualization, p.63-70, December 10-11, 1990, San Diego, California, United States
• 38: Craig Upson , Michael Keeler, V-buffer: visible volume rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.59-64, Aug. 1988
• 39: Lee Westover, Footprint evaluation for volume rendering, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.367-376, Aug. 1990
• 40: Jane Wilhelms , Allen Van Gelder, A coherent projection approach for direct volume rendering, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.275-284, July 1991
• 41: WILLIaMs, P.L. Issues in interactive direct projection volume rendering of nonrectilinear meshed data sets. Work in Progress Rep., San Diego Workshop on Volume Visualization Dec. 1990; available as Rep. 1059, Center for Supercomputing Research and Development, Univ. of Illinois at Urbana-Champaign, Dec. 1990.
• 42: WILLIAMS, P. L. Applications of computational geometry to volume visualization. In Proceedings 3rd Canadian Conference Computational Geometry (Aug. 1991), 247-251.
• 43: Peter Lawrence Williams, Interactive direct volume rendering of curvilinear and unstructured data, University of Illinois at Urbana-Champaign, Champaign, IL, 1992

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Viewing algorithms; Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design, Theory

Keywords:
Delaunay triangulation, depth ordering, finite element methods, mesh generation, point location, scattered data, scientific visualization, triangulation, visibility ordering, volume rendering, volume visualization