Intuitive shape control for boundary patches

A method and system for computer aided design (CAD) is disclosed for intuitive shape control of boundary patch. A boundary patch is also known as n-sided patch which is defined by a number of input curves/edges. Continuity constraints (G0, G1 and G2) can be specified individually for the input curves. Boundary patch is primarily used to cover a relatively flat area where other modeling operators such as loft, sweep or fillet cannot apply due to irregular shape of the area. The present invention provides a technique to directly manipulate boundary tangent magnitude of a patch and allows the user to deform the patch shape in a very intuitive way. Thus, the present invention is especially useful for industrial design applications.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to computer aided design (CAD) applications and, in particular, to intuitively controlling the shape of a boundary patch.

2. Description of the Related Art

Computer aided design systems are traditionally used for creating and editing geometric shapes, such as car body parts or engine components. Various modeling operators have been introduced for specific modeling situations. Most noticeable standard ones include loft, sweep and fillet which are well defined over a rectangular domain.

In practical design applications there are often situations to fill arbitrary regions bounded by multiple sides (typically, greater than four) where standard operators are no longer applicable. This calls for a special operator, the n-sided patch or the boundary patch. A boundary patch is defined by a set of input curves over a relatively flat area. Continuity constraints (G0, G1and G2) can be specified individually for these curves. The patch to be constructed should pass through all given curves and satisfy the continuity constraints within given tolerances.

It is, however, very challenging to construct a boundary patch that not only meets the boundary constraints but also possesses a fair shape under various geometric configurations. As a result, boundary patch has been a long standing problem in both design and research community and there are a large body of proposed solutions to it.

In general, there are two basic approaches to the n-sided problem: multiple patches and single patch. The multiple patches solution takes an n-sided region and subdivides it into a collection of triangular or 4-sided regions. The regions are then filled with standard surface type. The main difficulty with this approach is ensuring the internal smoothness of the resulting patch network. The single patch solution attempts to create a single patch to fill in an n-sided hole. Different techniques have been developed for very specific patch situations. For example, in one technique, a quadratic function is used to fill in three- or five-sided patches. In another technique, quadratics and cubics functions are used for three-, five- and six-sided patches. The problem with these techniques is that often unusual (non-rectangular, non-planar) parametric domains are used and the lack of possibility to control internal shape of the patch.

Another category of filling an n-sided hole is the subdivision approach. The basic process is to generate a surface by starting with a polygonal approximation and refine the approximation iteratively in each subdivision step. The fundamental problem with the subdivision approach, however, is the lack of a good method to handle the smoothness of extraordinary points and to create high quality surfaces.

Commercial CAD systems prefer the single patch approach since only one face needs to be constructed and thus is easier to be integrated in the modeling (especially solid modeling) environment. As the rectangular scheme of non-uniform ration B-spline (NURBS) has become the de facto standard for industrial applications, NURBS is often chosen to represent n-sided patches. First, a surface with a rectangular domain is created that is large enough to cover the entire n-sided hole. The surface is then trimmed back to the hole boundary. In this sense, the patch is a trimmed NURBS surface. This kind of n-sided patch is, however, locked by the boundary constraints, i.e. there are little possibilities to determine/change its interior shape. One can insert additional interior constraints such as interior curves and points to force the patch to pass through. However, these additional constraints introduce some artifacts in the patch shape so that the patch quality (e.g. curvature flow) may suffer. Certain tension control may be achieved but its influence over the entire patch shape is somewhat subtle and limited.

As the foregoing illustrates, what is needed in the art is a mechanism for modifying the patch shape in a direct and intuitive way.

SUMMARY OF THE INVENTION

One or more embodiments of the invention is a computer-implemented method for modifying the shape of a graphics object represented in a computer-aided design (CAD) application. The method includes the steps of generating a surface based on one or more boundaries of the graphics object, wherein the surface has a shape defined by a set of first coordinates, mapping the set of first coordinates to a set of second coordinates that identifies a different tangent for each of the one or more boundary edges, modifying a first tangent for a first boundary edge, and modifying the set of second coordinates based on the modified first tangent to generate a modified shape of the surface.

Advantageously, the technique described herein allows for the modification of a boundary patch by modifying tangent magnitudes along the boundaries.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Hardware Environment

FIG. 1is a computing environment configured to implement one or more embodiments of the invention. Embodiments of the invention are typically implemented using a computer100, which generally includes, inter alia, a display device102, data storage devices104, cursor control devices106, and other devices. Those skilled in the art will recognize that any combination of the above components, or any number of different components, peripherals, and other devices, may be used with the computer100.

