b) What are the advantages of non-uniform non-rational B-splines over uniform non-rational B-splines? [4]

a) What is the difference between G^oand C^O continuity? Explain the difference between C⁰, C¹, C²continuity. Suggest a scheme for approximating a set of 2D points using a curve that satisfies C² continuity. [3+3+6]

A breakpoint is where two curve segments meet within a piecewise curve. The continuity of a curve at a breakpoint describes how those curves meet at the breakpoint. Figure 8-4 shows four possible types of continuity:

*No continuity*		The curves do not meet at all.
C⁰*continuity*		The endpoints of the two curves meet (the curves have positional continuity only). There may be a sharp point where they meet.
C¹ *continuity*		The curves have identical tangents at the breakpoint. (The tangent is the slope at the breakpoint.) The curves join smoothly. C¹ curves also have positional continuity.
C² continuity		The curves have identical curvature at the breakpoint. (Curvature is defined as the rate of change of the tangents.) Curvature continuity implies both tangential and positional continuity.

The order of a curve determines the maximum continuity possible. Thus, you may need a higher order curve if you need more continuity. The maximum continuity is order - 2. For example, for cubic curves, the maximum continuity possible is C² (curvature continuity).

Figure 8-4. Continuity of a Curve

c) Can you connect two Hermite curves maintaining CI continuity? How? [5]

Curves and surfaces can have explicit, implicit, and parametric representations. Parametric representations are the most common in computer graphics.

Reparameterization

Parameterizations are in general not unique. Consider the following parameterizations for a line:

L(P0,P1) = P0 + u(P1-P0), u = [0...1]

L(P0,P1) = v(P1-P0)/2 + (P1+P0)/2, v = [-1...1]

Parameterizations can be changed to lie between desired bounds. To reparameterize from u = [a...b] to w = [0...1], we can use w = (u-a)/(b-a), which gives u = w(b-a) + a. Thus, we have:

P(u), u = [a...b] = P(w(b-a)+a), w = [0...1]

Parametric Cubic Curves

Cubic curves are commonly used in graphics because curves of lower order commonly have too little flexibility, while curves of higher order are usually considered unnecessarily complex and make it easy to introduce undesired wiggles.

A parametric cubic curve in 3D is defined by:

Usually, we consider t = [0...1].

A compact version of the parametric equations can be written as follows:

Similarly, we can write

y(t) = T B

z(t) = T C

Each dimension is treated independently, so we can deal with curves in any number of dimensions.

The derivatives of the curve with respect to t can be expressed as follows:

x'(t) = [3t^2 2t 1 0] A

It is often convenient to think of the parameter t as being time in order to visualize some of the properties of the curve. The derivatives also have an intuitive interpretation in the cartesian space of the curve:

A First Example

Suppose we wish to define a cubic curve such that the user specifies the position of two endpoints and a midpoint, as well as the tangent at the midpoint. The following figure illustrates some sample curves.

We'll first construct the cubic curve for x(t). There are four constraints that are to be met and four unknowns:

We can solve for A using A = B_inv G_x. The final equation for x is thus:

x(t) = T B_inv G_x

The matrix B_inv is often called the basis matrix, which we shall denote by M. We can thus write

x(t) = T M G_x

In this case, we have

[ -4 0 -4 4 ]

M = [ 8 -4 6 -4 ]

[ -5 4 -2 1 ]

[ 1 0 0 0 ]

Lastly, we can also write

x(t) = [ f1(t) f2(t) f3(t) f4(t) ] G_x

where f1(t) ... f4(t) are the functions obtained from the product T M. These are functions are called the blending or basis functions, because they serve to give a weighting to the various components of the geometry vector, G. In this case, these are

f1(t) = -4t^3 + 8t^2 - 5t + 1

f2(t) = -4t^2 + 4t

f3(t) = -4t^3 + 6t^2 - 2t

f4(t) = 4t^3 - 4t^2 + 1,

where f1(t) is the weighting function for P0, f2(t) is the weighting function for P0.5, f3(t) is the weighting function for T0.5, and f4(t) is the weighting function for P1. These basis functions look as follows:

The curves for y(t) and z(t) are contructed in an analogous fashion to that for x(t). The basis matrix and basis functions thus remain the same. Only the geometry vector changes. The geometry vector for y(t) gives the y components of P0, P0.5, T0.5, and P1. In general, we can write the curve as a single vector equation

P(t) = T M G

which encompasses the following three equations:

x(t) = T M G_x

y(t) = T M G_y

z(t) = T M G_z

Hermite Curves

As a second example, let's look at Hermite curves. Hermite curves are defined by two points and two tangent vectors.

Let's derive the equation for Hermite curves using the following geometry vector:

G_h = [ P1 P4 R1 R4 ]^T

As before, we'll express the curve as:

x(t) = T A_h

= T M_h G_h

The constraints we'll use to define the curve are:

x(0) = P1 = [ 0 0 0 1 ] A_h

x(1) = P4 = [ 1 1 1 1 ] A_h

x'(0) = R1 = [ 0 0 1 0 ] A_h

x'(1) = R4 = [ 3 2 1 0 ] A_h

Writing these constraints in matrix form gives:

G_h = B_h A_h

A_h = inv(B_h) G_h

x(t) = T A_h

= T inv(B_h) G_h

= T M_h G_h

The inverse of B_h is thus defined as the basis matrix for the hermite curve.

[ 2 -2 1 1 ]

M_h = [ -3 3 -2 -1 ]

[ 0 0 1 0 ]

[ 1 0 0 0 ]

As before, the basis functions are the weighting factors for the terms in the geometry vector, and are given by the product T M_h. Thus, for basis functions for Hermite curves are

f1(t) = 2t^3 - 3t^2 + 1

f2(t) = -2t^3 + 3t^2

f3(t) = t^3 - 2t^2 + t

f4(t) = t^3 - t^2

These basis functions look as follows:

Bezier Curves

Bezier curves are a variation of the Hermite curves. They are specified by four points:

The curve is closely related to the Hermite curve:

P1_h = P1

P4_h = P4

R1_h = 3 (P2 - P1)

R4_h = 3 (P4 - P3)

We'll arrive at the basis matrix by expressing the above in matrix form:

[ P1_h ] [ 1 0 0 0 ] [ P1 ]

[ P4_h ] = [ 0 0 0 1 ] [ P2 ]

[ R1_h ] [ -3 3 0 0 ] [ P3 ]

[ R4_h ] [ 0 0 -3 3 ] [ P4 ]

P_h = M_bh P_b

The equation for a bezier curve can thus be written as:

P(t) = T M_h M_bh P_b

P(t) = T M_b P_b

where

[ -1 3 -3 1 ]

M_b = [ 3 -6 3 0 ]

[ -3 3 0 0 ]

[ 1 0 0 0 ]

The Bezier basis functions are as follows:

P(t) = T M_b G_b

= f1(t) P1 + f2(t) P2 + f3(t) P3 + f4(t) P4

where

f1(t) = -t^3 + 3t^2 - 3t + 1

f2(t) = 3t^3 - 6t^2 + 3t

f3(t) = -3t^3 + 3t^2

f4(t) = t^3

or alternatively,

f1(t) = (1-t)^3

f2(t) = 3t (1-t)^2

f3(t) = 3t^2 (1-t)

f4(t) = t^3

Convex hull property

The convex hull property ensures that the curve will never pass outside of the convex hull formed by the four control vertices. As such, it lends a measure of predictability to the curve. The Bezier basis functions satisfy the conditions necessary for the convex hull property, namely:

0 <= fi(t) <= 1 for t in [0,1].

f1(t) + ... + fn(t) = 1

Bezier Curves of degree n

It is not per chance that the basis functions for Bezier curves have the convex hull property. How might one then go about designing a set of basis functions that sum to one and ensure that each individual basis function remain in the range [0,1]? The Bernstein polynomials have exactly the required properties.

Using the Bernsteinn polynomials, we can construct a Bezier curve of arbitrary degree. For curves of higher degree than the cubic Bezier curve discussed thus far, we'll need more than four control points. The general Bezier curve of degree n is given by

The basis functions are equivalent to the terms arising from the expansion of

using the binomial expansion theorem. It is also obvious from this why the sum of all the terms is equal to one.

Piecewise Hermite and Bezier Curves

Hermite curve segments can be connected in a continuous fashion by ensuring that the end-point of one curve is the same as the starting point of another, as well as ensuring that the tangent vectors for this point have the same direction.

In terms of the above figure, this means P1'=P4, R1'=k R4 . For a Bezier curve, the conditions are that the the last two points of one curve and the first two points of the second curve are aligned.

Geometric and Parametric Continuity

Geometric Continuity

G0: curves are joined

G1: first derivatives are proportional at the join point
The curve tangents thus have the same direction, but not necessarily the same magnitude. i.e., C1'(1) = (a,b,c) and C2'(0) = (k*a, k*b, k*c).

G2: first and second derivatives are proportional at join point

Parametric Continuity

C0: curves are joined

C1: first derivatives equal

C2: first and second derivatives are equal
If t is taken to be time, this implies that the acceleration is continuous.

Cn: nth derivatives are equal

As their names imply, geometric continuity requires the geometry to be continuous, while parametric continuity requires that the underlying parameterization be continuous as well.

Parametric continuity of order n implies geometric continuity of order n, but not vice-versa.

b) B-Spline curves or spline curve. Explain the role of blending function to plot a spline curve [9]

a) Show the n^th degree B-spline basis function B_i,n (x) = 0 , if x < t₁ or x > t_i+n-i. [6]

B-spline curves share many important properties with Bézier curves, because the former is a generalization of the later. Moreover, B-spline curves have more desired properties than Bézier curves. The list below shows some of the most important properties of B-spline curves.

In the following we shall assume a B-spline curve C(u) of degree p is defined by n + 1 control points and a knot vector U = { u₀, u₁, ...., u_m } with the first p+1 and last p+1 knots "clamped" (i.e., u₀ = u₁ = ... = u_p and u_m-p = u_m-p₊₁ = ... = u_m).

B-spline curve C(u) is a piecewise curve with each component a curve of degree p.
As mentioned in previous page, C(u) can be viewed as the union of curve segments defined on each knot span. In the figure below, where n = 10, m = 14 and p = 3, the first four knots and last four knots are clamped and the 7 internal knots are uniformly spaced. There are eight knot spans, each of which corresponds to a curve segment. In the left figure below, these knot points are shown as triangles.

