1 /***********************************************************
3 Copyright (c) 1987 X Consortium
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:
12 The above copyright notice and this permission notice shall be included in
13 all copies or substantial portions of the Software.
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.
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.
27 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
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.
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
47 ******************************************************************/
48 /* $XConsortium: mizerline.c,v 5.9 94/08/02 15:01:29 dpw Exp $ */
52 #include "scrnintstr.h"
54 #include "windowstr.h"
61 The bresenham error equation used in the mi/mfb/cfb line routines is:
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
72 e = 2Mdy - 2Ndx - dx - B
76 e = 2Ndx - 2Mdy - dy - B
79 At the start of the line, we have taken 0 X steps and 0 Y steps,
82 X major e = 2Mdy - 2Ndx - dx - B
85 Y major e = 2Ndx - 2Mdy - dy - B
88 At the end of the line, we have taken dx X steps and dy Y steps,
91 X major e = 2Mdy - 2Ndx - dx - B
92 = 2dxdy - 2dydx - dx - B
94 Y major e = 2Ndx - 2Mdy - dy - B
95 = 2dydx - 2dxdy - dy - B
98 Thus, the error term is the same at the start and end of the line.
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.
112 Case 1: X major, starting X coordinate moved by M steps
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
119 Since we are trying to find the smallest N that satisfies these
120 equations, we should use the > inequality to find the smallest:
122 N = floor((2Mdy - dx - B) / 2dx) + 1
123 = floor((2Mdy - dx - B + 2dx) / 2dx)
124 = floor((2Mdy + dx - B) / 2dx)
126 Case 1b: X major, ending X coordinate moved to M steps
128 Same derivations as Case 1, but we want the largest N that satisfies
129 the equations, so we use the <= inequality:
131 N = floor((2Mdy + dx - B) / 2dx)
133 Case 2: X major, ending X coordinate moved by M steps
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
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:
146 N = ceiling((2Mdy - dx + B) / 2dx)
147 = floor((2Mdy - dx + B + 2dx - 1) / 2dx)
148 = floor((2Mdy + dx + B - 1) / 2dx)
150 Case 2b: X major, starting X coordinate moved to M steps from end
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:
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)
160 Case 3: Y major, starting X coordinate moved by M steps
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
167 Since we are trying to find the smallest N that satisfies these
168 equations, we should use the >= inequality to find the smallest:
170 N = ceiling((2Mdy - dy + B) / 2dx)
171 = floor((2Mdy - dy + B + 2dx - 1) / 2dx)
172 = floor((2Mdy - dy + B - 1) / 2dx) + 1
174 Case 3b: Y major, ending X coordinate moved to M steps
176 Same derivations as Case 3, but we want the largest N that satisfies
177 the equations, so we use the < inequality:
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)
184 Case 4: Y major, ending X coordinate moved by M steps
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
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:
197 N = floor((2Mdy - dy - B) / 2dx) + 1
199 Case 4b: Y major, starting X coordinate moved to M steps from end
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:
204 N = floor((2Mdy + dy - B) / 2dx)
206 Now let's try the Y coordinates, we have the same 4 cases.
208 Case 5: X major, starting Y coordinate moved by N steps
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
215 Since we are trying to find the smallest M, we use the >= inequality:
217 M = ceiling((2Ndx - dx + B) / 2dy)
218 = floor((2Ndx - dx + B + 2dy - 1) / 2dy)
219 = floor((2Ndx - dx + B - 1) / 2dy) + 1
221 Case 5b: X major, ending Y coordinate moved to N steps
223 Same derivations as Case 5, but we want the largest M that satisfies
224 the equations, so we use the < inequality:
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)
231 Case 6: X major, ending Y coordinate moved by N steps
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
240 Largest # of X steps means smallest M, so use the > inequality:
242 M = floor((2Ndx - dx - B) / 2dy) + 1
244 Case 6b: X major, starting Y coordinate moved to N steps from end
246 Same derivations as Case 6, but we want the smallest # of X steps
247 which means the largest M, so use the <= inequality:
249 M = floor((2Ndx + dx - B) / 2dy)
251 Case 7: Y major, starting Y coordinate moved by N steps
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
258 To find the smallest M, use the > inequality:
260 M = floor((2Ndx - dy - B) / 2dy) + 1
261 = floor((2Ndx - dy - B + 2dy) / 2dy)
262 = floor((2Ndx + dy - B) / 2dy)
264 Case 7b: Y major, ending Y coordinate moved to N steps
266 Same derivations as Case 7, but we want the largest M that satisfies
267 the equations, so use the <= inequality:
269 M = floor((2Ndx + dy - B) / 2dy)
271 Case 8: Y major, ending Y coordinate moved by N steps
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
280 To find the highest X steps, find the smallest M, use the >= inequality:
282 M = ceiling((2Ndx - dy + B) / 2dy)
283 = floor((2Ndx - dy + B + 2dy - 1) / 2dy)
284 = floor((2Ndx + dy + B - 1) / 2dy)
286 Case 8b: Y major, starting Y coordinate moved to N steps from the end
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:
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)
296 So, our equations are:
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)
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)
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)
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)
318 We have the following constraints on all of the above terms:
320 0 < M,N <= 2^15 2^15 can be imposed by miZeroClipLine
321 0 <= dx/dy <= 2^16 - 1
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
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
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).
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.
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.
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.
346 For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators
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
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
360 #define MIOUTCODES(outcode, x, y, xmin, ymin, xmax, ymax) \
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;\
368 /* Bit codes for the terms of the 16 clipping equations defined below. */
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)
385 /* Bit masks defining the 16 equations used in miZeroClipLine. */
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)
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)
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)
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)
409 * returns: 1 for partially clipped line
410 * -1 for completely clipped line
414 miZeroClipLine(xmin, ymin, xmax, ymax,
415 new_x1, new_y1, new_x2, new_y2,
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;
431 int x1_orig, y1_orig, x2_orig, y2_orig;
433 int negslope, anchorval;
436 x1 = x1_orig = *new_x1;
437 y1 = y1_orig = *new_y1;
438 x2 = x2_orig = *new_x2;
439 y2 = y2_orig = *new_y2;
444 xmajor = IsXMajorOctant(octant);
445 bias = ((bias >> octant) & 1);
449 if ((oc1 & oc2) != 0) /* trivial reject */
456 else if ((oc1 | oc2) == 0) /* trivial accept */
461 SWAPINT_PAIR(x1, y1, x2, y2);
462 SWAPINT(clip1, clip2);
466 else /* have to clip */
468 /* only clip one point at a time */
471 SWAPINT_PAIR(x1, y1, x2, y2);
472 SWAPINT_PAIR(x1_orig, y1_orig, x2_orig, y2_orig);
474 SWAPINT(clip1, clip2);
481 negslope = IsYDecreasingOctant(octant);
482 utmp = xmin - x1_orig;
483 if (utmp <= 32767) /* clip based on near endpt */
486 eqn = (swapped) ? EQN2 : EQN1;
488 eqn = (swapped) ? EQN4 : EQN3;
491 else /* clip based on far endpt */
493 utmp = x2_orig - xmin;
495 eqn = (swapped) ? EQN1B : EQN2B;
497 eqn = (swapped) ? EQN3B : EQN4B;
499 negslope = !negslope;
503 else if (oc1 & OUT_ABOVE)
505 negslope = IsXDecreasingOctant(octant);
506 utmp = ymin - y1_orig;
507 if (utmp <= 32767) /* clip based on near endpt */
510 eqn = (swapped) ? EQN6 : EQN5;
512 eqn = (swapped) ? EQN8 : EQN7;
515 else /* clip based on far endpt */
517 utmp = y2_orig - ymin;
519 eqn = (swapped) ? EQN5B : EQN6B;
521 eqn = (swapped) ? EQN7B : EQN8B;
523 negslope = !negslope;
527 else if (oc1 & OUT_RIGHT)
529 negslope = IsYDecreasingOctant(octant);
530 utmp = x1_orig - xmax;
531 if (utmp <= 32767) /* clip based on near endpt */
534 eqn = (swapped) ? EQN2 : EQN1;
536 eqn = (swapped) ? EQN4 : EQN3;
539 else /* clip based on far endpt */
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.
548 utmp = xmax - x2_orig;
550 eqn = (swapped) ? EQN1B : EQN2B;
552 eqn = (swapped) ? EQN3B : EQN4B;
554 negslope = !negslope;
558 else if (oc1 & OUT_BELOW)
560 negslope = IsXDecreasingOctant(octant);
561 utmp = y1_orig - ymax;
562 if (utmp <= 32767) /* clip based on near endpt */
565 eqn = (swapped) ? EQN6 : EQN5;
567 eqn = (swapped) ? EQN8 : EQN7;
570 else /* clip based on far endpt */
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.
579 utmp = ymax - y2_orig;
581 eqn = (swapped) ? EQN5B : EQN6B;
583 eqn = (swapped) ? EQN7B : EQN8B;
585 negslope = !negslope;
591 negslope = !negslope;
593 utmp <<= 1; /* utmp = 2N or 2M */
596 else /* (eqn & T_2MDY) */
599 if (eqn & T_SUBDXORY)
603 else /* (eqn & T_DYNOTX) */
604 if (eqn & T_SUBDXORY)
608 if (eqn & T_BIASSUBONE)
610 else /* (eqn & T_SUBBIAS) */
614 else /* (eqn & T_DIV2DY) */
622 if (eqn & T_2NDX) /* We are calculating X steps */
623 x1 = anchorval + utmp;
624 else /* else, Y steps */
625 y1 = anchorval + utmp;
628 MIOUTCODES(oc1, x1, y1, xmin, ymin, xmax, ymax);
637 *pt1_clipped = clip1;
638 *pt2_clipped = clip2;
644 /* Draw lineSolid, fillStyle-independent zero width lines.
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
650 * Draws the same pixels regardless of sign(dx) or sign(dy).
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
660 #define MAX_COORDINATE ((1 << (((sizeof(DDXPointRec) >> 1) << 3) - 1)) - 1)
662 #define MI_OUTPUT_POINT(xx, yy)\
664 if ( !new_span && yy == current_y)\
684 miZeroLine(pDraw, pGC, mode, npt, pptInit)
687 int mode; /* Origin or Previous */
688 int npt; /* number of points */
691 int Nspans, current_y;
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;
700 int pt1_clipped, pt2_clipped = 0;
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 */
713 xright = pDraw->x + pDraw->width - 1;
714 ybottom = pDraw->y + pDraw->height - 1;
716 if (!pGC->miTranslate)
718 /* do everything in drawable-relative coordinates */
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.
729 if (xright > MAX_COORDINATE)
730 xright = MAX_COORDINATE;
731 if (ybottom > MAX_COORDINATE)
732 ybottom = MAX_COORDINATE;
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
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)
748 spans = pspanInit - 1;
749 widths = pwidthInit - 1;
754 if (pGC->miTranslate)
760 /* x2, y2, oc2 copied to x1, y1, oc1 at top of loop to simplify
766 MIOUTCODES(oc2, x2, y2, xleft, ytop, xright, ybottom);
771 (*pGC->ops->FillSpans)(pDraw, pGC, Nspans, pspanInit,
775 spans = pspanInit - 1;
776 widths = pwidthInit - 1;
785 if (pGC->miTranslate && (mode != CoordModePrevious))
790 else if (mode == CoordModePrevious)
797 MIOUTCODES(oc2, x2, y2, xleft, ytop, xright, ybottom);
799 CalcLineDeltas(x1, y1, x2, y2, adx, ady, signdx, signdy, 1, 1, octant);
804 e2 = e1 - (adx << 1);
806 length = adx; /* don't draw endpoint in main loop */
808 FIXUP_ERROR(e, octant, bias);
817 if ((oc1 | oc2) != 0)
819 result = miZeroClipLine(xleft, ytop, xright, ybottom,
820 &new_x1, &new_y1, &new_x2, &new_y2,
822 &pt1_clipped, &pt2_clipped,
823 octant, bias, oc1, oc2);
827 length = abs(new_x2 - new_x1);
829 /* if we've clipped the endpoint, always draw the full length
830 * of the segment, because then the capstyle doesn't matter
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);
844 /* draw the segment */
854 MI_OUTPUT_POINT(x, y);
864 else /* Y major line */
867 e2 = e1 - (ady << 1);
869 length = ady; /* don't draw endpoint in main loop */
871 SetYMajorOctant(octant);
872 FIXUP_ERROR(e, octant, bias);
881 if ((oc1 | oc2) != 0)
883 result = miZeroClipLine(xleft, ytop, xright, ybottom,
884 &new_x1, &new_y1, &new_x2, &new_y2,
886 &pt1_clipped, &pt2_clipped,
887 octant, bias, oc1, oc2);
891 length = abs(new_y2 - new_y1);
893 /* if we've clipped the endpoint, always draw the full length
894 * of the segment, because then the capstyle doesn't matter
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);
908 /* draw the segment */
918 MI_OUTPUT_POINT(x, y);
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
935 if ( (! pt2_clipped) && (pGC->capStyle != CapNotLast) &&
936 (((xstart != x2) || (ystart != y2)) || (ppt == pptInit + 1)))
938 MI_OUTPUT_POINT(x, y);
942 (*pGC->ops->FillSpans)(pDraw, pGC, Nspans, pspanInit,
945 DEALLOCATE_LOCAL(pwidthInit);
946 DEALLOCATE_LOCAL(pspanInit);
950 miZeroDashLine(dst, pgc, mode, nptInit, pptInit)
954 int nptInit; /* number of points in polyline */
955 DDXPointRec *pptInit; /* points in the polyline */
957 /* XXX kludge until real zero-width dash code is written */
959 miWideDash (dst, pgc, mode, nptInit, pptInit);