Basic Raster Graphics Algorithms for Drawing 2D Primitives Chapter 3.

  • Published on
    19-Jan-2016

  • View
    215

  • Download
    0

Transcript

Basic Raster Graphics Algorithms for Drawing 2D PrimitivesChapter 3Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives1. OverviewThe purpose of this chapter is to look at a graphics package from the implementors point of view -- that is, in terms of the fundamental algorithms for scan converting primitives to pixels, subject to their attributes, and for clipping them against an upright clip rectangle Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThe algorithms in this chapter are discussed in terms of the 2D integer Cartesian grid, but most of the scan-conversion algorithms can be extended to floating point, and the clipping algorithms can be extended to both floating point and 3D.The final section introduces the concept of antialiasingthe minimizing of jaggies by making use of a systems ability to vary a pixels intensity. Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives2. Scan Converting LinesA scan conversion algorithm for lines computes the coordinates of the pixel that lie on or near the ideal line.For now, consider only a 1-pixel-thick line, we will consider thick primitives, and deal with style later in the chapter.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesBasic properties of good scan conversion:Straight lines should appear as straight linesLines should pass through the endpoints (if possible)All lines should be drawn with constant brightness (regardless of length and orientation)As rapid as possibleChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesTo visualize the geometry, most people represent a pixel as a circular dot centered at the pixels (x,y) location on the integer grid.This is a convenient approximation to the cross-section of the CRTs electron beam.The exact spacing between spots on an actual display can vary greatly among systems. Some overlap while others leave spaces, but almost all have a tighter spacing in the horizontal than in the vertical direction.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThis figure shows a highly magnified view of a 1-pixel-thick line and the ideal line that it approximates.The intensified pixels are shown as filled circles, and the nonintensified pixels are shown as unfilled circles.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives2.1 The Basic Incremental AlgorithmThe simplest strategy for scan converting lines is to use the slope-intercept formulay = mx+BGiven two points on a line (x0,y0) and (x1,y1)compute the slope, m, of the lineremember, m = Dy/Dx = (y1-y0)/(x1-x0) B = y0-mx0Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThe basic idea is to increment x by 1 from the starting point (x0,y0) to the ending point (x1,y1) calculate y at each point, yi=mxi+Bturn on pixel (xi,Round(yi))where Round(yi)=Floor(0.5+yi)This brute force strategy is inefficient because each iteration requires:floating point multiplicationfloating point additionCall to function Floor( )Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesWe can eliminate the multiplication if we note:yi+1 = mxi+1 + B = m(xi + Dx) + B =yi + mDxand if Dx == 1yi+1 = yi+mChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesOther Cases:If the slope is greater than 1, you can swap the values of x and yIf the slope is negative, you start from the right endpoint and go to the left.Drawbacks:Floating point additionRound ( )Accumulation of floating point errorsChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives2.2 Midpoint Line AlgorithmIn 1965 Bresenham developed what is now the classic line drawing algorithm that removed the rounding and used only integer arithmetic.He showed that his algorithm provided the best-fit approximation to the true-line by minimizing the error.We are going to look at a generalization called the midpoint technique.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesMain Idea:Assumption:0 Line Representation ReviewImplicit representation:F(x,y) = ax + by + c = 0Slope-intercept representation:y = mx + B = (y1-y0)/(x1-x0) x + B = dy/dx x + BHow are they related?xdy - ydx + Bdx = 0 (a=dy, b=-dx, C=Bdx)Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThe sign of F(x,y) for any point (x,y)F(x,y) = 0 => point is on the lineF(x,y) > 0 => point is below the lineF(x,y) < 0 => point is above the lineCheck the sign of d=F(xp+1, yp+1/2)if d > 0, choose pixel NEif d < 0, choose pixel Eif d==0, choose either (we pick E)How should d be computed? Incrementally!Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesRemember by definition,d = a(xp+1)+b(yp+1/2)+cIf E was chosen, then we shift M over 1dnew=F(M1)= F(xp+2, yp+1/2) = a(xp+2)+b(yp+1/2)+cbut, remember dold = F(xp+1, yp+1/2)therefore: dnew=dold+a OR DE = aIf NE was chosen, then we shift M over & up 1dnew=F(M2)= F(xp+2, yp+3/2) = a(xp+2)+b(yp+3/2)+calso, dold = F(xp+1, yp+1/2)therefore: dnew=dold+a + b OR DNE=a+bChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesShort Summary of the midpoint technique:At each step we choose between two pixels based upon the sign of the decision variable (d)Then we update the d by adding DE or DNE depending on the choice of the pixelNow, how do we get started?We just need the first d value.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThe first midpoint, dstart, is F(x0+1,y0+1/2) = a(x0+1)+b(y0+1/2)+c = ax0+by0+c+a+b/2 = F(x0,y0)+a+b/2BUT (x0,y0) is on the line, so F(x0,y0)=0therefore dstart = a+b/2 = dy-dx/2Can we get rid of the division?Change the function F( ) to multiply everything by 2This changes the scalars (including DE and DNE) but does not change the sign (which is what we are interested in)So, dstart = 2dy - dxSo, now we have an algorithm based on integer arithmetic only.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesExample: (x0,y0)= (5,8)(x1,y1)=(9,11)dy = dx = DE = 2dy = DNE = (dy-dx)*2 =dstart = 2dy - dx =choose: E or NEdnew = choose: E or NEdnew =choose: E or NEdnew =choose: E or NEChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives2.3 Additional IssuesEndpoint order:A line from P0 to P1 should contain the same set of pixels as the line from P1 to P0.The only place where the choice of the pixel is dependent on the direction of the line is where the line passes directly through the midpoint.Going from left to right we picked ETherefore going from right to left we pick SW, not WWe cant just swap endpoints, since line styles are not swappable.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesStarting at the edge of a clip rectangleChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesVarying the intensity of a line as a function of slopeLine B has slope of 1 and is times as long as A, yet each line has 10 pixels.If intensity per pixel is constant, then the intensity per unit length is easily discernable by the user.Solution: make intensity a function of the slope.Antialiasing (3.14) will cover another method.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesOutline primitives composed of linesPolylines can be scan-converted one line segment at a time.Rectangles and Polygons can be done a line segment at a time, but this would result in some pixels being drawn outside.Sect 3.4 and 3.5 cover these.Shared verticescare must be taken to draw shared vertices of polylines only once.Drawing twice can change the color, shut it off, or if writing to film make the intensity too bright.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives3. Scan Converting CirclesReview of basic circle formulas:x2+y2 = R2circle centered at the origin (0,0) with radius R.(x-x0)2 + (y-y0)2 = R2Circle centered at (x0,y0) with radius R.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesA simple algorithmOverview:Draw only one quarter of the circle,use symmetry for the other three quarters.Outline:Step 1: x1 = 0, Dx = 1 Step 2: Step 3: round(yi)Step 4: draw (xi,round(yi))Step 5:xi=xiold+DxStep 6: if xi Computational cost:floating point multiplications, subtractions, square-root( ), round( )Problems:large gaps for x values close to RChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives3.1 Eight-Way SymmetryDraw one octant of the circleChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives3.2 Midpoint Circle AlgorithmBresenham in 1977 developed an incremental circle generator (for pen plotters) that is the foundation for the algorithm we will discuss.We will begin at x=0, and continue through the first octant. ( ) We will use the symmetry from the previous subsection to plot the rest of the circle.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesOverview:Assume that P has been chosen as closest to the circle.The next choice is pixel E and SE.if M is inside the circle, choose Eif M is outside, choose SEChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesF(x,y) = x2 + y2 - R2 = 0The sign of F(x,y) for any point (x,y)F(x,y) = 0 => point is on the circleF(x,y) > 0 => point is outside the circleF(x,y) < 0 => point is inside the circleCheck the sign of d=F(xp+1, yp-1/2)if d > 0, choose pixel SEif d < 0, choose pixel Eif d==0, choose either (we pick SE)Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesRemember by definition:d = (xp+1)2+(yp-1/2)2-R2If E was chosen, then we shift M over 1dnew=F(M1)= F(xp+2, yp-1/2) = (xp+2)2+(yp-1/2)2-R2a bunch of algebra later we getdnew=dold+(2xp+3) OR DE = (2xp+3) If SE was chosen, then M goes over & down 1dnew=F(M2)= F(xp+2, yp-3/2) = (xp+2)2+(yp-3/2)2-R2more algebra...dnew=dold+(2xp-2yp+5) OR DSE= +(2xp-2yp+5) Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesDid you notice that DE and DSE were not constants? Short Summary:choose between E and SE, based on the sign of dUpdate d by adding either DE or DSE All that remains is to compute the initial condition, dstart.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesHow should we compute dstart.The first midpoint will be at (1,R-1/2)F(1, R - 1/2) = 1 + (R - 1/2)2 - R2 = 5/4 - RMoving the algorithm from floats to intsDefine h = d - 1/4 then replace d by h+1/4hstart = 1 - RNow, dSecond-order differencesIf E is chosen: (xp, yp) --> (xp+1, yp) DEold = 2xp+3 DEnew = 2(xp+1)+3 DEnew - DEold = 2or DEnew = DEold + 2 DSEold = 2xp-2yp+5 DSEnew = 2(xp+1)+3 DSEnew - DSEold = 2 or DSEnew = DSEold + 2Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesIf SE is chosen: (xp, yp) --> (xp+1, yp-1) DEold = 2xp+3 DEnew = 2(xp+1)+3 DEnew - DEold = 2or DEnew = DEold + 2 DSEold = 2xp-2yp+5 DSEnew = 2(xp+1) - 2(yp - 1) + 5 DSEnew - DSEold = 4 or DSEnew = DSEold + 4Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThe revised algorithm has the following steps:Choose the pixel based on the sign of d computed during the previous iteration.Update d based with either DE or DSE.Update the Ds to take into account the move to the new pixel using the constant differences computed previously.Do the move. How should DE and DSE be initialized?Use the starting point (0,R) DEstart = 2xp+3 = 3 DSEstart = 2xp - 2yp + 5 = 5 - 2RChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives4. Filling RectanglesThe task of filling primitives can be broken down into two parts:the decision on which pixels to filland the easier decision of what to fill them withWe will first discuss filling unclipped primitives with a solid colorWe will see patterns in Section 6Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesIn general, determining which pixels to fill consists of taking successive scan lines that intersect the primitive and filling in spans of adjacent pixels from left to right.Basically we look for those pixels at which changes occur.By doing this, we take advantage of the coherence of the object -- the fact that is does not change very rapidly.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives5. Filling PolygonsThe general polygon scan-conversion algorithm we will study next handles both convex and concave polygons, even those that are self-intersecting or have interior holes.It operates by computing spans that lie between left and right edges of the polygon.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesIn this figure we can see the basic polygon scan-conversion process.Note: for line 8 a and d are at integer values, whereas b and c are not.We must determine which pixels on each scan line are within the polygon, and we must set the corresponding pixels (x=2 through 4, and 9 through 13) to their appropriate value.We then repeat this process for each scan line that intersects the polygon.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThis figure shows one problemIf we use the midpoint line scan-conversion algorithm to find the end of spans, we will select pixels outside the polygonNot good for polygons that share edges.(a) uses midpoint (b) uses interior onlyChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesAs with the original midpoint algorithm, we will use an incremental algorithm to calculate the span extrema on one scan line from those on the previous scan line. In scan line 8 of this figure, there are two spans of pixelsThese spans can be filled in a three step processFind the intersections of the scan line with all edges of the polygon.Sort the intersections by increasing x coordinateFill pixels between pairs that lie interior to the polygonChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThe first two steps will be covered later, so let us look at the span filling strategy.In this figure the sorted coordinates are:2, 4.5, 8.5, and 13When dealing with the span filling there are four elaborations we need to make.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThese elaborations are:Given an intersection with an arbitrary, fractional x value, how do we determine which pixel on either side of that intersection is interior?How do we deal with the special case of intersections at integer pixel coordinates?How do we deal with the special case in the second elaboration for shared vertices?How do we deal with the special case in the second elaboration in which the vertices define a horizontal edge.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesTo handle the first elaboration, we say that if we are approaching a fractional intersection to the right and inside the polygon, we round down the x coordinate of the intersection to define the interior pixel; if we are outside the polygon, we round up to be inside,We handle the second elaboration by applying the criterion we used to avoid conflicts at shared edges of rectanglesIf the leftmost pixel in a span has integer x coordinate, we define it to be interior;If the rightmost pixel has integer x coordinate, we define it to be exterior.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesFor the third case, we count the ymin vertex of an edge in the parity calculation, but not the ymax vertex; therefore a ymax vertex is drawn only if it is the ymin vertex for the adjacent edge.Consider vertex A in this example. It is counted in the parity calculation since it is the ymin for FA, and ignored as the ymax for ABThus edges are treated as intervals (closed at ymin, and open at ymax)Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesFor the fourth case (horizontal edges) the desired effect is that, as with rectangles, bottom edges are drawn but top edges are not. We will see int he next subsection that this happens if we follow the ymax ymin rules just outlined.Examples:scan line 8note pixel at d is not inside polygon by second clarification, therefor it is not drawn.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesExamples (cont.):scan line 3A counts since it is a ymin for AF.scan line 1hits vertex BAB and BC have their ymins at B therefore both change the paritytherefore B is drawn.scan line 9hits vertex FFA and EF have their ymaxs at F (therefore neither change the parity)therefore nothing is drawnChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives5.1 Horizontal EdgesWe deal properly with horizontal edges by not counting their verticesHere are the rules: Dont consider the vertex contribution for the horizontal edgeInvert the parity if the vertex is a ymin of some edge.Do not invert if the vertex is a ymax of some edgeChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesExamples:Consider the bottom edge AB. Vertex A is a ymin for edge JA, and AB does not contribute. Therefore the parity is odd and the span AB is drawn. Vertical edge BC has its ymin at B, but again AB does not contribute. The parity becomes even, and the span is terminated.At vertex J, edge IJ has a ymin vertex but edge JA does not, so the parity becomes odd and the span is drawn to edge BC.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesExamples (cont.):The span that starts at edge IJ (and hits C) sees no change at C because C is a ymax vertex for BC, so the span continues along bottom edge CDHowever at D, the edge DE has a ymin, so the parity s reset to even and the span ends.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesExamples (cont.):The span that starts at I the edge IJ has a ymax and edge HI does not contribute,so parity stays even and the top edge IH is not drawn.At H, however, edge GH has a ymin, so the parity becomes odd and the span is drawn from H to the pixel to the left of the intersection with edge EFFinally, there is no ymin vertex at G, nor is there one at F, so the top edge GF is not drawn.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesIssues:Good:Deals with shared vertices in a polygonDeals with edges shared by two adjacent polygonsDeals with horizontal edgesIt also allows self-intersecting polygons.Bad:It omits pixelsit cannot totally avoid writing shared pixels multiple times without a history.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives5.2 SliversThere is another problem with our scan-conversion algorithm, one that is not resolved as satisfactorily as is that of horizontal edges: polygons with slivers an area so thin that its interior does not contain a distinct span for each scan line.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThis problem of having missing pixels is another example of the aliasing problem representing a continuous signal with a discrete approximation.If we had multiple bits per pixel, we could use antialiasing techniques as introduced for lines in 3.14Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives5.3 Edge Coherence and the Scan-Line AlgorithmStep 1 in our procedure calculating intersections must be done cleverly.Brute Force Method: (very slow)test every polygon edge for intersection with every scan line.Efficient method:take advantage of edge coherenceNote: Calculate the x intercept based upon the previous one. And this can be done completely with integers.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesNow we can develop a scan-line algorithm that takes advantage of this edge coherence.We will use a data structure called the active-edge table (AET)the edges in the AET are sorted on their x intersection values, so we can fill the spans defined by pairs of intersection values (span extremas)As we move to the next scan line, y+1, the AET is updatedfirst those edges in the table whose ymax = y are deletedsecond those edges not in the table whose ymin=y+1 are addedfinally, new x intersections are calculated using the incremental edge algorithmChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesTo make the addition of edges to the AET efficient, we initially create a global edge table (ET) this contains all edges sorted by their smaller y coordinatethe ET is typically built using a bucket sort, with as many buckets as there are scan lines.Inside the bucket they are sorted by the x coordinate at the lower endpoint.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesOnce the ET has been filled, here is our algorithm:set y to the smallest y coordinate with an entry in the ETinitialize AET to empty.Repeat until AET and ET are empty.move from ET to AET bucket yremove from AET those entries for which y=ymax, then sort AET on xfill in the desired pixel values on scan y using pairs of x coordinates from AETy++for each nonvertical edge in AET, update x for the new y (use slope,)Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives6. Pattern FillingIntroduction:So far we have filled the interiors of a primitive with a solid color.Now we want to consider filling with a patternWe do this by adding extra control to the part of the scan conversion algorithm that actually writes each pixel.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives6.1 Pattern Filling Using Scan ConversionThe main issue for filling with pattern is the relation of the area of the pattern to that of the primitive. --- Where is the pattern anchored?Choice 1 Anchor to the leftmost pixel in the first row.some primitives (circles) cause you problemsChoice 2 Have the programmer specify the anchor.Choice 3 consider the entire screen as tiled with the primitive (anchor is lower left corner of the screen)computationally efficient and easy.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives6.2 Pattern Filling without Repeated Scan ConversionAnother technique is to scan convert the primitive first into a rectangular work area, and then to write each pixel from the bitmap to the appropriate place in the canvas.This two-step process is twice as much work as filling during scan conversion, and Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThis two-step process is twice as much work as filling during scan conversion, and therefore is not worthwhile for primitives that are encountered and scan-converted only once.It pays off however for primitives that would otherwise be scan-converted repeatedly.Fixed size fonts,...Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives7. Thick PrimitivesConceptually, you produce thick primitives by tracing the scan-converted single pixel outline primitive.But there are a lot of questions:What shape is the brush,If non-circular, what is the orientation,Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThere are four basic methods for drawing thick primitivesThe first method uses more than 1 pixel for each column or row during scan conversion.The second traces the pens cross section along the single pixel outline of the primitive.The third draws two copies of the primitive a thickness t apart and fills in the space.The fourth approximates all primitives by polylines and then uses a thick line for each polyline segment.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives7.1 Replacing PrimitivesA quick extension to the scan-conversion inner loop to write multiple pixels at each computed pixel works reasonably well for lines;Here pixels are duplicated in columns for lines with -1Problems:The line ends are always horizontal or vertical, which is not pleasing for rather thick lines. Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesProblems (cont.)The pixel replication algorithm also produces noticeable gaps in places where line segments meet at an angle, and misses pixels where there is a shift from horizontal to vertical replication Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesProblems (cont.)The thickness of lines varies by slope (another aliasing problem) if the thickness is horizontal or vertically determined.Even Thicknesses is also a problemAltogether pixel replication is an efficient but crude approximation that works best for primitives that are not very thick.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives7.2 The Moving PenChoosing a rectangular pen whose center or corner travels along the line works reasonably well for lines.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesProblems:The problems here are different. The line is now thicker at the angle than it is on the horizontal.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives8. Clipping in a Raster WorldAs noted earlier, clipping and scan-conversion need to be as fast as possible.Clipping can be done:Analytically,On the fly during scan-conversion,or as part of CopyPixelChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives9. Clipping LinesThis section treats analytic clipping of lines against rectangles; algorithms for clipping other primitives are handled in future sectionsAlthough there are specialized algorithms for rectangle and polygon clipping, it is important to note that primitives built out of lines can be clipped by repeated application of the line clipper.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesLines intersecting a rectangular clip region are always clipped into a single line segmentHere are several examples of clipped lines:Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives9.1 Clipping EndpointsBefore we discuss clipping lines, let us look at the simpler problem of clipping points.For a point to be inside, four inequalities must be satisfied: Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives9.2 Clipping Lines by Solving Simultaneous EquationsTo clip a line, we need only consider its endpoints.If both endpoints lie inside the clip rectangle, the line can be trivially accepted (AB)If one is inside and one outside (CD), the line intersects, and we must compute the intersection point.If both are outside, it may or may not intersect the clip rectangle. We have further work to do.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThe brute force method:Find the intersection points for the line with each of the four clip-rectangle edges.For each line and edge, we take the two lines and intersect themthen we test whether the intersection is interior G and H are, I and J are not.Altogether, the brute-force approach involves considerable calculation and testing; it is thus inefficient.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives9.3 The Cohen-Sutherland Line-Clipping AlgorithmThe more efficient Cohen-Sutherland algorithm performs initial tests on a line to determine whether intersection calculations can be avoided.First, endpoints pairs are checked for trivial acceptance. If they cannot be trivially accepted, region checks are then done.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesFor instance, two simple comparisons on x show that both endpoints of line EF have an x coordinate less than xmin and thus lie outside of the clip rectangletherefore EF is trivially rejected.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesIf a line segment cannot be trivially accepted or trivially rejected, it is divided into two segments at a clip edge so one segment can be trivially dealt with.See edge IJChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesTo perform the tests, we extend the edges of the clip rectangle to divide the plane into 9 regions.These segments help the processing of trivial rejects or accepts.If triviality is not possible, the line is segmented. And the highest bit tells which rectangle edge to intersect the line with with. (edge EI)Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives9.4 A Parametric Line-Clipping AlgorithmIntro:The Cohen-Sutherland algorithm is probably still the most commonly used line-clipping algorithm because it has been around the longest and has been widely published.In 1978, Cyrus and Beck published an algorithm that takes a fundamentally different and generally more efficient approach to line clipping.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesParametric Representation of a lineP(t) = P0+t(P1-P0), t has values in [0,1]t = 0, P(t) == P0t = 1, P(t) == P1This is a directed line segmentParametric vs Slope Intercept equationsSlope Intercept describe infinite linesParametric describe segments (finite lines)Slope Intercept cannot deal with vertical lines.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesCohen-Sutherland is efficient when testing is cheap (bit testing in assembler)trivial acceptance or rejection applies to the majority of the lines.Parametric line clipping wins when:many line segments need to be clipped, since the actual calculation can be postponed.Improvements to both these algorithms are discussed in the literatureChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives10. Clipping CirclesFirst you can do a test on the circles extent (the square containing the circle)If scan conversion is fast, or the circle is not too large, it is probably more efficient to scissor on a pixel-by-pixel basis.If the circle is filled, spans can be clipped individually and then filled.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives11. Clipping PolygonsAn algorithm that clips polygons must deal with many different cases.Note: (a) yields two polygons from one.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives11.1 The Sutherland-Hodgman Polygon-Clipping AlgorithmSutherland and Hodgmans polygon clipping algorithm uses a divide and conquer strategy.It solves a series of simple and identical problems that, when combined, solve the overall problem.The simple problem is to clip a polygon against a single infinite edge.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThe four clip edges, each defining one boundary of the clip rectangle, successively clip a polygon against the clip rectangle.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesNotice the differences between this algorithm and the Cohen-Sutherland line clipping algorithm.In this algorithm, the polygon is clipped against the four lines in succession.In the Line Algorithm, the clipper tested to see which edge was crossed and clipped only when necessary.This algorithm is actually generalizable to allow a polygon to be clipped any convex polyhedral volume.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives12. Generating CharactersThere are two basic techniques for defining characters.Define each character as a curved or polygonal outline and scan convert it as needed.Most general, but computationally expensive.Define each font as a small rectangular bitmap.Generating simply entails copying the pixels from a font cache into the frame buffer.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives14. AntialiasingThe primitives drawn so far have a common problem: They have jagged edges.This undesirable effect known as the jaggies or staircasing, is the result of an all-or-nothing approach to scan conversion in which each pixel is either replaced with the primitives color or is left unchanged.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesJaggies are an instance of a phenomenon known as aliasing. The application of techniques that reduce or eliminate aliasing is referred to as antialiasing.Chapter 14 discusses basic ideas from signal processing that explain how aliasing got its name, why it occurs, and how to reduce or eliminate it when creating pictures.Here, we content ourselves with a more intuitive explanation of why the primitives we have produced exhibit aliasing and how to generate antialiased lines.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives14.1 Increasing ResolutionConsider the midpoint algorithm to draw a 1-pixel thick line. In each column the algorithm sets the color of the pixel closest to the line to black.Each time the line moves between columns in which the pixels closest to the line are not in the same row, there is a sharp jag in the line.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesSuppose we now use a display with twice the horizontal and vertical resolution.The line passes through twice as many columns and therefore has twice as many jags, But each jag is half as large in x and in y.Although the resulting picture looks better, the improvement comes at a cost of quadrupling the memory cost, memory bandwidth, and scan-conversion time.Increasing the resolution only diminishes the problem, it does not eliminate it.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives14.2 Unweighted Area SamplingThe first approach to improving picture quality can be developed by recognizing that, although an ideal primitive such as a line has zero width, the primitive we drawing has nonzero width.A scan-converted area occupies a finite area on the screen.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThus, we think of any line as a rectangle of a desired thickness covering a portion of the grid of pixels.It follows that a line should not set the intensity of only a single pixel in a column to black, but rather should contribute some amount of intensity to each pixel in the columns whose area it intersects.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesBut what is the geometry of a pixel? How large is it?.It is computationally simple to assume that pixels form an array of non-overlapping square tiles covering the screen, centered on grid points, rather than disjoint circles as discussed earlier.We also assume that a line contributes to each pixels intensity an amount proportional to the percentage of the pixels tile it covers.Fully covered is black, Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesThis technique, as applied to the line shown previously is shown below:This blurring makes the line look better at a distance, despite the fact that it spreads the on-off transitions over multiple pixels in a column or row.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesWe call this technique of setting the intensity proportional to the amount of the area covered unweighted area sampling.The properties of unweighted area sampling are:First, the intensity of the pixel intersected by a line edge decreases as the distance between the pixel center and the edge increases.Second, the primitive cannot influence the pixel at all if it does not intersect the pixel.Third, equal areas contribute equal intensity Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives14.3 Weighted Area SamplingIn weighted area sampling, we keep the first and second properties of unweighted area sampling, but we alter the third.We let equal areas contribute unequally.Chapter 14 discusses Weighted Area Sampling in the context of filtering theory.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesTo explain the difference between weighted and unweighted sampling, let us look at one simple example:Traditional unweighted samplingChapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesTraditional weighted samplingNote the change from squares to circles (that overlap)Note also that the weight is centered at the center of the pixel.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives15. Advanced TopicsWe have only touched on the concepts of clipping and scan conversion in this chapter.In practice, many complex situations arise that require the applications of advanced approaches.These are fully discussed in Computer Graphics: Principles and Practice by Foley, vanDam, Feiner and Hughes (1990)Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D PrimitivesSummaryIn this chapter, we have taken our first look at the fundamental clipping and scan-conversion algorithms that are the meat and potatoes of raster graphics packages.The most important idea of this chapter is that, since speed is essential in interactive raster graphics, incremental scan-conversion algorithms using only integer operations in their inner loops are the best.Chapter 3 -- Basic Raster Graphics Algorithms for Drawing 2D Primitives

Recommended

View more >