This nice property allows us to design complex shapes with lower degree polynomials. For example, the right figure below shows a Bézier curve with the same set of control points. It still cannot follow the control polyline nicely even though its degree is 10!

In general, the lower the degree, the closer a B-spline curve follows its control polyline. The following figures all use the same control polyline and knots are clamped and uniformly spaced. The first figure has degree 7, the middle one has degree 5 and the right figure has degree 3. Therefore, as the degree decreases, the generated B-spline curve moves closer to its control polyline.

Equality m = n + p + 1 must be satisfied.
Since each control point needs a basis function and the number of basis functions satisfies m = n + p + 1.

Clamped B-spline curve C(u) passes through the two end control points P₀ and P_n.
Note that basis function N_0,p(u) is the coefficient of control point P₀ and is non-zero on [u₀,u_p₊₁). Since u₀ = u₁ = ... = u_p = 0 for a clamped B-spline curve, N_0,0(u), N_1,0(u), ...., N_p_-1,0(u) are zero and only N_p_,0(u) is non-zero (recall from the triangular computation scheme). Consequently, if u = 0, then N_0,p(0) is 1 and C(0) = P₀. A similar discussion can show C(1) = P_n

Strong Convex Hull Property: A B-spline curve is contained in the convex hull of its control polyline. More specifically, if u is in knot span [u_i,u_i₊₁), then C(u) is in the convex hull of control points P_i-p, P_i-p₊₁, ..., P_i.
If u is in knot span [u_i, u_i₊₁), there are only p+1 basis functions (i.e., N_i_,p(u), ... , N_i-p_+1,p(u), N_i-p_,p(u)) non-zero on this knot span. Since N_k,p(u) is the coefficient of control point P_k, only p+1 control points P_i, P_i_-1, P_i_-2, .., P_i-p have non-zero coefficients. Since on this knot span the basis functions are non-zero and sum to 1, their "weighted" average, C(u), must lie in the convex hull defined by control points P_i, P_i_-1, P_i_-2, .., P_i-p. The meaning of "strong" is that while C(u) still lies in the convex hull defined by all control points, it lies in a much smaller one.

The above two B-spline curves have 11 control points (i.e., n = 10), degree 3 (i.e., p=3) and 15 knots (m = 14) with first four and last four knots clamped. Therefore, the number of knot spans is equal to the number curve segments. The knot vector is

u₀	u₁	u₂	u₃	u₄	u₅	u₆	u₇	u₈	u₉	u₁₀	u₁₁	u₁₂	u₁₃	u₁₄
0	0	0	0	0.12	0.25	0.37	0.5	0.62	0.75	0.87	1	1	1	1

The left figure has u in knot span [u₄, u₅) = [0.12,0.25) and the corresponding point (i.e. C(u)) in the second curve segment. Therefore, there are p+1 = 4 basis functions non-zero on this knot span (i.e., N_4,3(u), N_3,3(u), N_2,3(u) and N_1,3(u) ) and the corresponding control points are P₄, P₃, P₂ and P₁. The shaded area is the convex hull defined by these four points. It is clear that C(u) lies in this convex hull.

The B-spline curve in the right figure is defined the same way. However, u is in [u₉, u₁₀) = [0.75,0.87) and the non-zero basis functions are N_9,3(u), N_8,3(u), N_7,3(u) and N_6,3(u). The corresponding control points are P₉, P₈, P₇ and P₆.

Consequently, as u moves from 0 to 1 and crosses a knot, a basis functions becomes zero and a new non-zero basis function becomes effective. As a result, one control point whose coefficient becomes zero will leave the the definition of the current convex hull and is replaced with a new control point whose coefficient becomes non-zero.

Local Modification Scheme: changing the position of control point P_i only affects the curve C(u) on interval [u_i, u_i+p₊₁).
This follows from another important property of B-spline basis functions. Recall that N_i,p(u) is non-zero on interval [u_i, u_i+p₊₁). If u is not in this interval, N_i,p(u)P_i has no effect in computing C(u) since N_i,p(u) is zero. On the other hand, if u is in the indicated interval, N_i,p(u) is non-zero. If P_i changes its position, N_i,p(u)P_i is changed and consequently C(u) is changed.

The above B-spline curves are defined with the same parameters as in the previous convex hull example. We intent to move control point P₂. The coefficient of this control point is N_2,3(u) and the interval on which this coefficient is non-zero is [u₂, u₂₊₃₊₁) = [u₂, u₆) = [0,0.37). Since u₂ = u₃ = 0, only three segments that correspond to [u₃, u₄) (the domain of the first curve segment), [u₄, u₅) (the domain of the second curve segment) and [u₅, u₆) (the domain of the third curve segment) will be affected. The right figure shows the result of moving P₂ to the lower right corner. As you can see, only the first, second and third curve segments change their shapes and all remaining curve segments stay in their original place without any change.

This local modification scheme is very important to curve design, because we can modify a curve locally without changing the shape in a global way. This will be elaborated on the moeing control point page. Moreover, if fine-tuning curve shape is required, one can insert more knots (and therefore more control points) so that the affected area could be restricted to a very narrow region. We shall talk about knot insertion later.

C(u) is C^p-k continuous at a knot of multiplicity k
If u is not a knot, C(u) is in the middle of a curve segment of degree p and is therefore infinitely differentiable. If u is a knot in the non-zero domain of N_i,p(u), since the latter is only C^p-k continuous, so does C(u).

The above B-spline curve has 18 control points (i.e., n = 17), degree 4, and the following clamped knot vector

u₀ to u₄	u₅	u₆ and u₇	u₈	u₉ to u₁₁	u₁₂	u₁₃ to u₁₆	u₁₇	u₁₈ to u₂₂
0	0.125	0.25	0.375	0.5	0.625	0.75	0.875	1

Thus, u₆ is a double knot, u₉ is a triple knot and u₁₃ is a quadruple knot. Consequently, C(u) is of C⁴ continuous at any point that is not a knot, C³ continuous at all simple knots, C² continuous at u₆, C¹ continuous at u₉, C⁰ continuous at u₁₃.

All points on the curve that correspond to knots are marked with little triangles. Those corresponding to multiple knots are further marked with circles and their multiplicities. It is very difficult to visualize the difference between C⁴, C ³ and even C² continuity. For the C¹ case, the corresponding point lies on a leg, while the C⁰ case forces the curve to pass through a control point. We shall return to this issue later when discussing modifying knots.

Variation Diminishing Property:
The variation diminishing property also holds for B-spline curves. If the curve is in a plane (resp., space), this means no straight line (resp., plane) intersects a B-spline curve more times than it intersects the curve's control polyline.

In the above figure, the blue line intersects both the control polyline and the B-spline curve 6 times, while the yellow line also intersects the control polyline and the B-spline curve 5 times. However, the orange line intersects the control polyline 6 times and the curve 4 times.

Bézier Curves Are Special Cases of B-spline Curves.
If n = p (i.e., the degree of a B-spline curve is equal to n, the number of control points minus 1), and there are 2(p + 1) = 2(n + 1) knots with p + 1 of them clamped at each end, this B-spline curve reduces to a Bézier curve.

Affine Invariance
The affine invariance property also holds for B-spline curves. If an affine transformation is applied to a B-spline curve, the result can be constructed from the affine images of its control points. This is a nice property. When we want to apply a geometric or even affine transformation to a B-spline curve, this property states that we can apply the transformation to control points, which is quite easy, and once the transformed control points are obtained the transformed B-spline curve is the one defined by these new points. Therefore, we do not have to transform the curve.

The Advantage of Using B-spline Curves

B-spline curves require more information (i.e., the degree of the curve and a knot vector) and a more complex theory than Bézier curves. But, it has more advantages to offset this shortcoming. First, a B-spline curve can be a Bézier curve. Second, B-spline curves satisfy all important properties that Bézier curves have. Third, B-spline curves provide more control flexibility than Bézier curves can do. For example, the degree of a B-spline curve is separated from the number of control points. More precisely, we can use lower degree curves and still maintain a large number of control points. We can change the position of a control point without globally changing the shape of the whole curve (local modification property). Since B-spline curves satisfy the strong convex hull property, they have a finer shape control. Moreover, there are other techniques for designing and editing the shape of a curve such as changing knots.

However, keep in mind that B-spline curves are still polynomial curves and polynomial curves cannot represent many useful simple curves such as circles and ellipses. Thus, a generalization of B-spline, NURBS, is required

a) How is B-spline curve different from Bezier Curve? [3]

A curve with complex shape may be represented by a composite Bézier curve formed by joining a number of Bézier curves with some constraints at the joints. The default constraint is that the curves are jointed smoothly. This in turn requires the continuity of the first-order derivative at the joint, which is known as the first-order parametric continuity. We may relax the constraint to require only the continuity of the tangent directions at the joint, which is known as the first-order geometric continuity. Increasing the order of continuity usually improves the smoothness of a composite Bézier curve. Although a composite Bézier curve may be used to describe a complex shape in CAGD applications, there are primarily two disadvantages associated the use of the composite Bézier curve:

It is considerably involved to join Bézier curves with some order of derivatives continuity.

For the reason that will become clear later, a composite Bézier curve requires more control vertices than a B-spline curve.

These disadvantages can be eliminated by working with spline curves. Originally, a spline curve was a draughtsman's aid. It was a thin elastic wooden or metal strip that was used to draw curves through certain fixed points (called nodes). The resulting curve minimizes the internal strain energy in the splines and hence is considered to be smooth. The mathematical equivalent is the cubic polynomial spline. However, conventional polynomial splines are not popular in CAD systems since they are not intuitive for iterative shape design. B-splines (sometimes, interpreted as basis splines) were investigated by a number of researchers in the 1940s. But B-splines did not gain popularity in industry until de Boor and Cox published their work in the early 1970s. Their recurrence formula to derive B-splines is still the most useful tool for computer implementation.

It is beyond the scope of this section to discuss different ways of deriving B-splines and their generic properties. Instead, we shall take you directly to the definition of a B-spline curve and then explain to you the mathematics of B-splines. Given M control vertices (or de Boor points) d_i (i = 0,1,�,M-1), a B-spline curve of order k (or degree n = k-1) is defined as

r(u) =

M-1
�
i = 0

d_i N_i,k(u),

where, N_i,k(u) are polynomials of degree n and known as B-splines of order k. Analogous to Bézier curves, N_i,k(u) are also called the B-spline basis functions. In most practical applications, the B-spline basis functions are derived from the following knot vector (or knot sequence):

