Polygon properties calculated from the vertex neighborhoods

ABSTRACT

Calculating properties of polyhedra given only the set of the locations and neighborhoods of the vertices is easy. Possible properties include volume, surface area, and point containment testing. No global topological information at all is explicitly needed (although the complete global topology could be recovered). The neighborhood of the vertex means the directions of the edges and faces on it but not their extents. These vertex-based formulae are dual to the usual formulae that use the faces. They have been implemented and the stability against inconsistent data tested. Alternative data structures and formulae for polyhedron calculation are important since special cases are a function partly of the data structure, and because different methods have different numerical accuracy and error detection properties.

REFERENCES

• Blinn: James F. Blinn, A Method for removing some Degeneracies in Hiden line and Ray tracing caculations, Jet Propulsion Lab, undated.
• Courter80: John A. Brewer, III , S. Mark Courter, Automated conversion of curvilinear wire-frame models to surface boundary models; a topological approach, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.171-178, Aug. 1986
• Eastman72: C.M. Eastman and C.I. Yessios, An Eficient Algorithm /or Finding the Union, Intersection, aud Differences of Spatial Domains, Sept. 1972. Carnegie-Mellon University, Dept. of Computer Science
• Franlclin82: Wm. Randolph Franklin, "Effkient Polyhedron Intersection and Union," Proc. Graphics Znterface'82, pp. 73-80, Toronto, 19-21 May 1982.
• Franklin83: Wm. Randolph Franklin, "Rays - New Representation for Polygons antl Polyhedra," Co?,lplrtcl, Graphics and lmage Processing , vol. 22, pp. 327- 338,1983.
• Guibas83: 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]
• Mantyla82: M. Mantyla and R. Sulonen, "GWB: A Solid Modeler with the Euler Operators," IEEE Conapde? Graphics and Applications, vol. 2, no. 7, pp. 17-31, September 1982.
• Mantyla84: M. Mantyla, "A Note on the Modeling Space of Euler Operators," Computer Vision, Graphics, wtd Image Processing, vol. 2G, pp. 4560, 1984.
• Weiler8G: Kevin J. Weiler, Topological Structures I'OI Geometric Modeling, Center for Interactive Computer Graphics, Rensselaer Polytechnic Institute, August 1986. PhD Thesis.
• White77: Denis White, "A New Method of Polygon Overlay,"An Advanced Study Symposium on Topological Data Structures for Geographic Injormation Systems, Laboratory for Computer Graphics and Spatial Analysis, Harvard University, Cambridge, MA, USA, 02138, Oct. X-21, 1977.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory