Starting from:
$30
CS148- Homework 1- Rasterization Solved
This is the first homework assignment for CS 148. We will have weekly assignments except when there are exams; check the course website for due dates, assignment materials, and the late day policy. Assignments like this are half written and half coding.
Note that algorithms like the one we are discussing in this assignment are wellknown and probably easy to find online; copying code or math from any such source is strictly forbidden.
In Lecture 2, we derived Bresenham’s algorithm for rasterizing lines. In this assignment, we are going to derive and implement a similar algorithm for rasterizing circles. In particular, we will rasterize the quadrant of the circle x2+ y2 = R2 where x, y ≥ 0 and positive integer R.
One obvious way you could attempt to rasterize such a circle would be to iterate over each√ x
corresponding to a pixel center and light up the pixel closest to (x, R2− x2).
Problem 1 (10 points). Why is this approach bad? Provide at least two reasons.
Instead, we will imitate our development of Bresenham’s algorithm for rasterizing lines. In fact, we can simplify matters somewhat: We can employ the symmetry of the circle to reduce the number of pixels we have to rasterize. Then, each time we rasterize a pixel we will also light up its symmetric counterpart.
Problem 2 (10 points). Suppose we are given (x, y) on the 45◦ arc of the circle between (0, R) and
(R/√2, R/√2). Find a corresponding symmetric point on the 45◦ arc from (R/√2, R/√2) to (R, 0) that takes no additional operations to compute.
For deriving methods like Bresenham’s algorithm, it is often more convenient to use implicit forms of curves. So, we define F(x, y) = x2 + y2 − R2. Then, our curve is given by F(x, y) = 0. Note that F(x, y) < 0 when (x, y) is inside the circle and F(x, y) 0 when (x, y) is outside the circle.
Just as in our method for rasterizing lines, we will be marching from left to right. Let’s say we are at a pixel whose center is (x, y). Then, neighboring pixel centers are given by (x ± 1, y ± 1). Our algorithm will make a local decision about which neighbor to choose next in its walk around the circle.
Problem 3 (10 points). Show that the slope of the circle in the 45◦ arc we are drawing satisfies −1 ≤ dy/dx ≤ 0. Use this fact to justify why if we trace pixels in increasing x along the circle, it is sufficient to consider only the neighbors (x + 1, y) and (x + 1, y − 1) of (x, y).
1
Suppose we just drew the pixel at (xP, yP). Our method will have the property that the circle will intersect the segment between (xP, yP −1/2) and (xP, yP +1/2) (it may help if you draw this for yourself). We will define our decision variable to be d = F(xP + 1, yP −1/2).
Problem 4 (10 points). Give a rule using d for choosing between (xP + 1, yP) and (xP + 1, yP − 1) using the property explained above.
We now have a rule for choosing which pixel to visit next, but now we’ll need to update d.
We will call the move from (xP, yP) to (xP + 1, yP) a move east (E) and the move from (xP, yP) to (xP + 1, yP − 1) a move southeast (SE).
Problem 5 (10 points). Provide update rules of the form dnew = dold +∆E and dnew = dold +∆SE to be applied depending on which pixel you choose.
Excitingly, you should find that if xP, yP are integers, so are ∆E and ∆SE. This suggests that we can do integer arithmetic while rasterizing circles, which can buy us some time!
To complete our rasterization algorithm, we just need a way to start out. For simplicity, we’ll actually change the convention we explained in class and assume pixel centers coincide with integer coordinates. So, we’ll start at (x, y) = (0, R).
Problem 6 (10 points). Provide an initial value for d and show that it isn’t an integer. Suggest an alternative decision variable h of the form h = d − c for some fixed constant c so that the initial value of h is an integer, and provide update and decision rules for h.
This completes our derivation of the Bresenham algorithm for rendering circles. To make sure you have all the pieces organized, you will implement it in C++.
Problem 7 (40 points). Implement your circle rasterization algorithm in C++. Skeleton code is provided on the CS 148 course website, including guidance on input and output. You must use integer arithemetic in your code – programs using doubles or any other type of decimal arithmetic will receive no credit.
Note that algorithms like the one we are discussing in this assignment are wellknown and probably easy to find online; copying code or math from any such source is strictly forbidden.
In Lecture 2, we derived Bresenham’s algorithm for rasterizing lines. In this assignment, we are going to derive and implement a similar algorithm for rasterizing circles. In particular, we will rasterize the quadrant of the circle x2+ y2 = R2 where x, y ≥ 0 and positive integer R.
One obvious way you could attempt to rasterize such a circle would be to iterate over each√ x
corresponding to a pixel center and light up the pixel closest to (x, R2− x2).
Problem 1 (10 points). Why is this approach bad? Provide at least two reasons.
Instead, we will imitate our development of Bresenham’s algorithm for rasterizing lines. In fact, we can simplify matters somewhat: We can employ the symmetry of the circle to reduce the number of pixels we have to rasterize. Then, each time we rasterize a pixel we will also light up its symmetric counterpart.
Problem 2 (10 points). Suppose we are given (x, y) on the 45◦ arc of the circle between (0, R) and
(R/√2, R/√2). Find a corresponding symmetric point on the 45◦ arc from (R/√2, R/√2) to (R, 0) that takes no additional operations to compute.
For deriving methods like Bresenham’s algorithm, it is often more convenient to use implicit forms of curves. So, we define F(x, y) = x2 + y2 − R2. Then, our curve is given by F(x, y) = 0. Note that F(x, y) < 0 when (x, y) is inside the circle and F(x, y) 0 when (x, y) is outside the circle.
Just as in our method for rasterizing lines, we will be marching from left to right. Let’s say we are at a pixel whose center is (x, y). Then, neighboring pixel centers are given by (x ± 1, y ± 1). Our algorithm will make a local decision about which neighbor to choose next in its walk around the circle.
Problem 3 (10 points). Show that the slope of the circle in the 45◦ arc we are drawing satisfies −1 ≤ dy/dx ≤ 0. Use this fact to justify why if we trace pixels in increasing x along the circle, it is sufficient to consider only the neighbors (x + 1, y) and (x + 1, y − 1) of (x, y).
1
Suppose we just drew the pixel at (xP, yP). Our method will have the property that the circle will intersect the segment between (xP, yP −1/2) and (xP, yP +1/2) (it may help if you draw this for yourself). We will define our decision variable to be d = F(xP + 1, yP −1/2).
Problem 4 (10 points). Give a rule using d for choosing between (xP + 1, yP) and (xP + 1, yP − 1) using the property explained above.
We now have a rule for choosing which pixel to visit next, but now we’ll need to update d.
We will call the move from (xP, yP) to (xP + 1, yP) a move east (E) and the move from (xP, yP) to (xP + 1, yP − 1) a move southeast (SE).
Problem 5 (10 points). Provide update rules of the form dnew = dold +∆E and dnew = dold +∆SE to be applied depending on which pixel you choose.
Excitingly, you should find that if xP, yP are integers, so are ∆E and ∆SE. This suggests that we can do integer arithmetic while rasterizing circles, which can buy us some time!
To complete our rasterization algorithm, we just need a way to start out. For simplicity, we’ll actually change the convention we explained in class and assume pixel centers coincide with integer coordinates. So, we’ll start at (x, y) = (0, R).
Problem 6 (10 points). Provide an initial value for d and show that it isn’t an integer. Suggest an alternative decision variable h of the form h = d − c for some fixed constant c so that the initial value of h is an integer, and provide update and decision rules for h.
This completes our derivation of the Bresenham algorithm for rendering circles. To make sure you have all the pieces organized, you will implement it in C++.
Problem 7 (40 points). Implement your circle rasterization algorithm in C++. Skeleton code is provided on the CS 148 course website, including guidance on input and output. You must use integer arithemetic in your code – programs using doubles or any other type of decimal arithmetic will receive no credit.
1 file (91.4KB)