u₀ = u₁ = � = u_n, u_k � � � u_j � � � u_M-1, u_M = u_M+1 = � = u_M+n

where, u_i are called knots. The reason to select the first and last k knots to be equal is that the control vertices d₀ and d_M-1 are the points on the curve. Furthermore, the tangent direction of the curve at d₀ is from d₀ to d₁ and the tangent direction at d_M-1 is from d_M-2 to d_M-1. Due to these properties, the shape of a B-spline curve resembles the shape of its control polygon formed by the control vertices d_i, although such resemblance is not as intuitive as that of a Bézier curve. In the literature, the M-k knots u_k, u_k+1, �, u_M-1 are sometimes called the interior knots. If the interior knots are all distinct, then the B-spline curve has M-k non-vanishing spans (i.e., the arc length of each span is not zero).

As we said previously, there are several methods to derive the B-spline basis functions N_i,k(u) in terms of the knot vector. We present only the recursive formula derived by de Boor and Cox as follows:

N_i,k(u) =

u-u_i

u_i+k-1-u_i

N_i,k-1(t)+

u_i-u

u_i+k-u_i+1

N_i+1,k-1(u),

with

N_i,1 =

�
�
�

1, u � [u_i,u_i+1)

0, elsewhere

These basis functions have the following properties:

The basis functions sum to 1, i.e., �_{i = 0}^M-1N_i,k(u) = 1. This means that, similar to a Bézier curve, a B-spline curve lies also within the convex hull.

N_i,k(u) > 0 for u_i < u < u_i+k and, elsewhere, N_i,k(u) = 0. This is known as the local support property of B-splines. In other words, a change of the control vertex d_i affects the B-spline curve locally only for u_i < u < u_i+k.

If the interior knots are distinctive, N_i,k(u) has continuity of order k-2. This implies that a B-spline curve has parametric continuity of order k-2 across all the spans.

b) What do you mean by rational B-spline? How is it more useful than non-rational B-spline in drawing curves? [5]

Rational B-splines have all of the properties of non-rational B-splines plus the following two useful features:

They produce the correct results under projective transformations (while non-rational B-splines only produce the correct results under affine transformations).

They can be used to represent lines, conics, non-rational B-splines; and, when generalised to patches, can represents planes, quadrics, and tori.

The antonym of rational is non-rational. Non-rational B-splines are a special case of rational B-splines, just as uniform B-splines are a special case of non-uniform B-splines. Thus, non-uniform rational B-splines encompass almost every other possible 3D shape definition. Non-uniform rational B-spline is a bit of a mouthful and so it is generally abbreviated to NURBS.

Rational B-splines are defined simply by applying the B-spline equation (Equation 87) to homogeneous coordinates, rather than normal 3D coordinates. We discussed homogeneous coordinates in the IB course. You will remember that these are 4D coordinates where the transformation from 4D to 3D is:

(94)

Last year we said that the inverse transform was:

(95)

This year we are going to be more cunning and say that:

(96)

Thus our 3D control point, , becomes the homogeneous control point, .

A NURBS curve is thus defined as:

b) Explain the role of surface revolution. [6]

A surface of revolution is generated by revolving a given curve about an axis. The given curve is a profile curve while the axis is the axis of revolution..

To design a surface of revolution, select Advanced Features followed by Cross Sectional Design. This will bring up the curve system. In the curve system, just design a profile curve based on the condition to be discussed below, and then select Techniques followed by Generate Surface of Revolution. The surface system will display a surface of revolution defined by the given profile curve.

Some special restrictions must be followed in order to design a surface of revolution under the curve system. First, the axis of revolution must be the z-axis. Second, the profile curve must be in the xz-plane. However, when brining up the curve system, only the xy-plane is shown. To overcome this problem, one can design a profile curve on the xy-plane and rotate the curve (not the scene) about the x-axis 90 degree (or -90 degree, depending on your need). In this way, the profile curve will be placed on the xz-plane. Note that to modify control points after this rotation, you must use the sliders.

Many commonly seen and useful surfaces are surfaces of revolution (e.g., spheres, cylinders, cones and tori).

surface of revolution is a surface in Euclidean space created by rotating a curve (the generatrix) around a straight line in its plane (the axis)^[1].
Examples of surfaces generated by a straight line are cylindrical and conical surfaces when the line is coplanar with the axis, as well as hyperboloids of one sheet when the line is skew to the axis. A circle that is rotated about a diameter generates a sphere and if the circle is rotated about a coplanar axis other than the diameter it generates a torus.

c) Describe the role of geometric curves in Font generation. [6]

The generation of scalable fonts in the PostScript type one format requires the use of cubic B_ezier

curves in order to describe the contours of a character. B_ezier curves were invented independently by de

Casteljau around 1959 and by B_ezier around 1962 and are described in the books by Farin (1993) and

Su and Liu (1989).

Given the current point (x0; y0), the PostScript command curveto takes the three points (x1; y1); (x2; y2); (x3; y3)

as parameters. The four points are called the B_ezier points. The B_ezier curve B(t) = (x(t); y(t)) can be

written as

x(t) = axt3 + bxt2 + cxt + x0

y(t) = ayt3 + byt2 + cyt + y0

where

ax =x3 􀀀 3(x2 􀀀 x1) 􀀀 x0 ay =y3 􀀀 3(y2 􀀀 y1) 􀀀 y0

bx =3(x2 􀀀 2x1 + x0) by =3(y2 􀀀 2y1 + y0)

cx =3(x1 􀀀 x0) cy =3(y1 􀀀 y0) .

Equivalently,

x(t) = x3t3 + 3x2t2(1 􀀀 t) + 3x1t(1 􀀀 t)2 + x0(1 􀀀 t)3

y(t) = y3t3 + 3y2t2(1 􀀀 t) + 3y1t(1 􀀀 t)2 + y0(1 􀀀 t)3 ;

in the Bernstein polynomial format. The monomial form of a B_ezier curve allows the computations to be

performed with Horner's method. A B_ezier curve of the third degree takes one of four possible shapes:

The junction point of the segments is known as a knot or a breakpoint. A spline S, composed of

two adjacent B_ezier curves B0 and B1 may be created as follows. Each curve has its own local parameter

t while S has a global parameter u, where u 2 R. The knot sequence can be represented in terms of the

parameter u, knot i having parameter value ui. The correspondence between t and u depends on the

actual length of each segment, t = (u 􀀀 ui)=(ui+1 􀀀 ui). We can think of B0 and B1 as two independent

curves each having a local parameter t ranging from 0 to 1 or we may regard it as two segments of

a composite curve with parameter u in the domain [u0; u2]. _sthetically pleasing composite curves are

obtained by introducing continuity restrictions and applying smoothness conditions to S (Manning, 1974).

Roughly speaking, continuity of the _rst and second order derivatives at knot points with respect to the

global parameter u is called C1 and C2 continuity respectively.

To illustrate these notions of smoothness, take two adjacent B_ezier sections B0 (with B_ezier points

b0; : : : ; b3) and B1 (with B_ezier points b3; : : : ; b6). C1 continuity at b3, the knot, occurs if b2, b3 and b4 are

collinear, and if jjb4 􀀀b3jj=jjb3 􀀀b2jj = _1=_0, where _1 = u2 􀀀u1 and _0 = u1 􀀀u0. Note that b1 and

b5 do not appear in the condition. With C2 continuity, the points b1; b2; b3; b4; b5 inuence the second

derivative at the junction point. If the curve S is C2 then there must a point d of a polygon b1; d; b5 that

describes the same global quadratic polynomial as the _ve points mentioned above do. Hence assuming

that the curve is already C1, the following equations must be satis_ed in order for d to exist:

b2 = (1 􀀀 t1)b1 + t1d

b4 = (1 􀀀 t1)d + t1b5 ;

where t1 = _0=(u2 􀀀 u0). The conditions for C1 and C2 curves are shown in the following _gure.

a)Describe global illumination model. Define surface normal and reflection vector. [9]

From Physics we can derive models, called "illumination models", of how light reflects from surfaces and produces what we perceive as color. In general, light leaves some light source, e.g. a lamp or the sun, is reflected from many surfaces and then finally reflected to our eyes, or through an image plane of a camera.

The contribution from the light that goes directly from the light source and is reflected from the surface is called a "local illumination model". So, for a local illumination model, the shading of any surface is independent from the shading of all other surfaces.

A "global illumination model" adds to the local model the light that is reflected from other surfaces to the current surface. A global illumination model is more comprehensive, more physically correct, and produces more realistic images. It is also more computationally expensive. We will first look at some basic properties of light and color, the physics of light-surface interactions, local illumination models, and global illumination models.

Scan-line rendering methods use only local illumination models, although they may use tricks to simulate global illumination.

The two major types of graphics systems that use global illumination models are radiosity and ray tracing. These produce more realistic images but are more computationally intensive than scan-line rendering systems.

Light consists of photons which sometimes behave as particles and sometimes as waves. This is known as the wave - particle duality and is true for all particles (even baseballs).

l = c / u ; E = h * u ;

where l = wavelength of light, c = speed of light, u = the frequency of light, E = the energy of the light, and h = Planck's constant. There is a correlation between u (and thus E) and the "color" we perceive.

Color and spectrum of light

A light source has a particular energy spectrum, i.e., the energy output is a function of the wavelength, rather than being constant. Below is a plot of output energy versus wavelength for a perfect "white" light.

The intensity of light is proportional to the number of photons of each wavelength. We could associate a spectrum for each light ray, i.e., look at the spectral composition. But this would make it difficult to model refraction since change in direction is a function of wavelength, so it is easier to associate each light ray with a particular wavelength.

An infinite number of color spectra can give rise to the same perceived "color". These are called metemers, i.e., they give perceptually equivalent color but are spectrally different. This happens because our eyes do not have receptors for all wavelengths but only certain ones. The eye contains 64% red cones, 32% green cones, and 4% blue cones

A surface has 4 types of interaction with light:

· Diffuse reflection - light is reflected uniformly with no specific direction

· Specular reflection - light is reflected in a specific direction

· Diffuse transmission - light is transmitted uniformly with no preferred direction

· Specular transmission - light is transmitted in a preferred direction

A surface normal, or simply normal, to a flat surface is a vector that is perpendicular to that surface. A normal to a non-flat surface at a point P on the surface is a vector perpendicular to the tangent plane to that surface at P. The word "normal" is also used as an adjective: a line normal to a plane, the normal component of a force, the normal vector, etc. The concept of normality generalizes to orthogonality.

