Path: utzoo!attcan!uunet!cs.utexas.edu!rutgers!apple!bloom-beacon!EXPO.LCS.MIT.EDU!keith
From: keith@EXPO.LCS.MIT.EDU
Newsgroups: comp.windows.x
Subject: Re: X line definition
Message-ID: <8906161811.AA07074@xenon.lcs.mit.edu>
Date: 16 Jun 89 18:11:55 GMT
References: <8906161725.AA02074@amd-26.hac.com>
Sender: daemon@bloom-beacon.MIT.EDU
Organization: The Internet
Lines: 28


(The first question is not answerable in closed form)

>The second question is about the line alorithm of the X server.  The 
>X protocol specification defines a line to be a filled rectangle with 
>vertices at:
	    
>     [x1-(w*sn/2),y1+(w*cs/2)],[x1+(w*sn/2),y1-(w*cs/2)],
>     [x2-(w*sn/2),y2+(w*cs/2)],[x2+(w*sn/2),y2-(w*cs/2)]

>using the fill algorithm also defined in the protocol spec.  The problem
>I have is that in the "Strategies for Porting the X v11 Sample Server", 
>dated March 1, 1988, section 2.4.14.2. (Second Round Optimizations), 
>describes how to optimize the line drawing performance of X by implementing
>a Bresenham edge walker.  First, I don't believe that line drawn with
>Bresenham's algorithm conforms to the X definition of a line.  Second, I
>am confused by the reference to a need for multiplication and
>division in implementing Bresenham's algorithm since the algorithm was 
>developed to avoid the need for multiplication and division

The strategies document was refering mostly to zero-width lines which are
not restricted by the above equations for pixelization -- a Bresenham
zero-width line is quite acceptable; the mfb sample ddx layer uses one.
The multiplication/division in the mfb implementation are required to
wind the algorithm past any clipped regions of the line as even zero-width
lines are supposed to draw the same pixels in the presence of clipping.
You could step the algorithm past the clipped region and simply avoid
the pixelization portions (this actually works quite well for short lines).