Компьютерлік графикада қисықтар мен беттерді бейнелеу әдісі

Method of representing curves and surfaces in computer graphics

Non uniform rational basis spline (NURBS) is a mathematical model using basis splines (B splines) that is commonly used in computer graphics for representing curves and surfaces. It offers great flexibility and precision for handling both analytic (defined by common mathematical formulae) and modeled shapes. It is a type of curve modeling, as opposed to polygonal modeling or digital sculpting. NURBS curves are commonly used in computer aided design (CAD), manufacturing (CAM), and engineering (CAE). They are part of numerous industry wide standards, such as IGES, STEP, ACIS, and PHIGS. Tools for creating and editing NURBS surfaces are found in various 3D graphics, rendering, and animation software packages. They can be efficiently handled by computer programs yet allow for easy human interaction. NURBS surfaces are functions of two parameters mapping to a surface in three dimensional space. The shape of the surface is determined by control points. In a compact form, NURBS surfaces can represent simple geometrical shapes. For complex organic shapes, T splines and subdivision surfaces are more suitable because they halve the number of control points in comparison with the NURBS surfaces. In general, editing NURBS curves and surfaces is intuitive and predictable. Control points are always either connected directly to the curve or surface, or else act as if they were connected by a rubber band. Depending on the type of user interface, the editing of NURBS curves and surfaces can be via their control points (similar to Bézier curves) or via higher level tools such as spline modeling and hierarchical editing.

Before computers, designs were drawn by hand on paper with various drafting tools. Rulers were used for straight lines, compasses for circles, and protractors for angles. But many shapes, such as the freeform curve of a ship's bow, could not be drawn with these tools. Although such curves could be drawn freehand at the drafting board, shipbuilders often needed a life size version which could not be done by hand. Such large drawings were done with the help of flexible strips of wood, called splines. The splines were held in place at a number of predetermined points, called "ducks" (which were made of lead and about 3 inches long: the "beak" of the "duck" pushed against the spline; the old yacht design books assumed these methods); between the ducks, the elasticity of the spline material caused the strip to take the shape that minimized the energy of bending, thus creating the smoothest possible shape that fit the constraints. The shape could be adjusted by moving the ducks. In 1946, mathematicians started studying the spline shape, and derived the piecewise polynomial formula known as the spline curve or spline function. I. J. Schoenberg gave the spline function its name after its resemblance to the mechanical spline used by draftsmen. As computers were introduced into the design process, the physical properties of such splines were investigated so that they could be modelled with mathematical precision and reproduced where needed. Pioneering work was done in France by Renault engineer Pierre Bézier, and Citroën's physicist and mathematician Paul de Casteljau. They worked nearly parallel to each other, but because Bézier published the results of his work, Bézier curves were named after him, while de Casteljau's name is only associated with related algorithms. NURBS were initially used only in the proprietary CAD packages of car companies. Later they became part of standard computer graphics packages. Real time, interactive rendering of NURBS curves and surfaces was first made commercially available on Silicon Graphics workstations in 1989. In 1993, the first interactive NURBS modeller for PCs, called NöRBS, was developed by CAS Berlin, a small startup company cooperating with the Technical University of Berlin.

The order of a NURBS curve defines the number of nearby control points that influence any given point on the curve. The curve is represented mathematically by a polynomial of degree one less than the order of the curve. Hence, second order curves (which are represented by linear polynomials) are called linear curves, third order curves are called quadratic curves, and fourth order curves are called cubic curves. The number of control points must be greater than or equal to the order of the curve. In practice, cubic curves are the ones most commonly used. Fifth and sixth order curves are sometimes useful, especially for obtaining continuous higher order derivatives, but curves of higher orders are practically never used because they lead to internal numerical problems and tend to require disproportionately large calculation times.

The control points determine the shape of the curve. Typically, each point of the curve is computed by taking a weighted sum of a number of control points. The weight of each point varies according to the governing parameter. For a curve of degree d, the weight of any control point is only nonzero in d+1 intervals of the parameter space. Within those intervals, the weight changes according to a polynomial function (basis functions) of degree d. At the boundaries of the intervals, the basis functions go smoothly to zero, the smoothness being determined by the degree of the polynomial. As an example, the basis function of degree one is a triangle function. It rises from zero to one, then falls to zero again. While it rises, the basis function of the previous control point falls. In that way, the curve interpolates between the two points, and the resulting curve is a polygon, which is continuous, but not differentiable at the interval boundaries, or knots. Higher degree polynomials have correspondingly more continuous derivatives. Note that within the interval the polynomial nature of the basis functions and the linearity of the construction make the curve perfectly smooth, so it is only at the knots that discontinuity can arise. In many applications the fact that a single control point only influences those intervals where it is active is a highly desirable property, known as local support. In modeling, it allows the changing of one part of a surface while keeping other parts unchanged. Adding more control points allows better approximation to a given curve, although only a certain class of curves can be represented exactly with a finite number of control points. NURBS curves also feature a scalar weight for each control point. This allows for more control over the shape of the curve without unduly raising the number of control points. In particular, it adds conic sections like circles and ellipses to the set of curves that can be represented exactly. The term rational in NURBS refers to these weights. The control points can have any dimensionality. One dimensional points just define a scalar function of the parameter. These are typically used in image processing programs to tune the brightness and color curves. Three dimensional control points are used abundantly in 3D modeling, where they are used in the everyday meaning of the word 'point', a location in 3D space. Multi dimensional points might be used to control sets of time driven values, e. g. the different positional and rotational settings of a robot arm. NURBS surfaces are just an application of this. Each control 'point' is actually a full vector of control points, defining a curve. These curves share their degree and the number of control points, and span one dimension of the parameter space. By interpolating these control vectors over the other dimension of the parameter space, a continuous set of curves is obtained, defining the surface.