· In the two-dimensional case, a normal line perpendicularly intersects the tangent line to a curve at a given point.

· The normal is often used in computer graphics to determine a surface's orientation toward a light source for flat shading, or the orientation of each of the corners (vertices) to mimic a curved surface with Phong shading.

· The operation of exchanging all points of a mathematical object with their mirror images (i.e., reflections in a mirror). Objects that do not change handedness under reflection are said to be amphichiral; those that do are said to be chiral.

· Consider the geometry of the left figure in which a point is reflected in a mirror (blue line). Then

(1)

· so the reflection of is given by

(2)

· The term reflection can also refer to the reflection of a ball, ray of light, etc. off a flat surface. As shown in the right diagram above, the reflection of a points off a wall with normal vector satisfies

(3)

· If the plane of reflection is taken as the -plane, the reflection in two- or three-dimensional space consists of making the transformation for each point. Consider an arbitrary point and a plane specified by the equation

(4)

· This plane has normal vector

(5)

· and the signed point-plane distance is

(6)

· The position of the point reflected in the given plane is therefore given by

			(7)
			(8)

· The reflection of a point with trilinear coordinates in a point is given by , where

			(9)
			(10)
			(11)

a) Describe different models used for illumination. How do you design surface normal vector. Explain it’s importance. [6]

Calculating a surface normal

For a convex polygon (such as a triangle), a surface normal can be calculated as the vector cross product of two (non-parallel) edges of the polygon.

For a plane given by the equation ax + by + cz + d = 0, the vector (a,b,c) is a normal. For a plane given by the equation r = a + αb + βc, where a is a vector to get onto the plane and b and c are non-parallel vectors lying on the plane, the normal to the plane defined is given by b × c (the cross product of the vectors lying on the plane).

For a hyperplane in n+1 dimensions, given by the equation r = a0 + α1a1 + α2a2 + ... + αnan, where a0 is a vector to get onto the hyperplane and ai for i = 1, ... , n are non-parallel vectors lying on the hyperplane, the (unscaled) normal to the hyperplane can be approximated by (AAT + bbT) − 1b where A = [a1, a2, ... , an] and b is an arbitrary vector in the space not in the linear span of ai.

If a (possibly non-flat) surface S is parameterized by a system of curvilinear coordinates x(s, t), with s and t real variables, then a normal is given by the cross product of the partial derivatives

If a surface S is given implicitly as the set of points (x,y,z) satisfying F(x,y,z) = 0, then, a normal at a point (x,y,z) on the surface is given by the gradient

since the gradient at any point is perpendicular to the level set, and F(x,y,z) = 0 (the surface) is a level set of F.For a surface S given explicitly as a function f(x,y) of the independent variables x,y (e.g., f(x,y) = a00 + a01y + a10x + a11xy), its normal can be found in at least two equivalent ways. The first one is obtaining its implicit form F(x,y,z) = z − f(x,y) = 0, from which the normal follows readily as the gradient

(Notice that the implicit form could be defined alternatively as F(x,y,z) = f(x,y) − z; these two forms correspond to the interpretation of the surface being oriented upwards or downwards, respectively, as a consequence of the difference in the sign of the partial derivative .) The second way of obtaining the normal follows directly from the gradient of the explicit form, ; it is apparent from inspection that , where is the upward unit vector.

If a surface does not have a tangent plane at a point, it does not have a normal at that point either. For example, a cone does not have a normal at its tip nor does it have a normal along the edge of its base. However, the normal to the cone is defined almost everywhere. In general, it is possible to define a normal almost everywhere for a surface that is Lipschitz continuous.

• Surface normals are essential in defining surface integrals of vector fields.

• Surface normals are commonly used in 3D computer graphics for lighting calculations; see Lambert's cosine law.

• Surface normals are often adjusted in 3D computer graphics by normal mapping.

• Render layers containing surface normal information may be used in Digital compositing to change the apparent lighting of rendered elements.

d) How can we generate shadow-using ray tracing algorithm? [4]

When a ray hits a surface, it could generate up to three new types of rays: reflection, refraction, and shadow.^[3] A reflected ray continues on in the mirror-reflection direction from a shiny surface. It is then intersected with objects in the scene; the closest object it intersects is what will be seen in the reflection. Refraction rays traveling through transparent material work similarly, with the addition that a refractive ray could be entering or exiting a material. To further avoid tracing all rays in a scene, a shadow ray is used to test if a surface is visible to a light. A ray hits a surface at some point. If the surface at this point faces a light, a ray (to the computer, a line segment) is traced between this intersection point and the light. If any opaque object is found in between the surface and the light, the surface is in shadow and so the light does not contribute to its shade. This new layer of ray calculation added more realism to ray traced images.

a)Outline the approach of the ray tracing and radiosity methods for rendering of scenes in computer graphics, and then explain which technique you would use to display i) an automobile and ii) the interior of a house, and why? [10]

Radiosity - Ray Tracing

The two most popular methods for calculating realistic images are radiosity and ray tracing. The difference in the simulation is the starting point: Ray tracing follows all rays from the eye of the viewer back to the light sources. Radiosity simulates the diffuse propagation of light starting at the light sources.

Ray Tracing

This method is very good at simulating specular reflections and transparency, since the rays that are traced through the scenes can be easily bounced at mirrors and refracted by transparent objects.

The last scene with the black monitor contains some diffuse reflection on the screen. This scene was very time consuming to calculate, since ray tracing is not very well suited for calculating diffuse reflections.

Radiosity

Calculating the overall light propagation within a scene, for short global illumination is a very difficult problem. With a standard ray tracing algorithm, this is a very time consuming task, since a huge number of rays have to be shot. For this reason, the radiosity method was invented. The main idea of the method is to store illumination values on the surfaces of the objects, as the light is propagated starting at the light sources.

Ray Casting

In ray casting the geometry which has been modeled is parsed pixel by pixel, line by line, from the point of view outward, as if casting rays out from the point of view. Where an object is intersected, the color value at the point may be evaluated using several methods. In the simplest, the color value of the object at the point of intersection becomes the value of that pixel. The color may be determined from a texture-map. A more sophisticated method is to modify the colour value by an illumination factor, but without calculating the relationship to a simulated light source. To reduce artifacts, a number of rays in slightly different directions may be averaged.

Rough simulations of optical properties may be additionally employed: a simple calculation of the ray from the object to the point of view is made. Another calculation is made of the angle of incidence of light rays from the light source(s), and from these as well as the specified intensities of the light sources, the value of the pixel is calculated. Another simulation uses illumination plotted from a radiosity algorithm, or a combination of these two.

Raycasting is primarily used for realtime simulations, such as those used in 3D computer games and cartoon animations, where detail is not important, or where it is more efficient to manually fake the details in order to obtain better performance in the computational stage. This is usually the case when a large number of frames need to be animated. The resulting surfaces have a characteristic 'flat' appearance when no additional tricks are used, as if objects in the scene were all painted with matte finish.

Ray tracing

Ray tracing aims to simulate the natural flow of light, interpreted as particles. Often, ray tracing methods are utilized to approximate the solution to the rendering equation by applying Monte Carlo methods to it. Some of the most used methods are Path Tracing, Bidirectional Path Tracing, or Metropolis light transport, but also semi realistic methods are in use, like Whitted Style Ray Tracing, or hybrids. While most implementations let light propagate on straight lines, applications exist to simulate relativistic spacetime effects^[1].

In a final, production quality rendering of a ray traced work, multiple rays are generally shot for each pixel, and traced not just to the first object of intersection, but rather, through a number of sequential 'bounces', using the known laws of optics such as "angle of incidence equals angle of reflection" and more advanced laws that deal with refraction and surface roughness.

Once the ray either encounters a light source, or more probably once a set limiting number of bounces has been evaluated, then the surface illumination at that final point is evaluated using techniques described above, and the changes along the way through the various bounces evaluated to estimate a value observed at the point of view. This is all repeated for each sample, for each pixel.

In distribution ray tracing, at each point of intersection, multiple rays may be spawned. In path tracing, however, only a single ray or none is fired at each intersection, utilizing the statistical nature of Monte Carlo experiments.

As a brute-force method, ray tracing has been too slow to consider for real-time, and until recently too slow even to consider for short films of any degree of quality, although it has been used for special effects sequences, and in advertising, where a short portion of high quality (perhaps even photorealistic) footage is required.

However, efforts at optimizing to reduce the number of calculations needed in portions of a work where detail is not high or does not depend on ray tracing features have led to a realistic possibility of wider use of ray tracing. There is now some hardware accelerated ray tracing equipment, at least in prototype phase, and some game demos which show use of real-time software or hardware ray tracing.

Radiosity

Radiosity is a method which attempts to simulate the way in which directly illuminated surfaces act as indirect light sources that illuminate other surfaces. This produces more realistic shading and seems to better capture the 'ambience' of an indoor scene. A classic example is the way that shadows 'hug' the corners of rooms.

The optical basis of the simulation is that some diffused light from a given point on a given surface is reflected in a large spectrum of directions and illuminates the area around it.

The simulation technique may vary in complexity. Many renderings have a very rough estimate of radiosity, simply illuminating an entire scene very slightly with a factor known as ambiance. However, when advanced radiosity estimation is coupled with a high quality ray tracing algorithim, images may exhibit convincing realism, particularly for indoor scenes.

In advanced radiosity simulation, recursive, finite-element algorithms 'bounce' light back and forth between surfaces in the model, until some recursion limit is reached. The colouring of one surface in this way influences the colouring of a neighbouring surface, and vice versa. The resulting values of illumination throughout the model (sometimes including for empty spaces) are stored and used as additional inputs when performing calculations in a ray-casting or ray-tracing model.

Due to the iterative/recursive nature of the technique, complex objects are particularly slow to emulate. Prior to the standardization of rapid radiosity calculation, some graphic artists used a technique referred to loosely as false radiosity by darkening areas of texture maps corresponding to corners, joints and recesses, and applying them via self-illumination or diffuse mapping for scanline rendering. Even now, advanced radiosity calculations may be reserved for calculating the ambiance of the room, from the light reflecting off walls, floor and ceiling, without examining the contribution that complex objects make to the radiosity—or complex objects may be replaced in the radiosity calculation with simpler objects of similar size and texture.

