Introduction to NURBS Curves and Surfaces

NURBS curves and surfaces are concise, yet very powerful and general representations of a wide variety of simple and complex geometries. Trimmed NURBS are becoming increasingly more prominent in informal and formal industry standards for geometric modeling and computer graphics. This is primarily due to their generality and effectiveness for representing both simple and complex shapes, for their powerful mathematical properties, and for their ease of manipulation and processing on the computer. Typical applications range from mechanical CAD (computer-aided design) to scientific visualization.

From a high-level mathematical description, a graphics system tessellates curved geometry into lines (in the case of curves) or triangles (in the case of surfaces), whose sizes depend on the spatial relation of the curve or surface to the eye, and on the complexity of the geometry.

This chapter discusses how this high-level description is specified using XGL operators and attributes, and how the XGL application can control the display of NURBS curves and surfaces. XGL NURBS semantics follow the PHIGS PLUS model for NURBS and add additional features such as dynamic tessellation for trimming and speed hints for simple geometry.

NURBS Curves

A NURBS curve is a mapping from a bounded one-dimensional parameter space into a set of m-dimensional points in 2D or 3D object space. A NURBS curve is rendered as a 2D or 3D set of lines. Various attributes (in addition to line attributes) can be set to control the display of the curve.

Mathematical Description of a NURBS Curve

A NURBS curve is mathematically defined by:

1. A set of control points.

2. The order of the curve.

3. A knot vector defining the mapping from parameter space to object space.

4. A [min,max] range in parameter space that defines the portion of the curve that is displayed.

The curve is defined by:

n

C (t) = B .

(t) P i, k i

(EQ 1)

i = 1

where

C(t) is the curve;

P are the n control points; i

t is the one-dimensional parameter;

Bi,k(t) are the scalar-valued B-spline basis functions in the variable t, of order k (degree k-1).

The B-spline basis functions are defined by the order k and a knot vector, {tj} (j = 1 to n+k), where the sequence tj is non-decreasing.

For more information on the mathematical characteristics of NURBS curves, refer to Curves and Surfaces for Computer Aided Geometric Design by Gerald Farin, Second Edition, Academic Press, Inc., San Diego, CA, 1990. The following sections discuss in more detail the three defining characteristics of a NURBS curve: control points, knot values, and parameter range.

Control Points

Control points determine the shape of the B-spline curve. The control points (Pi) of the curve may be defined using Cartesian coordinates (x,y,z) or using homogeneous coordinates (x,y,z,w). In the first case, the curve is said to be non-rational; in the second case, it is said to be rational.

The actual curve lies within the bounding polyhedron (called the convex hull) of the control points. When a control point is moved, the shape of the curve moves in that direction. This lends itself to interactive design. Figure 9-1 shows a B-spline curve of order 4 and its control points.

Figure 9-1

Rational curves are more useful than non-rational curves in at least two ways. First, the homogeneous component (w) of each control point acts as a weight associated with it. The greater the weight, the more the curve is pulled toward that point. This characteristic offers greater interactive control over the shape of the curve. Second, simple geometry such as conics (circles, ellipses, etc.) can only be represented using rational curves. The example program nurbs_circle.c provides an example of representing circles as NURBS curves.

Knots and Parameter Range

A NURBS curve actually consists of a number of curve segments, each of which is defined by a polynomial curve defined by its Bezier coefficients. This characteristic of a NURBS curve provides local control over individual segments of the curve, since moving one control point of the B-spline affects only a small portion of the spline.

The knot sequence of the curve specifies the exact intervals in parameter space from which the curve segments are mapped into object space. A B-spline is said to be uniform if these intervals are all equal; otherwise, it is said to be non-uniform. The number of knots must equal the number of control points plus the order:

(number of knots) = (number of control points + order)

For example, a curve of order 4 with 6 control points may have the following uniform knot vector:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

A curve with the following knot vector is non-uniform:

[0, 0, 0, 0, 1.5, 2, 2, 4, 4, 4, 4]

If the application only wants to create a Bezier curve of order k, it should use the knot sequence [0,0, ..k times, 1,1, ..k times].

A non-uniform knot sequence not only provides control over the curve's shape, but, by having multiple knots at the same value, it also provides control over the continuity between individual Bezier segments. For a NURBS curve of order 4, if there is only one knot at given value, there is second derivative continuity between the Bezier segments on either side. If there are two knots, there is first order continuity. If there are three knots, there is positional continuity (the segments touch). If there are four knots, the curve is discontinuous at that point. Thus,

(degree of continuity at a knot) = (order - 1 - knot multiplicity)

The parameter range [umin,umax] specifies which portion of the curve is actually rendered. This is analogous to surface trimming. Figure 9-2 on page 207 shows a NURBS curve with a defined parameter range.

Figure 9-2

Rendering a NURBS Curve

An XGL NURBS curve is rendered by calling xgl_nurbs_curve() or by creating a geometry cache (Gcache) from input data and rendering the Gcache every time the view or attributes change. Rendering NURBS curves with Gcaches will significantly improve performance. See Chapter 17, "Caching Geometry" for information on geometry caches for XGL NURBS.

The NURBS curve primitive generates a curve of the specified order based on the list of knots in the parameter space, the list of control points, and the parametric range. The NURBS curve primitive is:

void xgl_nurbs_curve ( Xgl_ctx ctx, Xgl_nurbs_curve *curve, Xgl_bounds_f1d *range, /* optional */ Xgl_curve_color_spline *color_spline) /* optional */

where ctx is the current Context, curve is a pointer to the definition of the curve, range is a pointer to a structure defining the parametric limits of the curve, and color_spline is a pointer to an Xgl_curve_color_spline structure that defines a curve whose control points are color coordinates. range and color_spline are optional and can be set to NULL.

The curve definition is defined in the Xgl_nurbs_curve structure as:

typedef struct { Xgl_usgn32 order; /* Order of curve */ Xgl_usgn32 num_knots; /* Number of knots */ float *knot_vector; /* Knot vector */ Xgl_pt_list ctrl_pts; /* List of control points */ } Xgl_nurbs_curve;

In this structure, order is the curve order, which must be a positive integer. num_knots is the number of knots. knot_vector is a pointer to the knot vector. ctrl_pts is the array of control points. The control point coordinates are input as (x,y,z) for nonrational curves and (x,y,z,w) for rational curves.

