1 /***********************************************************
2
3 Copyright (c) 1987 X Consortium
4
5 Permission is hereby granted, free of charge, to any person obtaining a copy
6 of this software and associated documentation files (the "Software"), to deal
7 in the Software without restriction, including without limitation the rights
8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 copies of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
11
12 The above copyright notice and this permission notice shall be included in
13 all copies or substantial portions of the Software.
14
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
19 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21
22 Except as contained in this notice, the name of the X Consortium shall not be
23 used in advertising or otherwise to promote the sale, use or other dealings
24 in this Software without prior written authorization from the X Consortium.
25
26
27 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
28
29 All Rights Reserved
30
31 Permission to use, copy, modify, and distribute this software and its
32 documentation for any purpose and without fee is hereby granted,
33 provided that the above copyright notice appear in all copies and that
34 both that copyright notice and this permission notice appear in
35 supporting documentation, and that the name of Digital not be
36 used in advertising or publicity pertaining to distribution of the
37 software without specific, written prior permission.
38
39 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
40 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
41 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
42 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
43 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
44 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
45 SOFTWARE.
46
47 ******************************************************************/
48 /* $XConsortium: mizerline.c,v 5.9 94/08/02 15:01:29 dpw Exp $ */
49 #include "X.h"
50
51 #include "misc.h"
52 #include "scrnintstr.h"
53 #include "gcstruct.h"
54 #include "windowstr.h"
55 #include "pixmap.h"
56 #include "mi.h"
57 #include "miline.h"
58
59 /*
60
61 The bresenham error equation used in the mi/mfb/cfb line routines is:
62
63 e = error
64 dx = difference in raw X coordinates
65 dy = difference in raw Y coordinates
66 M = # of steps in X direction
67 N = # of steps in Y direction
68 B = 0 to prefer diagonal steps in a given octant,
69 1 to prefer axial steps in a given octant
70
71 For X major lines:
72 e = 2Mdy - 2Ndx - dx - B
73 -2dx <= e < 0
74
75 For Y major lines:
76 e = 2Ndx - 2Mdy - dy - B
77 -2dy <= e < 0
78
79 At the start of the line, we have taken 0 X steps and 0 Y steps,
80 so M = 0 and N = 0:
81
82 X major e = 2Mdy - 2Ndx - dx - B
83 = -dx - B
84
85 Y major e = 2Ndx - 2Mdy - dy - B
86 = -dy - B
87
88 At the end of the line, we have taken dx X steps and dy Y steps,
89 so M = dx and N = dy:
90
91 X major e = 2Mdy - 2Ndx - dx - B
92 = 2dxdy - 2dydx - dx - B
93 = -dx - B
94 Y major e = 2Ndx - 2Mdy - dy - B
95 = 2dydx - 2dxdy - dy - B
96 = -dy - B
97
98 Thus, the error term is the same at the start and end of the line.
99
100 Let us consider clipping an X coordinate. There are 4 cases which
101 represent the two independent cases of clipping the start vs. the
102 end of the line and an X major vs. a Y major line. In any of these
103 cases, we know the number of X steps (M) and we wish to find the
104 number of Y steps (N). Thus, we will solve our error term equation.
105 If we are clipping the start of the line, we will find the smallest
106 N that satisfies our error term inequality. If we are clipping the
107 end of the line, we will find the largest number of Y steps that
108 satisfies the inequality. In that case, since we are representing
109 the Y steps as (dy - N), we will actually want to solve for the
110 smallest N in that equation.
111
112 Case 1: X major, starting X coordinate moved by M steps
113
114 -2dx <= 2Mdy - 2Ndx - dx - B < 0
115 2Ndx <= 2Mdy - dx - B + 2dx 2Ndx > 2Mdy - dx - B
116 2Ndx <= 2Mdy + dx - B N > (2Mdy - dx - B) / 2dx
117 N <= (2Mdy + dx - B) / 2dx
118
119 Since we are trying to find the smallest N that satisfies these
120 equations, we should use the > inequality to find the smallest:
121
122 N = floor((2Mdy - dx - B) / 2dx) + 1
123 = floor((2Mdy - dx - B + 2dx) / 2dx)
124 = floor((2Mdy + dx - B) / 2dx)
125
126 Case 1b: X major, ending X coordinate moved to M steps
127
128 Same derivations as Case 1, but we want the largest N that satisfies
129 the equations, so we use the <= inequality:
130
131 N = floor((2Mdy + dx - B) / 2dx)
132
133 Case 2: X major, ending X coordinate moved by M steps
134
135 -2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
136 -2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
137 -2dx <= 2Ndx - 2Mdy - dx - B < 0
138 2Ndx >= 2Mdy + dx + B - 2dx 2Ndx < 2Mdy + dx + B
139 2Ndx >= 2Mdy - dx + B N < (2Mdy + dx + B) / 2dx
140 N >= (2Mdy - dx + B) / 2dx
141
142 Since we are trying to find the highest number of Y steps that
143 satisfies these equations, we need to find the smallest N, so
144 we should use the >= inequality to find the smallest:
145
146 N = ceiling((2Mdy - dx + B) / 2dx)
147 = floor((2Mdy - dx + B + 2dx - 1) / 2dx)
148 = floor((2Mdy + dx + B - 1) / 2dx)
149
150 Case 2b: X major, starting X coordinate moved to M steps from end
151
152 Same derivations as Case 2, but we want the smallest number of Y
153 steps, so we want the highest N, so we use the < inequality:
154
155 N = ceiling((2Mdy + dx + B) / 2dx) - 1
156 = floor((2Mdy + dx + B + 2dx - 1) / 2dx) - 1
157 = floor((2Mdy + dx + B + 2dx - 1 - 2dx) / 2dx)
158 = floor((2Mdy + dx + B - 1) / 2dx)
159
160 Case 3: Y major, starting X coordinate moved by M steps
161
162 -2dy <= 2Ndx - 2Mdy - dy - B < 0
163 2Ndx >= 2Mdy + dy + B - 2dy 2Ndx < 2Mdy + dy + B
164 2Ndx >= 2Mdy - dy + B N < (2Mdy + dy + B) / 2dx
165 N >= (2Mdy - dy + B) / 2dx
166
167 Since we are trying to find the smallest N that satisfies these
168 equations, we should use the >= inequality to find the smallest:
169
170 N = ceiling((2Mdy - dy + B) / 2dx)
171 = floor((2Mdy - dy + B + 2dx - 1) / 2dx)
172 = floor((2Mdy - dy + B - 1) / 2dx) + 1
173
174 Case 3b: Y major, ending X coordinate moved to M steps
175
176 Same derivations as Case 3, but we want the largest N that satisfies
177 the equations, so we use the < inequality:
178
179 N = ceiling((2Mdy + dy + B) / 2dx) - 1
180 = floor((2Mdy + dy + B + 2dx - 1) / 2dx) - 1
181 = floor((2Mdy + dy + B + 2dx - 1 - 2dx) / 2dx)
182 = floor((2Mdy + dy + B - 1) / 2dx)
183
184 Case 4: Y major, ending X coordinate moved by M steps
185
186 -2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
187 -2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
188 -2dy <= 2Mdy - 2Ndx - dy - B < 0
189 2Ndx <= 2Mdy - dy - B + 2dy 2Ndx > 2Mdy - dy - B
190 2Ndx <= 2Mdy + dy - B N > (2Mdy - dy - B) / 2dx
191 N <= (2Mdy + dy - B) / 2dx
192
193 Since we are trying to find the highest number of Y steps that
194 satisfies these equations, we need to find the smallest N, so
195 we should use the > inequality to find the smallest:
196
197 N = floor((2Mdy - dy - B) / 2dx) + 1
198
199 Case 4b: Y major, starting X coordinate moved to M steps from end
200
201 Same analysis as Case 4, but we want the smallest number of Y steps
202 which means the largest N, so we use the <= inequality:
203
204 N = floor((2Mdy + dy - B) / 2dx)
205
206 Now let's try the Y coordinates, we have the same 4 cases.
207
208 Case 5: X major, starting Y coordinate moved by N steps
209
210 -2dx <= 2Mdy - 2Ndx - dx - B < 0
211 2Mdy >= 2Ndx + dx + B - 2dx 2Mdy < 2Ndx + dx + B
212 2Mdy >= 2Ndx - dx + B M < (2Ndx + dx + B) / 2dy
213 M >= (2Ndx - dx + B) / 2dy
214
215 Since we are trying to find the smallest M, we use the >= inequality:
216
217 M = ceiling((2Ndx - dx + B) / 2dy)
218 = floor((2Ndx - dx + B + 2dy - 1) / 2dy)
219 = floor((2Ndx - dx + B - 1) / 2dy) + 1
220
221 Case 5b: X major, ending Y coordinate moved to N steps
222
223 Same derivations as Case 5, but we want the largest M that satisfies
224 the equations, so we use the < inequality:
225
226 M = ceiling((2Ndx + dx + B) / 2dy) - 1
227 = floor((2Ndx + dx + B + 2dy - 1) / 2dy) - 1
228 = floor((2Ndx + dx + B + 2dy - 1 - 2dy) / 2dy)
229 = floor((2Ndx + dx + B - 1) / 2dy)
230
231 Case 6: X major, ending Y coordinate moved by N steps
232
233 -2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
234 -2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
235 -2dx <= 2Ndx - 2Mdy - dx - B < 0
236 2Mdy <= 2Ndx - dx - B + 2dx 2Mdy > 2Ndx - dx - B
237 2Mdy <= 2Ndx + dx - B M > (2Ndx - dx - B) / 2dy
238 M <= (2Ndx + dx - B) / 2dy
239
240 Largest # of X steps means smallest M, so use the > inequality:
241
242 M = floor((2Ndx - dx - B) / 2dy) + 1
243
244 Case 6b: X major, starting Y coordinate moved to N steps from end
245
246 Same derivations as Case 6, but we want the smallest # of X steps
247 which means the largest M, so use the <= inequality:
248
249 M = floor((2Ndx + dx - B) / 2dy)
250
251 Case 7: Y major, starting Y coordinate moved by N steps
252
253 -2dy <= 2Ndx - 2Mdy - dy - B < 0
254 2Mdy <= 2Ndx - dy - B + 2dy 2Mdy > 2Ndx - dy - B
255 2Mdy <= 2Ndx + dy - B M > (2Ndx - dy - B) / 2dy
256 M <= (2Ndx + dy - B) / 2dy
257
258 To find the smallest M, use the > inequality:
259
260 M = floor((2Ndx - dy - B) / 2dy) + 1
261 = floor((2Ndx - dy - B + 2dy) / 2dy)
262 = floor((2Ndx + dy - B) / 2dy)
263
264 Case 7b: Y major, ending Y coordinate moved to N steps
265
266 Same derivations as Case 7, but we want the largest M that satisfies
267 the equations, so use the <= inequality:
268
269 M = floor((2Ndx + dy - B) / 2dy)
270
271 Case 8: Y major, ending Y coordinate moved by N steps
272
273 -2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
274 -2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
275 -2dy <= 2Mdy - 2Ndx - dy - B < 0
276 2Mdy >= 2Ndx + dy + B - 2dy 2Mdy < 2Ndx + dy + B
277 2Mdy >= 2Ndx - dy + B M < (2Ndx + dy + B) / 2dy
278 M >= (2Ndx - dy + B) / 2dy
279
280 To find the highest X steps, find the smallest M, use the >= inequality:
281
282 M = ceiling((2Ndx - dy + B) / 2dy)
283 = floor((2Ndx - dy + B + 2dy - 1) / 2dy)
284 = floor((2Ndx + dy + B - 1) / 2dy)
285
286 Case 8b: Y major, starting Y coordinate moved to N steps from the end
287
288 Same derivations as Case 8, but we want to find the smallest # of X
289 steps which means the largest M, so we use the < inequality:
290
291 M = ceiling((2Ndx + dy + B) / 2dy) - 1
292 = floor((2Ndx + dy + B + 2dy - 1) / 2dy) - 1
293 = floor((2Ndx + dy + B + 2dy - 1 - 2dy) / 2dy)
294 = floor((2Ndx + dy + B - 1) / 2dy)
295
296 So, our equations are:
297
298 1: X major move x1 to x1+M floor((2Mdy + dx - B) / 2dx)
299 1b: X major move x2 to x1+M floor((2Mdy + dx - B) / 2dx)
300 2: X major move x2 to x2-M floor((2Mdy + dx + B - 1) / 2dx)
301 2b: X major move x1 to x2-M floor((2Mdy + dx + B - 1) / 2dx)
302
303 3: Y major move x1 to x1+M floor((2Mdy - dy + B - 1) / 2dx) + 1
304 3b: Y major move x2 to x1+M floor((2Mdy + dy + B - 1) / 2dx)
305 4: Y major move x2 to x2-M floor((2Mdy - dy - B) / 2dx) + 1
306 4b: Y major move x1 to x2-M floor((2Mdy + dy - B) / 2dx)
307
308 5: X major move y1 to y1+N floor((2Ndx - dx + B - 1) / 2dy) + 1
309 5b: X major move y2 to y1+N floor((2Ndx + dx + B - 1) / 2dy)
310 6: X major move y2 to y2-N floor((2Ndx - dx - B) / 2dy) + 1
311 6b: X major move y1 to y2-N floor((2Ndx + dx - B) / 2dy)
312
313 7: Y major move y1 to y1+N floor((2Ndx + dy - B) / 2dy)
314 7b: Y major move y2 to y1+N floor((2Ndx + dy - B) / 2dy)
315 8: Y major move y2 to y2-N floor((2Ndx + dy + B - 1) / 2dy)
316 8b: Y major move y1 to y2-N floor((2Ndx + dy + B - 1) / 2dy)
317
318 We have the following constraints on all of the above terms:
319
320 0 < M,N <= 2^15 2^15 can be imposed by miZeroClipLine
321 0 <= dx/dy <= 2^16 - 1
322 0 <= B <= 1
323
324 The floor in all of the above equations can be accomplished with a
325 simple C divide operation provided that both numerator and denominator
326 are positive.
327
328 Since dx,dy >= 0 and since moving an X coordinate implies that dx != 0
329 and moving a Y coordinate implies dy != 0, we know that the denominators
330 are all > 0.
331
332 For all lines, (-B) and (B-1) are both either 0 or -1, depending on the
333 bias. Thus, we have to show that the 2MNdxy +/- dxy terms are all >= 1
334 or > 0 to prove that the numerators are positive (or zero).
335
336 For X Major lines we know that dx > 0 and since 2Mdy is >= 0 due to the
337 constraints, the first four equations all have numerators >= 0.
338
339 For the second four equations, M > 0, so 2Mdy >= 2dy so (2Mdy - dy) >= dy
340 So (2Mdy - dy) > 0, since they are Y major lines. Also, (2Mdy + dy) >= 3dy
341 or (2Mdy + dy) > 0. So all of their numerators are >= 0.
342
343 For the third set of four equations, N > 0, so 2Ndx >= 2dx so (2Ndx - dx)
344 >= dx > 0. Similarly (2Ndx + dx) >= 3dx > 0. So all numerators >= 0.
345
346 For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators
347 are > 0.
348
349 To consider overflow, consider the case of 2 * M,N * dx,dy + dx,dy. This
350 is bounded <= 2 * 2^15 * (2^16 - 1) + (2^16 - 1)
351 <= 2^16 * (2^16 - 1) + (2^16 - 1)
352 <= 2^32 - 2^16 + 2^16 - 1
353 <= 2^32 - 1
354 Since the (-B) and (B-1) terms are all 0 or -1, the maximum value of
355 the numerator is therefore (2^32 - 1), which does not overflow an unsigned
356 32 bit variable.
357
358 */
359
360 #define MIOUTCODES(outcode, x, y, xmin, ymin, xmax, ymax) \
361 {\
362 if (x < xmin) outcode |= OUT_LEFT;\
363 if (x > xmax) outcode |= OUT_RIGHT;\
364 if (y < ymin) outcode |= OUT_ABOVE;\
365 if (y > ymax) outcode |= OUT_BELOW;\
366 }
367
368 /* Bit codes for the terms of the 16 clipping equations defined below. */
369
370 #define T_2NDX (1 << 0)
371 #define T_2MDY (0) /* implicit term */
372 #define T_DXNOTY (1 << 1)
373 #define T_DYNOTX (0) /* implicit term */
374 #define T_SUBDXORY (1 << 2)
375 #define T_ADDDX (T_DXNOTY) /* composite term */
376 #define T_SUBDX (T_DXNOTY | T_SUBDXORY) /* composite term */
377 #define T_ADDDY (T_DYNOTX) /* composite term */
378 #define T_SUBDY (T_DYNOTX | T_SUBDXORY) /* composite term */
379 #define T_BIASSUBONE (1 << 3)
380 #define T_SUBBIAS (0) /* implicit term */
381 #define T_DIV2DX (1 << 4)
382 #define T_DIV2DY (0) /* implicit term */
383 #define T_ADDONE (1 << 5)
384
385 /* Bit masks defining the 16 equations used in miZeroClipLine. */
386
387 #define EQN1 (T_2MDY | T_ADDDX | T_SUBBIAS | T_DIV2DX)
388 #define EQN1B (T_2MDY | T_ADDDX | T_SUBBIAS | T_DIV2DX)
389 #define EQN2 (T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX)
390 #define EQN2B (T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX)
391
392 #define EQN3 (T_2MDY | T_SUBDY | T_BIASSUBONE | T_DIV2DX | T_ADDONE)
393 #define EQN3B (T_2MDY | T_ADDDY | T_BIASSUBONE | T_DIV2DX)
394 #define EQN4 (T_2MDY | T_SUBDY | T_SUBBIAS | T_DIV2DX | T_ADDONE)
395 #define EQN4B (T_2MDY | T_ADDDY | T_SUBBIAS | T_DIV2DX)
396
397 #define EQN5 (T_2NDX | T_SUBDX | T_BIASSUBONE | T_DIV2DY | T_ADDONE)
398 #define EQN5B (T_2NDX | T_ADDDX | T_BIASSUBONE | T_DIV2DY)
399 #define EQN6 (T_2NDX | T_SUBDX | T_SUBBIAS | T_DIV2DY | T_ADDONE)
400 #define EQN6B (T_2NDX | T_ADDDX | T_SUBBIAS | T_DIV2DY)
401
402 #define EQN7 (T_2NDX | T_ADDDY | T_SUBBIAS | T_DIV2DY)
403 #define EQN7B (T_2NDX | T_ADDDY | T_SUBBIAS | T_DIV2DY)
404 #define EQN8 (T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY)
405 #define EQN8B (T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY)
406
407 /* miZeroClipLine
408 *
409 * returns: 1 for partially clipped line
410 * -1 for completely clipped line
411 *
412 */
413 int
miZeroClipLine(xmin,ymin,xmax,ymax,new_x1,new_y1,new_x2,new_y2,adx,ady,pt1_clipped,pt2_clipped,octant,bias,oc1,oc2)414 miZeroClipLine(xmin, ymin, xmax, ymax,
415 new_x1, new_y1, new_x2, new_y2,
416 adx, ady,
417 pt1_clipped, pt2_clipped, octant, bias, oc1, oc2)
418 int xmin, ymin, xmax, ymax;
419 int *new_x1, *new_y1, *new_x2, *new_y2;
420 int *pt1_clipped, *pt2_clipped;
421 unsigned int adx, ady;
422 int octant;
423 unsigned int bias;
424 int oc1, oc2;
425 {
426 int swapped = 0;
427 int clipDone = 0;
428 CARD32 utmp;
429 int clip1, clip2;
430 int x1, y1, x2, y2;
431 int x1_orig, y1_orig, x2_orig, y2_orig;
432 int xmajor;
433 int negslope, anchorval;
434 unsigned int eqn;
435
436 x1 = x1_orig = *new_x1;
437 y1 = y1_orig = *new_y1;
438 x2 = x2_orig = *new_x2;
439 y2 = y2_orig = *new_y2;
440
441 clip1 = 0;
442 clip2 = 0;
443
444 xmajor = IsXMajorOctant(octant);
445 bias = ((bias >> octant) & 1);
446
447 while (1)
448 {
449 if ((oc1 & oc2) != 0) /* trivial reject */
450 {
451 clipDone = -1;
452 clip1 = oc1;
453 clip2 = oc2;
454 break;
455 }
456 else if ((oc1 | oc2) == 0) /* trivial accept */
457 {
458 clipDone = 1;
459 if (swapped)
460 {
461 SWAPINT_PAIR(x1, y1, x2, y2);
462 SWAPINT(clip1, clip2);
463 }
464 break;
465 }
466 else /* have to clip */
467 {
468 /* only clip one point at a time */
469 if (oc1 == 0)
470 {
471 SWAPINT_PAIR(x1, y1, x2, y2);
472 SWAPINT_PAIR(x1_orig, y1_orig, x2_orig, y2_orig);
473 SWAPINT(oc1, oc2);
474 SWAPINT(clip1, clip2);
475 swapped = !swapped;
476 }
477
478 clip1 |= oc1;
479 if (oc1 & OUT_LEFT)
480 {
481 negslope = IsYDecreasingOctant(octant);
482 utmp = xmin - x1_orig;
483 if (utmp <= 32767) /* clip based on near endpt */
484 {
485 if (xmajor)
486 eqn = (swapped) ? EQN2 : EQN1;
487 else
488 eqn = (swapped) ? EQN4 : EQN3;
489 anchorval = y1_orig;
490 }
491 else /* clip based on far endpt */
492 {
493 utmp = x2_orig - xmin;
494 if (xmajor)
495 eqn = (swapped) ? EQN1B : EQN2B;
496 else
497 eqn = (swapped) ? EQN3B : EQN4B;
498 anchorval = y2_orig;
499 negslope = !negslope;
500 }
501 x1 = xmin;
502 }
503 else if (oc1 & OUT_ABOVE)
504 {
505 negslope = IsXDecreasingOctant(octant);
506 utmp = ymin - y1_orig;
507 if (utmp <= 32767) /* clip based on near endpt */
508 {
509 if (xmajor)
510 eqn = (swapped) ? EQN6 : EQN5;
511 else
512 eqn = (swapped) ? EQN8 : EQN7;
513 anchorval = x1_orig;
514 }
515 else /* clip based on far endpt */
516 {
517 utmp = y2_orig - ymin;
518 if (xmajor)
519 eqn = (swapped) ? EQN5B : EQN6B;
520 else
521 eqn = (swapped) ? EQN7B : EQN8B;
522 anchorval = x2_orig;
523 negslope = !negslope;
524 }
525 y1 = ymin;
526 }
527 else if (oc1 & OUT_RIGHT)
528 {
529 negslope = IsYDecreasingOctant(octant);
530 utmp = x1_orig - xmax;
531 if (utmp <= 32767) /* clip based on near endpt */
532 {
533 if (xmajor)
534 eqn = (swapped) ? EQN2 : EQN1;
535 else
536 eqn = (swapped) ? EQN4 : EQN3;
537 anchorval = y1_orig;
538 }
539 else /* clip based on far endpt */
540 {
541 /*
542 * Technically since the equations can handle
543 * utmp == 32768, this overflow code isn't
544 * needed since X11 protocol can't generate
545 * a line which goes more than 32768 pixels
546 * to the right of a clip rectangle.
547 */
548 utmp = xmax - x2_orig;
549 if (xmajor)
550 eqn = (swapped) ? EQN1B : EQN2B;
551 else
552 eqn = (swapped) ? EQN3B : EQN4B;
553 anchorval = y2_orig;
554 negslope = !negslope;
555 }
556 x1 = xmax;
557 }
558 else if (oc1 & OUT_BELOW)
559 {
560 negslope = IsXDecreasingOctant(octant);
561 utmp = y1_orig - ymax;
562 if (utmp <= 32767) /* clip based on near endpt */
563 {
564 if (xmajor)
565 eqn = (swapped) ? EQN6 : EQN5;
566 else
567 eqn = (swapped) ? EQN8 : EQN7;
568 anchorval = x1_orig;
569 }
570 else /* clip based on far endpt */
571 {
572 /*
573 * Technically since the equations can handle
574 * utmp == 32768, this overflow code isn't
575 * needed since X11 protocol can't generate
576 * a line which goes more than 32768 pixels
577 * below the bottom of a clip rectangle.
578 */
579 utmp = ymax - y2_orig;
580 if (xmajor)
581 eqn = (swapped) ? EQN5B : EQN6B;
582 else
583 eqn = (swapped) ? EQN7B : EQN8B;
584 anchorval = x2_orig;
585 negslope = !negslope;
586 }
587 y1 = ymax;
588 }
589
590 if (swapped)
591 negslope = !negslope;
592
593 utmp <<= 1; /* utmp = 2N or 2M */
594 if (eqn & T_2NDX)
595 utmp = (utmp * adx);
596 else /* (eqn & T_2MDY) */
597 utmp = (utmp * ady);
598 if (eqn & T_DXNOTY)
599 if (eqn & T_SUBDXORY)
600 utmp -= adx;
601 else
602 utmp += adx;
603 else /* (eqn & T_DYNOTX) */
604 if (eqn & T_SUBDXORY)
605 utmp -= ady;
606 else
607 utmp += ady;
608 if (eqn & T_BIASSUBONE)
609 utmp += bias - 1;
610 else /* (eqn & T_SUBBIAS) */
611 utmp -= bias;
612 if (eqn & T_DIV2DX)
613 utmp /= (adx << 1);
614 else /* (eqn & T_DIV2DY) */
615 utmp /= (ady << 1);
616 if (eqn & T_ADDONE)
617 utmp++;
618
619 if (negslope)
620 utmp = -utmp;
621
622 if (eqn & T_2NDX) /* We are calculating X steps */
623 x1 = anchorval + utmp;
624 else /* else, Y steps */
625 y1 = anchorval + utmp;
626
627 oc1 = 0;
628 MIOUTCODES(oc1, x1, y1, xmin, ymin, xmax, ymax);
629 }
630 }
631
632 *new_x1 = x1;
633 *new_y1 = y1;
634 *new_x2 = x2;
635 *new_y2 = y2;
636
637 *pt1_clipped = clip1;
638 *pt2_clipped = clip2;
639
640 return clipDone;
641 }
642
643
644 /* Draw lineSolid, fillStyle-independent zero width lines.
645 *
646 * Must keep X and Y coordinates in "ints" at least until after they're
647 * translated and clipped to accomodate CoordModePrevious lines with very
648 * large coordinates.
649 *
650 * Draws the same pixels regardless of sign(dx) or sign(dy).
651 *
652 * Ken Whaley
653 *
654 */
655
656 /* largest positive value that can fit into a component of a point.
657 * Assumes that the point structure is {type x, y;} where type is
658 * a signed type.
659 */
660 #define MAX_COORDINATE ((1 << (((sizeof(DDXPointRec) >> 1) << 3) - 1)) - 1)
661
662 #define MI_OUTPUT_POINT(xx, yy)\
663 {\
664 if ( !new_span && yy == current_y)\
665 {\
666 if (xx < spans->x)\
667 spans->x = xx;\
668 ++*widths;\
669 }\
670 else\
671 {\
672 ++Nspans;\
673 ++spans;\
674 ++widths;\
675 spans->x = xx;\
676 spans->y = yy;\
677 *widths = 1;\
678 current_y = yy;\
679 new_span = FALSE;\
680 }\
681 }
682
683 void
miZeroLine(pDraw,pGC,mode,npt,pptInit)684 miZeroLine(pDraw, pGC, mode, npt, pptInit)
685 DrawablePtr pDraw;
686 GCPtr pGC;
687 int mode; /* Origin or Previous */
688 int npt; /* number of points */
689 DDXPointPtr pptInit;
690 {
691 int Nspans, current_y;
692 DDXPointPtr ppt;
693 DDXPointPtr pspanInit, spans;
694 int *pwidthInit, *widths, list_len;
695 int xleft, ytop, xright, ybottom;
696 int new_x1, new_y1, new_x2, new_y2;
697 int x, y, x1, y1, x2, y2, xstart, ystart;
698 int oc1, oc2;
699 int result;
700 int pt1_clipped, pt2_clipped = 0;
701 Bool new_span;
702 int signdx, signdy;
703 int clipdx, clipdy;
704 int width, height;
705 int adx, ady;
706 int octant;
707 unsigned int bias = miGetZeroLineBias(pDraw->pScreen);
708 int e, e1, e2, e3; /* Bresenham error terms */
709 int length; /* length of lines == # of pixels on major axis */
710
711 xleft = pDraw->x;
712 ytop = pDraw->y;
713 xright = pDraw->x + pDraw->width - 1;
714 ybottom = pDraw->y + pDraw->height - 1;
715
716 if (!pGC->miTranslate)
717 {
718 /* do everything in drawable-relative coordinates */
719 xleft = 0;
720 ytop = 0;
721 xright -= pDraw->x;
722 ybottom -= pDraw->y;
723 }
724
725 /* it doesn't matter whether we're in drawable or screen coordinates,
726 * FillSpans simply cannot take starting coordinates outside of the
727 * range of a DDXPointRec component.
728 */
729 if (xright > MAX_COORDINATE)
730 xright = MAX_COORDINATE;
731 if (ybottom > MAX_COORDINATE)
732 ybottom = MAX_COORDINATE;
733
734 /* since we're clipping to the drawable's boundaries & coordinate
735 * space boundaries, we're guaranteed that the larger of width/height
736 * is the longest span we'll need to output
737 */
738 width = xright - xleft + 1;
739 height = ybottom - ytop + 1;
740 list_len = (height >= width) ? height : width;
741 pspanInit = (DDXPointPtr)ALLOCATE_LOCAL(list_len * sizeof(DDXPointRec));
742 pwidthInit = (int *)ALLOCATE_LOCAL(list_len * sizeof(int));
743 if (!pspanInit || !pwidthInit)
744 return;
745
746 Nspans = 0;
747 new_span = TRUE;
748 spans = pspanInit - 1;
749 widths = pwidthInit - 1;
750 ppt = pptInit;
751
752 xstart = ppt->x;
753 ystart = ppt->y;
754 if (pGC->miTranslate)
755 {
756 xstart += pDraw->x;
757 ystart += pDraw->y;
758 }
759
760 /* x2, y2, oc2 copied to x1, y1, oc1 at top of loop to simplify
761 * iteration logic
762 */
763 x2 = xstart;
764 y2 = ystart;
765 oc2 = 0;
766 MIOUTCODES(oc2, x2, y2, xleft, ytop, xright, ybottom);
767
768 while (--npt > 0)
769 {
770 if (Nspans > 0)
771 (*pGC->ops->FillSpans)(pDraw, pGC, Nspans, pspanInit,
772 pwidthInit, FALSE);
773 Nspans = 0;
774 new_span = TRUE;
775 spans = pspanInit - 1;
776 widths = pwidthInit - 1;
777
778 x1 = x2;
779 y1 = y2;
780 oc1 = oc2;
781 ++ppt;
782
783 x2 = ppt->x;
784 y2 = ppt->y;
785 if (pGC->miTranslate && (mode != CoordModePrevious))
786 {
787 x2 += pDraw->x;
788 y2 += pDraw->y;
789 }
790 else if (mode == CoordModePrevious)
791 {
792 x2 += x1;
793 y2 += y1;
794 }
795
796 oc2 = 0;
797 MIOUTCODES(oc2, x2, y2, xleft, ytop, xright, ybottom);
798
799 CalcLineDeltas(x1, y1, x2, y2, adx, ady, signdx, signdy, 1, 1, octant);
800
801 if (adx > ady)
802 {
803 e1 = ady << 1;
804 e2 = e1 - (adx << 1);
805 e = e1 - adx;
806 length = adx; /* don't draw endpoint in main loop */
807
808 FIXUP_ERROR(e, octant, bias);
809
810 new_x1 = x1;
811 new_y1 = y1;
812 new_x2 = x2;
813 new_y2 = y2;
814 pt1_clipped = 0;
815 pt2_clipped = 0;
816
817 if ((oc1 | oc2) != 0)
818 {
819 result = miZeroClipLine(xleft, ytop, xright, ybottom,
820 &new_x1, &new_y1, &new_x2, &new_y2,
821 adx, ady,
822 &pt1_clipped, &pt2_clipped,
823 octant, bias, oc1, oc2);
824 if (result == -1)
825 continue;
826
827 length = abs(new_x2 - new_x1);
828
829 /* if we've clipped the endpoint, always draw the full length
830 * of the segment, because then the capstyle doesn't matter
831 */
832 if (pt2_clipped)
833 length++;
834
835 if (pt1_clipped)
836 {
837 /* must calculate new error terms */
838 clipdx = abs(new_x1 - x1);
839 clipdy = abs(new_y1 - y1);
840 e += (clipdy * e2) + ((clipdx - clipdy) * e1);
841 }
842 }
843
844 /* draw the segment */
845
846 x = new_x1;
847 y = new_y1;
848
849 e3 = e2 - e1;
850 e = e - e1;
851
852 while (length--)
853 {
854 MI_OUTPUT_POINT(x, y);
855 e += e1;
856 if (e >= 0)
857 {
858 y += signdy;
859 e += e3;
860 }
861 x += signdx;
862 }
863 }
864 else /* Y major line */
865 {
866 e1 = adx << 1;
867 e2 = e1 - (ady << 1);
868 e = e1 - ady;
869 length = ady; /* don't draw endpoint in main loop */
870
871 SetYMajorOctant(octant);
872 FIXUP_ERROR(e, octant, bias);
873
874 new_x1 = x1;
875 new_y1 = y1;
876 new_x2 = x2;
877 new_y2 = y2;
878 pt1_clipped = 0;
879 pt2_clipped = 0;
880
881 if ((oc1 | oc2) != 0)
882 {
883 result = miZeroClipLine(xleft, ytop, xright, ybottom,
884 &new_x1, &new_y1, &new_x2, &new_y2,
885 adx, ady,
886 &pt1_clipped, &pt2_clipped,
887 octant, bias, oc1, oc2);
888 if (result == -1)
889 continue;
890
891 length = abs(new_y2 - new_y1);
892
893 /* if we've clipped the endpoint, always draw the full length
894 * of the segment, because then the capstyle doesn't matter
895 */
896 if (pt2_clipped)
897 length++;
898
899 if (pt1_clipped)
900 {
901 /* must calculate new error terms */
902 clipdx = abs(new_x1 - x1);
903 clipdy = abs(new_y1 - y1);
904 e += (clipdx * e2) + ((clipdy - clipdx) * e1);
905 }
906 }
907
908 /* draw the segment */
909
910 x = new_x1;
911 y = new_y1;
912
913 e3 = e2 - e1;
914 e = e - e1;
915
916 while (length--)
917 {
918 MI_OUTPUT_POINT(x, y);
919 e += e1;
920 if (e >= 0)
921 {
922 x += signdx;
923 e += e3;
924 }
925 y += signdy;
926 }
927 }
928 }
929
930 /* only do the capnotlast check on the last segment
931 * and only if the endpoint wasn't clipped. And then, if the last
932 * point is the same as the first point, do not draw it, unless the
933 * line is degenerate
934 */
935 if ( (! pt2_clipped) && (pGC->capStyle != CapNotLast) &&
936 (((xstart != x2) || (ystart != y2)) || (ppt == pptInit + 1)))
937 {
938 MI_OUTPUT_POINT(x, y);
939 }
940
941 if (Nspans > 0)
942 (*pGC->ops->FillSpans)(pDraw, pGC, Nspans, pspanInit,
943 pwidthInit, FALSE);
944
945 DEALLOCATE_LOCAL(pwidthInit);
946 DEALLOCATE_LOCAL(pspanInit);
947 }
948
949 void
miZeroDashLine(dst,pgc,mode,nptInit,pptInit)950 miZeroDashLine(dst, pgc, mode, nptInit, pptInit)
951 DrawablePtr dst;
952 GCPtr pgc;
953 int mode;
954 int nptInit; /* number of points in polyline */
955 DDXPointRec *pptInit; /* points in the polyline */
956 {
957 /* XXX kludge until real zero-width dash code is written */
958 pgc->lineWidth = 1;
959 miWideDash (dst, pgc, mode, nptInit, pptInit);
960 pgc->lineWidth = 0;
961 }
962