Radiosity calculations are viewpoint independent which increases the computations involved, but makes them useful for all viewpoints. If there is little rearrangement of radiosity objects in the scene, the same radiosity data may be reused for a number of frames, making radiosity an effective way to improve on the flatness of ray casting, without seriously impacting the overall rendering time-per-frame.

Because of this, radiosity is a prime component of leading real-time rendering methods, and has been used from beginning-to-end to create a large number of well-known recent feature-length animated 3D-cartoon films.

4. a) Describe the Phong illumination model. [8]

Phong Shading Model for Scan-Line Graphics

The third shading model, Phong shading, is similar to Gouraud shading except that the Normals are interpolated. Phong shading is more realistic than Gouraud shading, but requires more computation. It does not produce shadows or reflections. The surface normals at the triangle's points are used to compute a surface normal for each pixel, which in turn creates a more accurate RGB value for each pixel .Thus, the specular highlights are computed much more precisely than in the Gouraud shading model.

The algorithm is as follows:

1. Compute a normal N for each vertex of the polygon.

2. From bi-linear interpolation compute a normal, Ni for each pixel. (This must be renormalized each time)

3. From Ni compute an intensity Ii for each pixel of the polygon.

4. Paint pixel to shade corresponding to Ii.

Note that this method is much more computationally intensive than Gouraud shading:

Gouraud: 3 floating point adds per pixel (3 intensities).

Phong: 3 fp adds (normal) + (3 squares + sqrt for normal) + (recompute intensity - 3 * (about 10-20 fp multiplies depending on degree of approximation).

So may do Phong shading only when want good specular highlights

Phong shading is done by interpolating the vertex normals across the surface of a polygon, or triangle, and illuminating the pixel at each point, usually using the phong lighting model. At each pixel, you need to re-normalize the normal vector, and also calculate the reflection vector.

The reflection vector is calculated by:

R = 2.0*(N.L)*N - L

We feed these vectors into the illumination equation for the phong lighting model, which is

I = Ia*ka*Oda + fatt*Ip[kd*Od(N.L) + ks(R.V)^n]

Here, the variables are:

Ia is the ambient intensity

ka is the ambient co-efficient

Oda is the colour for the ambient

fatt is the atmospheric attenuation factor, ie depth shading

Ip is the intensity of the point light source

kd is the diffuse co-efficient

Od is the objects colour

ks is the specular co-efficient

n is the objects shinyness

N is the normal vector

L is the lighting vector

R is the reflection vector

V is the viewing vector

To do multiple light sources, you sum the term fatt*Ip[kd*Od(N.L) + ks(R.V)^n] for each light source. Also, you need to repeat this equation for each colour band you are interested in.

Such shading is incredibly expensive, and cannot be done in realtime on common hardware. So, people have been looking into optimizations and approximations of this for a long time.

OPTIMIZING THE PHONG SHADING MODEL

                Lets mathematically break down the phong shading model.  After all is said and done, you are left with the dot product of the pixel normal vector and the light vector divided by the product of the magnitudes of these two vectors.  Another way to express this value is (cos é), where é is the smallest angle  between the two vectors.

        u = pixel normal vector

        v = light vector

        u dot v = cos é * |u| * |v|

                 u dot v

        cos é = ---------

                |u| * |v|

So the dot product of a normal vector and a light vector divided by the product of the magnitudes of the two vectors is equal to the cosine of the smallest angle between the two vectors.  This  should be nothing new, it is the same technique used to find color  values in the lambert and gouraud shading techniques.  Lets attempt to graphically represent what is going on with phong, gouraud and

        lambert shading.

                                graph of y = cos é (*)

        |*    *

        |          *

        |             *

        |                *

        |                   *

        |                     *

        |                       *

        |                         *

      y |                          *

        |                           *

        |                            *

        |                             *

        |                              *

        |                               *

        |                                *

        |                                 *

        |                                  *

        |                                   *

        +------------------------------------------

é

                The phong shading model states that the intensity of light  at a given point is given by the dot product of the light and normal  vectors divided by the product of the magnitudes of the two vectors. Flat shading is the roughest approximation of this, planes are rendered in a single color which is determined by the cosine of the angle between the plane's normal vector and the light vector.  If  we graph the intensity of light striking flat shaded planes, we  should find that they roughly form a cosine curve, since the color  values at certain points are determined by the cosine of the angle

        between two vectors

                          graph of Intensity = cos é (*)

        |      flat shading approximations of light intensity shown as (X)

        |*XXXX*XX               dé  (angle between normal vectors)

        |          *       -------------

        |        XXXXX*XXXX            |

        |                *             | dI  (change in intensity)

        |                   *          |

        |                  XXX*XXXXXX  |

        |                       *

      I |                         *

        |                          *

        |                           *XXXXXX

        |                            *

        |                             *

        |                              *

        |                               *

        |                                *

        |                                 *XXXXX

        |                                  *

        |                                   *

        +------------------------------------------

é

                This graph tells us something that we already know by practical experience, that flat shading is very inaccurate for large values of dé, and much more accurate for small values of dé.  This  means that the shading appears smoother when the angle between normals (and therefore between planes) is very small.

                Now lets consider gouraud shading.  Gouraud shading is a linear interpolation of color between known intensities of light. The known intensities in gouraud shading are defined at each

        vertex, once again by use of the dot product.  In this case, the normal vector at each polygon vertex is the average of the normal vectors (the ones used in flat shading) for all planes which share

        that vertex.  Normals of planes which are greater than 90 and less than 270 degrees from the plane containing the vertex in question are not considered in the average because the two planes are facing away from each other.  If we plot interpolated intensities used in gouraud shading against the cosine curve, it is evident that gouraud shading is a much more accurate approximation than flat shading.

                        graph of Intensity = cos é (*)

        |        interpolated light intensities shown as (X)

        | ---------------------------------+

        |*X   *                            | in this region, the linear

        |  XXXX ---*--------+              | approximation is always going to

        |      XXX    *     | dI (error)   | be inaccurate without a very

        |         XXXX --*--+              | small value for dé

        |             XXX   *              |

        |                XXXXX*  --------------+

        ||____________________|X*              |

      I |        dé              X*            |

        |                         X*           | in this region, a gouraud

        |                          X*          | approximation is nearly

        |                           X*         | perfect because cos x is

        |                            X*        | nearly linear

        |                             X*       |

        |                              X*      |

        |                               X*     |

        |                                X*    |

        |                                 X*   |

        |                                  X*  |

        +------------------------------------------

é

                This graph tells us that gouraud shading is very accurate as é->90.  However, if é is small and dé is large, gouraud shading will look like an obvious linear approximation.  This can be avoided

        by using smaller values of dé (i.e. use more polygons to fill in the gaps in the interpolation).  With enough polygons, gouraud shading can be 100% correct.

                Phong shading is the most correct method of shading because  it is not an approximation, distinct colors are determined for each pixel.  These values follow the cosine curve exactly, because the intensity of each pixel was calculated using a dot product, which eventually yields the cosine of the angle between the plane at that pixel and the light vector.  If we plot phong shading intensities with the cosine curve, we find that the values follow the function exactly.

                        graph of Intensity = cos é (*)

        |            phong light intensities shown as (X)

        |X    X

        |          X

        |             X

        |                X

        |                   X

        |                     X

        |                       X

        |                         X

      I |                          X

        |                           X

        |                            X

        |                             X

        |                              X

        |                               X

        |                                X

        |                                 X

        |                                  X

        |                                   X

        +------------------------------------------

é

                Once again, shadings calculated using the phong model follow the cosine curve, because the dot product between the normal vector at each pixel and the light vector can be simplified to a function involving cos é.

c) Gourand Shading [9]

Gouraud shading model.

The second shading model, Gouraud shading, computes an intensity for each vertex and then interpolates the computed intensities across the polygons. Gouraud shading performs a bi-linear interpolation of the intensities down and then across scan lines. It thus eliminates the sharp changes at polygon boundaries

The algorithm is as follows:

1. Compute a normal N for each vertex of the polygon.

2. From N compute an intensity I for each vertex of the polygon.

3. From bi-linear interpolation compute an intensity Ii for each pixel.

4. Paint pixel to shade corresponding to Ii.

How do we compute N for a vertex? Let N = the average of the normals of the polygons which include the vertex. Note that 4 sided polygons have 4 neighbors and triangles have 6 neighbors.
We can find the neighbors for a particular vertex by searching the polygons and including any polygons which include the vertex. Now look at performing the bi-linear intensity interpolation. This is the same as the bi-linear interpolation for the z depth of a pixel (used with the z buffer visible surface algorithm).

Advantages of Gouraud shading:

Gouraud shading gives a much better image than faceted shading (the facets no longer visible). It is not too computationally expensive: one floating point addition (for each color) for each pixel. (the mapping to actual display registers requires a floating point multiplication)

Disadvantages to Gouraud shading:

It eliminates creases that you may want to preserve, e.g. in a cube. We can modify data structure to prevent this by storing each physical vertex 3 times, i.e. a different logical vertex for each polygon.

Gouraud Shading and Specular Highlights

Gouraud shading does not handle specular highlights very well. Look at the following case of a light source in three different positions relative to a polygon.

If the Phong number is high (corresponding to a small viewing cone and thus a small specular highlight), then the highlight should move across the surface of the polygon as the light is shifted. But since the intensities are only computed at the vertices, the highlight will appear in Case 1, disappear in Case 2, and reappear in Case 3. Also, the highlight will be smeared out in both Cases 1 and 3 since the interpolation of the intensities will cause it to decrease slower than it really should.

f) Explain, why Phong shading is more computationally demanding than Gouraud Shading and achieves better results, in particular for specular reflection? [4]

Phong shading is more realistic than Gouraud shading, but requires more computation. It does not produce shadows or reflections. The surface normals at the triangle's points are used to compute a surface normal for each pixel, which in turn creates a more accurate RGB value for each pixel .Thus, the specular highlights are computed much more precisely than in the Gouraud shading model.

e) Explain the ray tracing and describe the procedure to determine the intersection of an arbitrary ray with YZ plane. [4]

Ray-Tracing for planes

• The plane equation: n.R + D = 0

~ Where n is the normal vector and R=

• We calculate the intersection of a ray with a plane by using R(t),

from the ray equation in the plane eq.: n.R(t) + D = 0

• We get:

which allows us to find the intersection point.

b) Explain ray tracing and compare it with ray casting. Describe the intersection of an arbitrary ray with yz plane. [6]