The parameter range specifies which portion of the curve geometry is actually significant for display and picking. The range is defined in an Xgl_bounds_f1d structure:

typedef struct { float bmin; float bmax; } Xgl_bounds_f1d;

The minimum range value should not be greater than the maximum value, and both values should lie between knot_vector [order-1] and knot_vector [num_knots-order]. If the range parameter is NULL, the whole curve is displayed.

NURBS Curve Attributes

Conceptually, NURBS curves are rendered by evaluating a number of sample points on the curve (also known as tessellation) and displaying straight lines between adjacent points. The greater the number of these points, the more accurate and smooth the rendering will be. However, tessellating a curve into a greater number of segments increases rendering time.

XGL allows the application to specify the smoothness of the rendered curve (in other words, how finely tessellated the curve is), thus determining performance. XGL provides the application with two attributes that control tessellation. The application can:

• Specify an approximation type that defines the criteria that is used for tessellating the curve into lines (XGL_CTX_NURBS_CURVE_APPROX).
• Specify how finely the curve should be tessellated (XGL_CTX_CURVE_APPROX_VAL).

Approximation types can be dynamic or static. Dynamic approximation lets the XGL graphics system decide on the tessellation, based on the spatial relation of the curve to the eye and the complexity of the geometry. This means that portions of the curve that are nearer to the eye and portions that have a more complicated geometry will be tessellated into more numerous, smaller lines than other portions. It also means that the tessellation may change as the application changes the view or modeling transforms. Static approximation defines a constant number of lines for the tessellation of the curve.

The attribute XGL_CTX_NURBS_CURVE_APPROX enables the application to specify the approximation type using the following values:

XGL_CURVE_CONST_PARAM_SUBDIV_BETWEEN_KNOTS
   This attribute is a static approximation type because it specifies a fixed
   number of lines into which the curve is tessellated, between any two pair
   of knots.

XGL_CURVE_METRIC_WC
XGL_CURVE_METRIC_VDC
XGL_CURVE_METRIC_DC
   A metric dynamic approximation type specifies an upper limit on the size
   of the lines generated. The values may apply to world coordinates (WC),
   virtual device coordinates (VDC), or device coordinates (DC).

XGL_CURVE_CHORDAL_DEVIATION_WC
XGL_CURVE_CHORDAL_DEVIATION_VDC
XGL_CURVE_CHORDAL_DEVIATION_DC

A chordal deviation dynamic approximation type specifies an upper limit on the distance between the actual curve and the lines (chords) generated. The values may apply to world coordinates (WC), virtual device coordinates (VDC), or device coordinates (DC).

XGL_CURVE_RELATIVE_WC
XGL_CURVE_RELATIVE_VDC
XGL_CURVE_RELATIVE_DC

A relative dynamic approximation type indicates a relative quality of rendering quality to be maintained. The application can simply specify a value between 0 (lowest quality) to 1 (highest quality) for XGL_CTX_CURVE_APPROX_VAL, and let the XGL system figure out what metric and chordal deviation limits to use. The values may apply to world coordinates (WC), virtual device coordinates (VDC), or device coordinates (DC).

Figure 9-3 illustrates metric and chordal deviations.

Figure 9-3

Note that even in the case of dynamic tessellation, the number of points generated may sometimes be too large for interactive rendering. The application can control the number of points used to display the curve with the attributes XGL_CTX_MIN_TESSELLATION and XGL_CTX_MAX_TESSELLATION. These attributes provide a lower and upper limit respectively on the number of points computed between a pair of knots on the curve.

XGL_CTX_CURVE_APPROX_VAL sets the approximation value for the curve. Refer to the XGL Reference Manual for information on how the approximation value relates to various approximation types, and for limitations on the order of the curve for these approximation types.

Color Splines

Color can be associated with a NURBS curve via the xgl_nurbs_curve() color_spline field, which points to an Xgl_curve_color_spline structure. This structure defines a spline whose control points are color coordinates. The color coordinates can be in 3D (nonrational) or 3D+w (rational). The color for every evaluated point on the geometry spline is determined by evaluating the RGB value at the corresponding parameter value on the color spline. This color is the vertex color for each evaluated point on the geometry spline. The Context line rendering attributes determine how the vertex colors are used during curve rendering.

Curve Example Programs

The following example programs show the use of NURBS curves. Each example is a fragment of a larger program. The complete program includes nurbs_main.c and ex_utils.c, both of which are listed in Appendix B, as well as all the example programs listed in this chapter. To compile the complete program, type make nurbs in the example program directory.

Bezier Curve Example Program

The following program, nurbs_bezier.c, displays a Bezier curve using NURBS.

Figure 9-4 nurbs_bezier.c

Code Example 9-1 Bezier Curve Example

/*
 * nurbs_bezier.c
 */

#include <xgl/xgl.h>
#include "ex.h"

