Scan Conversion of Bezier Surfaces

Pouyan Jazayeri

SS 2004

1

bersicht

Gegenstand dieser Studienarbeit war die Implementierung eines Verfahrens zur Scankon-vertierung von Bzier-Flchen. Hierbei sollte eine geeignete Methode ausgewhlt undimplementiert werden, wobei die korrekte Interpolation der Normalen, Farben und Tex-turkoordinaten fr den jeweiligen Oberchenpunkt eine wichtige Rolle spielten.

Die Aufgabe wurde durch den Einsatz von der Newtonsche Methode, eine Methodezur Nullstellenberechnung von multidimensionalen Polynomen, gelst. Das Programmberechnet, anhand der Kontrollpunkte, einen geeigneten Boundingbox und untersuchtjeden Pixel in dem Boundingbox mit der Newton-Methode auf Zugehrigkeit zu der un-tersuchten Flche. Die Methode liefert im Falle eines positiven Befundes die zugehrigenParametern, die den Pixel auf der Flche eindeutig denieren. Diese Parameter sind mitden Texturkoordinaten identisch und ermglichen die Texturbelegung.

Auerdem liefert die Methode die Ableitung in beiden parametrischen Richtungen dereinzelnen Funktionen, die die Punkte auf der Flche denieren. Diese Ableitungen wer-den dann dazu verwendet, fr jeden einzelnen Punkt auf der Flche, die Normalvektorenzu berechnen und damit die Beleuchtung zu ermglichen.

Thema in der Ausarbeitung ist auerdem die Startwertprobleme die im Einsatz desNewton-Verfahrens eintreten. Das Verfahren muss jeden Pixel mit mehreren Startwertenuntersuchen, um die Zugehrigkeit zur Flche eindeutig feststellen zu knnen. Auerdemmuss hierbei gewhrleistet werden, dass es sich um den Punkt mit dem richtigen Z-Werthandelt, um die richtige Normalvektoren und Texturkoordinaten ausrechnen zu knnen.

Abschlieend werden ein paar Testresultate prsentiert und Vorschlge zur Lsung desPerformance-Einben vorgelegt.

2

Contents

1 Introduction 4

2 Theoretical basis 5

2.1 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Bezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Bezier Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4 Root nding methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4.1 Root Finding of Polynomials . . . . . . . . . . . . . . . . . . . . . 102.4.2 Systems of Nonlinear Equations . . . . . . . . . . . . . . . . . . . . 12

3 Scan Conversion 13

3.1 Bezier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Bezier Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 Implementation and Results 20

4.1 Test Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

5 Outlook 23

3

1 Introduction

The technique of modeling parametric surfaces plays a major role in Computer AidedDesign (CAD) systems. This is due to the great precision and exibility that comes alongwith these types of surfaces. Rendering these surfaces is usually accomplished by usingtriangles and polygones. The question is, whether this can be accomplished by directscan conversion of the surfaces in question.

The aim of this paper was the implementation of a procedure suited for the scan con-version of Bezier surfaces. Whereas the correct interpolation of normal vectors, lightingand texture coordinates also played a crucial part in this objective.

The paper is divided into four sections. The rst section deals with the theoreticalbasis needed to understand Bezier curves and surfaces and the algorithm which was im-plemented during the work on this paper. It also discusses root nding methods whichplay a crucial role in the process of the scan conversion of Bezier surfaces.

The second section explains the scan conversion process of Bezier curves and surfaces,providing a step by step walk through of the algorithm. It also deals with the problemswhich occurred during the implementation.

The third section presents some testing results, in form of the time needed for the algo-rithm to render the surface using scan conversion.

The nal section serves as an outlook to future ameliorations, which could be exam-ined to accelerate and enhance the scan conversion process.

4

2 Theoretical basis

This section covers the mathematical foundation of parametric curves and surfaces andspecically those invented by Pierre Etienne Bezier. It also discusses the concept ofnding the roots of one-dimensional and multi-dimensional polynomials. These numericalmethods are used in the scan conversion algorithm of this paper.

2.1 Representation

The representation of curves and surfaces in mathematics is handled explicitly, implicitlyor paramatically.[5]

An example of an explicit representation of a curve would be: y = f(x).

The implicit representation of a curve on the other hand, is of the form f(x, y) = 0and that of a surface of the form f(x, y, z) = 0.

