NURBS Considered Harmful for Gridding
(Alternative Offered)

[18 January, 1996 - This is a preliminary HTML version of this document without equations and figures]

John S. Letcher, Jr. and Michael Shook
AeroHydro, Inc.
P.O. Box 684
Southwest Harbor, Maine 04679

• ABSTRACT
• INTRODUCTION
• NURBS
• DEFICIENCIES OF NURBS IN GEOMETRIC MODELING AND PANELIZATION
  • (1) Division by Zero.
  • (2) Nonuniform Parameterization Of Arcs.
  • (3) Curves And Surfaces Which Cannot Be Accurately Represented By NURBS.
  • (4) Irregular Surface Meshes Resulting From Use Of Nonuniform Weights.
  • (5) Ill Conditioned Basis For Surface Fitting.
  • (6) Lack Of Closure.
• RELATIONAL GEOMETRY
• EXAMPLE
• CONCLUSIONS
• ACKNOWLEDGMENT
• REFERENCES

ABSTRACT

Volume gridding for CFD starts from a geometric model for the body surfaces. It is argued that NURBS based geometry definitions are fundamentally unable to deliver the degree of consistency and accuracy required for this purpose. The reasons for this are explored. Relational geometry is proposed as an advantageous alternative.

INTRODUCTION

Gridding is a significant bottleneck in the overall computational fluid dynamics (CFD) analysis work flow. As such, gridding is a hindrance to the emergence of CFD as an everyday engineering analysis tool. Correction of dirty model geometry prior to gridding is a large part of the overall gridding bottleneck.

For analysis of high Reynolds number viscous flows, volume element dimensions near the boundaries are on the order of 10-9 of the gross model dimensions. Geometric discrepancies on this order of magnitude play havoc with gridding and flow solutions.

Over the past ten years nonuniform rational B-splines (NURBS) have become the geometry definition of choice for computer aided design and computer aided manufacturing (CAD/CAM) implementors and vendors. Thus NURBS models have become the predominant raw material for gridding practitioners. The attractions to CAD implementors of a relatively simple, unified, homogeneous geometry definition are manifold. Frequently cited is NURBS ability to accurately represent conic sections. This seems to have expanded to an uncritical acceptance of NURBS as an accurate geometric representation.

We demonstrate a number of deficiencies of NURBS. The most significant deficiency is that NURBS is an open system: Most operations on NURBS objects (composition, intersection, projection) do not inherently result in NURBS objects. NURBS implementations rely heavily on fitting and approximation to forcibly close an inherently open system.

We propose Relational Geometry (RG) [1, 2] as a framework for geometric modeling which addresses NURBS' deficiencies listed above. We describe RG in sufficient detail to demonstrate how these deficiencies are answered. RG is the basis of our MultiSurf® surface modeler.

NURBS

NURBS curves and surfaces are both based on piecewise polynomial B-splines ,

which may be computed from the Cox-deBoor recurrence [3]

(1)

starting with (2)

is a knot vector satisfying

(3)

When the interior knots are uniformly spaced:

(4)

the knot are described as uniform.

The standard definition for a NURBS curve in 3-D is

(5)

where are 3-D control points,

are corresponding weights

and the knot vector is . When the weights are all constant, the denominator in (5) is constant and (5) simplifies to (NUBS):

. (6)

When, further, the knots are uniform, (6) represents a uniform B-spline (UBS) curve.

The standard definition for a NURBS surface in 3-D is

(7)

where are 3-D control points,

are corresponding weights.

The B-spline bases use separate knot vectors for the u and v directions.

When the weights wij are all uniform (constant wij = w), the denominator in (7) is constant, and (7) simplifies to (NUBS)

(8)

when, further, the knots for both u and v basis functions are uniform, (8) represents a uniform B-spline (UBS) tensor product surface.

DEFICIENCIES OF NURBS IN GEOMETRIC MODELING AND PANELIZATION

We mention first a number of specific problems in basing a geometry definition on NURBS. The last problem, lack of closure, is much broader and more fundamental.

(1) Division by Zero.

In most applications of NURBS, the division occurring in (5) or (7) is troublesome, as some combinations of weights can produce a zero denominator. Requiring all weights to be positive is a sufficient condition to prevent this, but as a set of inequality constraints is a difficult condition to impose during curve and surface fitting. Handling this possible error substantially complicates any NURBS-based geometry program. (This problem is absent in NUBS and UBS.)