void
nurbs_bezier (Xgl_object   ctx)
{

    Xgl_pt_list     pl;
    Xgl_pt_f2d      pt[20];
    Xgl_nurbs_curve curve;
    Xgl_bounds_f1d  range;

    float           knot_v[20];
    Xgl_color       color_m,
                    color_l;

    /*
     * clear the drawing area
     */

    xgl_context_new_frame (ctx);

    /*
     * set various attributes for the context
     */
    color_m = white_color;
    xgl_object_set (ctx, XGL_CTX_VDC_MAP, XGL_VDC_MAP_ASPECT,
            XGL_CTX_MARKER_SCALE_FACTOR, 6.0,
            XGL_CTX_MARKER_COLOR, &color_m,
            XGL_CTX_MARKER_DESCRIPTION, xgl_marker_circle,
            XGL_CTX_DEFERRAL_MODE, XGL_DEFER_ASAP,
            NULL);

    /*
     * initialize the control points
     */

    pt[0].x = -0.8;
    pt[0].y = -0.6;
    pt[1].x = -0.4;
    pt[1].y = 0.4;
    pt[2].x = 0.4;
    pt[2].y = 0.4;
    pt[3].x = 0.8;
    pt[3].y = -0.6;

    pl.num_pts = 4;
    pl.pt_type = XGL_PT_F2D;
    pl.pts.f2d = pt;
    pl.bbox = (Xgl_bbox *) NULL;

    /*
     * initialize a uniform knot vector to render
     * a bezier curve. Note that for a Bezier curve,
     * the knots are all the end-points.
     */
    knot_v[0] = knot_v[1] = knot_v[2] = knot_v[3] = 0.0;
    knot_v[4] = knot_v[5] = knot_v[6] = knot_v[7] = 1.0;

    curve.num_knots = 8;
    curve.knot_vector = knot_v;
    curve.order = 4;
    curve.ctrl_pts = pl;
    range.bmin = 0.0;
    range.bmax = 1.0;

    /*
     * set the approximation criteria so that the rendered
     * curve should not deviate from the actual curve by more
     * than 1 pixel
     */

   xgl_object_set (ctx,
         XGL_CTX_NURBS_CURVE_APPROX, XGL_CURVE_CHORDAL_DEVIATION_DC,
         XGL_CTX_NURBS_CURVE_APPROX_VAL, 1.0,
         NULL);

    /*
     * draw the nurbs curve
     */

    color_l = yellow_color;
    xgl_object_set (ctx, XGL_CTX_LINE_COLOR, &color_l, NULL);

    xgl_nurbs_curve (ctx, &curve, &range, NULL);

    /*
     * draw a simple marker at each control point location.
     * Draw a polyline from the control points.
     */

    color_l = green_color;
    xgl_object_set (ctx,
            XGL_CTX_LINE_COLOR, &color_l,
            XGL_CTX_LINE_STYLE, XGL_LINE_PATTERNED,
            NULL);

    xgl_multimarker (ctx, &pl);
    xgl_multipolyline (ctx, (Xgl_bbox *) 0, 1, &pl);

    /*
     * compute the subdivision of the bezier control points to
     * verify that the curve corresponds to a Bernstein polynomial.
     */

    pt[4].x = (pt[0].x + pt[1].x) / 2.0;
    pt[4].y = (pt[0].y + pt[1].y) / 2.0;

    pt[5].x = (pt[1].x + pt[2].x) / 2.0;
    pt[5].y = (pt[1].y + pt[2].y) / 2.0;

    pt[6].x = (pt[2].x + pt[3].x) / 2.0;
    pt[6].y = (pt[2].y + pt[3].y) / 2.0;

    color_l = cyan_color;
    xgl_object_set (ctx, XGL_CTX_LINE_COLOR, &color_l, 0);
    pl.pts.f2d = &(pt[4]);
    pl.num_pts = 3;
    xgl_multipolyline (ctx, (Xgl_bbox *) 0, 1, &pl);

    pt[7].x = (pt[4].x + pt[5].x) / 2.0;
    pt[7].y = (pt[4].y + pt[5].y) / 2.0;

    pt[8].x = (pt[5].x + pt[6].x) / 2.0;
    pt[8].y = (pt[5].y + pt[6].y) / 2.0;

    color_l = magenta_color;
    xgl_object_set (ctx, XGL_CTX_LINE_COLOR, &color_l, 0);
    pl.pts.f2d = &(pt[7]);
    pl.num_pts = 2;
    xgl_multipolyline (ctx, (Xgl_bbox *) 0, 1, &pl);

    xgl_object_set (ctx, XGL_CTX_LINE_STYLE, XGL_LINE_SOLID, NULL);

}

Circle Curve Example Program

The following program, nurbs_circle.c, displays circles as curves using different approximation criteria.

Figure 9-5 nurbs_circle.c

Code Example 9-2 Circle Curve Example

/*
 * nurbs_circle.c
 */

#include <xgl/xgl.h>
#include <math.h>
#include "ex.h"

void            create_nurbs_circle (
                        float,
                        float,
                        float,
                        Xgl_nurbs_curve*,
                        Xgl_bounds_f1d*);

void
nurbs_circle (Xgl_object  ctx)
{

    Xgl_pt_list       pl;
    Xgl_pt_f2h        pt_w[20];
    Xgl_nurbs_curve   curve;
    Xgl_bounds_f1d    range;
    float             knot_v[20];
    Xgl_color         color_m,
                      color_l

    /*
     * clear the drawing area
     */

    xgl_context_new_frame (ctx);

    /*
     * set various attributes for the context
     */

    xgl_object_set (ctx, XGL_CTX_VDC_MAP, XGL_VDC_MAP_ASPECT,
                     XGL_CTX_DEFERRAL_MODE, XGL_DEFER_ASAP,
                     NULL);

    /*
     * draw four circles. for each:
     * 1. construct a circle of the same size at a different location
     * 2. use a different approximation criteria
     * 3. draw nurbs curve
     */

    pl.pt_type = XGL_PT_F2H;
    pl.pts.f2h = pt_w;
    curve.ctrl_pts = pl;
    curve.knot_vector = knot_v;

    /*
     * I. constant # subdivisions between knots (static tessellation)
     */

    color_l = green_color;
    xgl_object_set (ctx,
            XGL_CTX_NURBS_CURVE_APPROX,
            XGL_CURVE_CONST_PARAM_SUBDIV_BETWEEN_KNOTS,
            XGL_CTX_NURBS_CURVE_APPROX_VAL, 7.0,
            XGL_CTX_LINE_COLOR, &color_l,
            NULL);

    create_nurbs_circle (0.5, 0.0, 0.4, &curve, &range);
    xgl_nurbs_curve (ctx, &curve, &range, NULL);

    /*
     * II. relative "quality" measure (0 to 1) in DC.
     */

    color_l = white_color;
    xgl_object_set (ctx,
            XGL_CTX_NURBS_CURVE_APPROX,
            XGL_CURVE_RELATIVE_DC,
            XGL_CTX_NURBS_CURVE_APPROX_VAL, 0.9,
            XGL_CTX_LINE_COLOR, &color_l,
            NULL);

    create_nurbs_circle (0.0, 0.5, 0.4, &curve, &range);
    xgl_nurbs_curve (ctx, &curve, &range, NULL);

    /*
     * III. limit on size (in VDC - 0 to 1) of line segments generated
     */

    color_l = cyan_color;
    xgl_object_set (ctx,
            XGL_CTX_NURBS_CURVE_APPROX,
            XGL_CURVE_METRIC_VDC,
            XGL_CTX_NURBS_CURVE_APPROX_VAL, 0.2,
            XGL_CTX_LINE_COLOR, &color_l,
            NULL);

    create_nurbs_circle (-0.5, 0.0, 0.4, &curve, &range);
    xgl_nurbs_curve (ctx, &curve, &range, NULL);

    /*
     * IV. limit on deviation (in WC) of approximated curve from
     * actual
     */

    color_l = yellow_color;
    xgl_object_set (ctx,
            XGL_CTX_NURBS_CURVE_APPROX,
            XGL_CURVE_CHORDAL_DEVIATION_WC,
            XGL_CTX_NURBS_CURVE_APPROX_VAL, 0.02,
            XGL_CTX_LINE_COLOR, &color_l,
            NULL);

    create_nurbs_circle (0.0, -0.5, 0.4, &curve, &range);
    xgl_nurbs_curve (ctx, &curve, &range, NULL);

 }

