Algorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation

ABSTRACT

This paper discusses a family of algorithms for computing the volume, moments of inertia, and other integral properties of geometrically complex solids, e.g. typical mechanical parts. The algorithms produce approximate decompositions of solids into cuboid cells whose integral properties are easy to compute. The paper focuses on versions of the algorithms which operate on solids represented by Constructive Solid Geometry (CSG), i.e., as set-theoretical combinations of primitive solid “building blocks.” Two known algorithms are summarized and a new algorithm is presented. The efficiencies and accuracies of the three algorithms are analyzed theoretically and compared experimentally. The new algorithm uses recursive subdivision to convert CSG representations of complex solids into approximate cellular decompositions based on variably sized blocks. Experimental data show that the new algorithm is efficient and has predictable accuracy. It also has other potential applications, e.g., in producing approximate octree representations of complex solids and in robot navigation.

REFERENCES

• 1: Ahuja, N., Chien, R.T., Yen, R., and Bridwell, N. Interference detection and collision avoidance among three dimensional objects. Proc. 1st Ann. Nat. Conf. on Artificial Intelligence, Palo Alto, Calif., 1980, pp. 44-48.
• 2: Boyse, J.W. Preliminary design for a geometric modeller. Res. Pub. GMR-2768, Computer Sci. Dept., General Motors Res. Labs., Warren, Mich., 1978.
• 3: Boyse, J.W., and Gilchrist, J.E. GMSolid: Interactive modeling for design and analysis of solids. IEEE Computer Graphics and Applications 2, 2 (March 1982) 27-40
• 4: Brown, C.M. PADL-2: A technical summary. IEEE Computer Graphics and Applications 2, 2 (March 1982) 69-84.
• 5: Jacques Cohen , Timothy Hickey, Two Algorithms for Determining Volumes of Convex Polyhedra, Journal of the ACM (JACM), v.26 n.3, p.401-414, july 1979 [doi>10.1145/322139.322141]
• 6: Dubois, P.F. Volume calculation and geometry checking in a Monte Carlo transport code. Report UCID-17522, Computation Dept., Lawrence Livermore Lab., Livermore, Calif., 1977.
• 7: Goldstein, R.A., and Nagel, R. 3-D visual simulation. Simulation 16, 1 (1971), 25-31.
• 8: Goldstein, R.A., and Malin, L. 3D modelling with the Synthavision system. Proc. 1st Ann. Conf. on Computer Graphics in CAD/CAM Systems, Cambridge, Mass., 1979, pp. 244-247.
• 9: Peter Henrici, Applied and computational complex analysis. Vol. 3: discrete Fourier analysis—Cauchy integrals—construction of conformal maps---univalent functions, John Wiley & Sons, Inc., New York, NY, 1986
• 10: Jackins, C.L., and Tanimoto, S.L. Oct-trees and their use in representing three-dimensional objects. Computer Graphics and Image Processing 14, 3 (Nov. 1980), 249-270.
• 11: Yong Tsui Lee , Aristides A. G. Requicha, Algorithms for computing the volume and other integral properties of solids. I. known methods and open issues, Communications of the ACM, v.25 n.9, p.635-641, Sept 1982 [doi>10.1145/358628.358643]
• 12: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 13: Okino, N., et. al. TIPS-I. Institute of Precision Engineering, Hokkaido Univ., Sapporo, Japan, 1978.
• 14: Requicha, A.A.G., and Voelcker, H.B. Constructive solid geometry. Tech. Memo. No. 25, Production Automation Project, Univ. of Rochester, November 1977.
• 15: Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
• 16: Roth, S.D. Ray casting for modeling solids. Computer Graphics and Image Processing 18, 2 (Feb. 1982) 109-144.
• 17: Tilove, R.B. Set membership classification: a unified approach to geometric intersection problems. IEEE Trans. Computers C-29, 10 (Oct. 1980), 874-883.
• 18: Tilove, R.B. Line/polygon classification: The complexity of a geometric computation. IEEE Computer Graphics and Applications 1, 2 (April 1981), 75-88.
• 19: Tilove R.B., and Requicha, A.A.G. Closure of Boolean operations on geometric entities. Computer Aided Design 12, 5 (Sept. 1980), 219-220.
• 20: H. Voelcker , A. Requicha , E. Hartquist , W. Fisher , J. Metzger , R. Tilove , N. Birrell , W. Hunt , G. Armstrong , T. Check , R. Moote , J. McSweeney, The PADL-1.0/2 system for defining and displaying solid objects, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.257-263, August 1978
• 21: Warnock, J.E. A hidden line algorithm for halftone picture representation. Tech. Rept. 4-5, Computer Sci. Dept., Univ. of Utah, 1968.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Multidimensional (multiple) quadrature

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms

Keywords:
CAD/CAM, Monte Carlo methods, cellular decompositions, constructive solid geometry, constructive solid, geometric modeling, mass properties, moments of inertia, numerical integration, octrees, programmable automation, ray casting, recursive, representation conversion, set membership classification, subdivision