Although both methods have their advantages and disadvantages, and have diverse usesin computergraphics and CAD, the focus of this paper however is on Bezier curves andsurfaces. Bezier curves and Bezier surfaces are dened parametrically. The parametricrepresentation of a curve is in the form:

x = f(t) y = g(t) z = h(t) (1)

This method of expressing curves and surfaces has a lot of advantages compared to theimplicit and the explicit representation. Since a point on a parametric curve is speciedby a single value of parameter, the use of parametric techniques emancipates from de-pendency on any particular system of coordinates. Therefore, the parametric descriptionof a curve enables coordinate transformations such as translation and rotation, requiredfor graphical display, to be performed very simply. The parametric form also avoidsproblems which can arise in representing closed or multiple-valued curves and curveswith vertical tangents in a xed coordinate system. Due to these advantages, parametriccurves are most commonly used in computer aided geometric design.[7]

Parametrical representation of a surface on the other hand, requires two parametersinstead of only one. The reason for this is the nature of a surface as a two dimensionalentity. The representation is in the form:

x = x(u, v) y = (u, v) z = z(u, v) (2)

In analogy with the curve representation, only the parameters u and v are needed tospecify a point on the surface.Having dealt with the dierent types of curve and surface representation and categorizingBezier curves and surfaces as parametric, the next subsections shall further dene andelaborate Bezier curves and surfaces.

5

2.2 Bezier Curves

Bezier curves are named after the french mathematician and engineer Pierre EtienneBezier(1910-1999). He invented them while he was working for Renault in the 1960s ona system called UNISURF. His system, despite initial resistance1, is still in use today.

A Bezier Curve is dened by the following term

C(t) =n

i=0

PiBi,n(t) 0 t 1 (3)

where Pi is a set of control points and Bn,i(t) is a set of basis or blending functions.The basis or blending functions are in fact Bernstein polynomials, which are dened as

Bi,n(t) =(

n

i

)ti(1 t)ni (4)

Fig. 1 illustrates the polynomials for n ranging from 3 to 5:

Three interesting observations can be made from these graphs:

Figure 1: Bernstein polynomials[6]

1. at t=0, B0,n is equal to 1 and all other polynomials are equal to zero.

2. at t=1, Bn,n is equal to 1 and all other polynomials are equal to zero.

3. All of the blending functions are positive for 0

These observations have the following implication:

Since each point on the Bezier curve is dened by a multiplication of the control pointswith the blending functions, observation 1 means that the rst control point is alwayson the curve and is in fact the starting point.

Observation 2 indicates, that the last control point must also lie on the curve and that itis in fact the ending point of the curve. Finally, observation 3 indicates, that the curveis a weighted average of the control points and must be contained within the convex hullof its dening control points.

A Bezier curve is therefor dependent of the number and position of the control pointsand has the following properties:

1. The bezier curve is a spline curve2, and it is thus sometimes called a Bezier spline.[8]

2. Degree: The degree of a Bezier curve is always one less than the number of controlpoints.

3. Interpolation: the rst and the last control point are always on the curve, animplication from the formula dening the curve at C(0) = P0 and C(1) = Pn.

4. Convex hull property: The curve is contained in the convex hull of its deningcontrol points. This is due to the fact that the curve is a weighted average of thecontrol points.

5. Variation diminishing property: No straight line intersects a Bzier curve moretimes than it intersects its control polygon3.[3]

6. Tangency: The endpoint tangent vectors are parallel to P1 P0 and Pn Pn1.

7. Global control: Moving a control point alters the shape of the whole curve.

2Spline curves are a family of functions that create smooth curves from control points3The polygon that is drawn by the control points.

7

2.3 Bezier Surfaces

The denition of Bezier surfaces is very straightforward and conclusive once one is fa-miliar with Bezier curves. In analogy with the curve, a Bezier surface is also dened bycontrol points and Bernstein polynomials. However, there are also a few dierences. Inorder to specify a point or a vertice on a surface, one requires two parameters and twosets of blending functions for each parametric direction. This is due to the fact that asurface is a two dimensional entity. Basically the Bezier surface is a cartesian product ofthe blending functions of two orthogonal Bezier curves.

Thus a Bezier surface is dened by the following term:

S(u, v) =n

i=0

mj=0

Pi,jBn,i(u)Bm,j(v) (5)

