1 /* $XConsortium: lines.c,v 1.2 91/10/10 11:18:21 rws Exp $ */
2 /* Copyright International Business Machines, Corp. 1991
4 * Copyright Lexmark International, Inc. 1991
7 * License to use, copy, modify, and distribute this software and its
8 * documentation for any purpose and without fee is hereby granted,
9 * provided that the above copyright notice appear in all copies and that
10 * both that copyright notice and this permission notice appear in
11 * supporting documentation, and that the name of IBM or Lexmark not be
12 * used in advertising or publicity pertaining to distribution of the
13 * software without specific, written prior permission.
15 * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
16 * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
17 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
18 * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. THE ENTIRE RISK AS TO THE
19 * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
20 * OR MAINTAIN, BELONGS TO THE LICENSEE. SHOULD ANY PORTION OF THE
21 * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
22 * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION. IN NO EVENT SHALL
23 * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
24 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
25 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
26 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
29 /* LINES CWEB V0003 ******** */
31 :h1.LINES Module - Rasterizing Lines
33 &author. Duaine W. Pryor, Jr. and Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
38 The included files are:
47 :h3.Functions Provided to the TYPE1IMAGER User
53 :h3.Functions Provided to Other Modules
55 This module provides the following entry point to other modules:
58 /*SHARED LINE(S) ORIGINATED HERE*/
61 :h3.Macros Provided to Other Modules
67 :h2.StepLine() - Produces Run Ends for a Line After Checks
69 The main work is done by Bresenham(); here we just perform checks and
70 get the line so that its Y direction is always increasing:
73 void StepLine(R, x1, y1, x2, y2)
74 register struct region *R; /* region being built */
75 register fractpel x1,y1; /* starting point */
76 register fractpel x2,y2; /* ending point */
80 IfTrace4((LineDebug > 0), ".....StepLine: (%p,%p) to (%p,%p)\n",
86 We execute the "GOING_TO" macro to call back the REGIONS module, if
87 necessary (like if the Y direction of the edge has changed):
89 GOING_TO(R, x1, y1, x2, y2, dy);
95 Bresenham(R->edge, x2, y2, x1, y1);
97 Bresenham(R->edge, x1, y1, x2, y2);
101 :h3.Bresenham() - Actually Produces Run Ends
103 This routine runs a Bresenham line-stepping
104 algorithm. See, for example, Newman and Sproul, :hp1/Principles
105 of Interactive Computer Graphics/, pp. 25-27.
106 When we enter this, we
107 are guaranteed that dy is positive.
108 We'd like to work in 8 bit precision, so we'll define some macros and
109 constants to let us do that:
112 #define PREC 8 /* we'll keep fraction pels in 8 bit precision */
114 RoundFP() rounds down by 'b' bits:
116 #define RoundFP(xy,b) (((xy)+(1<<((b)-1)))>>(b))
119 TruncFP() truncates down by 'b' bits:
121 #define TruncFP(xy,b) ((xy)>>(b))
124 void Bresenham(edgeP,x1,y1,x2,y2)
125 register pel *edgeP; /* pointer to top of list (y == 0) */
126 register fractpel x1,y1; /* starting point on line */
127 register fractpel x2,y2; /* ending point on the line (down) */
129 register long dx,dy; /* change in x and y, in my own precision */
130 register long x,y; /* integer pel starting point */
131 register int count; /* integer pel delta y */
132 register long d; /* the Bresenham algorithm error term */
134 x1 = TruncFP(x1, FRACTBITS-PREC);
135 y1 = TruncFP(y1, FRACTBITS-PREC);
136 x2 = TruncFP(x2, FRACTBITS-PREC);
137 y2 = TruncFP(y2, FRACTBITS-PREC);
142 Find the starting x and y integer pel coordinates:
145 x = RoundFP(x1,PREC);
146 y = RoundFP(y1,PREC);
148 count = RoundFP(y2,PREC) - y;
149 /*------------------------------------------------------------------*/
150 /* Force dx to be positive so that dfy will be negative */
151 /* this means that vertical moves will decrease d */
152 /*------------------------------------------------------------------*/
157 d=(dy*(x1-(x<<P)+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
170 else /* positive dx */
173 d = (dy*((x<<P)-x1+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;