Algorithm 783: Pcp2Nurb—smooth free-form surfacing with linearly trimmed bicubic B-splines

ABSTRACT

Unrestricted control polyhedra facilitate modeling free-form surfaces of arbitrary topology and local patch-layout by allowing n-sided, possibly nonplanar, facets and m-valent vertices. By cutting off edges and corners, the smoothing of an unrestricted control polyhedron can be reduced to the smoothing of a planar-cut polyhedron. A planar-cut polyhedron is a generalization of the well-known tensor-product control structure. The routine Pcp2Nurb in turn translates planar-cut polyhedra to a collection of four-sided linearly trimmed bicubic B-splines and untrimmed biquadratic B-splines. The routine can thus serve as central building block for overcoming topological constraints in the mathematical modeling of smooth surfaces that are stored, transmitted, and rendered using only the standard representation in industry. Specifically, on input of a nine-point subnet of a planar-cut polyhedron, the routine outputs a trimmed bicubic NURBS patch. If the subnet does not have geometrically redundant edges, this patch joins smoothly with patches from adjacent subnets as a four-sided piece of a regular C1 surface. The patch integrates smoothly with untrimmed biquadratic tensor-product surfaces derived from subnets with tensor-product structure. Sharp features can be retained in this representation by using geometrically redundant edges in the planar-cut polyhedron. The resulting surface follows the outlines of the planar-cut polyhedron in the manner traditional tensor-product splines follow the outline of their rectilinear control polyhedron. In particular, it stays in the local convex hull of the planar-cut polyhedron.

REFERENCES

• 1: CATMULL, E. AND CLARK, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Comput. Aided Des. 10, 350-355.
• 2: 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
• 3: Charles Loop , T. D. DeRose, Generalized B-spline surfaces of arbitrary topology, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.347-356, Aug. 1990
• 4: Martti Mäntylä, An introduction to solid modeling, Computer Science Press, Inc., New York, NY, 1987
• 5: PETERS, J. 1995a. Biquartic C 1-surface splines over irregular meshes. Comput. Aided Des. 27, 12 (Dec.), 895-903.
• 6: Jörg Peters, C1-surface splines, SIAM Journal on Numerical Analysis, v.32 n.2, p.645-666, April 1995 [doi>10.1137/0732029]
• 7: Jörg Peters, Smoothing polyhedra made easy, ACM Transactions on Graphics (TOG), v.14 n.2, p.162-170, April 1995 [doi>10.1145/221659.221670]
• 8: WERNECKE, J. 1993. The Inventor Mentor. Addison Wesley, New York.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Splines

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations

General Terms:
Algorithms

Keywords:
C1 surface, Matlab, NURBS, arbitrary patch layout, arbitrary surface topology, biquadratic tensor-product B-splines, free-form surface, planar-cut polyhedron, trimmed bicubic B-splines