PJS@GROUCH.JPL.NASA.GOV (Peter Scott) (09/01/89)
Question about the clipping algorithm used in X, prompted by some recent postings: say I draw a line from (x1, y1) to (x2,y2) within a window. Then a portion of the window is obscured, cutting off the portion of the line from (x1,y1) to (x,y). Then the window is exposed again, and I set that rectangle that needs to be repainted as a clipping region and redraw my line from (x1,y1) to (x2,y2). Will the same pixels be turned on in the segment (x1,y1)->(x,y) as before? Or does X use (say) the Cohen-Sutherland clipping algorithm, which might result in a slightly different line if the original did not pass *exactly* through (x,y)? Peter Scott (pjs@grouch.jpl.nasa.gov)
keith@EXPO.LCS.MIT.EDU (Keith Packard) (09/01/89)
Peter Scott (PJS@grouch.jpl.nasa.gov) asks about the requirements in the protocol for drawing clipped lines: > Question about the clipping algorithm used in X, prompted by some recent > postings: say I draw a line from (x1, y1) to (x2,y2) within a window. > Then a portion of the window is obscured, cutting off the portion of > the line from (x1,y1) to (x,y). Then the window is exposed again, and > I set that rectangle that needs to be repainted as a clipping region > and redraw my line from (x1,y1) to (x2,y2). Will the same pixels be > turned on in the segment (x1,y1)->(x,y) as before? For any graphics other than zero-width lines, the answer is very simple; X pixelization rules are exact, and never affected by clipping. For zero width lines, the protocol specifies that clipping cannot have any affect (quoting from the red book, page 402): Thin lines (zero line-width) are "one-pixel wide" lines drawn using an un- specified, device-dependent algorithm. There are only two constraints on this algorithm. First, if a line is drawn unclipped from [x1,y1] to [x2,y2] and another line is drawn unclipped from [x1+dx,y1+dy] to [x2+dx,y2+dy], then a point [x,y] is touched by drawing the first line if and only if the point [x+dx,y+dy] is touched by drawing the second line. Second, the effective set of points comprising a line cannot be affected by clipping. Thus, a point is touched in a clipped line if and only if the point lines inside the clipping re- gion and the point would be touched by the line when drawn unclipped. In the sample server, zero-width lines are drawn using the obvious bresenham, clipping is implemented as a collection of clipping rectangles. The starting conditions of the error terms are adjusted to correct for the starting point of each unclipped portion of the line. It is exact, and correct, but non-optimal for non-rectangular clipping regions (clipping to round objects takes quite a bit of time). This results in reasonable speed for the unclipped case (most common). Unclipped lines draw at 3900 100 pixel segments/second. With 16 clip rectangles, the speed drops to 1700 100 pixel segments/second (these numbers are for a 3/60 in color using x11perf). Yes, a less exact algorithm could speed these numbers up; no, it would not correspond to the requirements in the protocol. Keith Packard MIT X Consortium