Bn,i and Bm,j are the Bernstein basis function in the u and v parametric directions with:

Bn,i(u) =(

n

i

)ui(1 u)ni (6)

Bm,j(v) =(

m

j

)uj(1 v)mj

The Pi,j are the vertices of a polygon control net, as shown in g.2

Figure 2: a control net and resulting Bezier surface[6]

8

Bezier surfaces have a few very important properties:

1. The surface generally follows the shape of the control net.

2. Only the corner points and the resulting Bezier surface are coincident.

3. The surface is contained within the convex hull of the control net.

4. The degree of the surface in each parametric direction is one less than the numberof control net vertices in that direction.

5. Each of the boundary curves of a Bezier surface is a bezier curve.[5]

The second property becomes evident by setting the u and v to 0 or 1.The following rule applies :

S(u, v) = Pu,v u {0, 1} v {0, 1} (7)

Since we start counting at 0, the indices n and m are always one less than the numberof control vertices in the u and v direction, which explains the fourth property.

Having dened dened Bezier curves and surfaces, the nex subchapter will discuss rootnding methods which are an elementary part of the scan conversion algorithm.

9

2.4 Root nding methods

Finding the roots of a polynomial function f(x) = 0 is an elementary problem of mathe-matics. The Rasterization program that was implemented for this paper, also uses rootnding methods for the scan conversion of Bezier curves and surfaces. For Bezier curves,we will need a method that nds the roots of a polynomial. For surfaces, we will need amethod to solve a system of nonlinear equations.

2.4.1 Root Finding of Polynomials

A polynomial is dened as:

ni=0

aixi (8)

with ai as the coecients and n as the degree of the polynomial.

Finding the roots of polynomials is a classic problem of mathematics. An interestingexample were the old Babylonians, who were able to determine the square root of a pos-itive integer number 4000 years ago by using numerical methods 4.

To nd the roots of a polynomial of the second degree, one would use the quadraticformula5 and for those of the third degree, the formula of Cardano6.The Cardano formula uses trigonometric functions to determine the real roots of cubicpolynomial, thus making it unsuitable for computation. To make matters worse, thereis no linear method to solve the roots of polynomials with higher degrees. Numericalanalysis on the other hand, oers several methods to solve this problem. Among thesemethods are the Secant methode, Regula Falsi and the Newton method. Because of itsquadratic convergence, the newton method is the right choice for the implementation.

The newton method is an iterative, ecient method which is dened as:

xn+1 = xn f(x)f (x)

(9)

The iteration can only work by initiating with a start value close enough to the ac-tual root. If the start value is close enough, the iteration manages to approximate theroot with sucient accuracy in only a few loops.

4for more information see: http://www.maths.uwa.edu.au/ schultz/3M3/L1Babylonianroot2.html5for more information see: http://en.wikipedia.org/wiki/Quadratic_equation6for more information see: http://en.wikipedia.org/wiki/Cubic_equation

10

Figure 3: An illustration of Newton's method[1]

As an example, consider solving the following equation: cos(x) = x3

The problem can be rephrased as: cos(x) x3 = 0

Now all that is left to be done is nding the roots of the equation using newtonsmethod:we have f (x) = sin(x) x3 and since cos(x) 1 x and x3 > 1 x > 1, the rootmust lie between 0 and 1.

By trying a start value x=0.5, we get:

x1 = x0 f(x0)f (x0) = 0.5cos(0.5)0.53

sin(0.5)30.52 = 1.112141637097

x2 = x1 f(x1)f (x1)... = 0.909672693736

x3...

... = 0.867263818209

x4...

... = 0.865477135298

x5...

... = 0.865474033111

x6...

... = 0.865474033102

(10)

The underlined numbers are the correct digits of the root. The iteration manages toapproximate the root very precisely after only a few iterations. The quadratic conver-gence can be observed by looking at the iteration steps from three to ve. The correctdigits grow from two to ten and emphasize the convergence speed of the iteration.

11

2.4.2 Systems of Nonlinear Equations

Newton's method can be extended to nd the roots of multidimensional polynomials.The method is not able to nd the roots of a single polynomial, it can however solvea system of Nonlinear equations. The Newton-Raphson method employs the derivativeof a function to estimate its intercept with the axis of the independent variable. Thisestimate was based on a rst-order Taylor series expansion.[9]For clarication, we consider the following example:

