Modelling with implicit surfaces that interpolate

ABSTRACT

We introduce new techniques for modelling with interpolating implicit surfaces. This form of implicit surface was first used for problems of surface reconstruction and shape transformation, but the emphasis of our work is on model creation. These implicit surfaces are described by specifying locations in 3D through which the surface should pass, and also identifying locations that are interior or exterior to the surface. A 3D implicit function is created from these constraints using a variational scattered data interpolation approach, and the iso-surface of this function describes a surface. Like other implicit surface descriptions, these surfaces can be used for CSG and interference detection, may be interactively manipulated, are readily approximated by polygonal tilings, and are easy to ray trace. A key strength for model creation is that interpolating implicit surfaces allow the direct specification of both the location of points on the surface and the surface normals. These are two important manipulation techniques that are difficult to achieve using other implicit surface representations such as sums of spherical or ellipsoidal Gaussian functions ("blobbies"). We show that these properties make this form of implicit surface particularly attractive for interactive sculpting using the particle sampling technique introduced by Witkin and Heckbert. Our formulation also yields a simple method for converting a polygonal model to a smooth implicit model, as well as a new way to form blends between objects.

REFERENCES

• 1: Bittar, E., Tsingos, N., and Gascuel, M.-P. 1995. Automatic reconstruction of unstructured 3D data: Combining a medial axis and implicit surfaces. Computer Graphics Forum (Proceedings of Eurographics '95) 14, 3, 457--468.
• 2: James F. Blinn, A Generalization of Algebraic Surface Drawing, ACM Transactions on Graphics (TOG), v.1 n.3, p.235-256, July 1982 [doi>10.1145/357306.357310]
• 3: J. Bloomenthal, Polygonization of implicit surfaces, Computer Aided Geometric Design, v.5 n.4, p.341-355, Nov. 1988 [doi>10.1016/0167-8396(88)90013-1]
• 4: Jules Bloomenthal, An implicit surface polygonizer, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 5: Jules Bloomenthal , Brian Wyvill, Introduction to Implicit Surfaces, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 6: J. C. Carr , R. K. Beatson , J. B. Cherrie , T. J. Mitchell , W. R. Fright , B. C. McCallum , T. R. Evans, Reconstruction and representation of 3D objects with radial basis functions, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.67-76, August 2001 [doi>10.1145/383259.383266]
• 7: George Celniker , Dave Gossard, Deformable curve and surface finite-elements for free-form shape design, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.257-266, July 1991
• 8: Duchon, J. 1977. Spline minimizing rotation-invariant semi-norms in Sobolev spaces. In Constructive Theory of Functions on Several Variables, Lecture Notes in Mathematics 571, W. Schempp and K. Zeller, Eds. Springer-Verlag, Berlin.
• 9: Tom Duff, Interval arithmetic recursive subdivision for implicit functions and constructive solid geometry, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.131-138, July 1992
• 10: Dyn, N. 1987. Interpolation of scattered data by radial basis functions. In Topics in Multivariate Approximation, L. L. S. C. K. Chui and F. I. Utreras, Eds. Academic Press, Cambridge, 47--61.
• 11: Federico Girosi , Michael Jones , Tomaso Poggio, Priors Stabilizers and Basis Functions: From Regularization to Radial, Tensor and Additive Splines, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 12: Grimson, W. E. L. 1983. Surface consistancy constraints in vision. Computer Vision, Graphics, and Image Processing 24, 1 (Oct.), 28--51.
• 13: Hart, J. 1993. Ray tracing implicit surfaces. Siggraph 93 Course Notes: Design, Visualization and Animation of Implicit Surfaces, 1--16.
• 14: Hart, J. 1997. Sphere tracing: A geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer 12, 10, 527--545.
• 15: D. Kalra , A. H. Barr, Guaranteed ray intersections with implicit surfaces, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.297-306, July 1989
• 16: Keren, D. and Gotsman, C. 1998. Tight fitting of convex polyhedral shapes. Int. J. Shape Modeling, 111--126.
• 17: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 18: Shigeru Muraki, Volumetric shape description of range data using “Blobby Model”, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.227-235, July 1991
• 19: Bryan S. Morse , Terry S. Yoo , David T. Chen , Penny Rheingans , K. R. Subramanian, Interpolating Implicit Surfaces from Scattered Surface Data Using Compactly Supported Radial Basis Functions, Proceedings of the International Conference on Shape Modeling & Applications, p.89, May 07-11, 2001
• 20: Nishimura, H., Hirai, M., Kawai, T., Kawata, T., Shirkawa, I., and Omura, K. 1985. Object modeling by distribution function and a method of image generation. Trans. Inst. Elect. Commun. Eng. Japan J68-D, 4, 718--725.
• 21: Hans Køhling Pedersen, Decorating implicit surfaces, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.291-300, September 1995 [doi>10.1145/218380.218458]
• 22: Hans Køhling Pedersen, A framework for interactive texturing on curved surfaces, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.295-302, August 1996 [doi>10.1145/237170.237268]
• 23: Roth, S. 1982. Ray casting as a method for solid modeling. Computer Graphics and Image Processing 18, 2, 109--144.
• 24: Savchenko, V. V., Pasko, A. A., Okunev, O. G., and Kunni, T. L. 1995. Function representation of solids reconstructed from scattered surface points and contours. Computer Graphics Forum 14, 4 (Oct.), 181--188.
• 25: John M. Snyder, Interval analysis for computer graphics, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.121-130, July 1992
• 26: Barton T. Stander , John C. Hart, Guaranteeing the topology of an implicit surface polygonization for interactive modeling, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.279-286, August 1997 [doi>10.1145/258734.258868]
• 27: R. Szeliski, Fast Surface Interpolation Using Hierarchical Basis Functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.6, p.513-528, June 1990 [doi>10.1109/34.56188]
• 28: Taubin, G. 1993. An improved algorithm for algebraic curve and surface fitting. In Fourth International Conference on Computer Vision (ICCV '93). IEEE, Berlin, Germany, 658--665.
• 29: Demetri Terzopoulos, The Computation of Visible-Surface Representations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.4, p.417-438, July 1988 [doi>10.1109/34.3908]
• 30: Greg Turk , James F. O'Brien, Shape transformation using variational implicit functions, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.335-342, July 1999 [doi>10.1145/311535.311580]
• 31: William Welch , Andrew Witkin, Free-form shape design using triangulated surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.247-256, July 1994 [doi>10.1145/192161.192216]
• 32: Andrew P. Witkin , Paul S. Heckbert, Using particles to sample and control implicit surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.269-277, July 1994 [doi>10.1145/192161.192227]
• 33: Wyvill, G., McPheeters, C., and Wyvill, B. 1986. Data structures for soft objects. The Visual Computer 2, 4, 227--234.

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

General Terms:
Algorithms

Keywords:
Implicit surfaces, function interpolation, modeling, thin-plate techniques