Cis 457 Computer Graphics Some Classical cg algorithms in Chapter 4



Download 23.82 Kb.
Date conversion03.05.2017
Size23.82 Kb.
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 x2 + y 2 = r2, and that when

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

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

our error (difference from r2) 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 ((x2 + y2) and r2) ) 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 + y2 ) - ( x2 + (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: yI = ymax, and xI 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: b3b2b1b0

b3 = 1 iff x < xmin; b2 = 1 iff x > xmax; b1 = 1 iff y < ymin; b0 = 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 P0, P1, … Pn-1 be the vertices of the input polygon; output polygon (Vector of Point 2D objects)

is initialized to empty



For each edge Pn-1P0, P0P1, P2P3, …Pn-2Pn-1.

do the following:

1) If the 2 points (Pi and Pi+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 Pi+1 is on the same side of the clipping line as the rectangle, add Pi+1 to the output

polygon


-See Fig. 4.12, and code on pages 115-119
*********************************************************************************

Sec. 4-6

Bezier curves in R2
-Bezier curves in R2 : B(t) a parametric vector function of t, where t is in interval [0,1]; know how to construct Bezier function given control points P0, P1, … Pn; 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) = P0, B(1) = Pn; 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 Pn; 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 (P0, P1, … Pn ), 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 – Pn-1) (a vector with direction from Pn-1 to Pn and length equal to n times length of Pn – Pn-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); 1st –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; 2nd-order continuity (also referred to as “curvature continuity”) at the common point for curves defined parametrically means that there is 1st-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 B1 and B2, 2nd-oder continuity is achieved if B1(1) = B2(0) and B1’(1) = B2’(0) (note that this last equality is obtained if the 2 vectors have same direction and same magnitude; if B1(1) and B2(0) are equal and B1’(1) and B2’(0) have same direction then the curve has 1st-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 2nd 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” – 2nd order continuity, and more: at points where the 2 cubic polynomials are joined the 2nd derivative of the vectors are equal;


The database is protected by copyright ©ininet.org 2016
send message

    Main page