/*
 * given a center and radius of a circle, create nurbs control pts
 * and knots. Asummes dynamic storage is pre-allocated.
 */

void
create_nurbs_circle (
   float              center_x,
   float              center_y,     /* input  */
   float              radius,
   Xgl_nurbs_curve    *curve,       /* output */
   Xgl_bounds_f1d     *range)
{

    float isqrt_2 = sqrt ((double) 0.5);
    Xgl_pt_f2h   *cpt;
    float        *knot;

    /*
     * initialize the control points
     */

    curve->order = 3;
    curve->ctrl_pts.num_pts = 9;
    curve->ctrl_pts.pt_type = XGL_PT_F2H;
    cpt = curve->ctrl_pts.pts.f2h;

    cpt[0].x = center_x + radius;

    cpt[0].y = center_y;
    cpt[0].w = 1.0;
    cpt[1].x = (center_x + radius) * isqrt_2;
    cpt[1].y = (center_y + radius) * isqrt_2;
    cpt[1].w = isqrt_2;
    cpt[2].x = center_x;
    cpt[2].y = center_y + radius;
    cpt[2].w = 1.0;
    cpt[3].x = (center_x - radius) * isqrt_2;
    cpt[3].y = (center_y + radius) * isqrt_2;
    cpt[3].w = isqrt_2;
    cpt[4].x = center_x - radius;
    cpt[4].y = center_y;
    cpt[4].w = 1.0;
    cpt[5].x = (center_x - radius) * isqrt_2;
    cpt[5].y = (center_y - radius) * isqrt_2;
    cpt[5].w = isqrt_2;
    cpt[6].x = center_x;
    cpt[6].y = center_y - radius;
    cpt[6].w = 1.0;
    cpt[7].x = (center_x + radius) * isqrt_2;
    cpt[7].y = (center_y - radius) * isqrt_2;
    cpt[7].w = isqrt_2;
    cpt[8].x = center_x + radius;
    cpt[8].y = center_y;
    cpt[8].w = 1.0;

    /*
     * use a nonuniform knot vector to render a circle.
     * recall the relation: # knots = # ctrl pts + order
     */

    curve->num_knots = 12;
    knot = curve->knot_vector;

    knot[0] = knot[1] = knot[2] = 0.;
    knot[3] = knot[4] = 1.;
    knot[5] = knot[6] = 2.;
    knot[7] = knot[8] = 3.;
    knot[9] = knot[10] = knot[11] = 4.;

    range->bmin = 0.;
    range->bmax = 4.;
}

NURBS Surfaces

A NURBS surface is a mapping from two-dimensional parameter space into object space. The NURBS surface is rendered as a set of triangles. Various attributes can be set to control the display of the surface.

---

Note - Some of the geometry and attributes for NURBS surfaces are logical extensions of NURBS curve geometry and attributes. This section assumes that you have read the section on NURBS curves; therefore, not all of the information covered in that section is repeated here.

---

Mathematical Description of a NURBS Surface

A NURBS surface is mathematically defined by:

1. A two-dimensional grid of control points.

2. The order of the surface in u and v.

3. Knot sequences in u and v (the two dimensions of the parameter space).

4. Trimming information that specifies which portion of the rectangular parameter space is actually mapped to object space.

The surface is defined by:

n m

S (u, v) =...B . .

(u) B (v) P i, k..j, l..i, j

(EQ 2)

i = 1j = 1

where

S(u,v) is the surface;

P are an (n . m) array of control points; i,j

u and v are the two parameters;

Bi,k (u) is the i-th B-spline basis function of order k, defined by the knot vector {up} (p = 1 to n+k);

Bj,l (v) is the j-th B-spline basis function of order l, defined by the knot vector {vq} (q = 1 to m+l)

The B-spline basis functions are defined by the orders k and l, and their respective non-decreasing knot sequences.

For more information on the mathematics of B-spline surfaces, refer to Curves and Surfaces for Computer Aided Geometric Design by Gerald Farin, Second Edition, Academic Press, Inc., San Diego, CA, 1990. The following sections discuss surface control points and knot vectors.

Control Points

The above mathematical definition of a NURBS surface is best understood by considering it as an extension to the definition of a NURBS curve, since the inner loop of equation EQ2 is simply the definition of a NURBS curve. If you start with a NURBS curve and sweep the curve in an orthogonal direction by defining a NURBS curve path for each control point, the path swept by the original curve defines the surface.

The control points (Pi,j) may be defined in Cartesian or homogeneous coordinates. Accordingly, the surface is said to be non-rational or rational. As in

the case of curves, the actual surface follows the shape of the control polygon. Simple geometry such as planar or conics (spherical, cylindrical) can only be represented using rational surfaces.

Knots

Just as a NURBS curve consists of a number of curve segments, a NURBS surface consists of surface segments called patches. The u and v knot sequences define a grid in two-dimensional parameter space and specify the exact intervals in parameter space from which the segments are mapped onto object space. A B-spline is said to be uniform if all u knot intervals are equal, and all v knot intervals are equal; otherwise, it is said to be non-uniform. Refer to page 206 for more details on knot vectors.

Rendering a NURBS Surface