One or more embodiments of the invention are implemented by a computer-implemented graphics program108(e.g., a CAD program), wherein the graphics program108is represented by a window displayed on the display device102. Generally, the graphics program108comprises logic and/or data embodied in or readable from a device, media, carrier, or signal, e.g., one or more fixed and/or removable data storage devices104connected directly or indirectly to the computer100, one or more remote devices coupled to the computer100via a data communications device, etc. Further, the graphics/drawing program108may utilize a database110such as a spatial database.

Computer100may also be connected to other computers100(e.g., a client or server computer) via network112comprising the Internet, LANs (local area network), WANs (wide area network), or the like. Further, database110may be integrated within computer100or may be located across network112on another computer100or accessible device.

Those skilled in the art will recognize that the exemplary environment illustrated inFIG. 1is not intended to limit the present invention. Indeed, those skilled in the art will recognize that other alternative environments may be used without departing from the scope of the present invention. Accordingly,FIG. 1illustrates a CAD system that combines the traditional capabilities of CAD tools with common spatial management features. In this regard, such a solution enables the use of true geometry, precision, powerful creation and editing tools, and drawing and document production of a CAD system. Further, single or multiple users may integrate their workflow using such a system.

As described above, one or more embodiments of the invention is implemented in a CAD system. The invention provides a technique for intuitively modifying the shape of a boundary patch defined by a set of input curves/edges.

Surface Representation

FIG. 2illustrates a graphics object202generated using the drawing program108ofFIG. 1, according to one embodiment of the invention. To construct a surface that passes through all input curves204of the graphics object202identified by a user of the graphics program108, a parametrization is first defined for the surface. An obvious choice is to first create a so called best-fit plane that best fits the input curves in the least squares sense. The necessary parametrization is then obtained by projecting the curves onto the plane. Without loss of generality, such a best-fit plane can be assumed to be the X-Y plane. Importantly, any plane can be converted to the X-Y plane by affine transformations. Thus, the boundary patch can be expressed in the explicit form z=S(x, y). To achieve a fair shape the boundary patch is further designed to minimize the following smoothness function:

A surface created with the above smoothness tends to distribute curvature over large regions and produces very graceful shapes. If B-spline is used to represent the boundary patch, solving the smoothness functional becomes the discrete matrix minimization problem:
min[(xT]Kx)  (2)
xT={Pi,j} is a vector of (m×n) control points and K defines the stiffness matrix and is given by:

Boundary Constraints

Boundary constraints include G0, G1and G2constraints and can be written as linear equations:
Ax=b(4)
where each row of the matrix A represents a linear constraint on x and the vector b are the values of these constraints. The final equations for determining X are determined by minimizing the quadratic functional (2) subject to the constrained equation (4).

Boundary constraints include G0, G1and G2constraints and can be written as linear equations. G0constraint is a position constraint that requires the surface to interpolate a specified position. Thus, b just contains the position coordinates, namely the z coordinates. G1constraint requires the surface to assume a specified normal vector=(N)(x),N(y),N(z)).

Let=(1,0,Sx) and=(0,1,Sy) be the surface partial derivatives, the sufficient G1conditions are then given by:

From the above equation we can see that both Sxand Syare fully determined by the surface normal. As a result, there is no degree of freedom to modify them in the presence of G1constraint.

Two surfaces are said G2at a touch point if their curvatures at that point agree in all directions. For regular surfaces G2condition holds if the curvatures of the two surfaces are the same in three independent directions. Therefore, the G2constrained equations can be derived in a manner similar to that of G1.

Modified Spherical Coordinate System

Boundary tangents of a surface have great influence over its overall shape. If only position constraints are required, i.e. a boundary patch only needs to interpolate given boundaries, both directions and magnitudes of boundary tangents can be used to adjust the patch shape. However, if G1or G2constraints are present, boundary tangents are fully constrained. As shown in the previous section, there is no degree of freedom to modify either their directions or magnitudes in the Cartesian coordinate system. To overcome this limitation, a new coordinate system called the modified spherical coordinate system is defined as described below.

Let O be the origin of the coordinate system and the reference plane is the X-Z plane. Then a point P=(x,y,z) in the Cartesian coordinate system is defined by the coordinate triple (r,u,v) in the modified spherical coordinate system as:

Similarly, r is the radius or radial distance of point P to a point O′ resulted from moving the origin O a distance of ƒ(x,y) along the positive Z-axis. u is the polar angle between the Y-axis and the line segmentO′Pand v the so-called the azimuthal angle measured from the positive Z-axis to the orthogonal projection of the line segmentO′Pon the reference plane. ƒ(x,y) is a function defined over the (x,y) domain and will be further described in the next section. Point O′ can be viewed as the origin of the new coordinate system and the modified coordinate system as a spherical coordinate system with a variable origin.

From equation (8) it is trivial to derive the formulae of mapping from the modified spherical coordinate system to the Cartesian coordinate system as follows:

∫∫[(∂2⁢r∂u2)2+2⁢(∂2⁢r∂u⁢∂v)2+(∂2⁢r∂v2)2]⁢ⅆu⁢ⅆv(10)
The corresponding discrete matrix form is re-written in the same way as in (3).

The boundary constraints can be expressed in the modified spherical coordinate system. For G1constraints, first the 1stpartial derivatives of the surface in u and v are computed:

Su⁢:⁢⁢{xu=(ru⁢cos⁢⁢u-r⁢⁢sin⁢⁢u)⁢sin⁢⁢vyu=ru⁢sin⁢⁢u+r⁢⁢cos⁢⁢uzu=(ru⁢cos⁢⁢u-r⁢⁢sin⁡(u)⁢cos⁢⁢v]-fu⁢⁢Sv⁢:⁢⁢{xv=(rv⁢sin⁢⁢v+r⁢⁢cos⁡(v)⁢cos⁢⁢u]yv-rv⁢sin⁢⁢uzv=(rv⁢cos⁢⁢v-r⁢⁢sin⁢⁢v)⁢cos⁢⁢u-fv
The 1stpartial derivatives of ƒ(x,y) are then derived through the chain rule as:

{fu=fx⁢xu+fy⁢yu=ru⁡(fx⁢cos⁢⁢u⁢⁢sin⁢⁢v+fy⁢sin⁢⁢u)+r⁡(fy⁢cos⁢⁢u-fx⁢sin⁢⁢u⁢⁢sin⁢⁢v)fv=fx⁢xv+fy⁢yv=rv⁡(fx⁢cos⁢⁢u⁢⁢sin⁢⁢v+fy⁢sin⁢⁢u)+rfx⁢cos⁢⁢u⁢⁢cos⁢⁢v
Finally, the G1condition (3) is rewritten in the following equation

From the above equation, the surface tangent is now determined by the constraint normalas well as the unknown function ƒ(x,y). Since the constraint normal is given, ƒ(x,y) is used to modify surface tangents which will be further described in the next section.

To see how the function ƒ(x,y) affects the surface tangent vector, the following assumption is made ƒ(x,y)=C, where C is a constant. Based on this assumption:
ƒu=ƒv=ƒx=ƒy=0  (15)
Both ruand rvare proportional to r. If equation (14) is inserted into the equations (11) and (12), it becomes clear thatandare also proportional to r. r is computed by:
r=√{square root over (x2+v2+(z+C)2)}  (16)

Therefore, if C increases, then the value r goes up and effectively scales up the magnitudes of surface tangentsand. Similarly decreasing C will scale down the tangent magnitudes. Since the change of C equally affects surface tangents along the boundary, we call this kind of change the “uniform” scaling of surface tangent magnitudes, and C the scale factor. Obviously, the relative influence of C over r (consequently the surface tangents) is dependent on the dimension of r and therefore the size of the model.

FIGS. 3-5illustrate scaling with scale factors of 0.3, 0.5 and 0.8 respectively. In each ofFIGS. 3-5, the surface302is the constraint surface and the surface304,402and504are the boundary patches, respectively. For user convenience, the scale factor may be normalized between 0 and 1. The final surface is obtained by mapping back from the modified spherical coordinate system to the Cartesian coordinate system using (9).

In practice, the user may want to use variable scale factors along the boundary to achieve the desired surface shape. This calls for the non-uniform scaling which allows the user to specify some seed scale factors on the boundary. A “scaling” curve along the boundary is then created that interpolates the seed scale factors. Finally, the scaling curve is used to fit a surface that is ƒ(x,y). The fitting is, in fact, the same procedure as described in the section “Surface Representation” where the coordinate z is replaced by the scale factor.FIG. 6illustrates a non-uniform scaling example.

FIG. 7is a flow diagram of method steps for modifying the shape of a surface of a graphics object, according to one embodiment of the invention. Although the method steps are described in conjunction with the systems forFIGS. 1-6, persons skilled in the art will understand that any system configured to perform the method steps, in any order, is within the scope of the invention.

The method700begins at step702, where the graphics program108generates a surface of the graphics object202based on one or more input boundary edges identified by the user of the graphics program108. The surface is represented in a Cartesian coordinate system and one or more constraints.

At step704, the graphics program108maps the Cartesian coordinates representing the surface to a modified spherical coordinates. The manner in which the Cartesian coordinates are mapped to spherical coordinates is described in great detail above. At step706, the graphics program108modifies the tangent magnitudes along the input boundary in the spherical coordinate system according to one or more constraints specified by the user.

At step708, the graphics program creates a surface in the spherical coordinate system according to the modified tangents. At step710, the graphics program maps the modified spherical coordinates back to Cartesian coordinates that represent the new shape of the surface.

In other embodiments, the coordinates can be represented in coordinate systems other than Cartesian and the modified spherical coordinates. The computations involved with such coordinate systems would be well-known in the art.