2D piecewise algebraic splines for implicit modeling

ABSTRACT

2D splines are a powerful tool for shape modeling, either parametrically or implicitly. However, compared with regular grid-based tensor-product splines, most of the high-dimensional spline techniques based on nonregular 2D polygons, such as box spline and simplex spline, are generally very expensive to evaluate. Though they have many desirable mathematical properties and have been proved theoretically to be powerful in graphics modeling, they are not a convenient graphics modeling technique in terms of practical implementation. In shape modeling practice, we still lack a simple and practical procedure in creating a set of bivariate spline basis functions from an arbitrarily specified 2D polygonal mesh. Solving this problem is of particular importance in using 2D algebraic splines for implicit modeling, as in this situation underlying implicit equations need to be solved quickly and accurately. In this article, a new type of bivariate spline function is introduced. This newly proposed type of bivariate spline function can be created from any given set of 2D polygons that partitions the 2D plane with any required degree of smoothness. In addition, the spline basis functions created with the proposed procedure are piecewise polynomials and can be described explicitly in analytical form. As a result, they can be evaluated efficiently and accurately. Furthermore, they have all the good properties of conventional 2D tensor-product-based B-spline basis functions, such as non-negativity, partition of unit, and convex-hull property. Apart from their obvious use in designing freeform parametric geometric shapes, the proposed 2D splines have been shown a powerful tool for implicit shape modeling.

REFERENCES

• 1: Bajaj, C. L., Chen, J., and Xu, G. 1994. Free form surface design with A-patches. In Proceedings of Graphics Interface. 174--181.
• 2: Bajaj, C. L. and Xu, G. 1999. A-splines: Local interpolation and approximation using g^k-continuous piecewise real algebraic curves. Comput. Aided Geom. Des. 16, 6, 557--578.
• 3: Chandrajit L. Bajaj , Guoliang Xu, Regular algebraic curve segments (III)—applications in interactive design and data fitting, Computer Aided Geometric Design, v.18 n.3, p.149-173, April 2001 [doi>10.1016/S0167-8396(01)00010-3]
• 4: Barthe, L., Dodgson, N. A., Sabin, M. A., Wyvill, B., and Gaildrat, V. 2003. Two-Dimentional potential fields for advanced implicit modeling operators. Comput. Graph. Forum 22, 1, 23--33.
• 5: 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]
• 6: Philip Fong , Hans-Peter Seidel, An implementation of multivariate B-spline surfaces over arbitrary triangulations, Proceedings of the conference on Graphics interface '92, p.1-10, September 1992, Vancouver, British Columbia, Canada
• 7: Hsu, P. C. and Lee, C. 2002. The scale method for blending operations in functionally-based constructive geometry. Comput. Graph. Forum 22, 2, 143--158.
• 8: Li, Q. 2005. Implicit spline curves and surfaces. In Proceedings of the Chinese Automation and Computing Society Conference in the UK (CACSUK'05), H. Hu et al., Eds. Pacilantic International Ltd, Colchester, England, 201--206.
• 9: Li, Q. 2007. Smooth piecewise polynomial blending operations for implicit shapes. Comput. Graph. Forum 26, 2, 157--171.
• 10: Q. Li , J. G. Griffiths , J. Ward, Constructive implicit fitting, Computer Aided Geometric Design, v.23 n.1, p.17-44, January 2005 [doi>10.1016/j.cagd.2005.04.011]
• 11: Qingde Li , Roger Phillips, Implicit curve and surface design using smooth unit step functions, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
• 12: Li, Q., Wills, D., Phillips, R., Viant, W. J., Griffiths, J. G., and Ward, J. 2004. Implicit fitting using radial basis functions with ellipsoid constraint. Comput. Graph. Forum 23, 1, 55--70.
• 13: Charles Loop , Jim Blinn, Real-time GPU rendering of piecewise algebraic surfaces, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 14: Pasko, A. A., Adzhiev, V., Sourin, A., and Savchenko, V. V. 1995. Function representation in geometric modeling: Concepts, implementation and applications. The Visual Comput. 11, 8, 429--446.
• 15: Galina I. Pasko , Alexander A. Pasko , Tosiyasu L. Kunii, Bounded Blending for Function-Based Shape Modeling, IEEE Computer Graphics and Applications, v.25 n.2, p.36-45, March 2005 [doi>10.1109/MCG.2005.37]
• 16: Bradley A. Payne , Arthur W. Toga, Distance Field Manipulation of Surface Models, IEEE Computer Graphics and Applications, v.12 n.1, p.65-71, January 1992 [doi>10.1109/38.135885]
• 17: Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198798]
• 18: Ricci, A. 1973. A constructive geometry for computer graphics. Comput. J. 16, 3, 157--160.
• 19: Ryan Schmidt , Brian Wyvill, Generalized sweep templates for implicit modeling, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, November 29-December 02, 2005, Dunedin, New Zealand [doi>10.1145/1101389.1101428]
• 20: Chen Shen , James F. O'Brien , Jonathan R. Shewchuk, Interpolating and approximating implicit surfaces from polygon soup, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198651]
• 21: Natalya Tatarchuk , Jeremy Shopf , Christopher DeCoro, Real-Time Isosurface Extraction Using the GPU Programmable Geometry Pipeline, ACM SIGGRAPH 2007 courses, August 05-09, 2007, San Diego, California [doi>10.1145/1281500.1361219]
• 22: Gabriel Taubin, Estimation of Planar Curves, Surfaces, and Nonplanar Space Curves Defined by Implicit Equations with Applications to Edge and Range Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.11, p.1115-1138, November 1991 [doi>10.1109/34.103273]
• 23: 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]
• 24: Greg Turk , James F. O'brien, Modelling with implicit surfaces that interpolate, ACM Transactions on Graphics (TOG), v.21 n.4, p.855-873, October 2002 [doi>10.1145/571647.571650]
• 25: Guoliang Xu , Chandrajit L. Bajaj , Chuan I. Chu, Regular algebraic curve segments (II)-interpolation and approximation, Computer Aided Geometric Design, v.17 n.6, p.503-519, July 2000 [doi>10.1016/S0167-8396(00)00013-3]
• 26: Guoliang Xu , Chandrajit L. Bajaj , Weimin Xue, Regular algebraic curve segments (I)-definitions and characteristics, Computer Aided Geometric Design, v.17 n.6, p.485-501, July 2000 [doi>10.1016/S0167-8396(00)00012-1]

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:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

General Terms:
Algorithms, Design

Keywords:
Algebraic splines, CSG, function-based shape modeling, implicit curve, implicit modeling, implicit surface, isosurface, level set