A NURBS surface is specified and rendered by calling xgl_nurbs_surface() or by creating a geometry cache (Gcache) from input data and rendering the Gcache every time the view or attributes changes. Using a Gcache for rendering will significantly increase performance. See Chapter 17, "Caching Geometry" for information on geometry caches for XGL NURBS.

The NURBS surface primitive is:

void xgl_nurbs_surface ( Xgl_ctx ctx, Xgl_nurbs_surf *surface, Xgl_trim_loop_list *trimming, /* optional */ Xgl_nurbs_surf_simple_geom *hints, /* optional */ Xgl_surf_color_spline *color_spline, /* optional*/ Xgl_surf_data_spline_list *data_splines) /* not implemented */

In this structure, ctx is the current Context, surface is a pointer to the definition of the surface, trimming is a pointer to a structure defining the surface trimming information, and hints is a pointer to a structure providing information about the shape of the surface. color_spline is a pointer to a NURBS surface whose control points are color coordinates.

The Xgl_nurbs_surf structure is defined as:

typedef struct { Xgl_usgn32 order_u; /* Order of surface in u */ Xgl_usgn32 order_v; /* Order of surface in v */ Xgl_usgn32 num_knots_u; /* Number of knots in u */ float *knot_vector_u;/* Knot vector in u */ Xgl_usgn32 num_knots_v; /* Number of knots in v */ float *knot_vector_v;/* Knot vector in v */ Xgl_pt_list ctrl_pts; /* Row-ordered list of control points (index changes faster in u than v) */ } Xgl_nurbs_surf;

This structure gives the order of the surface, the surface u and v directions, the number of knots in the u and v parameters, the knot vectors in the u and v directions, and the array of control points for the surface.

Surface Trimming

B-spline surface mapping is defined on a two-dimensional parameter space rectangle defined by the knot vectors. Figure 9-6 on page 225 shows an untrimmed surface and the grid of control points.

Not all real-life surfaces have a rectangular topology. To define a non-rectangular surface, a set of trimming loops can be specified to carve out portions of the rectangular region. Only the portion enclosed by trimming loops is significant (rendered), and the rest of the surface is discarded. If no trimming is specified, the entire rectangular region is displayed.

Each trimming loop consists of one or more trimming curves. Trimming curves are NURBS curves in 2D parameter space joined in a head-to-tail fashion. The trimming loop should be continuous, closed, and should not intersect itself or another trimming loop. In general, an individual trimming curve on a trimming loop should only touch another trimming curve or itself when they are adjacent in a trimming loop, and then only at their endpoints. However, XGL's NURBS implementation allows trimming curves to touch at isolated points as long as they do not coincide along any finite length.

Figure 9-6

Trimming curves define a mapping from a one-dimensional parameter space to the two-dimensional parameter space of the surface. Refer to the section on NURBS curves for the definition and properties of curves used as trimming curves. Trimming curves should have an order greater than 1.

The significant region of the trimmed surface is doubly defined through the following rules:

1. Odd Winding Rule: A point is in the significant region if a ray projected from that point in any direction has an odd number of intersections with the set of trimming loops.

2. Curve Orientation Rule: For any given directed trimming loop, the significant region is "to the left", and the outside region is "to the right". What this means is that if the trimming curve is in a clockwise direction, the region of the surface inside the trimming curve is not rendered. If the trimming curve is counterclockwise, the region of the surface inside the trimming curve is rendered. For the definition of the terms "to the left" and "to the right", see the PHIGS PLUS documentation.

Figure 9-7 shows trimming loops in the surface's parameter space.

Figure 9-7

The NURBS implementation handles wrong trimming input by flagging errors and using a "recover and display as much as possible" philosophy. If a trimming loop is not continuous, the trimming curves are adjusted to close the loop. XGL attempts to localize other trimming input errors by displaying as much of the trimmed surface as possible and treating the "wrong" portions as untrimmed.

Figure 9-8 on page 227 shows a trimmed surface.

Figure 9-8

Performance Hints for Simple Geometry

A majority of real-life surfaces, especially in mechanical CAD, are fairly simple. They may be just planar, or they may be conics (spherical, cylindrical, conical). Even so, the application may want to use NURBS to represent surfaces because of the generality of NURBS and the ability to trim these surfaces. For example, a trimmed NURBS representation is well suited to represent the surfaces of the Boolean intersection of a cylinder and a cone.

Even though the NURBS representation is adequate for display, the graphical processing (in particular, the computation of surface normals for lighting) can be speeded up considerably if the application lets XGL know about the original simple geometry. For example, if the XGL software knows that a given NURBS surface is spherical, it can compute the normal at a given point on the surface

by simply taking the vector from the center of the sphere to the given point, instead of taking the cross product of the derivative surface functions. This can speed up display substantially.

Thus, in addition to giving the control points, knot vectors, and trimming information, the application can optionally provide hints about the original geometry via the hints field of the xgl_nurbs_surface() primitive. This field points to an Xgl_nurbs_surf_simple_geom structure that provides information on the type of surface and the original geometry. Table 9-1 lists the available surface types and the geometry required.

Table 9-1

Surface	Geometry Hints
Planar	Surface normal
Cylindrical	Point on axis, axis direction, radius, flag indicating the front and back sides of the surface
Conical	Apex, axis direction, cone angle, flag indicating the front and back sides of the surface
Spherical	Center, radius, flag indicating the front and back sides of the surface

If the geometry hints are inconsistent with the NURBS information, the surface may be shaded wrongly. Please refer to the XGL Reference Manual for information on the data structures used for surface hints.

NURBS Surface Attributes

Just as NURBS curves are rendered as a set of lines, NURBS surfaces are rendered by evaluating the surface at a number of points and generating triangles. XGL enables the application to control the smoothness of the surface tessellation using the following attributes:

• XGL_CTX_NURBS_SURF_APPROX, which specifies the criteria uses for tessellation.
• XGL_CTX_NURBS_SURF_APPROX_VAL_U and XGL_CTX_NURBS_SURF_APPROX_VAL_V, which supply u and v values for tessellation.

XGL_CTX_NURBS_SURF_APPROX gives the application a choice of the following surface approximation types:

XGL_SURF_CONST_PARAM_SUBDIV_BETWEEN_KNOTS
   A static approximation type analogous to the curve approximation type
   XGL_CURVE_CONST_PARAM_SUBDIV_BETWEEN_KNOTS.