u(x, y) = 0 (11)v(x, y) = 0

A rst-order Taylor series expansion can be written as

ui+1 = ui + (xi+1 xi)uix

+ (yi+1 yi)uiy

(12)

vi+1 = vi + (xi+1 xi)vix

+ (yi+1 yi)viy

Rearranging the equation gives

uix

xi+1 +uiy

yi+1 = ui + xiuix

+ yiuiy

(13)

vix

xi+1 +viy

yi+1 = vi + xivix

+ yiviy

and nally

xi+1 = xi ui

viy vi

uiy

uix

viy

uiy

vix

(14)

yi+1 = yi vi

uix ui

viy

uix

viy

uiy

vix

The implementation of this iterative method is very straightforward. We do howeverhave to specify a termination criteria, which is small enough to rule out any false posi-tives. If the criteria is chosen too generously, it could lead the method to nd the wrongroots and the algorithm would not be able to render the surface correctly.

Having discussed the theoretical basis of Bezier curves and surfaces and the root nd-ing methods used in the algorithm, the next chapter will discuss the scan conversionalgorithm.

12

3 Scan Conversion

Rasterization or scan conversion is the process by which a primitive is converted to atwo-dimensional image.[4] This chapter discusses the algorithms for the scan conversionof Bezier curves and surfaces. To keep things a little simpler, it will only handle theimplementation for cubic Bezier curves and cubic Bezier surfaces.Cubic Bezier curves are interpolated by 4 control points (n=3) and cubic Bezier surfacesare interpolated from a grid of 4 4 controlpoints(n=m=3)

3.1 Bezier Curves

A good example of rasterization is the Bresenham line-drawing algorithm. It basicallyworks by wandering over the x-achses pixelwise and determining the corresponding y-values.7 A line is dened by the following term:

f(x) = ax + c (15)

The polynomial dening the line is of the rst degree. The consequence is, that the gra-dient is constant for all x, namely c, and that each x-value has one unique correspondingy-value. The mentioned properties facilitate the implementation. With bezier curves,specically cubic bezier curves, unfortunately, these two advantages are nonexistent. Ifwe split up the denition of the curve in the functions which dene each dimension, weget:

C(t) =

f(t) =

3i=0 PxiBi,3(t), with f dening the x-values;

g(t) =3

i=0 PyiBi,3(t), with g dening the y-values.

(16)

The curve is thus dened by a set of two functions.

The polynomials dening each x and y value are of the third degree, therefor the gra-dient varies throughout the functions and each x-value might have up to three dierentcorresponding y-values. The Bezier curve is thus not a function, it is a relation.

For the scan conversion of the surface, we have to determine the t value(s) for the current

7for more information see:http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

13

x-value and substitute them in the g function, determining the corresponding y-value(s)in the process.In order to achieve this goal, it is necessary to transform the f -function in the followingway:

f(t) =3

i=0

PxiBi,3(t) 0 t 1 (17)

f(t) = (1 t)3x0 + 3t(1 t)2x1 + 3t2(1 t)x2 + t3x3 f(t) = (Px0 + 3Px1 3Px2 + Px3)t3 + (3Px0 6Px1 + 3Px2)t2

+ (3Px0 + 3Px1)t + Px0

The value of f(t) is evident, since it is the actual x-value of the scan conversion al-gorithm. Keeping this in mind, the equation can be transformed to:

(Px0 + 3Px1 3Px2 + Px3)t3 + (3Px0 6Px1 + 3Px2)t2 (18)+(3Px0 + 3Px1)t + Px0 f(t) = 0

The coordinates of the control points and the value of f(t) are a given, which reduces theproblem to nding the roots of a polynomial of the third degree. This problem can besolved by using newtons method(see 2.4.1 on page 10).

Having dealt with the problem of nding the actual coordinates of the curve, we arestill left with one problem: where do we start scanning the screen and where do we stop?

It is of course possible to scan the whole x-axis, but that would be a waist of resources.With lines, the answer is simple: we want to draw a line between two lines, so we wouldstart the algortihm at the x-coordinate of the point with the smallest x-value and ter-minate at the x-coordiante of the other point. Figure 4 illustrates that that approach isnot possible with Bezier curves, because they can have a much more complex shape.

Nevertheless, it is possible to isolate the scan range. We already know from the Bezierproperties(see 2.2 on page 6), that the curve must lie inside the polygon of the controlpoints. The scan range can therefor be limited to the highest and lowest x-value of thecontrol points.

