Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Construction of Smooth Curves and Surfaces from Polyhedral Models

Leon A. Shirman

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-90-602
December 1990

http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-602.pdf

This work is devoted to the problem of constructing geometrically continuous interpolating curves and surfaces through a given set of points. Geometric continuity is a relaxed measure of parametric continuity and is defined in terms of continuity of tangent vector for curves and of tangent plane for surfaces. Various solutions to the above problem have been proposed. However, the resulting curves and surfaces are often of poor visual quality and contain unnecessary 'wiggles' and 'overshoots'. Our method breaks the process of curve or surface construction into several independent procedural steps and assigns available degrees of freedom based on geometric reasoning. This greatly improves the resulting visual quality of the object.

Our curve interpolation method builds G^1 continuous curves from cubic Bezier segments. A number of heuristic rules for determining vertex normals and curve control points is introduced. Furthermore, this approach is extended to produce curvature continous (G^2) cubic splines.

This procedural approach is generalized to the construction of surfaces from a raw polyhedral model, supplied by the user. This construction proceeds in several steps: first, suitable normals at each vertex of the original model are computed; they will become the normals of the final surface at these points. Second, cubic Bezier curves are constructed in place of the edges of the original model; the final surface will interpolate these curves. Third, surface patches are defined with these curves as their boundaries; the patches will jointly form an interpolating G^1 surface. At each of the above steps, heuristic rules are used that assign reasonable values to available degrees of freedom, such as vertex normals or tangent directions of boundary curves. However, the user always has an option of overriding default assignments with prescribed values.

From the mathematical analysis of G^1 continuity conditions between Gregory and/or Bezier patches, it follows that the surface can be defined in several ways and still maintain required locality and interpolating properties. These available degrees of freedom that are intrinsically present in the system, are utilized to alter the cubic boundaries as well as the shape of the two patches near their common seam. They are made available to the user in the form of intuitively understandable shape parameters.

Simplicity of the surface representation is important for rendering efficiency. Therefore, a method was developed that replaces the Gregory patches used in the original implementation by polynomial quadrilateral and triangular Bezier patches.

The described method of surface construction has several important advantages. The method is modular, i.e. the construction process is split into several separate stages so that a change of procedural rules at one stage does not affect another. The method is also local, and the underlying surface representation is simple. The method is flexible because surfaces can be built for various types of data (e.g. points, points with normals, profile curves). Finally, the method gives to a user many shape parameters that can be used to alter the final shape; however, an automatic default solution can always be computed.

Advisor: Carlo H. Séquin


BibTeX citation:

@phdthesis{Shirman:CSD-90-602,
    Author = {Shirman, Leon A.},
    Title = {Construction of Smooth Curves and Surfaces from Polyhedral Models},
    School = {EECS Department, University of California, Berkeley},
    Year = {1990},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/5342.html},
    Number = {UCB/CSD-90-602},
    Abstract = {This work is devoted to the problem of constructing geometrically continuous interpolating curves and surfaces through a given set of points. Geometric continuity is a relaxed measure of parametric continuity and is defined in terms of continuity of tangent vector for curves and of tangent plane for surfaces. Various solutions to the above problem have been proposed. However, the resulting curves and surfaces are often of poor visual quality and contain unnecessary 'wiggles' and 'overshoots'. Our method breaks the process of curve or surface construction into several independent procedural steps and assigns available degrees of freedom based on geometric reasoning. This greatly improves the resulting visual quality of the object. <p>Our curve interpolation method builds <i>G</i>^1 continuous curves from cubic Bezier segments. A number of heuristic rules for determining vertex normals and curve control points is introduced. Furthermore, this approach is extended to produce curvature continous (<i>G</i>^2) cubic splines. <p>This procedural approach is generalized to the construction of surfaces from a raw polyhedral model, supplied by the user. This construction proceeds in several steps: first, suitable normals at each vertex of the original model are computed; they will become the normals of the final surface at these points. Second, cubic Bezier curves are constructed in place of the edges of the original model; the final surface will interpolate these curves. Third, surface patches are defined with these curves as their boundaries; the patches will jointly form an interpolating <i>G</i>^1 surface. At each of the above steps, heuristic rules are used that assign reasonable values to available degrees of freedom, such as vertex normals or tangent directions of boundary curves. However, the user always has an option of overriding default assignments with prescribed values. <p>From the mathematical analysis of <i>G</i>^1 continuity conditions between Gregory and/or Bezier patches, it follows that the surface can be defined in several ways and still maintain required locality and interpolating properties. These available degrees of freedom that are intrinsically present in the system, are utilized to alter the cubic boundaries as well as the shape of the two patches near their common seam. They are made available to the user in the form of intuitively understandable shape parameters. <p>Simplicity of the surface representation is important for rendering efficiency. Therefore, a method was developed that replaces the Gregory patches used in the original implementation by polynomial quadrilateral and triangular Bezier patches. <p>The described method of surface construction has several important advantages. The method is modular, i.e. the construction process is split into several separate stages so that a change of procedural rules at one stage does not affect another. The method is also local, and the underlying surface representation is simple. The method is flexible because surfaces can be built for various types of data (e.g. points, points with normals, profile curves). Finally, the method gives to a user many shape parameters that can be used to alter the final shape; however, an automatic default solution can always be computed.}
}

EndNote citation:

%0 Thesis
%A Shirman, Leon A.
%T Construction of Smooth Curves and Surfaces from Polyhedral Models
%I EECS Department, University of California, Berkeley
%D 1990
%@ UCB/CSD-90-602
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/5342.html
%F Shirman:CSD-90-602