(2) Nonuniform Parameterization Of Arcs.

One useful property of NURBS (as opposed to NUBS or UBS) is that circular arcs can be represented exactly. For example, eq. (5) with:

(9)

precisely describes a quadrant of a circle. The same arc is described by

(10)

Although the point-sets described by (9) and (10) are identical, the parameterizations are different; i.e., x(t) = y(t) only for t = 0, .5, and 1.

We assert that the "uniform" parametrization of (10) -- uniform with respect to angle and arc length -- is singularly natural and advantageous for modeling and panelization. Alternative NURBS representations of arcs are available, but none provides uniform parameterization.

One panelization consequence is that a surface mesh taken at uniform parameter intervals from a NURBS representation of a surface of revolution will have nonuniform panel sizes in the circumferential direction. The panelization lacks the rotational symmetry of the underlying body. (Fig. 1)

Fig. 1                                                                     
NURBS representation of a surface    Same patch with uniform               
of revolution has nonuniform mesh    parameterization                      
circumferentially.                                                         

(3) Curves And Surfaces Which Cannot Be Accurately Represented By NURBS.

The helix and helicoidal surfaces are very common engineering entities which have no exact NURBS representations. Modeling a helix to an accuracy of 1 part in 103 requires approximately 10 control points per revolution.

The surface defined by

x(u,v) = ( u, v, 16UV) (11)

where U = u(1-u), V = v(1-v) is exactly representable by NURBS (by UBS, in fact). It exhibits (Fig. 2a) the typical "corner flatness" of NURBS surfaces; at the corners, the surface is always tangent to the plane through the corner point and the two edge control points adjacent to the corner.

By contrast, the surface defined by

x(u,v) = ( u, v, 8UV/(U+V)) (12)

has a very different character in the corners (Fig. 2b), unobtainable with NURBS. Although (12) is a rational polynomial surface, it is not representable by NURBS because the degrees of the denominator and numerator are different.

(4) Irregular Surface Meshes Resulting From Use Of Nonuniform Weights.

Free-form NURBS surfaces are shaped by positioning a net of control points and adjusting their weights. Control points with high weights "attract" the mesh of parametric lines. Use of much variation in the weights, e.g. as degrees of freedom in surface fitting, therefore tends to produce irregular meshes which are hard to visualize, and possibly undesirable for analysis. (Fig. 3)

(5) Ill Conditioned Basis For Surface Fitting.

Again, free-form NURBS surfaces are shaped by positioning a net of control points and adjusting their weights. There are two sources of ill-conditioning when the surface representation (7) is used for least-squares fitting of surfaces to data. First, the effect of a weight is often very similar to the effect of moving a control point normal to the surface. Second, movement of a control point in a tangential direction (two degrees of freedom per control point) has orders of magnitude weaker effect on the fit than movement in the normal direction. The result is that fitted surfaces are very sensitive to small changes and errors in the data, and usually have very irregular meshes due to weight variations and/or irregular control point nets.

(6) Lack Of Closure.

The most fundamental obstacle to use of NURBS as a basis for accurate geometry definition is that it is an open system; i.e., curves and surfaces that naturally arise during modeling with NURBS cannot be accurately represented as NURBS curves and surfaces. Common operations that produce non-NURBS curves are:

composition (mapping a NURBS curve in parameter space onto a NURBS surface)

projection of a NURBS curve onto a NURBS surface

intersection of two NURBS surfaces.

In each case a curve is produced which, except in special cases, cannot be exactly represented by NURBS. Often the resulting curve is to be used for the edge of a new surface, which of course also cannot be exactly represented as a NURBS surface, since all edges of a NURBS surface are necessarily NURBS curves.

(Technically, composition does produce a spline, but one that is high order and highly degenerate. For example, a cubic spline in parameter space mapped onto a cubic spline surface produces a piecewise ninth degree parabola, with only two continuous derivatives at its irregularly spaced (septuple) knots. High order splines and highly degenerate splines are typically avoided, possibly for reasons of numerical stability.)

The prevailing answer to the closure problem is approximation. If a curve can't be exactly represented by splines, it can always be approximated with them. Of course, by increasing the number of data points, control points and knots, the precision of fit can be brought within any specified tolerance; however, convergence with respect to n is not rapid, so for high precision the model data size and computational costs can be prohibitive.