14

Figure 4: Bezier curves

Summerizing the steps above, the algorithm functions in the following way:

1. Find out the highest and the lowest x-Value of the control points.

2. Initiate a loop starting from the lowest and ending at the highest x-value of thecontrol points, incrementing by a pixel.

3. For each x-value, nd out the t-value(s) of the f -function by using newton's method(see 2.4.1on page 10).

4. Substitute the t-value(s) in the g-function to calculate the corresponding y-value(s).

15

3.2 Bezier Surfaces

This part of the paper discusses the algorithm for the scan conversion and the interpo-lation of normal vectors, lighting and textures of a cubic Bezier surface. A cubic Beziersurface is dened and shaped by a grid of 16 control points and is illustrated in gure 5.

Figure 5: bicubic bezier surface[2]

The algorithm has some analogy to the one for the Bezier curves. We have to denea scan range and determine the pixels that are on the surface. However, the procedureis much more complex. This becomes evident by looking at the formula more closely. Ifwe split the denition of the entire surface to specify the x,y,z parameters, we get:

S(u, v) =

f(u, v) =n

i=0

mj=0 Pxi,jBn,i(u)Bm,j(v), with f dening the x-values;

g(u, v) =n

i=0

mj=0 Pyi,jBn,i(u)Bm,j(v), with g dening the y-values.

h(u, v) =n

i=0

mj=0 Pzi,jBn,i(u)Bm,j(v), with g dening the z-values.

(19)

16

If we proceed the way we did with Bezier curves, two problems occur:

Firstly, the surface is a two-dimensional primitive in a three-dimensional space. Aswe already know from the denition of rasterizaton, we have to convert this primitiv intoa two-dimensional image. This procedure was not necessary in the previous algorithm,because the curve was already a one-dimensional primitive in a two-dimensional space.

The consequence of this approach is, that we do not need to render each vertice ofthe surface. It fully suces to calculate the vertices on the front of the view screen. Theother vertices do not appear on the screen and are therefor neglected by the renderingalgorithm. When it becomes necessary to display the other vertices, for example whenviewing the surface in an other angle, all that is needed to be done, is to transform thecontrol points respectively and calculate the surface again, using the new control points.

The second problem is that of nding the roots of the functions in analogy to our otheralgorithm. The newton method for multidimensional polynomials is not able to nd theroots of a single multidimensional function. It can however solve a system of nonlinearequations. This means that we can not scan the x-axis and draw the surface. The algo-rithm has to examine each pixel of the screen and determine if it is part of the surfaceor not.

Fortunately, it is possible to limit the scanning range by using the third property ofBezier surfaces, which states that the surface is contained within the convex hull of thecontrol net(see 2.3 on page 8). This implicates, that it suces to specify a bounding box.By rephrasing the f and g-function, we get:

ni=0

mj=0

Pxi,jBn,i(u)Dm,j(v) f(u, v) = 0 (20)

ni=0

mj=0

Pyi,jBn,i(u)Dm,j(v) g(u, v) = 0

f(u,v) an g(u,v) are a given, because they are the actual (x,y) coordinates of the pixelwe are scanning. Finding the roots of f and g is accomplished by using the Newtonmethod. The Method needs a starting-value-tuple (u,v) close enough to the actual root,to determine if the coordinate in question is part of the surface. With bezier surfaces, itis clear from the denition that the (u,v) tuple is between zero and one.

The advantage of this method is that in addition to determining if the pixel lies on thesurface, it also delivers the u and v coordinates belonging to the pixel and the derivatives

17

in each parametric direction.From these derivatives, and the derivatives of the h-function(for the z-value) we can cal-culate the normal vector for each pixel in the following way:

fuguhu

fvg

vhv

=nxny

nz

= ~n (21)

and the normalized normal vector:

~n0 =~n

|~n|(22)

The normalized normal vectors are therefor calculated for each pixel and lighting canbe applied to the surface. Applying texture on the surface is also very simple. As statedabove, the numerical method automatically determines the u and v parameter that spec-ies the position of the vertice on the surface. In OpenGL for example, all one has todo, is call the glTexCoord2f command, with the calculated u and v as parameters, beforecalling the command that actually puts the pixel on the screen.