Ray-casting is a technique that transform a limited form of data (a very simplified map or floor plan) into a 3D projection by tracing rays from the view point into the viewing volume

Like ray-casting, ray-tracing "determines the visibility of surfaces by tracing imaginary rays of light from viewer's eye to the object in the scene" (Foley 701).

From both definitions, it seems that ray-casting and ray-tracing is the same. Indeed, some books use both terms interchangeably. From game programmers perspective, however, ray-casting is regarded as a special implementation (subclass) of ray-tracing.

This distinctions because is made because in general, ray-casting is faster than ray-tracing. This is possible because ray-casting utilizes some geometric constraint to speed up the rendering process. For instance: walls are always perpendicular with floors (you can see this in games such as Doom or Wolfenstein 3D). If it were not for such constraints, ray-casting will not be feasible. We would not want to ray-cast arbitrary splines for instance, because it is difficult to find a geometrical constraints on such shapes.

Table 1 is a general comparison between ray-casting and ray-tracing. The main point to remember is that there are "less number of rays" to trace in ray-casting because of some "geometric constraints." Or, it can also be said that ray-casting is a special purpose implementation of ray-tracing.

Bidvertiser

TABLE 1: A COMPARISON BETWEEN RAY-CASTING AND RAY-TRACING
(GAME PROGRAMMERS/GAME DEVELOPERS PERSPECTIVE)

Ray-Casting	Ray-Tracing
Principle: rays are cast and traced in groups based on some geometric constraints. For instance: on a 320x200 display resolution, a ray-caster traces only 320 rays (the number 320 comes from the fact that the display has 320 horizontal pixel resolution, hence 320 vertical column).	Principle: each ray is traced separately, so that every point (usually a pixel) on the display is traced by one ray. For instance: on a 320x200 display resolution, a ray-tracer needs to trace 320x200 (64,000) rays. (That is roughly 200 times slower than ray-casting.)
Formula: in most cases, inexact.	Formula: in most cases, exact.
Speed: very fast compared to ray-tracing; suitable for real time process.	Speed: slow; unsuitable for real time process (at least not until we got a 500Ghz machine).
Quality: resulting image is not very realistic. Often, they are blocky (Figure 3).	Quality: resulting image is very realistic - sometimes too realistic (Figure 4).
World: limited by one or more geometric constraints (simple geometric shapes).	World: almost any shape can be rendered.
Storage: small. Rendered images are not stored on disk. Normally, only the map is stored, and corresponding images are generated "on the fly."	Storage: Rendered images are stored on disk and loaded when needed. Presently, no hardware is fast enough for "on the fly" rendering.
Examples: Wolfenstein 3D (iD Software), Shadow Caster (Raven), Arena (Bethesda), Doom (iD Software), Dark Forces (LucasArts).	Examples: Examples: 7th Guest (Trilobyte), Critical Path (Mechadeus), 11th Hour (Trilobyte), Myst (Cyan), Cyberia (Xatrix).

a) Design an algorithm for hidden-surface elimination using ray-tracing. [10]

Raytracing algorithm

Raytracing is, in many ways, a standardized technique. Almost all raytracing programs (known as "raytracers") use the same basic algorithm in one way or the other. This algorithm is presented below.

· The Pre-Rendering Section

· The Main Rendering Loop

· The Post-Rendering Section

The Pre-Rendering Section

This section is executed before the actual rendering of the scene takes place. It is the most implementation and programmer dependent of all the sections of the algorithm. Its structure and content relies entirely on how the programmer has chosen to describe and store his scene and what variables need to be initialized for the program to run properly. Some parts that are usually present in some form or the other include generation of efficiency structures, initialization of the output device, setting up various global variables etc. No standard algorithm exists for this section.

The Main Rendering Loop

This section actually produces the picture of the 3-D scene. The algorithm for this section is given below. Note that the procedure RayTrace is recursive, that is, it calls itself.

Procedure RenderPicture()

  For each pixel on the screen,

    Generate a ray R from the viewing position through the point on the view

      plane corresponding to this pixel.

    Call the procedure RayTrace() with the arguments R and 0

    Plot the pixel in the colour value returned by RayTrace()

  Next pixel

End Procedure

Procedure RayTrace(ray R, integer Depth) returns colour

  Set the numerical variable Dis to a maximum value

  Set the object pointer Obj to null

  For each object in the scene

    Calculate the distance (from the starting point of R) of the nearest

      intersection of R with the object in the forward direction

    If this distance is less than Dis

      Update Dis to this distance

      Set Obj to point to this object

    End if

  Next object

  If Obj is not null

    Set the position variable Pt to the nearest intersection point of R and Obj

    Set the total colour C to black

    For each light source in the scene

      For each object in the scene

        If this object blocks the light coming from the light source to Pt

          Attenuate the intensity of the received light by the transmittivity

            of the object

        End if

      Next object

      Calculate the perceived colour of Obj at Pt due to this light source

        using the value of the attenuated light intensity

      Add this colour value to C

    Next light source

    If Depth is less than a maximum value

      Generate two rays Refl and Refr in the reflected and refracted directions,

        starting from Pt

      Call RayTrace with arguments Refl and Depth + 1

      Add (the return value * reflectivity of Obj) to C

      Call RayTrace with arguments Refr and Depth + 1

      Add (the return value * transmittivity of Obj) to C

    End if

  Else

    Set the total colour C to the background colour

  End if

  Return C

End Procedure

The Post-Rendering Section

This section is also more or less programmer dependent, but the functions performed usually fall into one or more of the following groups

· Memory cleanup: The space taken up for the scene and rendering data is released.

· Applying post-process filters: Special effects such as blur, edge highlighting, suppression of colour channels, gamma correction etc may be added to the picture after the actual rendering has taken place. Antialiasing, motion blur etc are usually a part of the main rendering section.

· Freeing output devices: If the output device is a file, it is closed. If it is a hardware device, then any link established with it may be suspended.

· Displaying statistics and other user data: This is, of course, entirely up to the programmer. But it is useful to know the details of the rendering process.

a) Suggest a scheme for modeling transparency and refraction in a scene assuming existence of point light source. [10]

Ray Tracing

· For each pixel, compute the colour that the viewer's eye will see in the scene

· hidden surface removal is a product of this

· ray tracing is also effective for photorealistic rendering

Ray Tracing

· ray tracers need to compute intersection of eye ray with every object, and save the closest object point found

o recall: ray is a direction in 3D space

o require various mathematical formulae to compute intersection of ray with planes, spheres, ellipsoids, cylinders, other surfaces and volumes

· contrast ray tracing with pure Z buffering

o ray tracing: 1024 by 1024 screen, 100 objects --> 100 Million intersections to compute

o Z buffering: saves nearest z value of objects that project to that pixel

§ --> no intersections, and only visible pixels used

· Ray tracing still useful for its ability to calculate lighting & effects, which would have to be done in Z buffering application anyway

· Can speed up ray tracing by exploiting coherence properties:

o optimizing intersection calculations, by computing equation values in advance and saving them; exploiting special properties of some geometries;

o avoiding intersection computations (object extent checks)

o exploiting spatial partitioning

b) Intersection of the ray from the viewpoint to the object is first checked for its intersection with the extent of the object. Suggest an efficient algorithm for this task. [9]

a) Compute the illumination of specular model for following:

n =j , L= -I +2j –k , S= I +3/2 j + 1/2 k [6]

e) Describe how hidden surface removal and projection are integrated into the ray-tracing process? [4]

b) The (implicit) canonical equation for an elliptic paraboloid is x² + y²- z = 0. Determine if a ray represented by the parametric vector s + td (where vector s specifies its starting point and d describes its direction) intersects the paraboloid. [10]

a) Explain briefly the OpenGL Utility Toolkit (GLUT). [6]

GLUT (pronounced like the glut in gluttony) is the OpenGL Utility Toolkit, a window system independent toolkit for writing OpenGL programs. It implements a simple windowing application programming interface (API) for OpenGL. GLUT makes it considerably easier to learn about and explore OpenGL programming. GLUT provides a portable API so you can write a single OpenGL program that works across all PC and workstation OS platforms.

GLUT is designed for constructing small to medium sized OpenGL programs. While GLUT is well-suited to learning OpenGL and developing simple OpenGL applications, GLUT is not a full-featured toolkit so large applications requiring sophisticated user interfaces are better off using native window system toolkits. GLUT is simple, easy, and small.

The toolkit supports:

· Multiple windows for OpenGL rendering

· Callback driven event processing

· Sophisticated input devices

· An 'idle' routine and timers

· A simple, cascading pop-up menu facility

· Utility routines to generate various solid and wire frame objects

· Support for bitmap and stroke fonts

· Miscellaneous window management functions

c) Explain RGBA mode of OpenGL. [6]

OpenGL has two color modes — the RGBA mode and color index mode. In RGBA mode, a color is specified by three intensities (for the Red, Green, and Blue components of the color) and optionally a fourth value, Alpha, which controls transparency.

The function glColor4f(red, green, blue, alpha) maps available red, green, and blue intensities onto (0.0, 1.0) where 0.0 means that the color component is absent ((0.0, 0.0, 0.0) is black) and 1.0 is a saturated color ((1.0, 1.0, 1.0) is white.)

The number of bits used to represent each color depends upon the graphics card. Current graphics cards have several Mbytes of memory, and use 24 or 32 bits for color (24-bit: 8 bits per color; 32-bit: 8 bits per color + 8 bits padding or transparency). The term bitplane refers to an image of single-bit values. Thus, a system with 24 bits of color has 24 bitplanes. Not long ago, 8 to 16 bits of color was usual, permitting only 256 to 64K individual colors. In order to increase the range of colors displayed, a color lookup table was often used. In the table, colors would be represented by, m−bit entries (e.g.m = 24). The length of this table was 2n, with colors selected1by an n-bit index.

For a system with 8 bitplanes, 28 = 256 different colors could be displayed simultaneously. These 256 colors could be selected from a set of 2m colors. For m = 24 this gives 224 _ 16 million colours. The color table could be altered to give different palettes of colors.

OpenGL supports this mode, called color index mode.The command glIndexf(cindex) sets the current color index

to cindex.

Analogous to glClearColor() there is a corresponding glClearIndex(clearindex) which sets the clearing color to

clearindex.2 OpenGL has no function to set a color lookup table, but GLUT has the function glutSetColor(GLint index, GLfloat red, GLfloat green, GLfloat blue) which sets the color at index to the intensities specified by red, green, and blue.