Typical CAD surface models for CFD analysis consist of multiple (often many) nominally joined NURBS surface patches. Each patch is internally represented by its own control point net, weights, and knot vectors. However, for two NURBS patches to actually join exactly (C0 continuity) along a common edge, the following conditions are necessary:

the edges must have identical knot locations in 3-D; (13a)

they must consist of identical rational Bezier segments

between the knots. (13b)

The following conditions are sufficient:

identical degree k in this parametric direction; (14a)

identical knots in this parametric direction; (14b)

identical control points along this edge; (14c)

proportional weights on these control points. (14d)

(In fact, the rules of knot insertion [4] and degree elevation [5] provide some further freedom than rules (14) suggest -- basically allowing multiple NURBS representations of a given NURBS curve, through insertion of inactive knots, or representation of polynomials of lower degree as degenerate instances of higher degree polynomials.)

Because n, k, and knot vectors are constant across each NURBS patch, these conditions propagate from patch to patch in a quiltlike fashion, imposing very restrictive nonlocal constraints on the CAD model. Conventional CAD programs do not provide any facilities for imposing rules such as (14), much less for knot insertion and degree elevation. Wherever conditions (13) do not obtain, there will be discrepancies between edges. These may be small enough to be visually unapparent, and insignificant from the point of view of manufacturing, and still be enormous on the scale required for volume gridding.

RELATIONAL GEOMETRY

Relational Geometry (RG) is a framework for geometric modeling which addresses all these issues. At the core of RG is an acyclic directed graph or digraph. The nodes of the graph are geometric objects. The arcs represent the dependency relationships between the geometric objects.

A simple model provides an example. Fig. 4 display a model consisting of three points and two lines. Listing 1 displays the RG model file which describes this model.

Each line of the model file describes an object in the model. This simple model consists of objects which are instantiations of one of three entities, AbsPoint, Line or AbsBead. RG entities and objects correspond to the "classes" and "objects" in object-oriented programming terminology.

Fig. 4. A simple relational model consisting of three points and two lines.

AbsPoint A1 2. 2. 0. ;
AbsPoint A2 2. 4. 0. ;
Line line_A A1 A2 ;
AbsPoint B2 6. 4. 0. ;
Line line_B A2 B2 ;
AbsBead bead_B line_B .25 ;

Listing 1. The RG model file representation for the model of Fig. 4.

Each object description has a entity name, an object name and object data and supports.

Entity name        Object name        Object data and    Description        
                                      supports                              
AbsPoint           A1                 2. 2. 0.           x, y and z         
                                                         coordinates of     
                                                         point              
Line               line_A             A1 A2              Name of end        
                                                         points             
AbsBead            bead_B             line_B .25         Supporting curve   
                                                         and t              

Table 1. Components of sample object descriptions.

Fig. 5 show the digraph described by the model file.

Fig. 5. The digraph representing the model of Fig. 4.

When referring to the digraph, we speak in terms of supports and dependents. A1's only dependent is line_A. line_B's supports are A2 and B2. Supports and dependents can be either direct or indirect. bead_B's direct support is line_B. bead_B's indirect supports are A2 and B2.

The value of an object in RG is a table. For surface objects this table contains a rectangular array of 3d points representing points at the intersections of the u and v isoparms of the surface. For curve objects it contains a vector of 3d points and for point objects it contains a single 3d point. This value representation leads to two evaluation modes: fast and accurate. In fast mode, when the evaluation of an object requires a position at a particular parameter value on a supporting object, that position is determined by linear interpolation in the table. In accurate mode the table is not used; the supporting object is explicitly evaluated with the parameter value.

An internal representation of the digraph allows the user of an RG based interactive modeler to edit the model while maintaining the relationships. The modeler accomplishes this by using the digraph to recursively update any dependents of an object after the object is edited. Thus if the user moves point A2 to 3,2,0 all objects supported by A2 are automatically updated.

Fig. 6. The model of Fig. 4, following a change in position of point 'A2'.

RG's digraph and automatic update capability facilitate the creation of parametric series of models based variations in a small number of a model's objects.

While the RG digraph enables a system to capture user intent and provide the powerful automatic update function, a rich collection of entities are necessary for a complete and useful modeler. The current RG implementation includes 20 point entities, 32 curve entities and 23 surface entities.

These include many entities embedded in objects of higher or equal dimension:

points embedded in a curve (beads)

points embedded in a surface (magnets)

curves embedded in on a surface (snakes)

curves embedded in another curve (subcurve)

surfaces embedded in another surface (subsurf)