The correct interpolation of the lighting and texture coordinates does however pose someproblems. This is due to the newton method. The Method does not tell us anythingabout the z-value of the examined coordinate.The surface could have multiple vertices, which have the same x and y-value but dierentz-values. Therefor, it is critical that the numerical method examines each coordinate withdierent start-value-tuples to nd out the vertice with the lowest or highest (dependingon the viewpoint specied by the user) z-value. Only then can it be guaranteed, that theright normal vector and texture coordinates are calculated.

A summarization of the algorithm would be the following steps:

1. We have to specify a bounding box with the lowest(highest) x-value of the controlpoints and the lowest(highest) y-value as the left down(right upper) corner.

2. We have to scan every pixel in the boundingbox in the following way:

18

Figure 6: Scan conversion of a Bezier Surface

a) We use the Newton-Raphson to determine if the pixel is on the surface. Ithas to be noted that the method has to be applied several times to make surethat the right z-value is detected

b) We have to save the (u,v) tuple and the derivatives which are calculated bythe numerical method.

c) We calculate the derivative of the h-function in both parametric directions

d) We calculate the normalized normal vectors, using the already specied deriva-tives.

e) We use the (u,v) tuple and the normalized normal vector to apply lightingand texture to the pixel.

3. For a view transformation, the control points need to be transformed and thesurface calculated again using the new control points

There were however several issues that had to be dealt with during the implementationof the algorithms for scan converting Bezier surfaces. These problems and the results ofthe implementation are elaborated in the next chapter.

19

4 Implementation and Results

A crucial step in implementing was the correct calculation of the three functions deningeach dimension of the surface8 and their respective derivatives in each parametric direc-tion.By taking a look at the f -function,

f(u, v) =n

i=0

mj=0

Pxi,jBn,i(u)Bm,j(v)

one can easily observe that the calculation of the formula in it's original form wouldbe a terrible waist of resources. The formula has to be brought in to a dierent form:

f(u, v) = c3,3u3v3 + c3,2u3v2... + c0,0 (23)

With ci,j as the coecient which consists of multiplications and additions of the x-valuesof the control points. For example, c0,0, c0,1 and c0,2 have the following values:

c0,0 = Px0,0 , c0,1 = 3(Px0,0 + Px0,1), c0,2 = 3(Px0,0 2Px0,1 + Px0,2) (24)

Rearranging the function in the above gives us some important advantages. The co-ecients are only calculated at the initiation of the algorithm, which removes a greatamount of redundant calculation. It also facilitates the calculation of the derivativeswhich then have the form:

f

u= 3c3,3u2v3 + 3c3,2u2v2... + c1,0 (25)

f

v= 3c3,3u3v2 + 2c3,2u2v... + c0,1

Another problem that had to be faced was that of the start-value-tuple. Because the pa-rameter tuple (u,v) is ranged between zero and one, one would assume that choosing thetuple (0.5,0.5) would approximate the root suciently in order for the numerical methodto work. Unfortunately, this was not the case. The algorithm needed several dierent

8see formula 19 on page 16

20

Figure 7: rendered with multiple start-value-tuples per pixel

Figure 8: rendered with a single start-value-tuples per pixel

start-value-tuples for each pixel to correctly pinpoint the surface. This is illustrated ingure 8, where there are clear holes in the surface on the right side. The start-value-tuple(0.5,0.5) was clearly near enough to the actual root for most vertices, but unfortunatelynot for all of them. This causes the algorithm to produce false negatives, which explainsthe incorrectly rendered surface in gure 8.

Additionally, due to the problem discussed in chapter 3.2 on page 16, it had to be guar-anteed, that the correct z-value was determined, to make sure that the normal vectorsand the texture coordinates are calculated correctly. This means, that it does not suceto terminate the iteration after a hit. The Newton iteration has to nd all the roots of apixel and calculate the appropriate z-value. Due to these two problems, the algorithm'seciency is reduced considerably.The following subchapter presents some test results of the rendering algorithm.

21

4.1 Test Results

The algorithm was tested on the following test system:

Test System

CPU 1.4 ghz centrino

FSB 400 MHZ

Memory 256 MB DDR-RAM

Graphics Intel 82855GME shared memory

Screen Size 640480 pixel

Figure 9: time to render: 8967 millisec-onds

Figure 10: time to render: 8009 millisec-onds