XGL_SURF_METRIC_WC
XGL_SURF_METRIC_VDC
XGL_SURF_METRIC_DC
   A dynamic approximation type analogous to the curve metric
   approximation types. The values may apply to world coordinates (WC),
   virtual device coordinates (VDC), or device coordinates (DC).

XGL_SURF_CHORDAL_DEVIATION_WC
XGL_SURF_CHORDAL_DEVIATION_VDC
XGL_SURF_CHORDAL_DEVIATION_DC
   A dynamic approximation type analogous to the curve chordal deviation
   approximation types. The values may apply to world coordinates (WC),
   virtual device coordinates (VDC), or device coordinates (DC).

XGL_SURF_RELATIVE_WC
XGL_SURF_RELATIVE_VDC
XGL_SURF_RELATIVE_DC

A dynamic approximation type analogous to the curve relative approximation types. The values may apply to world coordinates (WC), virtual device coordinates (VDC), or device coordinates (DC).

XGL_CTX_NURBS_SURF_APPROX_VAL_{U,V} sets the approximation quality of NURBS surfaces as follows:

• For constant parametric approximation, the attribute represents the number of subdivisions of the surface.
• For metric approximation, the attribute represents a maximum distance between two points in the u or v parametric directions.
• For chordal deviation approximation, the attribute sets the maximum deviation between the surface and the approximation. Only XGL_CTX_NURBS_SURF_APPROX_VAL_U is used.
• For relative approximations, the attribute sets a relative quality measure. Only XGL_CTX_NURBS_SURF_APPROX_VAL_U is used

As in the case of curves, the application can specify limits on the number of sample points generated between two consecutive u/v knot values using XGL_CTX_MIN_TESSELLATION and XGL_CTX_MAX_TESSELLATION.

Refer to page 208 for the descriptions of the curve approximation types. Refer to the XGL Reference Manual for more information on how the approximation values relate to the approximation types.

Controlling the Appearance of Trimming Curves

The approximation criteria for trimming curves are specified as part of the trimming curve geometry itself so that individual trimming curves may have their own properties. A trimming curve is defined as follows:

typedef struct { /* control points, knot vector, parameter range: same as for NURBS curves */ Xgl_usgn32 order; Xgl_usgn32 num_knots; float *knot_vector; Xgl_bounds_f1d range; Xgl_pt_list ctrl_pts; /* * trimming curve structure fields */ Xgl_boolean trim_curve_vis; /* Highlight trim curve*/ Xgl_trim_curve_approx trim_curve_approx; /* Approx type */ float trim_curve_approx_value; /*Approx value*/ } Xgl_trim_curve;

The Xgl_trim_curve_approx structure is defined as:

typedef enum { XGL_TRIM_CURVE_CONST_PARAM_SUBDIV_BETWEEN_KNOTS; /* static tessellation */ XGL_TRIM_CURVE_VIEW_DEPENDENT; /* dynamic tessellation */ } Xgl_trim_curve_approx;

In the case of XGL_TRIM_CURVE_CONST_PARAM_SUBDIV_BETWEEN_KNOTS, a fixed number of points to be sampled between two knot values of the trimming curve is given by the field trim_curve_approx_value.

XGL_TRIM_CURVE_VIEW_DEPENDENT is a dynamic approximation type that allows XGL to decide on the number of sample points for a curve by considering the tessellation of the portion of the surface it lies on and the geometry of the curve itself. In this case, the trim_curve_approx_value field should provide a number between 0 and 1. This number is mapped to a size threshold in parameter space. A step size is computed for the trim curve using this threshold as well as the subdivisions of the portion of the surface it lies on. This ensures that the trimmed surface is tessellated well in cases when the trimming curve geometry is more complicated than the underlying surface, or vice versa.

The trimming curves constitute the boundaries of the surface. If the surface is not trimmed, the parametric limits constitute the boundaries. These boundaries are rendered using edge attributes. The trim_curve_vis flag is used to control the visibility of individual trim curves. If the front/back surface fill style (as defined by XGL_3D_CTX_SURF_BACK_FILL_STYLE or XGL_CTX_SURF_FRONT_FILL_STYLE) is XGL_SURF_FILL_HOLLOW, the surface is rendered only along these surface boundaries.

NURBS Surface Parametric Style

In addition to specifying the interior surface fill style and trimming edges, XGL allows the application to enhance the display of the NURBS surface using the XGL_CTX_NURBS_SURF_PARAM_STYLE attribute. This attribute can take the following values:

XGL_SURF_PLAIN No additional lines or edges are displayed on the surface. This is the default value.

XGL_SURF_ISO_CURVES Isoparametric curves are drawn on the surface. This attribute allows the application to specify that a fixed number of lines be drawn over the surface to give a wireframe appearance. The placement of the isoparametric curves is specified with the attribute XGL_CTX_NURBS_SURF_ISO_PLACEMENT, which can take the following values:

• XGL_ISO_CURVE_BETWEEN_KNOTS: Lines are uniformly spaced between two consecutive knots.
• XGL_ISO_CURVE_BETWEEN_LIMITS: Lines are uniformly spaced over the entire surface.

The number of lines in u and v directions is specified with the attributes

  XGL_CTX_NURBS_SURF_ISO_CURVE_U_NUM and
  XGL_CTX_NURBS_SURF_ISO_CURVE_V_NUM. These lines have polyline
  attributes and are rendered on top of the shaded surface (if the latter is
  displayed), but they have lower priority than the edges of the surface.

XGL_SURF_SHOW_TESSELLATION
  Edges of all tessellated facets are drawn using edge attributes. This is useful
  in visualizing the approximated surface.

XGL_SURF_INCR_SILHOUETTE_TESS For better rendering quality, the surface is tessellated more finely near areas of silhouette edges. This value is valid only for dynamic surface approximation types and is ignored for static approximation types.

XGL_SURF_DEVICE_DEPENDENT Same as XGL_SURF_PLAIN. No additional lines or edges are rendered.

A combination that is often used to implement wireframe mode is to turn off lighting, turn on edges, and display isoparametric lines.

Color Surfaces

