**CIS 457 Computer Graphics**
**Some Classical CG Algorithms in Chapter 4** (Ammeraal and Zhang)
**Section 4.1-4.2**
**Line Drawing: Input: Graphics g, int xP, int yP, int xQ, int yQ**
**-**First consider case where the slope m is greater than or equal to 0 and less than or equal to 1
and where xP < xQ; see **drawLine1 **method, pg. 93-94; uses float types;
**drawLine2** method – **Bresenham’s algo. uses ints and is faster than drawLine1**
-**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
*******************************************************************************
**Section 4.3**
**Circle Drawing: Input: Graphics g, int xC, int yC, int r // (xC, yC) pixel coords. of center**
// **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^{2} + y ^{2} = r^{2}, and that when
we increment x by 1 and keep y the same we introduce an error of
((x + 1)^{2} + y^{2} ) - ( x^{2} + y^{2}) = **2x + 1**; i.e. if we keep on incrementing x without decrementing y,
our error (difference from r^{2}) 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^{2} + y^{2}) and r^{2}) ) 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 ^{2} + y^{2} ) - ( x^{2} + (y - 1)^{2}) = **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.
**How do we determine when to decrement y? **In the loop after incrementing x, we add u to the
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.
**General version of drawCircle** (top of pg. 106): this version exploits symmetry, and uses
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_{3}b_{2}b_{1}b_{0}
b_{3} = 1 iff x < xmin; b_{2} = 1 iff x > xmax; b_{1} = 1 iff y < ymin; b_{0} = 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
*******************************************************************************
**Sec. 4-5**
**Sutherland-Hodgman Polygon Clipping**
**Input: float xmin, float ymin, float xmax, float ymax //a rectangle used for clipping**
**Vector
**
// the polygon to be clipped
- The Sutherland-Hodgman algorithm makes **4 passes** (one for each side of the rectangle): clipping
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_{0}, P_{1}, … P_{n-1 }be the vertices of the input polygon; output polygon (Vector of Point 2D objects)
is initialized to empty
**For each edge** P_{n-1}P_{0, }P_{0}P_{1}, P_{2}P_{3}, …P_{n-2}P_{n-1}.
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
-See Fig. 4.12, and code on pages 115-119
*************************************************************************************
**Sec. 4-6**
**Bezier curves in R**^{2}
-Bezier curves in R^{2} : B(t) a parametric vector function of t, where t is in interval [0,1]; know how to construct Bezier function given control points P_{0}, P_{1}, … P_{n}; n + 1 control points gives polynomial of degree n; note B(t) = (x(t), y(t)) where x(t) is the x-coordinate of a point on the curve at “time” t, and y(t) is the coordinate of the curve at time t.
-Properties of Bezier curves: n control points gives polynomial of degree n -1; B(0) = P_{0}, B(1) = P_{n}; viewing the independent variable t as time, the Bezier curve begins by passing through the first control point (P0) at time t = 0 and ends at time t =1 at control point P_{n}; if the curve given by B(t) is viewed as the plot of location of points (end points of vectors originating at origin) at time t, then the tangent vector to the curve, given by B^{’}(t), is the velocity vector – it has magnitude (magnitude of the vector B’(t) can be interpreted as the speed) and direction; for a Bezier curve with n + 1 control points (P_{0}, P_{1}, … P_{n} ), B’(0) = n(P1 – P0) (a vector with direction from P0 to P1 and length n times length of (P1 – P0) ); B’(1) = n (Pn – P_{n-1}) (a vector with direction from P_{n-1} to P_{n} and length equal to n times length of Pn – P_{n-1}. Also, the entire Bezier curve lies within the convex hull of {P0, P1, …, PN}. Know definition of convex hull, and theorem that states that the convex hull of a set S is the set of all linear combinations of points in S with coefficients on those linear combos. greater than or equal to 0, and summing to 1. This theorem makes it clear why the entire Bezier curve lies within the convex hull of the control points (coefficients on the control points in B(t) are all greater than 0 and sum to 1).
-Recursive, midpoint method of drawing a cubic Bezier curve (4 control points) – see bezier method on page 123; know how to select the points used in the recursive calls; compare with “analytic” version, bezier1 (pg. 125) and analytic version, bezier2 (pg. 129) that uses Horner’s rule
-Design techniques for Bezier curves: making it closed: select end point equal to start point; specifying multiple control points at same position give more weight to that position (“pulls” curve toward that position); for “local control” (i.e. control over small portions of curve) consider piecing together Bezier curves
-A continuous function that is defined piecewise using polynomials is called a spline (note that a Bezier function B(t) is a spline – note the midpoint recursive method – the first half of the Bezier curve is itself a Bezier curve)
-When piecing together 2 curve segments C1 and C2, there is 0-order continuity (also referred to as “positional continuity”) if the endpoint of C1 equals the start point of C2 (this makes the entire curve continuous); 1^{st} –order continuity (also referred to as “tangential continuity”) at the common point means that there is 0-order continuity there, and the slope of the tangent line at the end point of C1 is equal to the slope of the tangent line at the start point of C2; 2^{nd}-order continuity (also referred to as “curvature continuity”) at the common point for curves defined parametrically means that there is 1^{st}-order continuity there, and the “velocity vectors” at that point are equal (i.e. have same direction and same magnitude); if you are connecting two Bezier curves B_{1} and B_{2}, 2^{nd}-oder continuity is achieved if B_{1}(1) = B_{2}(0) and B_{1}’(1) = B_{2}’(0) (note that this last equality is obtained if the 2 vectors have same direction and same magnitude; if B_{1}(1) and B_{2}(0) are equal and B_{1}’(1) and B_{2}’(0) have same direction then the curve has 1^{st}-order continuity at the common point).
-B-Splines – given n control points, P0, P1, …, Pn, a sequence of n-3 cubic polynomials are joined together; the first cubic polynomial uses control points P0, P1, P2, P3; the 2^{nd} cubic polynomial uses P1, P2, P3, P4; etc. So a B-spline with n control points has n – 3 curve segments, each segment being a degree 3 polynomial; the entire segment lies within the convex hull of {P0, P1, …, Pn}; the B-spline does not pass through the control points, so it is an “approximation” curve rather than an “interpolation” curve (a curve that passes through the control points); a cubic interpolation curve is referred to as a “natural cubic spline”; Benefits of B-splines as opposed to natural cubic splines are: i) “local control” (moving 1 control point affects only a small part of curve); ii) computation time (time needed to compute coefficients for B-spline much less than that for a natural cubic spline.
B-splines are “very smooth” – 2^{nd} order continuity, and more: at points where the 2 cubic polynomials are joined the 2^{nd} derivative of the vectors are equal; |