Algorithms for computing the volume and other integral properties of solids. I. known methods and open issues

ABSTRACT

The volume, moments of inertia, and similar properties of solids are defined by triple (volumetric) integrals over subsets of three-dimensional Euclidean space. The automatic computation of such integral properties for geometrically complex solids is important in CAD/CAM, robotics, and other fields and raises interesting mathematical and computational problems that have received little attention from numerical analysts and computer scientists. This paper summarizes the known methods for calculating integral properties of solids that may be geometrically complex and identifies some significant gaps in our current knowledge.

REFERENCES

• 1: Apostol, T. M. Calculus. Blaisdell Pub. Co., Waltham, MA, Vol. 2, 1962.
• 2: Braid, I. C. Designing with volumes: computation of weight, centre of gravity, moments of inertia and principal axes. C.A.D. Group Doc. 81, Univ. of Cambridge, U.K., 1973.
• 3: Cohen, E., Lyche, T., and Riesenfeld, R. Discrete B-splines and subdivision techniques in computer aided geometric design and computer graphics. Computer Graphics and Image Processing 14, 2 (Oct. 1980), 87-111.
• 4: 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]
• 5: Cook, P. N., Cook, L. T., Batnitzky, S., Lee, K. R., Anderson, W. H., and Dwyer III, S. J. Volume and surface area estimates using tomographic data. IEEE Trans. on Pattern Analysis and Machine Intelligence PAMI-2, 5 (Sept. 1980), 478-479.
• 6: Davis, P. J., and Rabinowitz, P. Methods of Numerical Integration. Academic, New York, 1975.
• 7: 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.
• 8: Haber, S. Numerical evaluation of multiple integrals. SIAM Review 12, 4 (Oct. 1970), 481-526.
• 9: Hammersley, J. M., and Handscomb, D. C. Monte Carlo Methods. Methuen & Co., London, 1965.
• 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: Lane, J. M., and Carpenter, L. A generalized scan line algorithm for the computer display of parametrically defined surfaces. Computer Graphics and Image Processing 11, (1979), 290-297.
• 12: Lane, J. M., and Riesenfeld, F. R. A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Trans. on Pattern Analysis and Machine Intelligence, PAMI-2, 1 (Jan. 1980), 35-46.
• 13: Yong Tsui Lee , Aristides A. G. Requicha, Algorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation, Communications of the ACM, v.25 n.9, p.642-650, Sept 1982 [doi>10.1145/358628.358648]
• 14: Messner, A. M. A surface integral method for computer calculation of mass properties. Paper 852, 29th Ann. Conf. of the Society of Aeronautical Weight Engineers, Washington, D.C., 1970.
• 15: Messner, A. M., Taylor, G. Q., and Price, C. F. Interdisciplinary computer analyses of three dimensional solids defined by polyhedral surfaces. J. Spacecraft and Rockets 11, l (Jan. 1974), 52-54.
• 16: A. M. Messner , G. Q. Taylor, Algorithm 550: Solid Polyhedron Measures [Z], ACM Transactions on Mathematical Software (TOMS), v.6 n.1, p.121-130, March 1980 [doi>10.1145/355873.355885]
• 17: O'Leary, J. R. Evaluation of mass properties by finite elements. Journal of Guidance and Control 3, 2 (March-April 1980), 188-190.
• 18: 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]
• 19: Shreider, Yu. A. The Monte Carlo Method. Pergamon Press Ltd., Oxford, 1966.
• 20: Stroud, A, H. Approximate Calculation of Multiple Integrals. Prentice Hall, Englewood Cliffs, N.J., 1971.
• 21: Tilove, R. B. Line/polygon classification: A study of the complexity of geometric computation. IEEE Computer Graphics and Applications 1, 2 (April 1981), 75-86.
• 22: Timmer, H. G., and Stern, J. M. Computation of global geometric properties of solid objects. Computer Aided Design 12, 6 (1980), 301-304.
• 23: Voelcker, H. B., and Requicha, A. A. G. Geometric modelling of mechanical parts and processes. 1EEE Computer 10, 12 (Dec. 1977), 48-57.
• 24: Michael A. Wesley, Construction and Use of Geometric Models, Computer Aided Design: Modelling, Systems Engineering, CAD-Systems - CREST Advanced Course, p.79-136, September 08-19, 1980
• 25: Wilson, H. B., and Farrior, D. S. Computation of geometrical and inertial properties for general areas and volumes of revolution. Computer Aided Design 8, 4 (1976), 257-263.

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: Boundary representations; Geometric algorithms, languages, and systems

General Terms:
Algorithms

Keywords:
CAD/CAM, Monte Carlo methods, geometric modeling, mass properties, moments of inertia, numerical integration, programmable automation