CHAPTER ONE: INTRODUCTORY MATERIAL

1  Introduction

Computer Aided Geometric Design (CAGD) has its origin in the automobile industry and it is a discipline dealing with computational aspects of geometric objects. It deals fundamentally with describing forms, curves and surfaces of objects (i. e: a piece of machinery, the hull of a ship or of an aircraft... or some part of them)  in a simple but efficient and precise mathematical way which permits to transfer the characteristics of the object to the place where it will be manufactured.

Computer-Aided Geometric Design (CAGD) is the basis for modern design in most branches of industry, from naval and aeronautic to textile industry. Therefore this subject should be included in most schools and faculties of engineering. In principle, students should just get familiar with some specific design applications, such as FORAN, Rhino3D, Maxsurf, but a thorough knowledge of their capabilities comes from learning at least the algorithms that lie behind the application, even if the student is not to become a developer himself. This is the purpose of CAGD, the geometric description of algorithms for design.

The early developments in this field begin in 1959: the French automobile company Citroën employed a young mathematician in order to solve some of the theoretical problems that arose from the blueprint-to-computer challenge. The mathematician was Paul de Faget de Casteljau, who had just finished his PhD. He began to develop a system which primarily aimed at the ab initio design of curves and surfaces instead of focusing on the reproduction of existing blueprints. He adopted the use of Bernstein polynomials for his curve and surface definitions from the very beginning, together with what is now known as the de Casteljau algorithm.

Nowadays industrial design is mainly grounded on Non-Uniform Rational B-Splines (NURBS). These do not require great mathematical developments, just knowledge of polynomial and rational functions and a little bit of differential geometry of curves and surfaces. Therefore a course of CAGD could be included in the first semesters of most engineering studies.

One of the major drawbacks of a course on CAGD is that most design applications are too complicated for a basic course, since they usually include more possibilities than can be covered in it.  It would be advisable then either to provide simple tools that implement the basic algorithms of CAGD or to allow the students to write their own codes in a programming language familiar to them (C, Java, Matlab, Maple).

2  The affine plane

The affine plane is a couple of sets: A², formed by elements called points; and the linear space R²: the vector plane whose elements are the so called vectors. Vectors and points are linked by an application φ, that associates to each pair of points x,y ∊ A² the vector that connects them, i.e., the vector with origin and end in, respectively, x and y.

This can be computed by substraction: xy = y-x, y = x+xy. This states the fact that every point y is the result of a translation (adding) of the point x by the vector xy. 

The affine plane can be transformed by affine maps, sometimes called improperly linear. They respect the vector structure of the plane: if we use the relation between points and vectors in order to define in the vector plane a map f, having as a starting point the affine map f:

this map f shall be linear:

Hence, in order to define an affine map we only need a linear map and the image of a point, because if x = a+v,

These concepts can be easily extended to the affine space without any problem.

2.1  Cartesian Coordinates

As we shall work in the affine plane it is convenient to introduce a system of reference: we can describe the points as a couple of numbers: the so called cartesian coordinates of the point. Example.

In this cartesian system of reference, we must give a point, the origin of coordinates, and a pair of vectors that should be a basis in the vector plane. In a reference {a,e₁, e₂} we are able to express every point x of the plane by the coordinates  (x₁,x₂) of the vector that links it to the origin, ax,

As a way of distinguishing vectors from points, it is of convenient to express the coordinates of a point x as (1,x₁,x₂), and those of the vector ax as (0,x₁,x₂).

If  f is a linear map associated to the affine map f and M is the matrix of f in the basis {e₁,e₂}, therefore, due to f(x) = f(a)+f(ax), we can express the cartesian coordinates (y₁,y₂) of f(x) as:

As a result, if we have the image of a reference, we have, at the same time, the affine map described in a unique way.

2.2  Barycentric Coordinates

We will use them as a coordinate system when dealing with the plane. They are related with the cartesian coordinate system {a,e₁, e₂} by a translation: if we translate the origin a by each vector of the basis we obtain the barycentric reference  {a,b,c}, b = a+e₁, c = a+e₂.

If a point x has coordinates (1,x₁,x₂) in a cartesian reference, the barycentric coordinates are:

This states that a point with cartesian coordinates (1,x₁,x₂) has barycentric coordinates (1-x₁-x₂,x₁,x₂), that obviously sum one, because the sum of the coefficients of a barycentric combination must be equal to unity.

In the same way, a vector (0,x₁,x₂) in cartesian coordinates has barycentric coordinates (-x₁-x₂,x₁,x₂), which sum zero, as corresponds to a vector.

The interpretation of barycentric coordinates is quite simple: Consider two points {a,b}. If a point x is a barycentric combination of {a,b}, it can be written as x = (1-t)a+t b, i. e., ax = tab. Consequently barycentric combinations of {a,b} describe the straight line by a and b. 

If the barycentric coordinates (1-t) and t lie between zero and one, the point x belongs to the segment ab. The point a corresponds to t = 0 and the point b to t = 1. The points with t > 1 are beyond b and the ones with t < 0 are beyond a. Example

This leads us to a classical construction of affine geometry: the ratio of three collinear points a,b,x, is defined by

This is just the proportion between the two segments which the point x divides the segment ab into. Example

