Cis 457 Computer Graphics Some Classical cg algorithms in Chapter 4

and where xP < xQ; see drawLine1 method, pg. 93-94; uses float types;

-General Bresenham algo.: drawLine method on pgs. 95-96 exploits symmetry using 2 general cases: i) absolute value of slope is less than or equal to 1 (dy <= dx in the code); ii) absolute value of the slope is greater than 1 (“else” part on pg. 96); note: for each of these 2 cases there are 4 subcases which are identified by the value of xInc and yInc

-Algo. for doubling the line-drawing speed: in each iteration of this algorithm, 2 pixels are displayed, based on 1 of 4 possible patterns; doubleStep1 method on pg. 99 uses float types for m and d; a fast integer version, doubleStep2 on page 101-102, uses only int variables

*******************************************************************************

// r is the radius

- As an aside: recall Graphics method drawOval in Java: g.drawOval( xC –r, yC –r, 2 * r, 2 * r);

-First consider case: center is at the origin:

“easy” solution (but not fast): draw several line segments from successive points with coordinates:

x = xC + r cos φ, y = xC + r sin φ, where φ = 2 * П * i / n , i = (0, 1, 2, …, n -1)

question: why is this not “fast”?

-Looking for a faster solution: First consider case center at the origin, draw arc from P(0, r) to

Q (r/sqrt(2), r/sqrt(2)) : the NNE sector of the circle. Note that moving from P to Q, the change in

x is greater, in absolute value, than the change in y (Why? Show r/sqrt(2) > | r – r/sqrt(2) | )

So, as we did in the first case for line drawing, we’ll begin by putting the pixel (0, r), and then in

a loop, we’ll increment x and decide whether or not to decrement y; the loop condition will be:

while (x <= y) // this is for the NNE sector

To determine whether or not pixel coordinate y should be decremented when we increment pixel

coordinate x, we make the observation: the equation of the circle is x² + y ² = r², and that when

we increment x by 1 and keep y the same we introduce an error of

((x + 1)² + y² ) - ( x² + y²) = 2x + 1; i.e. if we keep on incrementing x without decrementing y,

our error (difference from r²) grows from an original 0 (when x = 0 and y = r) , to 1, to (1+3), to

(1+3+5),… Note that 2x + 1 increases by 2 for every increase in x by 1.

At some time during the iteration, if we decrement y, the error (absolute value of difference

between ((x² + y²) and r²) ) will likely be reduced; see Fig. 4.6 on pg. 104: in that diagram, it

appears that we should decrement y when x becomes 3.

So, analytically, how do we determine when to decrement y?

Suppose we’ve already incremented x in the loop (its value now is in the variable x). By

decrementing y, the change in the error is: (x ² + y² ) - ( x² + (y - 1)²) = 2y – 1;

In the code of arc8 on page 105, the variable u is used for storing 2x + 1, and the variable v is

used for storing 2y – 1. Note initially (for the point (0, r)) that u = 1 and v = 2 * r -1, and that

just as 2 is added to u for every increase of 1 by x (and the error is increased by u for every

increase of 1 by x) , 2 is subtracted from v whenever y is decreased by 1.

error, stored in variable e, and we add 2 to u. Then to decide whether or not to decrement y,

we compare |e| with |e – v|. Which is smaller? It can be shown that | e – v| < | e| if (and only if)

v < 2 * e (try to show this). See code for arc8 on page 105, and trace through it with r = 8.

This method uses all int type variables and is attributed to Bresenham.

the algorithm found in the arc8 method. It puts pixels in NNE, ESE, SSE, and WNW sectors

inside the loop before incrementing x, modifying e, modifying u, and testing v against 2 * e. The

way this code is written, the putPixel method will never be called on the same pixel point. This

may be important if the call g.setXORMode(Color.white) is used before a call to drawCircle (this

changes black pixels to white and vice versa, and can be used for “erasing” the circle). Read

bottom half of page 106.
*****************************************************************************

Section 4.4

Cohen-Sutherland Line Clipping: Input: Graphics g, float xP, float yP, float xQ, float yQ,

float xmin, float ymin, float xmax, float ymax

//2 points, P and Q and a rectangle that “clips” the line segment PQ
- goal : to draw only that part of the segment PQ that lies within (or on) the rectangle

(see Fig. 4.7: line segment PQ clipped to segment PI

- In Fig. 4.7, it is easy to find coordinates of I: y_I = y_max, and x_I can be found by using relationship

between similar triangles (ratio of corresponding sides are equal):

(length of PA)/(length of AI) = (length of PB)/(length of QB)
-Cohen Sutherland Algorithm: divides the plane into 9 regions and assigns a 4 bit “clip code” to each point (x,y) in the plane: b₃b₂b₁b₀

b₃ = 1 iff x < xmin; b₂ = 1 iff x > xmax; b₁ = 1 iff y < ymin; b₀ = 1 iff y > ymax

See Fig. 4.8

-Notes: 1) If P and Q both have clipcodes equal to 0 (0000), then they both lie within the rectangle

and the segment PQ is entirely within the rectangle; 2) If P and Q have clipcodes that have a 1 in the same bit position, then P and Q lie on the same side of the rectangle, outside of the rectangle, so that the clipping of the segment PQ is empty (i.e. there are no points on the “clipped” line);
The Cohen-Sutherland line clipping algorithm: (see clipLine method pgs. 110-111)

While P and Q have different clipcodes and do not have clipcodes with a 1 in the same position

//see pg. 111

if clipcode of P is not 0

if P is to the left of the rectangle, find P’ (the new P), using similar triangles, that is the

intersection of PQ with the line x = xmin (see Fig. 4.8);

else if … //P is to the rt. of the rectangle; get intersection with x = xmax

else if … //P is below the rectangle; get intersection with y = ymin

else if … // P is above the rectangle; get intersection with y = ymax

get clipcode for the new P

else if clipcode of Q is not 0

if Q is to the left of the rectangle , find Q’ (the new Q) using similar triangles, that is the

intersection of PQ with the line x = xmin

else if … //Q is to the rt. of the rectangle; get intersection with x = xmax

else if … //Q is below the rectangle; get intersection with y = y min

else if … // Q is above the rectangle; get intersection with y = ymax

get clipcode for the new Q

//end while

- Look over program, pgs.109-112; see Fig. 4.9, pg. 113

*******************************************************************************

against x = xmax, then clipping against x = xmin, then clipping against y = ymax, then clipping against

y = ymin. Before each pass an input polygon (input sequence of vertices) is used; the output polygon

from each pass (except the last pass) is used as the input polygon to the next pass;

the output polygon from the final pass is the clipped polygon

- The input polygon to the first pass is the original polygon given as input to the algorithm

- The algorithm on each pass (one pass for each side of the rectangle):

Let P₀, P₁, … P_n-1 be the vertices of the input polygon; output polygon (Vector of Point 2D objects)

is initialized to empty

do the following:

1) If the 2 points (P_i and P_i+1) of the edge are on different sides of the clip line

being considered, add the point of intersection to the output polygon

2) If P_i+1 is on the same side of the clipping line as the rectangle, add P_i+1 to the output

polygon