Color can be associated with a NURBS surface via the xgl_nurbs_surface() color_spline field, which points to an Xgl_surf_color_spline structure. This structure defines a surface whose control points are color coordinates. The color coordinates can be in 3D (nonrational) or 3D+w (rational). The color for every evaluated point on the geometry surface is determined by evaluating the RGB value at the corresponding parameter value on the color surface. This color is the vertex color for each evaluated point on the geometry surface. The Context surface illumination attributes determine how the vertex colors are used during surface rendering.

If the color spline data is not provided for a surface, surface front/back color is used instead, and surface illumination is based only on intrinsic color.

Displaying Silhouettes on NURBS Surfaces

An application can display the silhouette edges between visible and hidden portions of the surface by setting the XGL_3D_CTX_SURF_SILHOUETTE_EDGE_FLAG attribute in the Context to TRUE. Because the human eye is sensitive to areas near silhouette edges, finer tessellation in these areas may be needed. The XGL_SURF_INCR_SILHOUETTE_TESS value of the attribute XGL_CTX_NURBS_SURF_PARAM_STYLE can be used to increase the tessellation near silhouette edges. Note that setting this value does not have any effect for static approximation types.

The XGL_3D_CTX_SURF_SILHOUETTE_EDGE_FLAG and XGL_SURF_INCR_SILHOUETTE_TESS attributes are independent of each other. If XGL_SURF_INCR_SILHOUETTE_TESS is set, but XGL_3D_CTX_SURF_SILHOUETTE_EDGE_FLAG is not set, areas near silhouette edges will be tessellated more finely, but the silhouette edges themselves will not be displayed.

If the surface has discontinuous first derivatives in either the u or v directions, silhouette edges may be displayed incorrectly. If the multiplicity of each internal knot is less than or equal to the order of the surface minus 2 in each direction, the surface will always have continuous first derivatives.

Surface Example Program

The following example program shows a trimmed sphere. The example is a fragment of a larger program, which includes nurbs_main.c and ex_utils.c, both of which are listed in Appendix B, as well as all the example programs listed in this chapter. To compile the complete program, type make nurbs in the example program directory.

Figure 9-9 nurbs_sphere.c

Code Example 9-3 NURBS Surface Example

/*
 * nurbs_sphere.c
 */

#include <xgl/xgl.h>
#include "ex.h"

/* data values for surface parameters */

/* knot vectors */

static float      knot_vector_u[10]     = {-1,-1,-1,0,0,1,1,2,2,2};
static float      knot_vector_v[8]      = {-1,-1,-1,0,0,1,1,1};

/* control points for sphere centered at origin with radius 0.5 */

static Xgl_pt_f3h ctrl_pts_arr[35]      = {

   { 0,          0,          -1.41421,          2.82843 },
   { 0,          0,          -0.707107,         1.41421 },
   { 0,          0,          -1.41421,          2.82843 },
   { 0,          0,          -0.707107,         1.41421 },
   { 0,          0,          -1.41421,          2.82843 },
   { 0,          0,          -0.707107,         1.41421 },
   { 0,          0,          -1.41421,          2.82843 },

   { -1.0,       0,          -1.0,              2       },
   { -0.5,       -0.866025,  -0.5,              1       },
   { 0.5,        -0.866025,  -1.0,              2       },
   { 1.0,        0,          -0.5,              1       },
   { 0.5,        0.866025,   -1.0,              2       },
   { -0.5,       0.866025,   -0.5,              1       },
   { -1.0,       0,          -1.0,              2       },

   {-1.41421,    0,          0,                 2.82843 },
   {-0.707107,   -1.22474,   0,                 1.41421 },
   { 0.707107,   -1.22474,   0,                 2.82843 },
   { 1.41421,    0,          0,                 1.41421 },
   { 0.707107,   1.22474,    0,                 2.82843 },
   { -0.707107,  1.22474,    0,                 1.41421 },
   { -1.41421,   0,          0,                 2.82843 },

   { -1.0,       0,          1.0,               2       },
   { -0.5,       -0.866025,  0.5,               1       },
   { 0.5,        -0.866025,  1.0,               2       },
   { 1.0,        0,          0.5,               1       },
   { 0.5,        0.866025,   1.0,               2       },
   { -0.5,       0.866025,   0.5,               1       },
   { -1.0,       0,          1.0,               2       },

   { 0,          0,          1.41421,           2.82843 },
   { 0,          0,          0.707107,          1.41421 },
   { 0,          0,          1.41421,           2.82843 },
   { 0,          0,          0.707107,          1.41421 },
   { 0,          0,          1.41421,           2.82843 },
   { 0,          0,          0.707107,          1.41421 },
   { 0,          0,          1.41421,           2.82843 }
};

/* trimming curves data */
static float      trim_knot_vector1[7]  = {0,0,1,2,3,4,4};
static float      trim_knot_vector2[12] = {0,0,0,1,1,2,2,3,3,4,4,4};

/* boundaries of the surface parameters range */
static Xgl_pt_f2d trim_ctrl_arr1[5]     =
{
   {-1,-1}, {2,-1}, {2,1}, {-1,1}, {-1,-1}
};

/* control points for a circle centered at (0,0) with radius 0.5 */
static Xgl_pt_f2h trim_ctrl_arr2[9]     = {
   { 0.5,          0,          1        },
   { 0.353553,     -0.353553,  0.707107 },
   { 0,            -0.5,       1        },
   { -0.353553,    -0.353553,  0.707107 },
   { -0.5,         0,          1        },
   { -0.353553,    0.353553,   0.707107 },
   { 0,            0.5,        1        },
   { 0.353553,     0.353553,   0.707107 },
   { 0.5,          0,          1        }
};