A bead object is shown in the previous examples. The essential interchangeability of these entities within each dimensionality class is facilitated by consistent parameterization: all curves are parameterized from 0 to 1; all surfaces are parameterized from 0 to 1 in both u and v.

Constrained entities can be used interchangeably with other entities of the same dimensionality. Thus, in the example above, bead_B could be used as a support for a curve, the same as any other point object.

An RG based system can avoid difficulties associated with surface-surface intersections and trimming of surfaces along such intersections. RG provide several ways to accomplish this:

    1. Two lofted surfaces will join                                       
      accurately and durably along a                                       
 common edge if they are of the same                                       
  type, they have the same number of                                       
   defining curves, and the defining                                       
             curves share endpoints.                                       
Fig. 7.                                       
      2. RG supports several surface                                       
 entities that interpolate 1, 2 or 4                                       
  boundary curves. Two such surfaces                                       
  that share the same defining curve                                       
     will have a durable common edge                                       
 along that curve. Here a surface of                                       
        revolution and a translation                                       
   surface share a defining B-spline                                       
                   curve as an edge.                                       
Fig. 8.                                       
 3. It is possible to join a surface                                       
    to a second, supporting surface,                                       
 not along an edge of the supporting                                       
        surface but somewhere in its                                       
   interior. This is done by using a                                       
    snake on the supporting surface.                                       
    The dependent surface is defined                                       
         using a surface entity that                                       
      interpolates its edges and the                                       
         snake is used as one of its                                       
               defining edge curves.                                       
Fig. 9.                                       

Methods 2 and 3 involve designing the curve of intersection first and then attaching the surfaces to it. It is not surprising that this is far easier to execute than the usual intersection-trimming method. RG does support surface-surface intersections where these techniques cannot be used.

EXAMPLE

Fig. 10 is an example of a wing-pylon-nacelle configuration modeled with relational geometry (MultiSurf). The wing is a ruled surface between two airfoil sections, and the nacelle is a surface of revolution. These base surfaces were developed first, and a "footprint" snake was drawn on each for the upper and lower edges of the pylon. The pylon is a B-lofted surface, a surface entity which interpolates its opposite edge curves. Subsurfaces were made on the wing and nacelle to panelize the portions outside the footprints. The use of the same snakes to bound the subsurfaces and to define the pylon edges allows the exact matching of panels along the wing-pylon and pylon-nacelle junctions. Not obvious from the figure is that the model has many parametric degrees of freedom (e.g., nacelle radius, length, position, wing chord, sweep, and sections) with all the topological properties of the panelization automatically maintained.

Fig. 10. Panelization of a wing-pylon-nacelle combination using methods of relational geometry. Panels match exactly across the wing-pylon and nacelle-pylon junctions.

CONCLUSIONS

Difficulties experienced with use of CAD models for volume gridding can be traced to fundamental limitations in geometric modeling with NURBS curves and surfaces. While we realize that gridding practitioners often have no control over the source of their geometry, we feel that it is important that designers at very least be aware of the NURBS' limitations. We offer RG in the face of the NURBS' momentum in the marketplace.

ACKNOWLEDGMENT

This work was supported in part by the Naval Surface Warfare Center, Carderock Division, contract N-00167-95-C-0003.

REFERENCES:

1. Letcher, J. S. Jr., Shook, D. M. and Shepherd, S. G.: "Relational Geometric Synthesis -- Part 1: Framework", Computer Aided Design (accepted for publication)

2. Letcher, J. S. Jr. and Shook, D. M.: "Parametric Design and Gridding Through Relational Geometry", Proceedings of the Surface Modeling, Grid Generation and Related Issues in Computational Flow Dynamic (CFD) Solutions, NASA Lewis Research Center, May 9-11, 1995, p. 783-800

3. deBoor, C.: A Practical Guide to Splines, Springer-Verlag, New York (1978)

4. deBoor, C.: "B-Spline Basics", in Fundamental Developments of Computer-Aided Geometric Modeling (L. Piegl, Ed.), Academic Press, New York (1993)

5. Farin, G. and Worsey, A.: "Reparameterization and Degree Elevation for Rational Bezier Curves" in NURBS for Curve and Surface Design (G. Farin, Ed.), S. I. A. M., Philadelphia (1991)

6. Hoffman, C. M.: Geometric and Solid Modeling, Morgan Kauffman, San Mateo CA (1989)

Back to Relational Geometry