Alison's New App is now available on iOS and Android! Download Now
Hello and welcome to lecture number 26 in the course Computer Graphics, we will continue our discussion on the graphics pipeline. For a quick recap, let us just go through the stages.
So, we have already discussed the first stage that is object representation, second stage modeling transformation, third stage lighting, fourth stage viewing pipeline, and the only stage that is remaining is the fifth stage scan conversion. We are currently discussing the fifth stage.
In the last lecture, we talked about rendering of lines, which is part of the fifth stage. And there we talked about a very intuitive approach as well as a slightly improved approach that is the DDA methods. Today, we will continue our discussion on line rendering, where we will talk about even better approach. And also we will discuss rendering of circles.
Now, before we go into the discussion on a better line rendering approach, let us quickly recap what we have seen in the previous lecture on line rendering.
So the idea was to map a description from viewport to a pixel grid. That is, of course, the objective of the fifth stage.
In order to do that, simplest approach is just to round off the real coordinates to the nearest integers, which are pixels, for example, from (2.3, 2.6) to (2, 3). Now, this is good for points but for mapping lines or circles or other primitive shapes, this may not be good.
And for line what we did? So we first assume that a line segment is defined by the endpoints. And our objective is to map all the points that are on the line to the appropriate pixels.
The straightforward approach that we discussed is that first we map the end points to pixels, then we start with one endpoint which is having the lower x and y coordinate values, then we work out y-coordinate values for successive x-coordinates, where the x-coordinates differ by 1 because we are talking pixel grids. And then, this y values that we computed are mapped to the nearest integer thereby getting the pixels.
Now, this approach has two problems. First, we require multiplication which is a floating-point operation. And secondly, we require rounding off which is also a floating-point operation. Now, these floating-point operations are computationally expensive and may result in slower rendering of lines.
To improve, we discussed one incremental approach. There we did not go for multiplication, instead we used addition. So to compute y, we simply added this m value to the current value, or to compute x, new x, we simply added this 1 by m value to the current x value. Now when to
choose whether to compute x or y, that depends on the slope. So if the m value is within this range, then we compute y given x, otherwise, we compute x given y using the line equation.
Now, the DDA can reduce some floating-point operations as we have discussed, particularly multiplications. However, it still requires other floating-point operations, namely additions and rounding off. So it is still not completely efficient so to speak, and we require a better approach. One such approach is given by Bresenham’s algorithm.
Now, this is an efficient way to scan convert line segments and we will discuss the algorithm assuming m to be within these ranges. That means we will concentrate on computing y value given the x value.
Now, let us try to understand the situation. Suppose, this is the actual point on the line and we are moving along the x-direction, the current position is given by this point (xk, yk). Now, the actual point on the line is a floating-point number real number, so we need to map it to the nearest pixel grid point.
Now, there are two potential candidates for that, one is this pixel or the upper candidate pixel that is (xk+1, yk+1), and the other one is the lower candidate pixel that is (xk+1, yk), and we have to choose 1 of those. How to choose that?
Our objective is to choose a pixel that is closer with respect to the other pixel to the original line. So between these two pixels, we have to decide which one is closer to the original line and choose that pixel.
Let us denote by dupper, the distance of the pixel (xk+1), (yk+1) from the line that is the upper candidate pixel from the line as shown here. Similarly, d lower indicates the distance of the lower candidate pixel from the line.
Now, at (xk+1), that is at these points y is given by this expression using the line equation, where m is the slope. Then we can say that d upper can be given by ((yk+1) – y), that is this value minus this y value, which is given here or this expression.
Similarly, dlower can also be given as y minus yk. As you can see here, this is the y value and this is the yk value. So replacing the y from this equation, you can get this expression. Now, let us do some mathematical trick on these expressions.
But before that, we should note that if the difference is less than 0 then the lower pixel is closer and we choose it, otherwise, we choose the upper pixel. Distance between the y values here, here, and here; the two distances that we have used in expressing dupper and dlower. If the difference is less than 0, then we choose the lower pixel because that point is closer to the line, otherwise, we choose the upper pixel.
Now, let us substitute m with this ratio, Δy/Δx, where Δy is the y coordinate difference between the endpoints and Δx is the x coordinate difference between the endpoints. And then we rearrange and replace this expression with c, which is a constant term. As you can see here, all are constants.
Then what do we get? This term to be equal to this term, both sides we have multiplied by Δx and replace m with these expressions. Rearranging and expanding, we get this, then we replace this constant term here with c to get this expression. This is a simple manipulation of the terms.
Now, let us denote the left-hand side by pk, we call it a decision parameter for the kth step. Now, this parameter is used to decide the closeness of a pixel to the line. Now, its sign will be same as that of the sign of the difference dlower - dupper.
Thus, if pk˂0, then this lower pixel is closer to the line and we choose it, otherwise, we choose the upper pixel.
So that is at step k. Now, at step k+1 that is the next step, we get pk+1. Now, that is essentially given by this expression where we replaced xk with xk+1 and yk with yk+1. These two terms we replaced with the next term. Then we take a difference between the two, pk+1 - pk, which gives us this expression.
Now, we know because we are dealing with a pixel grid that xk+1 is essentially xk + 1. So we can rearrange and rewrite the expression as pk+1 = pk + 2Δy – {this term}. That means the decision variable at k+1th step is given by the decision variable at kth step plus a term; this and that term.
Now, if pk
Log in to save your progress and obtain a certificate in Alison’s free Computer Graphics: Clipping and Scan Conversion online course
Sign up to save your progress and obtain a certificate in Alison’s free Computer Graphics: Clipping and Scan Conversion online course
Please enter you email address and we will mail you a link to reset your password.