1 /* $XConsortium: lines.c,v 1.2 91/10/10 11:18:21 rws Exp $ */
2 /* Copyright International Business Machines, Corp. 1991
3 * All Rights Reserved
4 * Copyright Lexmark International, Inc. 1991
5 * All Rights Reserved
6 *
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.
14 *
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
27 * THIS SOFTWARE.
28 */
29 /* LINES CWEB V0003 ******** */
30 /*
31 :h1.LINES Module - Rasterizing Lines
32
33 &author. Duaine W. Pryor, Jr. and Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
34
35
36 :h3.Include Files
37
38 The included files are:
39 */
40
41 #include <stdio.h>
42
43 #include "types.h"
44 #include "objects.h"
45 #include "spaces.h"
46 #include "paths.h"
47 #include "regions.h"
48 #include "lines.h"
49
50 /*
51 :h3.Functions Provided to the TYPE1IMAGER User
52
53 None.
54 */
55
56 /*
57 :h3.Functions Provided to Other Modules
58
59 This module provides the following entry point to other modules:
60 */
61
62 /*SHARED LINE(S) ORIGINATED HERE*/
63
64 /*
65 :h3.Macros Provided to Other Modules
66
67 None.
68 */
69
70 /*
71 :h2.StepLine() - Produces Run Ends for a Line After Checks
72
73 The main work is done by Bresenham(); here we just perform checks and
74 get the line so that its Y direction is always increasing:
75 */
76
StepLine(R,x1,y1,x2,y2)77 void StepLine(R, x1, y1, x2, y2)
78 register struct region *R; /* region being built */
79 register fractpel x1,y1; /* starting point */
80 register fractpel x2,y2; /* ending point */
81 {
82 register fractpel dy;
83
84 IfTrace4((LineDebug > 0), ".....StepLine: (%d,%d) to (%d,%d)\n",
85 x1, y1, x2, y2);
86
87 dy = y2 - y1;
88
89 /*
90 We execute the "GOING_TO" macro to call back the REGIONS module, if
91 necessary (like if the Y direction of the edge has changed):
92 */
93 GOING_TO(R, x1, y1, x2, y2, dy);
94
95 if (dy == 0)
96 return;
97
98 if (dy < 0)
99 Bresenham(R->edge, x2, y2, x1, y1);
100 else
101 Bresenham(R->edge, x1, y1, x2, y2);
102 return;
103 }
104 /*
105 :h3.Bresenham() - Actually Produces Run Ends
106
107 This routine runs a Bresenham line-stepping
108 algorithm. See, for example, Newman and Sproul, :hp1/Principles
109 of Interactive Computer Graphics/, pp. 25-27.
110 When we enter this, we
111 are guaranteed that dy is positive.
112 We'd like to work in 8 bit precision, so we'll define some macros and
113 constants to let us do that:
114 */
115
116 #define PREC 8 /* we'll keep fraction pels in 8 bit precision */
117 /*
118 RoundFP() rounds down by 'b' bits:
119 */
120 #define RoundFP(xy,b) (((xy)+(1<<((b)-1)))>>(b))
121
122 /*
123 TruncFP() truncates down by 'b' bits:
124 */
125 #define TruncFP(xy,b) ((xy)>>(b))
126
127
Bresenham(edgeP,x1,y1,x2,y2)128 void Bresenham(edgeP,x1,y1,x2,y2)
129 register pel *edgeP; /* pointer to top of list (y == 0) */
130 register fractpel x1,y1; /* starting point on line */
131 register fractpel x2,y2; /* ending point on the line (down) */
132 {
133 register LONG dx,dy; /* change in x and y, in my own precision */
134 register LONG x,y; /* integer pel starting point */
135 register int count; /* integer pel delta y */
136 register LONG d; /* the Bresenham algorithm error term */
137
138 x1 = TruncFP(x1, FRACTBITS-PREC);
139 y1 = TruncFP(y1, FRACTBITS-PREC);
140 x2 = TruncFP(x2, FRACTBITS-PREC);
141 y2 = TruncFP(y2, FRACTBITS-PREC);
142
143 dx = x2 - x1;
144 dy = y2 - y1;
145 /*
146 Find the starting x and y integer pel coordinates:
147 */
148
149 x = RoundFP(x1,PREC);
150 y = RoundFP(y1,PREC);
151
152 edgeP += y;
153 count = RoundFP(y2,PREC) - y;
154 /*------------------------------------------------------------------*/
155 /* Force dx to be positive so that dfy will be negative */
156 /* this means that vertical moves will decrease d */
157 /*------------------------------------------------------------------*/
158 if (dx<0)
159 {
160 dx = -dx;
161 #define P PREC
162 d=(dy*(x1-(x<<P)+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
163 #undef P
164 while(--count >= 0 )
165 {
166 while(d<0)
167 {
168 --x;
169 d += dy;
170 }
171 *(edgeP++) = x;
172 d -= dx;
173 }
174 }
175 else /* positive dx */
176 {
177
178 if ( dx == 0 ) {
179 while(--count >= 0 ) {
180 *(edgeP++) = x;
181 }
182 return;
183
184 }
185
186 #define P PREC
187 d = (dy*((x<<P)-x1+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
188 #undef P
189 while(--count >= 0 )
190 {
191 while(d<0)
192 {
193 ++x;
194 d += dy;
195 }
196 *(edgeP++) = x;
197 d -= dx;
198 }
199 }
200 }
201