The function glGetIntegerv() with arguments GL_RED_BITS, GL_GREEN_BITS, GL_BLUE_BITS, GL_ALPHA_BITS, and

GL_INDEX_BITS allows you to determine the number of bits for the identified entity.

Color-index mode does not support transparency.

Choosing between color modes

In general, RGBA mode provides more flexibility, and is fully supported by current hardware.

Color index mode may be useful when:

• porting or modifying an existing program using color-index mode

• only a small number of bitplanes are available (e.g., 8 bits — possibly 3 for red, 3 for green, and 2 for blue, giving a

very small range for each color)

• drawing layers or color-map animation are used.

Shading models

OpenGL has two shading models; primitives are drawn with a single color (flat shading) or with a smooth color variation

from vertex to vertex (smooth shading, or Gouraud shading) The shading mode is specified with glShadeModel(mode) where mode is either GL_SMOOTH or GL_FLAT.

In RGBA mode, the color variation is obtained by interpolating the RGB values. The interpolation is on each of the R, G, and B components, and is in the horizontal and vertical directions. In color index mode, the index values are interpolated, so the color table must be loaded with a set of smoothly changing colors.

For flat shading, the color of a single vertex determines the color of the polygon. For the situation where lighting elements are present, a more elaborate shading algorithm can be used.

b) Explain the procedure of rendering the pipelines. [6]

In 3D graphics rendering, the stages required to transform a three-dimensional image into a two-dimensional screen. The stages are responsible for processing information initially provided just as properties at the end points (vertices) or control points of the geometric primitives used to describe what is to be rendered. The typical primitives in 3D graphics are lines and triangles. The type of properties provided per vertex include x-y-z coordinates, RGB values, translucency, texture, reflectivity and other characteristics.

An Assembly Line
Graphics rendering is like a manufacturing assembly line with each stage adding something to the previous one. Within a graphics processor, all stages are working in parallel. Because of this pipeline architecture, today's graphics processing units (GPUs) perform billions of geometry calculations per second. They are increasingly designed with more memory and more stages, so that more data can be worked on at the same time.

The Goal
For gamers, photorealistic rendering at full speed is the goal, and human skin and facial expressions are the most difficult. Although there are always faster adapters on the market with more memory and advanced circuitry that render 3D action more realistically, thus far, no game has fooled anyone into believing a real person is on screen, except perhaps for a few seconds.

Bus interface/Front End
Interface to the system to send and receive data and commands.

Vertex Processing
Converts each vertex into a 2D screen position, and lighting may be applied to determine its color. A programmable vertex shader enables the application to perform custom transformations for effects such as warping or deformations of a shape.

Clipping
This removes the parts of the image that are not visible in the 2D screen view such as the backsides of objects or areas that the application or window system covers

The Pipeline

These are the various stages in the typical pipeline of a modern graphics processing unit (GPU). (Illustration courtesy of NVIDIA Corporation.)

Primitive Assembly, Triangle Setup
Vertices are collected and converted into triangles. Information is generated that will allow later stages to accurately generate the attributes of every pixel associated with the triangle.

Rasterization
The triangles are filled with pixels known as "fragments," which may or may not wind up in the frame buffer if there is no change to that pixel or if it winds up being hidden.

Occlusion Culling
Removes pixels that are hidden (occluded) by other objects in the scene.

Parameter Interpolation
The values for each pixel that were rasterized are computed, based on color, fog, texture, etc.

Pixel Shader
This stage adds textures and final colors to the fragments. Also called a "fragment shader," a programmable pixel shader enables the application to combine a pixel's attributes, such as color, depth and position on screen, with textures in a user-defined way to generate custom shading effects.

Pixel Engines
Mathematically combine the final fragment color, its coverage and degree of transparency with the existing data stored at the associated 2D location in the frame buffer to produce the final color for the pixel to be stored at that location. Output is a depth (Z) value for the pixel.

Frame Buffer Controller
The frame buffer controller interfaces to the physical memory used to hold the actual pixel values displayed on screen. The frame buffer memory is also often used to store graphics commands, textures as well as other attributes associated with each pixel.

c) Explain the following statement:

void glPolygonMode(GLenum face, GLenum mode);

void glFrontFace(GLenum mode); [4]

glPolygonMode — select a polygon rasterization mode

C Specification

void glPolygonMode( GLenum face, GLenum mode);

Parameters

face

Specifies the polygons that mode applies to. Must be GL_FRONT for front-facing polygons, GL_BACK for back-facing polygons, or GL_FRONT_AND_BACK for front- and back-facing polygons.

mode

Specifies how polygons will be rasterized. Accepted values are GL_POINT, GL_LINE, and GL_FILL. The initial value is GL_FILL for both front- and back-facing polygons.

The glFrontFace function defines front-facing and back-facing polygons.

Copy

void WINAPI glFrontFace( GLenum mode);

mode

The orientation of front-facing polygons. GL_CW and GL_CCW are accepted. The default value is GL_CCW.

Return Value

This function does not return a value.

c) Describe rendering pipeline in OpenGL. [10]

OpenGL Pipeline has a series of processing stages in order. Two graphical information, vertex-based data and pixel-based data, are processed through the pipeline, combined together then written into the frame buffer. Notice that OpenGL can send the processed data back to your application. (See the grey colour lines)

OpenGL Pipeline

Display List

Display list is a group of OpenGL commands that have been stored (compiled) for later execution. All data, geometry (vertex) and pixel data, can be stored in a display list. It may improve performance since commands and data are cached in a display list. When OpenGL program runs on the network, you can reduce data transmission over the network by using display list. Since display lists are part of server state and reside on the server machine, the client machine needs to send commands and data only once to server's display list. (See more details in Display List.)

Vertex Operation

Each vertex and normal coordinates are transformed by GL_MODELVIEW matrix (from object coordinates to eye coordinates). Also, if lighting is enabled, the lighting calculation per vertex is performed using the transformed vertex and normal data. This lighting calculation updates new color of the vertex. (See more details in Transformation)

Primitive Assembly

After vertex operation, the primitives (point, line, and polygon) are transformed once again by projection matrix then clipped by viewing volume clipping planes; from eye coordinates to clip coordinates. After that, perspective division by w occurs and viewport transform is applied in order to map 3D scene to window space coordinates. Last thing to do in Primitive Assembly is culling test if culling is enabled.

Pixel Transfer Operation

After the pixels from client's memory are unpacked(read), the data are performed scaling, bias, mapping and clamping. These operations are called Pixel Transfer Operation. The transferred data are either stored in texture memory or rasterized directly to fragments.

Texture Memory

Texture images are loaded into texture memory to be applied onto geometric objects.

Raterization

Rasterization is the conversion of both geometric and pixel data into fragment. Fragments are a rectangular array containing color, depth, line width, point size and antialiasing calculations (GL_POINT_SMOOTH, GL_LINE_SMOOTH, GL_POLYGON_SMOOTH). If shading mode is GL_FILL, then the interior pixels (area) of polygon will be filled at this stage. Each fragment corresponds to a pixel in the frame buffer.

Fragment Operation

It is the last process to convert fragments to pixels onto frame buffer. The first process in this stage is texel generation; A texture element is generated from texture memory and it is applied to the each fragment. Then fog calculations are applied. After that, there are several fragment tests follow in order; Scissor Test ⇒ Alpha Test ⇒ Stencil Test ⇒ Depth Test.
Finally, blending, dithering, logical operation and masking by bitmask are performed and actual pixel data are stored in frame buffer.

Feedback

OpenGL can return most of current states and information through glGet*() and glIsEnabled() commands. Further more, you can read a rectangular area of pixel data from frame buffer using glReadPixels(), and get fully transformed vertex data using glRenderMode(GL_FEEDBACK). glCopyPixels() does not return pixel data to the specified system memory, but copy them back to the another frame buffer, for example, from front buffer to back buffer.

g)OpenGL provides three basic commands for manipulating image data, explain each briefly. [4]

OpenGL provides three basic commands that manipulate image data:

glReadPixels() - Reads a rectangular array of pixels from the framebuffer and stores the data in processor memory.
glDrawPixels() - Writes a rectangular array of pixels into the framebuffer from data kept in processor memory.
glCopyPixels() - Copies a rectangular array of pixels from one part of the framebuffer to another. This command behaves something like a call to glReadPixels() followed by a call to glDrawPixels(), but the data is never written into processor memory.

c) Define point, line and polygon w.r.t. OpenGL [6]

A point, for example (a single location defined by [x, y, z] coordinates), is defined by one vertex, but often simply thought of as a simple 3D location in space. Points can make excellent particle effects such as sparks, or dust particles glimmering as they pass through the rays of light. Even though we are working with 3D graphics, rendering a single point on the screen by itself creates an illusion of 2D space, because our monitor screens are flat, or 2-dimensional and there is nothing to indicate depth.

A line has only 2 vertices - which are its starting and its ending points; a line can be thought of as two connected vertices in 3D space, if the two vertices are positioned in the same exact [x,y,z] location, it can be thought of as a point, but almost never used in that way. Lines are great for visual representations of the concepts of physics, such as springs, as well as other interesting objects that don't make sense to be drawn with points or polygons, such as electrical wires.

A polygon is a 3-Dimensional surface defined by 3 or more vertices. A triangle is, for instance, a polygon with 3 vertices. A quad is not truly a primitive, because in software it is always broken into two triangles anyway. However, under the OpenGL implementation quads are treated as separate primitives, as long as the two triangles they always consist of are coplanar.

The main function (and quite possibly the most used OpenGL call) is the function named glVertex. This function defines a point (or a vertex) in your 3D world and it can vary from receiving from 2 to up to 4 coordinates.

glVertex

glVertex2f(100.0f, 150.0f); defines a point at x = 100, y = 150, z = 0; this function takes only 2 parameters, z is always 0. glVertex2f can be used in special cases and won't be used a lot unless you're working with pseudo-2D sprites or triangles and points that always have to be constrained by the depth coordinate. glVertex3f(100.0f, 150.0f, -25.0f); defines a point at x = 100, y = 150, z = -25.0f; this function takes 3 parameters, defining a fully 3D point in your world. This function will be used a lot to define any kind of shapes you will possibly want. glVertex4f(100.0f, 150.0f, -25.0f, 1.0f); this is the same as glVertex3f, the only difference is in the last coordinate that specifies a scaling factor. The scaling factor is set to 1.0f by default.