If x lies in the segment ab, the ratio is positive and the value is contained in the interval (0,∞). If X is beyond b, the ratio takes a value in the interval (-∞,-1). If x is beyond a, it takes a value in (-1,0). These are the degenerated cases: 

The importance of the ratio is due to the fact that affine maps are ratio preserving.

In the plane, we can classify points in terms of their barycentric coordinates. Given a reference {a,b,c}, if x = u a+v b+w c, and u+v+w = 1, the point x will be inside the triangle described by the reference if 0 < u,v,w < 1. If u = 0, the point will lie on the straight line bc and so. Example.

This property can be easily generalised to barycentric combinations of different points {a₁,...,a_n}: A point x = Σu_ia_i, with Σu_i = 1 and 0 < u₁,...,u_n < 1 is located inside the convex hull of {a₁,...,a_n}, i.e., the smallest convex polygon (with interiors angles smaller than π) that encloses each and every point.

Affine maps can be easily expressed in barycentric coordinates. Given x = x₀a+x₁b+x₂c,

Consequently, affine maps preserve barycentric coordinates,

This fact will be very useful on defining Bézier parametrizations.

Hence, we can express an affine map in a reference {a,b,c} as 

where (y₀,y₁,y₂) are the barycentric coordinates of the image, f(x), of a point x, of coordinates (x₀,x₁,x₂). The columns of the matrix M of the map are the coordinates of the images of the points in the reference {a,b,c}.

3  The projective plane

The asymmetry between points and vectors in the affine plane can be avoided thanks to a more complicated construction: the projective plane. In it points and vectors share the same expression. Only going back to the affine plane we could find the difference. Vectors will be the points at infinity.

Consider in R³ the set of all straight lines through the origin, and, assign  to every straight line a point in the projective plane P². In order to identify any point of P², let us take a point on every straight line by cutting them all by a plane, for instance, the plane x₀ = 1. Any straight line cuts that plane in a unique point, exception made of horizontal lines, parallel to the plane, that will cut x₀ = 1 in a point at infinity.

With this construction we have just assigned a point in the projective plane to every point of the affine plane x₀ = 1. The rest of the points are the so called points at infinity which can be associated to each and every direction of the horizontal lines that belong to the plane x₀ = 0. Therefore, every point at infinity matches a vector (actually, a straight line of vectors).

With this heuristic construction, we can transfer objects defined in the projective plane into the affine plane. A point belonging to the projective plane, defined in R³ by the vector (x₀,x₁,x₂), or by any other of the straight line (λx₀,λx₁,λx₂), in homogenous coordinates, can be transformed  into the point (1,x₁/x₀,x₂/x₀) if x₀ ≠ 0, of the affine plane, in inhomogenous coordinates. In case x₀ is equal to zero, it will be identified with the vector (0,x₁,x₂).

3.1  Projective Coordinates

In order to define a reference system in the projective plane we have to take three non-collinear points a,b,c of the projective plane (vector non-coplanar straight lines), and add a fourth point d, so that in the set {a,b,c;d} there are no three collinear points.  We call d the unity point, because it helps us to solve the ambiguity in choosing three vectors in R³ that verify

These vectors are unique, exception made of a multiplicative global factor (note that λa, λb, λc, λd, verify the condition as well).

Consequently, every time we fix the vector basis, {a,b,c}, the coordinates of x are (x₀,x₁,x₂), the point x of the projective plane will have as homogenous coordinates (λx₀,λx₁, λx₂), for any λ ≠ 0.

3.2  Projective Maps 

A projective map of the plane is an application f: P²® P², i. e., maps vector lines of R³ into vector lines of R³, and defines at the same time a linear map f: R³® R³, that: if f(x) = y, hence f(x) = y, where x,y are the representatives of the points x,y in the projective plane.

In a vector reference of R³, {a,b,c}, the map f will have a coordinate expression

where (x₀,x₁,x₂), (y₀,y₁,y₂) are the coordinates of x, f(x), respectively, in that basis and M is the matrix of f.

In the projective plane, in a reference {a,b,c;d}, where a,b,c,d are the vectors that verify (13), the matrix expression will be,

exception made of a multiplying factor λ ¹ 0.

Let us see it in an easy example on the projective line, P¹. In this case the equations of the projective map are

Now, if we project over the affine line and divide by the first component:

These are the so called Möbius transformations of the real line. In general, they are rational functions, but if B = 0, we recover the affine maps of the real line. If not, the image of x₁ = -A/B is off the affine line, because it is a point at infinity. They are projective maps that have not an affine equivalent, due to the fact of mixing the point at infinity with affine ones.

Let (C,D) be proportional to (A,B). We can factorize  the application and we get y₁ = const. This is a degenerated case that we can avoid assuming that AD-BC ≠ 0, i. e., assuming that the linear map is regular.

The projective maps are not ratio preserving, but cross ratio preserving. 

They preserve the quotient of two ratios. We define cross ratio  of the points a,b,c,x:

If we move the point b to infinity, the quotient cb/xb tends to unity and the cross ratio is well defined. Even more, assume that a = 0, c = 1 (if (1,0), (0,1) are the coordinates of a,b, respectively, then (1,1) are the ones of the unity point c). We get [0,∞,1,x] = x. Consequently, the cross ratio [a,b,c,x] provides us the inhomogenous coordinate of x in the reference {a,b;c}. Example