void
nurbs_sphere (Xgl_object               ctx)
{

   Xgl_nurbs_surf                      surface;
   Xgl_trim_loop_list                  trimming;
   Xgl_nurbs_surf_simple_geom          hints;
   Xgl_trim_loop                       trim_loop[2];
   Xgl_trim_curve                      trim_curves1, trim_curves2;

   /* Fill in the surface data structure */

   surface.order_u = 3;
   surface.order_v = 3;
   surface.num_knots_u = 10;
   surface.num_knots_v = 8;
   surface.knot_vector_u = knot_vector_u;
   surface.knot_vector_v = knot_vector_v;
   surface.ctrl_pts.pt_type = XGL_PT_F3H;
   surface.ctrl_pts.bbox = NULL;
   surface.ctrl_pts.num_pts = 35;
   surface.ctrl_pts.pts.f3h = ctrl_pts_arr;

 /* Fill in the trimcurve data structure */
   trim_curves1.order = 2;
   trim_curves1.num_knots = 7;
   trim_curves1.knot_vector = trim_knot_vector1;
   trim_curves1.range.bmin = 0.0;
   trim_curves1.range.bmax = 4.0;
   trim_curves1.ctrl_pts.pt_type = XGL_PT_F2D;
   trim_curves1.ctrl_pts.bbox = NULL;
   trim_curves1.ctrl_pts.num_pts = 5;
   trim_curves1.ctrl_pts.pts.f2d = trim_ctrl_arr1;
   trim_curves1.trim_curve_vis = FALSE;
   trim_curves1.trim_curve_approx = XGL_TRIM_CURVE_VIEW_DEPENDENT;
   trim_curves1.trim_curve_approx_value = 0.5;

   trim_curves2.order = 3;
   trim_curves2.num_knots = 12;
   trim_curves2.knot_vector = trim_knot_vector2;
   trim_curves2.range.bmin = 0.0;
   trim_curves2.range.bmax = 4.0;
   trim_curves2.ctrl_pts.pt_type = XGL_PT_F2H;
   trim_curves2.ctrl_pts.bbox = NULL;
   trim_curves2.ctrl_pts.num_pts = 9;
   trim_curves2.ctrl_pts.pts.f2h = trim_ctrl_arr2;
   trim_curves2.trim_curve_vis = FALSE;
   trim_curves2.trim_curve_approx = XGL_TRIM_CURVE_VIEW_DEPENDENT;
   trim_curves2.trim_curve_approx_value = 0.5;

   trim_loop[0].num_curves = 1;
   trim_loop[0].curves = &trim_curves1;
   trim_loop[1].num_curves = 1;
   trim_loop[1].curves = &trim_curves2;

   trimming.num_loops = 2;
   trimming.trim_loops = trim_loop;

   /* Fill in the hints data structure */

   hints.surf_type = XGL_SURF_SPHERICAL;
   hints.geom_desc.spherical.center.x = 0.0;
   hints.geom_desc.spherical.center.y = 0.0;
   hints.geom_desc.spherical.center.z = 0.0;
   hints.geom_desc.spherical.radius = 0.5;
   hints.geom_desc.spherical.norm_flag = TRUE;

   /* Set various context attributes */

  xgl_object_set (ctx,
    XGL_CTX_VDC_MAP, XGL_VDC_MAP_ASPECT,
    XGL_CTX_NURBS_SURF_APPROX, XGL_SURF_RELATIVE_DC,
    XGL_CTX_NURBS_SURF_APPROX_VAL_U, 0.5,
    XGL_CTX_NURBS_SURF_PARAM_STYLE, XGL_SURF_ISO_CURVES,
    XGL_CTX_NURBS_SURF_ISO_CURVE_PLACEMENT,
    XGL_ISO_CURVE_BETWEEN_LIMITS,
    XGL_CTX_NURBS_SURF_ISO_CURVE_U_NUM, 15,
    XGL_CTX_NURBS_SURF_ISO_CURVE_V_NUM, 15,
    XGL_CTX_SURF_FRONT_FILL_STYLE, XGL_SURF_FILL_SOLID,
    XGL_3D_CTX_SURF_FACE_CULL, XGL_CULL_BACK,
    XGL_CTX_MARKER_SCALE_FACTOR, 6.0,
    XGL_CTX_MARKER_COLOR, &white_color,
    XGL_CTX_MARKER_DESCRIPTION, xgl_marker_circle,
    0);

   /* draw control points as markers */
   xgl_multimarker (ctx, &surface.ctrl_pts);

   /* Finally, draw the surface */
   xgl_nurbs_surface (ctx, &surface, &trimming, &hints, NULL, NULL);
}

Using Geometry Cache for Curve and Surface Rendering

The preceding sections of this chapter discussed rendering NURBS curves and surfaces directly. Improved performance for NURBS curve and surface rendering can be achieved using a Geometry Cache object. As described in Chapter 17, "Caching Geometry", a Gcache object is used to store an XGL primitive and break it down into a simpler form for fast, per-frame display.

The application has the choice of creating a Gcache that stores a tessellation-independent form of the curve or surface, which is dynamically tessellated into lines or triangles each time the curve or surface is displayed, a tessellated form of the curve or surface, or a combination of forms in which tessellation is regenerated only when necessary. The application can choose the appropriate mode depending on memory availability, speed and display quality requirements, or the complexity of NURBS data and viewing requirements. For more information on NURBS Gcache objects, refer to Chapter 17, "Caching Geometry" or the XGL Reference Manual.

Getting the Best Out of XGL NURBS

The following tips will enable an application to get the best performance using the XGL NURBS implementation.

• Performance with NURBS curves and surfaces may be significantly improved using Gcache objects. If the application creates a NURBS Gcache once, and then calls xgl_display_gcache() for every frame, performance will increase by an order of magnitude because substantial preprocessing is performed when the Gcache is created. See Chapter 17, "Caching Geometry" for information on Gcache objects and Gcache NURBS operators and attributes.
• As mentioned on page 227, if the application supplies hints about simple surface geometry, a major performance improvement can be expected when there is lighting and shading.
• Enabling clipping will instruct XGL to discard portions of the NURBS outside of the clipping region. This will considerably speed up the display.
• Using front/back face culling will speed up display substantially.
• If the device does not have fast triangle shading, wireframe mode can be simulated by turning off lighting, turning on edge display, and specifying isoparametric lines. Further, if the surface interior fill style is XGL_SURF_FILL_SOLID, a hidden-line image is generated.
• Using static approximation types (as opposed to dynamic approximation types) may not yield any performance gain. In fact, in cases where there are substantial view changes and zooms, a fixed approximation value does not make much sense. The application is encouraged to use dynamic approximation types, especially the RELATIVE types. By taking advantage of this simple rendering quality measure, the application can trade-off speed for display quality.