资源描述
WHERE TO DRAW A LINE?nLine drawing is accomplished by calculating intermediate positions along the line path between specified end points.nPrecise definition of line drawing Given two points P and Q in the plane,both with integer coordinates,determine which pixels on a raster screen should be on in order to make a picture of a unit-width line segment starting from P and ending at Q.0 1 2 3 4 5 66543210(3,3)Line drawing(cont)nThe thinnest line is of one-pixel wide.We will concentrate on drawing a line of 1 pixel resolution.nThe Cartesian slope-intercept equation for a straight line is y=m.x+b m is the slope of the line and b is the y intercept.Given the endpoints of a line segment.m=y2-y1/x2-x1 b=y1-m.x1Line Drawing(cont)nAlso for any given interval x along a line,we can compute the corresponding y interval y from y=m.xnSimilarly we can obtain the x interval x corresponding to a specified y as x=y/mnThese equations form the basis for determining deflection voltages in analog devices.Line Drawing(cont)nAlso,for any given x interval x along a line,we can compute the corresponding y interval y from y=m.xnThese equations form the basis for determining deflection voltages in analog devices.nOn Raster systems,lines are plotted with pixels,and step sizes in the horizontal and vertical directions are constrained by pixel separations.Hence we ought to“sample”a line at discrete positions and determine the nearest pixel to the line at each sampled position.SymmetrynIf we could draw lines with positive slope(0=slope=slope=-1)We negate all Y valuesnFor a line with slope 1 or slope-1we just swap x and y axes450(y,x)(x,y)(x,-y)(y,-x)(-y,x)(x,-y)(-x,-y)(-y,-x)Code for drawing a lineInvert_y_draw(int x,int y)draw_pixel(x,-y)Swap_xy_draw(int x,int y)draw_pixel(y,x)Swap_xy_invert_y_draw(int x,int y)draw_pixel(y,-x).If(0=slope=1)draw_fn=draw_pixel draw_lne(Px,PY,QX,QY,draw_fn)Else if(-1=slope=0)draw_fn=invert_y_draw Draw_line(PX,-PY,QX,-QY,draw_fn)Else if(1 0.Parameter c is a constant and has the value 2y+x(2b-1)(independent of pixel position)nIf pixel at yk is closer to line-path than pixel at yk+1 (i.e,if d1 d2)then pk is negative.We plot lower pixel in such a case.Otherwise,upper pixel will be plotted.Bresenhams algorithm(cont)nAt step k+1,the decision parameter can be evaluated as,pk+1=2yxk+1-2xyk+1+cnTaking the difference of pk+1 and pk we get the following.pk+1 pk=2y(xk+1-xk)-2x(yk+1 yk)nBut,xk+1=xk+1,so that pk+1=pk+2y-2 x(yk+1 yk)nWhere the term yk+1-yk is either 0 or 1,depending on the sign of parameter pkBresenhams Line AlgorithmnThe first parameter p0 is directly computed p0=2 yxk-2 xyk+c=2 yxk 2 y+x(2b-1)nSince(x0,y0)satisfies the line equation,we also have y0=y/x*x0+bnCombining the above 2 equations,we will have p0=2y x The constants 2y and 2y-2x are calculated once for each time to be scan convertedBresenhams Line AlgorithmnSo,the arithmetic involves only integer addition and subtraction of 2 constantsInput the two end points and store the left end point in(x0,y0)Load(x0,y0)into the frame buffer (plot the first point)Calculate the constants x,y,2y and 2y-2x and obtain the starting value for the decision parameter as p0=2y-x Bresenhams Line AlgorithmAt each xk along the line,starting at k=0,perform the following test:If pk 0,the next point is(xk+1,yk)and pk+1=pk+2yRepeat step 4(above step)x timesOtherwisePoint to plot is(xk+1,yk+1)pk+1=pk+2y-2x Where do we draw a circle?Properties of a circle:nA circle is defined as a set of points that are all the given distance(xc,yc).This distance relationship is expressed by the pythagorean theorem in Cartesian coordinates as (x xc)2+(y yc)2=r2nWe could use this equation to calculate the points on the circle circumference by stepping along x-axis in unit steps from xc-r to xc+r and calculate the corresponding y values at each position as y=yc +(-)(r2 (xc x)2)1/2nThis is not the best method:nConsiderable amount of computationnSpacing between plotted pixels is not uniformPolar co-ordinates for a circlenWe could use polar coordinates r and,x=xc+r cos y=yc+r sinnA fixed angular step size can be used to plot equally spaced points along the circumferencenA step size of 1/r can be used to set pixel positions to approximately 1 unit apart for a continuous boundarynBut,note that circle sections in adjacent octants within one quadrant are symmetric with respect to the 45 deg line dividing the to octantsnThus we can generate all pixel positions around a circle by calculating just the points within the sector from x=0 to x=ynThis method is still computationally expensiveBresenham to MidpointnBresenham requires explicit equationnNot always convenient(many equations are implicit)nBased on implicit equations:Midpoint Algorithm(circle,ellipse,etc.)nImplicit equations have the form F(x,y)=0.Midpoint Circle AlgorithmnWe will first calculate pixel positions for a circle centered around the origin(0,0).Then,each calculated position(x,y)is moved to its proper screen position by adding xc to x and yc to ynNote that along the circle section from x=0 to x=y in the first octant,the slope of the curve varies from 0 to-1nCircle function around the origin is given byfcircle(x,y)=x2+y2 r2nAny point(x,y)on the boundary of the circle satisfies the equation and circle function is zeroMidpoint Circle AlgorithmnFor a point in the interior of the circle,the circle function is negative and for a point outside the circle,the function is positivenThus,nfcircle(x,y)0 if(x,y)is outside the circle boundaryykYk-1xk xk+1 Xk+3MidpointX2+y2-r2=0Midpoint between candidate pixels at sampling position xk+1 along a circular pathMidpoint Circle AlgorithmnAssuming we have just plotted the pixel at(xk,yk),we next need to determine whether the pixel at position(xk+1,yk-1)is closer to the circlenOur decision parameter is the circle function evaluated at the midpoint between these two pixels pk=fcircle(xk+1,yk-1/2)=(xk+1)2+(yk-1/2)2 r2 If pk 0,this midpoint is inside the circle and the pixel on the scan line yk is closer to the circle boundary.Otherwise,the mid position is outside or on the circle boundary,and we select the pixel on the scan line yk-1Midpoint Circle AlgorithmnSuccessive decision parameters are obtained using incremental calculations Pk+1=fcircle(xk+1+1,yk+1-1/2)=(xk+1)+12+(yk+1-1/2)2 r2 OR Pk+1=Pk+2(xK+1)+(yK+12 yk2)(yk+1-yk)+1Where yk+1 is either yk or yk-1,depending on the sign of pknIncrements for obtaining Pk+1:2xk+1+1 if pk is negative 2xk+1+1-2yk+1 otherwiseMidpoint circle algorithmnNote that following can also be done incrementally:2xk+1=2xk+2 2 yk+1=2yk 2nAt the start position(0,r),these two terms have the values 2 and 2r-2 respectivelynInitial decision parameter is obtained by evaluating the circle function at the start position(x0,y0)=(0,r)p0=fcircle(1,r-1/2)=1+(r-1/2)2-r2OR P0=5/4-r nIf radius r is specified as an integer,we can round p0 to p0=1-rThe actual algorithm1:Input radius r and circle center(xc,yc)and obtain the first point on the circumference of the circle centered on the origin as (x0,y0)=(0,r)2:Calculate the initial value of the decision parameter as P0=5/4-r 3:At each xk position starting at k=0,perform the following test:If pk=yMidpoint EllipsenDerivationMidpoint Ellipse AlgorithmnInput and ellipse center and obtain the first point on an ellipse centered on the origin as nCalculate the initial value of the decision parameter in region 1 asMidpoint Ellipse.nAt each position in region 1,starting at k=0,perform the following test.if ,the next point along the ellipse centered on(0,0)is and nOtherwise,the next point along the ellipse is andwithand continue untilMidpoint Ellipse Contd.nCalculate the initial value of the decision parameter in region 2 as where is the last position calculated in region 1nAt each position in region 2,starting at k=0,perform the following test.if ,the next point along the ellipse centered on(0,0)is andnOtherwise,the next point along the ellipse is andnUsing the same incremental calculations for x and y as in region 1.Continue until y=0 Midpoint EllipsenFor both regions,determine symmetry points in the other three quadrantsnMove each calculated pixel position(x,y)onto the elliptical path that is centered on and plot the coordinate values
展开阅读全文