Modelling Three-Dimensional Objects (Introduction to Computer Graphics Using Java 2D and 3D) Part 4

Efficient Computation of Polynomials

In order to draw a parametric curve, polynomials have to be evaluated. The same applies to freeform surfaces. In most cases, polynomials of degree 3 are used. This section presents an efficient scheme for evaluating polynomials, which is based on similar principles of incremental computations as introduced in the context of the midpoint algorithm in Sect. 3.2. Although floating point arithmetic cannot be avoided for polynomials in this way, it is at least possible to reduce the repeated calculations to additions only.

For drawing a cubic curve, the parametric curve is evaluated at equidistant values of the parameter t. The corresponding points are computed and connected by line segments. The same applies to freeform surfaces, which are also modelled by parametric curves or surfaces in the form of polynomials. For evaluating a polynomial f(t) at the points t0, t1 = t0 + δ, t2 = t0 + 2δ, … with a step width of δ > 0, a scheme of forward differences is applied. The polynomial has to be evaluated once for the initial value f0 = f(t0) at the point t0 and then the changes

are added in an incremental fashion as

or

For a polynomialof degree 3, this leads to

In this way, the evaluation of polynomials of degree 3 can be reduced to an addition of ^-values. The computation of these ^-values requires evaluations of polynomials of degree 2. These polynomials are also not explicitly evaluated. The same scheme of forward differences is also applied to them:

The ^-values of the original polynomial of degree 3 are calculated from the equation

A multiplication is still necessary for the computation of the ^2-values. Applying the scheme of forward differences once again, one obtains

With this final step, multiplications are only required for the computation of the initial value at t0 = 0. We have

For the calculation of all further values, only additions are needed. Table 6.1 illustrates this principle of difference schemes. Table 6.2 shows the calculations of the forward differences for an example, the polynomial f(t) = t3 + 2t + 3, i.e., a = 1, b = 0, c = 2, d = 3, with a step width of δ = 1.

Table 6.1 Forward difference for a general polynomial of degree 3

t0 = 0		tQ + δ		t0 + 2δ		t0 + 3δ …
		+		+		+ …
		+		+		+ …
		+		+		+ …

Table 6.2 Forward differences for the polynomial f(t) = t³ + 2t + 3 with step width δ = 1

t = 0		t=1		t = 2		t=3		t =4 …
3		6		15		36		75 …
3		9		21		39		63 …
6		12		18		24		30 …
6		6		6		6		6 …

Freeform Surfaces

As mentioned in Sect. 6.8, freeform surfaces are closely related to parametric curves. Freeform surfaces have two parameters to describe the two-dimensional surface, whereas only one parameter t is needed for curves. When one parameter of a freeform surface is considered as fixed, then the variation of the other parameter yields a curve on the surface as can be seen in Fig. 6.21.

Bézier surfaces are composed of Bézier curves with parameters s and t:

Most common are Bézier curves of degree 3. This means m = n = 3. For the definition of a Bézier surface (m + 1) · (n + 1) Bézier points bi;-, i.e., 16 in the case of cubic Bézier surfaces, have to be specified. Figure 6.22 illustrates how a net of Bézier points determines the Bézier surface.

Bézier surfaces have similar nice properties as Bézier curves. The four points at the corners b00, b0m, bn0, bnm lie on the surface. This does not apply to the other control points in general. The surface stays within the convex hull of the control point. Curves with a constant value s = s0 are Bézier curves with respect to the points

and analogously for curves with constant parameter t = t0.

Fig. 6.21 A parametric freeform surface

Fig. 6.22 A net of Bézier points for the definition of a Bézier surface

Since tesselations, as they are required in computer graphics, approximate surfaces with triangles and not with rectangles, Bézier surfaces of degree n, usually n = 3, are sometimes defined over a grid of triangles in the following way:

The corresponding Bernstein polynomials are given by

where t1 +12 +13 = 1, t1,t2,t3 > 0 and i + j + k = n (for i, j,k e N). The triangular grid is shown in Fig. 6.23.

Fig. 6.23 A triangular grid for the definition of a Bézier surface