These functions are glBegin( int mode ); and glEnd( void ); glBegin and glEnd delimit the vertices of a primitive or a group of like primitives. What this means is that everytime you want to draw a primitive on the screen you will first have to call glBegin, specifying what kind of primitive it is that you want to draw in the mode parameter of glBegin, and then list all vertices one by one (by sequentially calling glVertex) and finally call glEnd to let OpenGL know that you're done drawing a primitive. The parameter mode of the function glBegin can be one of the following: GL_POINTS GL_LINES GL_LINE_STRIP GL_LINE_LOOP GL_TRIANGLES GL_TRIANGLE_STRIP GL_TRIANGLE_FAN GL_QUADS GL_QUAD_STRIP GL_POLYGON These flags are self-explanatory. As an example I want to show how to draw some primitives and then you will be able to understand how to draw the rest of them.

// this code will draw a point located at [100, 100, -25]

glBegin(GL_POINTS);

glVertex3f(100.0f, 100.0f, -25.0f);

glEnd( );

// next code will draw a line at starting and ending coordinates specified by glVertex3f

glBegin(GL_LINES);

glVertex3f(100.0f, 100.0f, 0.0f); // origin of the line

glVertex3f(200.0f, 140.0f, 5.0f); // ending point of the line

glEnd( );

// the following code draws a triangle

glBegin(GL_TRIANGLES);

glVertex3f(100.0f, 100.0f, 0.0f);

glVertex3f(150.0f, 100.0f, 0.0f);

glVertex3f(125.0f, 50.0f, 0.0f);

glEnd( );

// this code will draw two lines "at a time" to save

// the time it takes to call glBegin and glEnd.

glBegin(GL_LINES);

glVertex3f(100.0f, 100.0f, 0.0f); // origin of the FIRST line

glVertex3f(200.0f, 140.0f, 5.0f); // ending point of the FIRST line

glVertex3f(120.0f, 170.0f, 10.0f); // origin of the SECOND line

glVertex3f(240.0f, 120.0f, 5.0f); // ending point of the SECOND line

glEnd( );

b) In OpenGL programming, explain how you can specify lines with different widths and lines that are stippled in various ways-dotted, dashed, drawn with alternating dots and dashes. [8]

Displaying Points, Lines, and Polygons

By default, a point is drawn as a single pixel on the screen, a line is drawn solid and 1 pixel wide, and polygons are drawn solidly filled in. The following paragraphs discuss the details of how to change these default display modes.

Point Details

To control the size of a rendered point, use glPointSize() and supply the desired size in pixels as the argument.

void glPointSize(GLfloat size);

Sets the width in pixels for rendered points; size must be greater than 0.0 and by default is 1.0.

The actual collection of pixels on the screen that are drawn for various point widths depends on whether antialiasing is enabled. (Antialiasing is a technique for smoothing points and lines as they’re rendered; see “Antialiasing” and “Point Parameters” in Chapter 6 for more detail.) If antialiasing is disabled (the default), fractional widths are rounded to integer widths, and a screen-aligned square region of pixels is drawn. Thus, if the width is 1.0, the square is 1 pixel by 1 pixel; if the width is 2.0, the square is 2 pixels by 2 pixels; and so on.

Line Details

With OpenGL, you can specify lines with different widths and lines that are stippled in various ways—dotted, dashed, drawn with alternating dots and dashes, and so on.

Wide Lines

void glLineWidth(GLfloat width);

Sets the width, in pixels, for rendered lines; width must be greater than 0.0 and by default is 1.0.

Version 3.1 does not support values greater than 1.0, and will generate a GL_INVALID_VALUE error if a value greater than 1.0 is specified.

The actual rendering of lines is affected if either antialiasing or multisampling is enabled. (See “Antialiasing Points or Lines” on page 269 and “Antialiasing Geometric Primitives with Multisampling” on page 275.) Without antialiasing, widths of 1, 2, and 3 draw lines 1, 2, and 3 pixels wide. With antialiasing enabled, noninteger line widths are possible, and pixels on the boundaries are typically drawn at less than full intensity. As with point sizes, a particular OpenGL implementation might limit the width of non-antialiased lines to its maximum antialiased line width, rounded to the nearest integer value. You can obtain the range of supported aliased line widths by using GL_ALIASED_LINE_WIDTH_RANGE with glGetFloatv(). To determine the supported minimum and maximum sizes of antialiased line widths, and what granularity your implementation supports, call glGetFloatv(), with GL_SMOOTH_LINE_WIDTH_RANGE and GL_SMOOTH_LINE_WIDTH_GRANULARITY.

With non-antialiased wide lines, the line width isn’t measured perpendicular to the line. Instead, it’s measured in the y-direction if the absolute value of the slope is less than 1.0; otherwise, it’s measured in the x-direction. The rendering of an antialiased line is exactly equivalent to the rendering of a filled rectangle of the given width, centered on the exact line.

Stippled Lines

To make stippled (dotted or dashed) lines, you use the command glLineStipple() to define the stipple pattern, and then you enable line stippling with glEnable().

glLineStipple(1, 0x3F07);

glEnable(GL_LINE_STIPPLE);

void glLineStipple(GLint factor, GLushort pattern);

Sets the current stippling pattern for lines. The pattern argument is a 16-bit series of 0s and 1s, and it’s repeated as necessary to stipple a given line. A 1 indicates that drawing occurs, and a 0 that it does not, on a pixel-by-pixel basis, beginning with the low-order bit of the pattern. The pattern can be stretched out by using factor, which multiplies each subseries of consecutive 1s and 0s. Thus, if three consecutive 1s appear in the pattern, they’re stretched to six if factor is 2. factor is clamped to lie between 1 and 256. Line stippling must be enabled by passing GL_LINE_STIPPLE to glEnable(); it’s disabled by passing the same argument to glDisable().

Compatibility Extension

glLineStipple

GL_LINE_STIPPLE

With the preceding example and the pattern 0x3F07 (which translates to 0011111100000111 in binary), a line would be drawn with 3 pixels on, then 5 off, 6 on, and 2 off. (If this seems backward, remember that the low-order bit is used first.) If factor had been 2, the pattern would have been elongated: 6 pixels on, 10 off, 12 on, and 4 off. Figure 2-8 shows lines drawn with different patterns and repeat factors. If you don’t enable line stippling, drawing proceeds as if pattern were 0xFFFF and factor were 1. (Use glDisable() with GL_LINE_STIPPLE to disable stippling.) Note that stippling can be used in combination with wide lines to produce wide stippled lines.

One way to think of the stippling is that as the line is being drawn, the pattern is shifted by 1 bit each time a pixel is drawn (or factor pixels are drawn, if factor isn’t 1). When a series of connected line segments is drawn between a single glBegin() and glEnd(), the pattern continues to shift as one segment turns into the next. This way, a stippling pattern continues across a series of connected line segments. When glEnd() is executed, the pattern is reset, and if more lines are drawn before stippling is disabled the stippling restarts at the beginning of the pattern. If you’re drawing lines with GL_LINES, the pattern resets for each independent line.

Example 2-5. Line Stipple Patterns: lines.c

#define drawOneLine(x1,y1,x2,y2) glBegin(GL_LINES); glVertex2f((x1),(y1)); glVertex2f((x2),(y2)); glEnd();

void init(void)

{

glClearColor(0.0, 0.0, 0.0, 0.0);

glShadeModel(GL_FLAT);

}

void display(void)

{

int i;

glClear(GL_COLOR_BUFFER_BIT);

/* select white for all lines */

glColor3f(1.0, 1.0, 1.0);

/* in 1st row, 3 lines, each with a different stipple */

glEnable(GL_LINE_STIPPLE);

glLineStipple(1, 0x0101); /* dotted */

drawOneLine(50.0, 125.0, 150.0, 125.0);

glLineStipple(1, 0x00FF); /* dashed */

drawOneLine(150.0, 125.0, 250.0, 125.0);

glLineStipple(1, 0x1C47); /* dash/dot/dash */

drawOneLine(250.0, 125.0, 350.0, 125.0);

/* in 2nd row, 3 wide lines, each with different stipple */

glLineWidth(5.0);

glLineStipple(1, 0x0101); /* dotted */

drawOneLine(50.0, 100.0, 150.0, 100.0);

glLineStipple(1, 0x00FF); /* dashed */

drawOneLine(150.0, 100.0, 250.0, 100.0);

glLineStipple(1, 0x1C47); /* dash/dot/dash */

drawOneLine(250.0, 100.0, 350.0, 100.0);

glLineWidth(1.0);

/* in 3rd row, 6 lines, with dash/dot/dash stipple */

/* as part of a single connected line strip */

glLineStipple(1, 0x1C47); /* dash/dot/dash */

glBegin(GL_LINE_STRIP);

for (i = 0; i < 7; i++)

glVertex2f(50.0 + ((GLfloat) i * 50.0), 75.0);

glEnd();

/* in 4th row, 6 independent lines with same stipple */

for (i = 0; i < 6; i++) {

drawOneLine(50.0 + ((GLfloat) i * 50.0), 50.0,

50.0 + ((GLfloat)(i+1) * 50.0), 50.0);

}

/* in 5th row, 1 line, with dash/dot/dash stipple */

/* and a stipple repeat factor of 5 */

glLineStipple(5, 0x1C47); /* dash/dot/dash */

drawOneLine(50.0, 25.0, 350.0, 25.0);

glDisable(GL_LINE_STIPPLE);

glFlush();

}

DOEACC NOTES

Monday, August 20, 2012

COMPUTER GRAPHICS AND MULTIMEDIA SYSTEMS - CURVES

Calculating a surface normal

Radiosity - Ray Tracing

Ray tracing

Radiosity

Phong Shading Model for Scan-Line Graphics

Gouraud shading model.

Ray-casting is a technique that transform a limited form of data (a very simplified map or floor plan) into a 3D projection by tracing rays from the view point into the viewing volume

Raytracing algorithm

·

The Pre-Rendering Section

·

The Main Rendering Loop

·

The Post-Rendering Section

The Pre-Rendering Section

The Main Rendering Loop

The Post-Rendering Section

Ray Tracing

Ray Tracing

Return Value

Display List

Vertex Operation

Primitive Assembly

Pixel Transfer Operation

Texture Memory

Raterization

Fragment Operation

Feedback

Wide Lines

Stippled Lines

Example 2-5. Line Stipple Patterns: lines.c

No comments:

Post a Comment