Figure 11: time to render: 4684 millisec-onds

Figure 12: time to render: 3076 millisec-onds

The gures above are of the same Bezier surface, which is rotated on the x-axis. One caneasily observe that the algorithm is much faster once the volume of the bounding boxis diminished. Concordantly, gure 12 is rendered almost three times faster than gure 9.

The high rendering time can be explained due to two problems already discussed inchapter 3.2: The start-value-tuple problem and the z-value Problem.

Solving these two problems would greatly accelerate the algorithm. If the surface couldbe rendered correctly, using only one start-value-tuple per pixel, the render time for theabove gures would be:

22

gure rendertime in msec/frame

9 971

10 827

11 451

12 237

5 Outlook

The algorithm developed during the work on this paper is able to successfully and cor-rectly scan convert a cubic Bezier surface. The task of correctly interpolate lighting,normal vectors and texture coordinates was accomplished as well.

The algorithm uses a numerical method, namely newton's method, to examine eachpixel in a predened bounding box, determined by the control points. The method isused to calculate the correct parameter coordinates and normalized normal vectors ofeach pixel.

There were however some problems which are discussed in the previous chapter. Theseproblems have to do with the eciency of the whole algorithm. As we already have dis-cussed, the shortcoming of the procedure is concentrated in the newton method, specif-ically in the start-value-tuple. The algorithm would be much more ecient if it werepossible to nd the roots by applying the numerical method only once for each pixel.

Two suggestions can be made to solve these problems. The rst suggestion is to ap-ply an other numerical method, which could be able to solve the root nding method ina more ecient way.

The second suggestion is to nd out a way to calculate the appropriate start-value-tuplebefore using it in newton's method. The second and fth property of Bezier surfaces(see 2.3 on page 8) clearly state that the corner points and the surface are coincidentand that each of the boundary curves of a Bezier surface is a Bezier curve. One canspeculate, that it could be possible to calculate a better start-value-tuple for each pixelfrom these statements.

23

References

[1] http://en.wikipedia.org/wiki/Newton%27s_method.

[2] http://home.tiscali.be/piet.verplancken3/bezier/node17.html.

[3] Andrs Iglesias. COMPUTER-AIDED GEOMETRIC DESIGN AND COMPUTERGRAPHICS: BEZIER CURVES AND SURFACES.http://personales.unican.es/iglesia, 2000.

[4] David Blythe. The OpenGL Graphics System.http://www.opengl.org/documentation/specs/version1.1/glspec1.1/node1.

html, 1997.

[5] David f. Rogers. An Introduction to NURBS. MORGAN KAUFMANN, 2002.

[6] Gerda Holmann und Astrid Heinze. Opengl.http://www-lehre.informatik.uni-osnabrueck.de/~cg/2000/skript/7_3_B%

_233_zier_Kurven.html, 2000.

[7] Pascal Vuylsteker. Types of Curves/Surface.http://escience.anu.edu.au/lecture/cg/Spline/curveTypes.en.html, 2002.

[8] Peter Shirley. Fundamentals of Computer Graphics. AK peters, 2002.

[9] Taechul Lee. Numerical Analysis for Chemical Engineers.http://prosys.korea.ac.kr/~tclee/lecture/numerical/lecture.html, 2001.

24

http://en.wikipedia.org/wiki/Newton%27s_methodhttp://home.tiscali.be/piet.verplancken3/bezier/node17.htmlhttp://personales.unican.es/iglesiahttp://www.opengl.org/documentation/specs/version1.1/glspec1.1/node1.htmlhttp://www.opengl.org/documentation/specs/version1.1/glspec1.1/node1.htmlhttp://www-lehre.informatik.uni-osnabrueck.de/~cg/2000/skript/7_3_B% _233_zier_Kurven.htmlhttp://www-lehre.informatik.uni-osnabrueck.de/~cg/2000/skript/7_3_B% _233_zier_Kurven.htmlhttp://escience.anu.edu.au/lecture/cg/Spline/curveTypes.en.htmlhttp://prosys.korea.ac.kr/~tclee/lecture/numerical/lecture.html

IntroductionTheoretical basisRepresentationBezier CurvesBezier SurfacesRoot finding methodsRoot Finding of PolynomialsSystems of Nonlinear Equations

Scan ConversionBezier CurvesBezier Surfaces

Implementation and ResultsTest Results

Outlook