The knot vector is a sequence of parameter values that determines where and how the control points affect the NURBS curve. The number of knots is always equal to the number of control points plus curve degree plus one (i. e. number of control points plus curve order). The knot vector divides the parametric space in the intervals mentioned before, usually referred to as knot spans. Each time the parameter value enters a new knot span, a new control point becomes active, while an old control point is discarded. It follows that the values in the knot vector should be in nondecreasing order, so (0, 0, 1, 2, 3, 3) is valid while (0, 0, 2, 1, 3, 3) is not. Consecutive knots can have the same value. This then defines a knot span of zero length, which implies that two control points are activated at the same time (and of course two control points become deactivated). This has impact on continuity of the resulting curve or its higher derivatives; for instance, it allows the creation of corners in an otherwise smooth NURBS curve. A number of coinciding knots is sometimes referred to as a knot with a certain multiplicity. Knots with multiplicity two or three are known as double or triple knots. The multiplicity of a knot is limited to the degree of the curve; since a higher multiplicity would split the curve into disjoint parts and it would leave control points unused. For first degree NURBS, each knot is paired with a control point. The knot vector usually starts with a knot that has multiplicity equal to the order. This makes sense, since this activates the control points that have influence on the first knot span. Similarly, the knot vector usually ends with a knot of that multiplicity. Curves with such knot vectors start and end in a control point. The values of the knots control the mapping between the input parameter and the corresponding NURBS value. For example, if a NURBS describes a path through space over time, the knots control the time that the function proceeds past the control points. For the purposes of representing shapes, however, only the ratios of the difference between the knot values matter; in that case, the knot vectors (0, 0, 1, 2, 3, 3) and (0, 0, 2, 4, 6, 6) produce the same curve. The positions of the knot values influences the mapping of parameter space to curve space. Rendering a NURBS curve is usually done by stepping with a fixed stride through the parameter range. By changing the knot span lengths, more sample points can be used in regions where the curvature is high. Another use is in situations where the parameter value has some physical significance, for instance if the parameter is time and the curve describes the motion of a robot arm. The knot span lengths then translate into velocity and acceleration, which are essential to get right to prevent damage to the robot arm or its environment. This flexibility in the mapping is what the phrase non uniform in NURBS refers to. Necessary only for internal calculations, knots are usually not helpful to the users of modeling software. Therefore, many modeling applications do not make the knots editable or even visible. It's usually possible to establish reasonable knot vectors by looking at the variation in the control points. More recent versions of NURBS software (e. g., Autodesk Maya and Rhinoceros 3D) allow for interactive editing of knot positions, but this is significantly less intuitive than the editing of control points.

As the term suggests, knot insertion inserts a knot into the knot vector. If the degree of the curve is , then control points are replaced by new ones. The shape of the curve stays the same. A knot can be inserted multiple times, up to the maximum multiplicity of the knot. This is sometimes referred to as knot refinement and can be achieved by an algorithm that is more efficient than repeated knot insertion.

Knot removal is the reverse of knot insertion. Its purpose is to remove knots and the associated control points in order to get a more compact representation. Obviously, this is not always possible while retaining the exact shape of the curve. In practice, a tolerance in the accuracy is used to determine whether a knot can be removed. The process is used to clean up after an interactive session in which control points may have been added manually, or after importing
a curve from a different representation, where a straightforward conversion process leads to redundant control points.

A NURBS curve of a particular degree can always be represented by a NURBS curve of higher degree. This is frequently used when combining separate NURBS curves,
e. g., when creating a NURBS surface interpolating between a set of NURBS curves or when unifying adjacent curves. In the process, the different curves should be brought to the same degree, usually the maximum degree of the set of curves. The process is known as degree elevation.

The most important property in differential geometry is the curvature It describes the local properties (edges, corners, etc.) and relations between the first and second derivative, and thus, the precise curve shape. Having determined the derivatives it is easy to compute or approximated as the arclength from the second derivative The direct computation of the curvature with these equations is the big advantage of parameterized curves against their polygonal representations.