Loading

Module 1: Stages of Graphics Pipeline - Object Representation Techniques

Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Hello and welcome to lecture number 8 in the course Computer Graphics.
Today
we are going to discuss in detail about these two types of splines. Along with that, we are going
to talk about how these splines can be used to represent curves and surfaces in computer
graphics. Let us start with the idea of interpolating splines.
If you recall, interpolating splines are those where we define a set of control points and the Spline curve passes through those points. And we also mention 3 popular interpolating splines. Namely the Natural cubic spline, the Hermite cubic splines and the Cardinal cubic splines, all 3 are interpolating splines, meaning that they are defined by control points which passes through the Spline curves. So, let us now, go into some detailed discussion on each of these popular types. We will start with natural cubic spline.
Just a little bit of history. So this is one of the first splines. That was used in computer graphics applications. And as the name suggests, since it is a cubic spline so it is made up of pieces of third degree polynomials.
Now, each piece, each of the polynomial pieces is defined by 4 control points, we can denote
them as p0, p1, p2, p3. Recollect that when we are talking of polynomial interpolation, what we
mentioned earlier is that if we are using a polynomial of degree n, then we are going to have n
plus 1 control points. So, similarly here since the degree is three, so we have 4 control points.
Now in the case of natural cubic splines two of the control points p0 and p3 denote two boundary points that means the boundary value of the parameter u so p0 refers to the point when u = 0 and p3 refers to the point where u = 1. Now, the other two control points are essentially denoting the first and second derivatives at the starting point that is equal to 0. So, two control points are essentially points on the curves p0 and p3, which represents the two boundary points and the other two points are not points on the Curves, rather the first and second order derivatives with respect to the parameter u at u equal to 0.
Now let us try to represent this spline using one of the representation techniques. So, recollect again that spline can be represented in either of the two ways, namely a basis matrix representation and a blending function representations. We also mentioned that they are equivalent. So, any one representation is good enough. Now, in the context of interpolating representations, we will try to represent them using basis matrix form.
So, in case of natural cubic spline, since we are using cubic polynomial so the general polynomial piece equations should look something like this. Where a0, a1, a2 and a3 are coefficients, u is the parameter. Now we already know that p0 or the control point p0 and the control point p1 control point p2, it should be p2 and the control point p3 have specific meaning, so p0 and p3 represent the point at the boundaries. So, then we can set up the equations, something like this, p0 is the function value at u equal to 0 which we can obtain by replacing u with 0.
So, we will get a0, 0.a1, 0 square a2, 0 cube a3 just replace 0, replace u with 0. Similarly for p3, we have the function value at u equal to 1. So, in this case we replace u with 1 and we get something like this. These two are equations corresponding to the control points, p0 and p3, p1 and p2, as we said represent the first order and the second order derivative at u equal to 0. So, p1 is the first order derivative, p2 is the second order derivative with respect to u.
Now if we compute the derivatives and then replace u with value of 0 in case of p1, what we will get will get equation, something like this. You can try it yourself to first obtain the derivative and then replace the u values with 0. Now we compute the derivative again to get the second order derivative at u equal to 0 corresponding to p2 and then replace u with 0 again. And we get equation something like this.
So, these 4 equations represent the system of equations that we can obtain by utilizing the control point characteristics. And from these equations, from these set of equations, we can derive the basis matrix. How we can do that, we can first construct the constraint matrix by taking simply these values attached to the coefficients and then we take the inverse of that to get the basis matrix.
So, what is the constraint matrix? Let us recast the equation here. So, from there what we get, as
we can see, 1, 0, 0, 0, this is the first row. 0 1 0 0. This is the second row, 0 0, 2 and 0 this is the third row and finally 1, 1, 1, 1. This is the fourth row. So, just by utilizing these values, we get the constant matrix C.
Now, to get basis matrix what we need to do, we need to take the inverse of C, how to compute the inverse that we will not discuss here, of course, because that is a very basic knowledge. And you can refer to any book on basic matrix. Also, you can refer to the appendix of the reference material that will be mentioned at the end of this lecture to learn how to get the inverse of a matrix, assuming we already know that. So, if this is our constraint matrix C and if we take the inverse, the matrix that we will get is this one. And this is the basis matrix for the natural cubic spline.
So, let us recollect the series of steps we followed to get the basis matrix first we defined the control points then using those control points. We set up the system of equations and from the equations we formulated the constraint matrix C. Then we took the inverse of C to get the basis matrix, since basis matrix is the characteristic matrix for the cubic polynomials and that natural Cubic spline, are made up of cubic polynomials.
So, we can say that this basis matrix, which is characteristics of cubic polynomial is good enough to represent the natural cubic spline. So, we will follow that line of argument as discussed in the previous lecture.
So, if we simply use the matrix, then we can say that this is the natural cubic spline instead of specifying the equations or anything. Now, another important property here that these cubic splines have are that they support continuity conditions up to C2 continuity, parametric continuity up to C2 that means they support C0 continuity, C1 continuity and C2 continue.
But the problem is that cubic splines do not have local controllability. That means if we have a spline and we want to change its shape slightly by modifying a very few points on the curve, then we have to re-compute the whole curve rather than re-computing, only the localized area.
So, that is essentially a very inefficient approach. For example, suppose I have curve like this and I want to change this part to something like this, but then instead of just restricting our computation within this part, we have to actually compute the whole curve again. So, it does not support local controllability. Now, let us come to the second type of interpolating splines that is Hermite cubic splines like natural cubic, Hermite cubic splines are also represented by 4 control points.
However, it has one important property it supports local controllability. So, the main problem with natural cubic splines is alleviated with the Hermite cubic splines. So, the 4 control points that defines Hermite cubic splines can be denoted by p0, p1, p2 and p3.
Now where p0 and p2 are the values at the parameter boundaries that means u equal to 0 and u equal to 1, p1 is the first derivative at u equal to 0 and p2 is the first derivative at u = 1. So, earlier we had p0 and p3 to be the points at the boundary p1 and p2 are the first and second derivatives at the same point that is u equal to 0.
Now what we have is p0 and p2 here using to represent the points at the parameter boundaries, namely u equal to 0 and u equal to 1. P1 is the first derivative at u equal to 0 and P2 is the first derivative at u equal to 1. So, at both the boundary points we have first derivative denoted by the control points P1 and P2.
Following the approach we used to derive the basis matrix for natural cubic splines, we can also derive the basis matrix for the Hermite cubic splines, will not do that here. And you can try it yourself. The approach is same. So, you set up a system of equations, identify the constraint matrix take its inverse and get the basic matrix. The Matrix looks something like this, which is the representation for the Hermite cubic splines. Now, although the Hermite cubic splines support local controllability, but they do not support all
parametric continuity conditions, unlike the natural cubics, they support only C0 and C1 continuity conditions and do not support C2 condition. But natural cubics support all these threes C0, C1, C2. This implies that the curve that results from the Hermite cubics polynomials are less smooth compared to natural cubic polynomial base spline. So, at the expense of smoothness. We are getting the local controllability property, so we are getting local controllability, but we are losing to some extent, the degree of smoothness in the curve.
Now, one problem here is that we have to specify the first order derivatives. As control points and both the boundaries, clearly this puts extra burden on the user. To avoid that we have another spline curve that is the cardinal cubic splines. Now, with this spline, we can resolve the problem that we faced with Hermite cubic splines that is having to define the first order derivative and both the boundary points.
Like before since again, we are dealing with cubic splines, this splines is also made up of polynomial pieces, and each piece is defined by 4 control points. Again, we are denoting them using p0 to p3. Same notations we are using but here p1 and p2 represent the boundary values that means at u equal to 0 and u equal to 1. P0 and p3 are used to obtain first order derivatives at the boundaries. How, look at this system of equations here. This is the p1 control point which is the function value at 0. This is p2 control point which is the function value at 1, u equal to 1.
Now first order derivative at u = 0 can be obtained using this equations. Similarly first order derivative at u = 1 can be obtained using these equations. Where we have used that to control points in this fashion. And also used one additional parameter t in both cases. Now t is called tension Parameter. So, essentially it determines the shape of the curve when t
equal to 0 what we get is the catmull-rom or overhuset spline. So, that is a special type of spline when t equal to 0. So, using the value of t we can actually control the shape of the overall spline curve. So, here we do not have to actually compute the derivatives instead we can derive it using the control points and the value of t, so that actually makes the life of the user simpler.
But again, the Cardinal Cubic also suffered from the same problem. That is it supports up to C0 and see one parametric continuity conditions. It does not support C2. So, it has less smooth curve than natural Cubics.
So, then what is left is the basis matrix formulation. This is slightly complicated, but again, you
can try using the same approach by setting up the system of equations where some rearrangements may required. Then you create the constraint matrix, take the inverse to get the basis matrix for the cardinal cubic spline. Which is represented in the form of S where S is this expression.
So, to summarize, we have learned about 3 interpolating splines. Each of these interpolating splines are made up of polynomial pieces. And these pieces are Cubic. So, each piece is defined by 4 control points. In case of natural cubic, the control points are defined in a particular way, in case of Hermite cubic it is defined in a different way and in case of Cardinal Cubic, it is defined in yet another way. So, natural Cubic is very smooth, but it has some problems.
Those problems are particularly related to local controllability, which is taken care of in the Hermite Cubic, but at the expense of smoothness. But specifying Hermite Cubic’s is slightly difficult, which is again taken care of by Cardinal Cubic’s. But the smoothness remains less compared to natural Cubic’s. Now, let us move to the other category of splines, namely the approximate splines, so what are these splines? Just to recap here, we have a set of control points, but this spline need not pass through all the points. Instead, the control points are used to
define the convict’s hull, which determines the shape of the overall Spline curve.
Now, there are two popular approximating splines used in computer graphics. One is called Cubic Bezier curves, and the other one is B splines. Like in the case of interpolating splines, let us try to understand these types in a little more details. We will start with cubic Bezier curves. Now, these particular curves, the Cubic Bezier curves are among the widely used representation technique in graphics. The name has been derived from the French engineer Pierre Bezier, who
first used it to design Renault Car bodies.
Since it is Cubic curve so defined by 4 control points as before, but here the difference is that the
curve is an approximating Spline that means the polynomial pieces do not pass through all the 4 control points. We can denote these points like before p0, p1, p2 and p3. So, there are 4 points, but it is not necessary that the curve passes through all the points. Instead, these points are used to define the convex hull, so each piece originates at p0 and ends at p3, that is the first and the last control points. The other two points are used to determine the convex hull within which the curve lies. So, 2 points are on the curve and other 2 points are controlling the shape of the curve.
Now, the control points can be used to define first order derivatives at the boundary values that is u equal to 0 and u equal to one using these expressions. So, this is the first order derivative at u equal to 0 and this is the first order derivative u equal to 1 And t hese two derivatives are defined
in terms of the control points as shown in these examples.
From this set of equation we can rearrange and get this form shown here for the control points. Now, from that rearranged form, we can get the constraint matrix as shown here. This is the constraint matrix. Then we take the inverse of the constraint matrix C-1 to get the basis matrix, representation of the Bezier curves, which is something like this. So, note here we followed the same approach that is first we created the set of equations using the control point characteristics, then we formulated the constraint matrix and finally we took the inverse of the constraint matrix to get the basis matrix.
There is actually a blending function representation also for Bezier curves. We already said they are equivalent, but blending function representation for Bezier curves is also quite popularly used. Which as a general form something like this, where pk is the control points and Bez is the blending functions. And the function is defined within this range is u between 0 and 1. Now, these blending functions are actually special functions, sometimes they are known as
Bernstein Polynomial which has this form where C is this one. So, Bezier curves we can represent using blending functions where the blending functions are called Bernstein polynomials, which takes the forms on here in this first line.Where the term C (n, k) is shown in the second line.
Now, if we expand the blending functions for say a cubic Bezier where n equal to 3, then how it looks? BEZ 0, 3 is (1-u)3, 1, 3 is this one 2, 3 is this one and 3, 3 is this one. So, these are the blending functions for Bezier Cubic curve. Same thing we can derive from the basis matrix also.
As I said in the previous lecture, that they are equivalent. One can be derived from another and you can try to do the same.
So, one major problem with the Bezier Cubic is that they do not support local controllability.
That is, of course a major concern. Now, let us move to the other category of splines that is B splines.
Now here, the idea is slightly more complicated. Now, B splines are approximating splines, as
we have already mentioned, they support up to C2 continuity conditions, parametric continuity conditions. That means C0, C1 and C2 all three they support. In other words, these splines give us a very smooth curve and they support local controllability. So, Bezier curves do not have local controllability, whereas these splines is very smooth. They are very smooth as well as they support local controllability. So, all our problems are solved with these splines. Now, let us try to understand the basic idea, the mathematics behind it is slightly complicated, so we will try to keep it at the minimum for simplicity. What is the idea? The idea is based on representing a polynomial in terms of other polynomials, as we have seen in the blending function representation. So, that is where this idea starts, that a polynomial can be represented in terms of other polynomial.
So, what is the most general form of such representation, we have encountered this expression in the previous lecture pi control points and bi is the blending function. So, we are assuming in this representation that the function f is a linear combination of the blending functions where the control points p serve as the coefficients. Now, in this definition, one thing to be noted here is that we are using a parameter t instead of u. Now this parameter is more general. That means that we need not restrict ourselves to the range defined for you that is between 0 and 1. So, the t can take any value, not necessarily within the range 0 to 1.
Now, each bi is a polynomial. Let us assume that so then f can be considered as a spline made up of polynomial pieces, which is basically the idea now we can represent each bi as a combination of other functions, like the overall function f. So, f is represented as a linear combination of bi’s,
each bi in turn can be represented as a combination of other functions. Then conceptually, each bi is also spline, because it is made up of other polynomials.
So, when we talked about Spline, we said that Spline is a curve which is made up of lower degree polynomials now each of these polynomials. Again, we are assuming to be made up of even other polynomials. So, this polynomial pieces are themselves splines rather than simple polynomials. And that is the overall idea of B splines. That is we are having a spline, which is made up of basis spline rather than polynomial pieces.
Now, each basis spline is made up of polynomial pieces. So, the definition is one level higher than basic definition of Spline. In spline we have a curve made up of polynomial pieces in this spline. We have a curve made up of basis splines, which in turn is made up of polynomial pieces.
So, what we get is a spline made up of B-splines and that is the overall idea. So, when we are talking of B- splines, we are actually referring to the constituent splines. Let us try to understand in terms of an example. Suppose we have 4 control points and we want to fit a curve through those points. So, since we have 4 points. So, our curve function will look something like this, we expand the general form on shown earlier to get the 4 blending functions in the general form. Now, assume that we are using a linear B-spline that means B-splines pieces made up of linear polynomials.
Then, each B-spline will have two linear pieces as per the following equation. This is the B-spline and these are the linear pieces defined within range of t. So, as you can see in the previous formulation, that each B-spline is defined between sub intervals of the parameter T now within this sub interval, the pieces that made that are the constituents of the B-splines have their own range. So, we have a range for the B- spline and we have sub ranges for the constituent polynomial pieces of the spline. Now, those points in the parameter range where the piece starts or ends are called knot points or
simply knot for the ith B-spline, the knots are i+1 and i+2. Just to recollect, so we have a spline
made up of B- spline. Now each B-spline is defined within a range that range is subdivided for each constituent piece of a B-spline. Now, where a piece starts or ends are called knot points or simply knots. For the ith B-spline. We can define the knots as i, i+1 and i+2. For the 4 control points in our example, i takes the value 1 to 4. So, then we can have the knots. As 1, 2, 3, 4, 5, 6, these are the 6 knot points, and this set of points is the vector of knots, also known as the knot vector. Which is, of course, an increasing order of parameter values.
So, then to summarize each B- spline is made up of k where k equal to d+1, d is the degree of the polynomial. Now parameter t ranges between 1 to n+k having n+k knots. In our example n is 4, n is the number of control points k is 2 since d is 1. So, the range is between 1 to 6 with 6 knots.
The ith B- spline is defined within the knots i and i+k, for example, the second B-spline that means i=2 is defined between 2 and 2+2 or 4, because k is 2. So, between 2 to 4, that means the knot values are 2, 3 and 4.
So, each B-spline has k+1 knot's. Now, in our example, since k equal to 2. So, each B-spline will have 3 knots for any other value of k the B-spline will have k+1 knots. So, these are the characteristics of the B-spline.
Another characteristics is k is actually very crucial in determining all these characteristics. So, this k value is often called the B-spline parameter. So, you should keep this in mind that k is very important, it plays a very crucial role in determining the B- spline characteristics that we have enumerated earlier. So, often k is called the B- spline parameter. Now, let us see various types of B-spline. So far, we have given a basic idea, basic introductory idea of B- spline. Now let us see the types that are there for B spline.
There are 3 types, uniform B-spline, non-uniform B-spline and nurbs or non-uniform rational B- spline we will briefly introduce each of these types.
So, when we have the knots that are uniformly spaced in the knot vector, like in the case of the example we have seen before, those B-spline are called uniform B-splines. If the knot vectors are not uniformly spaced, spacing between consecutive knots is not the same. Then we get non-
uniform B spline. And finally, nurbs referred to the B-splines which actually refers to ratio of two quantities shown
here in this expression. Each i’s are the scalar weights and bi’s are non-uniform B-splines and also it should be noted that the same B-spline are used in both numerator and denominator. So, nurbs essentially refer to this ratio, so we have a uniform B-spline where knot points are uniformly spaced, we have non-uniform B-spline, where knot points are not uniformly spaced.
And we have nurbs where we talk of ratio of two quantities, each of which is made up of same non-uniform B-spline.
Now, the basic idea of splines is that using this, we should be able to represent some curves and render it on the screen. Now how can we display spline curves?
So, where we started how to fit a curve to a given set of control points, so we are given a set of control points and we want to fit a curve, we discussed how to use the idea of spline to get the curve. Now what we can do. So, we got the spline. Then what we can do the simplest way is to
determine or interpolate new control points using the spline equation and then joined the control points using line segments. We can also use the blending function representation for interpolating these points.
As an example, suppose we are given two control points p0 and p1 this p0 and this is p1 since two control points out there we can use a linear interpolating spline and once we identify the spline representation using the approaches mentioned already, we can evaluate the spline function to create 3 new control points shown here. And we will get the parameter value for these control points defined here, and then we will get the actual function value.
So, we are given two control points, we are using a linear interpolating spline and using that spline, we are creating 3 new control points and once these points are created. We can join them using a line segment to get the curve.
And we can keep on adding more and more points to get a final curve. In fact, if more control points are there we can use more control points to get better splines,
higher order splines instead of linear splines and do the same approach, follow the same approach. So, anything is possible.But the main problem is that we have to evaluate the blending function again and again. Now, when we want to display the splines at a very high rate, these computations may be costly and may slow the rendering process. So, we require some alternative approach. One of those approaches is known as De Casteljau algorithm. And we will have a quick look at the algorithm.
So, the algorithm consists of a few steps. They are n control points given. What we do, we join
the consecutive pairs of control points with line segments and then we continue till a single point
is obtained. What we do, we first divide each line segment in the ratio, d:1-d to get n-1 new points where d is any real number greater than 0. Now join these new points with line segments and then we go back to step 1.So, this is kind of look how it works. Let us see one example, suppose here n equal to 4 and we have decided on d to be one third. So,
p0, p1, p2, p3 are the initial points, then at one third of the p are say p0 and p1 we took one point.
Similarly, one third of the p are p1, p2 you took another point and then another point? And then these p0 has been modified to refer to this. Then we continue in the loop to finally get point here after the algorithm is executed So, this division continues till we get one point. And at that point, we stop. So, that is the output point. This is, in short how we can use an iterative procedure to a simpler procedure to get points on the curve using the algorithm. So, what we are doing in each run, we are getting a new point and we can execute it any time we want to get m new points, when these points are joined with line segments, we get the Bezier curves. So, here it has to be noted that we get this particular curve, not all Spline types. So, this algorithm actually refers to creation of a Bezier curves, which is an approximating spline. We can execute the algorithm m times to get the m points on the Bezier curve. So, that is how we can get the points and create the curve.
Now there is another thing in computer graphics, so we are not necessarily satisfied with only curves. What we need are surfaces also curved surfaces. So, using spline idea how can we get curved surfaces is very simple. Look at this figure here. We can actually create a grid of control points like shown in this figure.
So, each subset of the grid can be used to get a curve in different ways and when we put together these curves, we get a surface, so to get the surface, we define a grid shown in the field of circles here using one subset, we get one spline curve. Using another subset, we get another Spline curve which are intersecting, and when we get this grid of curves, we get the surface, the surface is defined by that grid. So, this is the simple way of getting a surface.