Computing moments of objects enclosed by piecewise polynomial surfaces

ABSTRACT

Combining a polynomial free-form surface representation with Gauss' divergence theorem allows efficient and exact calculation of the moments of the enclosed objects. For example, for an cubic representation, volume, center of mass, and the inertia tensor can be computed in seconds even for complex objects with serval thousand patches while change due to local modification of the surface geometry can be computed in real-time as feedback for animation or design. Speed and simplicity of the approach allow solving the inverse problem of modeling to match prescribed moments.

REFERENCES

• 1: CATMULL, E. AND CLARK, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Comput. Aided Des. 10, 350-355.
• 2: C. Cattani , A. Paoluzzi, Boundary integration over linear polyhedra, Computer-Aided Design, v.22 n.2, p.130-135, Mar. 1990 [doi>10.1016/0010-4485(90)90007-Y]
• 3: DE BOOR, C. 1987. B-form basics. In Geometric Modeling: Algorithms and New Trends, G. Farin, Ed., SIAM, Philadelphia, 131-148.
• 4: DEROSE, T. D. AND LOOP, C.T. 1988. S-patches: A class of representations for multi-sided surface patches. Tech. Rep., University of Washington, Department of Computer Science, Seattle.
• 5: DOO, D. AND SABIN, M. 1978. Behaviour of recursive subdivision surfaces near extraordinary points. Comput. Aided Des. 10, 6 (Nov.), 356-360.
• 6: Matthias Eck , Hugues Hoppe, Automatic reconstruction of B-spline surfaces of arbitrary topological type, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.325-334, August 1996 [doi>10.1145/237170.237271]
• 7: Gerald Farin, Curves and surfaces for computer aided geometric design (3rd ed.): a practical guide, Academic Press Professional, Inc., San Diego, CA, 1993
• 8: Philip Fong , Hans-Peter Seidel, An implementation of triangular B-spline surfaces over arbitrary triangulations, Computer Aided Geometric Design, v.10 n.3-4, p.267-275, Aug. 1993
• 9: Cindy M. Grimm , John F. Hughes, Modeling surfaces of arbitrary topology using manifolds, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.359-368, September 1995 [doi>10.1145/218380.218475]
• 10: Leif Kobbelt, Robust and efficient evaluation of functionals on parametric surfaces, Proceedings of the thirteenth annual symposium on Computational geometry, p.376-378, June 04-06, 1997, Nice, France [doi>10.1145/262839.263009]
• 11: 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]
• 12: LEIN, S. AND KAJIYA, J. 1984. A symbolic method for calculating the integral properties of arbitrary nonconvex polyhedra. IEEE Comput. Graph. Appl. 4, 9 (Oct.), 35-41.
• 13: 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]
• 14: MILES, R. G. AND TOUGH, J.G. 1983. A method for computation of inertia properties for general areas. Comput. Aided Des. 15, 196-200.
• 15: Jörg Peters, C1-surface splines, SIAM Journal on Numerical Analysis, v.32 n.2, p.645-666, April 1995 [doi>10.1137/0732029]
• 16: Jörg Peters, Algorithm 783: Pcp2Nurb—smooth free-form surfacing with linearly trimmed bicubic B-splines, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.261-267, Sept. 1998 [doi>10.1145/292395.292399]
• 17: PETERS, J. AND NASRI, A. 1997. Computing volumes of solids enclosed by recursive subdivision surfaces. Comput. Graph. Forum 16, 3 (Sept.), C-89-C-94.
• 18: Hartmut Prautzsch, Freeform splines, Computer Aided Geometric Design, v.14 n.3, p.201-206, April 1997 [doi>10.1016/S0167-8396(96)00029-5]
• 19: Richard J. Prokop , Anthony P. Reeves, A survey of moment-based techniques for unoccluded object representation and recognition, CVGIP: Graphical Models and Image Processing, v.54 n.5, p.438-460, Sept. 1992 [doi>10.1016/1049-9652(92)90027-U]
• 20: REIF, U. 1998. Turbs--topologically unrestricted B-splines. Constr. Approx. (to appear).
• 21: Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill, Inc., New York, NY, 1987
• 22: SHIRMAN, L. AND SEQUIN, C. 1987. Local surface interpolation with B~zier patches. J. CAGD 6, 2, 167-172.
• 23: TIMMER, H. AND STERN, J. 1980. Computation of global geometric properties of solid objects. Comput. Aided Des. 12, 6, 301-304.
• 24: Luren Yang , Fritz Albregtsen , Torfinn Taxt, Fast computation of three-dimensional geometric moments using a discrete divergence theorem and a generalization to higher dimensions, Graphical Models and Image Processing, v.59 n.2, p.97-108, March 1997 [doi>10.1006/gmip.1997.0418]
• 25: Denis Zorin , Peter Schröder , Wim Sweldens, Interpolating Subdivision for meshes with arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.189-192, August 1996 [doi>10.1145/237170.237254]

INDEX TERMS

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

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

General Terms:
Algorithms, Design

Keywords:
CAD/CAM, animation techniques, geometic modeling, interactive techniques, splines and surfaces, university education, virtual/interactive environments