1
/* $XFree86: xc/programs/Xserver/mi/mizerclip.c,v 1.1 1999/10/13 22:33:13 dawes Exp $ */
2
/***********************************************************
4
Copyright 1987, 1998 The Open Group
8
The above copyright notice and this permission notice shall be included in
9
all copies or substantial portions of the Software.
11
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
12
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
13
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
14
OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
15
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
16
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
18
Except as contained in this notice, the name of The Open Group shall not be
19
used in advertising or otherwise to promote the sale, use or other dealings
20
in this Software without prior written authorization from The Open Group.
23
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
27
Permission to use, copy, modify, and distribute this software and its
28
documentation for any purpose and without fee is hereby granted,
29
provided that the above copyright notice appear in all copies and that
30
both that copyright notice and this permission notice appear in
31
supporting documentation, and that the name of Digital not be
32
used in advertising or publicity pertaining to distribution of the
33
software without specific, written prior permission.
35
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
36
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
37
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
38
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
39
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
40
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
43
******************************************************************/
51
The bresenham error equation used in the mi/mfb/cfb line routines is:
54
dx = difference in raw X coordinates
55
dy = difference in raw Y coordinates
56
M = # of steps in X direction
57
N = # of steps in Y direction
58
B = 0 to prefer diagonal steps in a given octant,
59
1 to prefer axial steps in a given octant
62
e = 2Mdy - 2Ndx - dx - B
66
e = 2Ndx - 2Mdy - dy - B
69
At the start of the line, we have taken 0 X steps and 0 Y steps,
72
X major e = 2Mdy - 2Ndx - dx - B
75
Y major e = 2Ndx - 2Mdy - dy - B
78
At the end of the line, we have taken dx X steps and dy Y steps,
81
X major e = 2Mdy - 2Ndx - dx - B
82
= 2dxdy - 2dydx - dx - B
84
Y major e = 2Ndx - 2Mdy - dy - B
85
= 2dydx - 2dxdy - dy - B
88
Thus, the error term is the same at the start and end of the line.
90
Let us consider clipping an X coordinate. There are 4 cases which
91
represent the two independent cases of clipping the start vs. the
92
end of the line and an X major vs. a Y major line. In any of these
93
cases, we know the number of X steps (M) and we wish to find the
94
number of Y steps (N). Thus, we will solve our error term equation.
95
If we are clipping the start of the line, we will find the smallest
96
N that satisfies our error term inequality. If we are clipping the
97
end of the line, we will find the largest number of Y steps that
98
satisfies the inequality. In that case, since we are representing
99
the Y steps as (dy - N), we will actually want to solve for the
100
smallest N in that equation.
102
Case 1: X major, starting X coordinate moved by M steps
104
-2dx <= 2Mdy - 2Ndx - dx - B < 0
105
2Ndx <= 2Mdy - dx - B + 2dx 2Ndx > 2Mdy - dx - B
106
2Ndx <= 2Mdy + dx - B N > (2Mdy - dx - B) / 2dx
107
N <= (2Mdy + dx - B) / 2dx
109
Since we are trying to find the smallest N that satisfies these
110
equations, we should use the > inequality to find the smallest:
112
N = floor((2Mdy - dx - B) / 2dx) + 1
113
= floor((2Mdy - dx - B + 2dx) / 2dx)
114
= floor((2Mdy + dx - B) / 2dx)
116
Case 1b: X major, ending X coordinate moved to M steps
118
Same derivations as Case 1, but we want the largest N that satisfies
119
the equations, so we use the <= inequality:
121
N = floor((2Mdy + dx - B) / 2dx)
123
Case 2: X major, ending X coordinate moved by M steps
125
-2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
126
-2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
127
-2dx <= 2Ndx - 2Mdy - dx - B < 0
128
2Ndx >= 2Mdy + dx + B - 2dx 2Ndx < 2Mdy + dx + B
129
2Ndx >= 2Mdy - dx + B N < (2Mdy + dx + B) / 2dx
130
N >= (2Mdy - dx + B) / 2dx
132
Since we are trying to find the highest number of Y steps that
133
satisfies these equations, we need to find the smallest N, so
134
we should use the >= inequality to find the smallest:
136
N = ceiling((2Mdy - dx + B) / 2dx)
137
= floor((2Mdy - dx + B + 2dx - 1) / 2dx)
138
= floor((2Mdy + dx + B - 1) / 2dx)
140
Case 2b: X major, starting X coordinate moved to M steps from end
142
Same derivations as Case 2, but we want the smallest number of Y
143
steps, so we want the highest N, so we use the < inequality:
145
N = ceiling((2Mdy + dx + B) / 2dx) - 1
146
= floor((2Mdy + dx + B + 2dx - 1) / 2dx) - 1
147
= floor((2Mdy + dx + B + 2dx - 1 - 2dx) / 2dx)
148
= floor((2Mdy + dx + B - 1) / 2dx)
150
Case 3: Y major, starting X coordinate moved by M steps
152
-2dy <= 2Ndx - 2Mdy - dy - B < 0
153
2Ndx >= 2Mdy + dy + B - 2dy 2Ndx < 2Mdy + dy + B
154
2Ndx >= 2Mdy - dy + B N < (2Mdy + dy + B) / 2dx
155
N >= (2Mdy - dy + B) / 2dx
157
Since we are trying to find the smallest N that satisfies these
158
equations, we should use the >= inequality to find the smallest:
160
N = ceiling((2Mdy - dy + B) / 2dx)
161
= floor((2Mdy - dy + B + 2dx - 1) / 2dx)
162
= floor((2Mdy - dy + B - 1) / 2dx) + 1
164
Case 3b: Y major, ending X coordinate moved to M steps
166
Same derivations as Case 3, but we want the largest N that satisfies
167
the equations, so we use the < inequality:
169
N = ceiling((2Mdy + dy + B) / 2dx) - 1
170
= floor((2Mdy + dy + B + 2dx - 1) / 2dx) - 1
171
= floor((2Mdy + dy + B + 2dx - 1 - 2dx) / 2dx)
172
= floor((2Mdy + dy + B - 1) / 2dx)
174
Case 4: Y major, ending X coordinate moved by M steps
176
-2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
177
-2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
178
-2dy <= 2Mdy - 2Ndx - dy - B < 0
179
2Ndx <= 2Mdy - dy - B + 2dy 2Ndx > 2Mdy - dy - B
180
2Ndx <= 2Mdy + dy - B N > (2Mdy - dy - B) / 2dx
181
N <= (2Mdy + dy - B) / 2dx
183
Since we are trying to find the highest number of Y steps that
184
satisfies these equations, we need to find the smallest N, so
185
we should use the > inequality to find the smallest:
187
N = floor((2Mdy - dy - B) / 2dx) + 1
189
Case 4b: Y major, starting X coordinate moved to M steps from end
191
Same analysis as Case 4, but we want the smallest number of Y steps
192
which means the largest N, so we use the <= inequality:
194
N = floor((2Mdy + dy - B) / 2dx)
196
Now let's try the Y coordinates, we have the same 4 cases.
198
Case 5: X major, starting Y coordinate moved by N steps
200
-2dx <= 2Mdy - 2Ndx - dx - B < 0
201
2Mdy >= 2Ndx + dx + B - 2dx 2Mdy < 2Ndx + dx + B
202
2Mdy >= 2Ndx - dx + B M < (2Ndx + dx + B) / 2dy
203
M >= (2Ndx - dx + B) / 2dy
205
Since we are trying to find the smallest M, we use the >= inequality:
207
M = ceiling((2Ndx - dx + B) / 2dy)
208
= floor((2Ndx - dx + B + 2dy - 1) / 2dy)
209
= floor((2Ndx - dx + B - 1) / 2dy) + 1
211
Case 5b: X major, ending Y coordinate moved to N steps
213
Same derivations as Case 5, but we want the largest M that satisfies
214
the equations, so we use the < inequality:
216
M = ceiling((2Ndx + dx + B) / 2dy) - 1
217
= floor((2Ndx + dx + B + 2dy - 1) / 2dy) - 1
218
= floor((2Ndx + dx + B + 2dy - 1 - 2dy) / 2dy)
219
= floor((2Ndx + dx + B - 1) / 2dy)
221
Case 6: X major, ending Y coordinate moved by N steps
223
-2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
224
-2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
225
-2dx <= 2Ndx - 2Mdy - dx - B < 0
226
2Mdy <= 2Ndx - dx - B + 2dx 2Mdy > 2Ndx - dx - B
227
2Mdy <= 2Ndx + dx - B M > (2Ndx - dx - B) / 2dy
228
M <= (2Ndx + dx - B) / 2dy
230
Largest # of X steps means smallest M, so use the > inequality:
232
M = floor((2Ndx - dx - B) / 2dy) + 1
234
Case 6b: X major, starting Y coordinate moved to N steps from end
236
Same derivations as Case 6, but we want the smallest # of X steps
237
which means the largest M, so use the <= inequality:
239
M = floor((2Ndx + dx - B) / 2dy)
241
Case 7: Y major, starting Y coordinate moved by N steps
243
-2dy <= 2Ndx - 2Mdy - dy - B < 0
244
2Mdy <= 2Ndx - dy - B + 2dy 2Mdy > 2Ndx - dy - B
245
2Mdy <= 2Ndx + dy - B M > (2Ndx - dy - B) / 2dy
246
M <= (2Ndx + dy - B) / 2dy
248
To find the smallest M, use the > inequality:
250
M = floor((2Ndx - dy - B) / 2dy) + 1
251
= floor((2Ndx - dy - B + 2dy) / 2dy)
252
= floor((2Ndx + dy - B) / 2dy)
254
Case 7b: Y major, ending Y coordinate moved to N steps
256
Same derivations as Case 7, but we want the largest M that satisfies
257
the equations, so use the <= inequality:
259
M = floor((2Ndx + dy - B) / 2dy)
261
Case 8: Y major, ending Y coordinate moved by N steps
263
-2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
264
-2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
265
-2dy <= 2Mdy - 2Ndx - dy - B < 0
266
2Mdy >= 2Ndx + dy + B - 2dy 2Mdy < 2Ndx + dy + B
267
2Mdy >= 2Ndx - dy + B M < (2Ndx + dy + B) / 2dy
268
M >= (2Ndx - dy + B) / 2dy
270
To find the highest X steps, find the smallest M, use the >= inequality:
272
M = ceiling((2Ndx - dy + B) / 2dy)
273
= floor((2Ndx - dy + B + 2dy - 1) / 2dy)
274
= floor((2Ndx + dy + B - 1) / 2dy)
276
Case 8b: Y major, starting Y coordinate moved to N steps from the end
278
Same derivations as Case 8, but we want to find the smallest # of X
279
steps which means the largest M, so we use the < inequality:
281
M = ceiling((2Ndx + dy + B) / 2dy) - 1
282
= floor((2Ndx + dy + B + 2dy - 1) / 2dy) - 1
283
= floor((2Ndx + dy + B + 2dy - 1 - 2dy) / 2dy)
284
= floor((2Ndx + dy + B - 1) / 2dy)
286
So, our equations are:
288
1: X major move x1 to x1+M floor((2Mdy + dx - B) / 2dx)
289
1b: X major move x2 to x1+M floor((2Mdy + dx - B) / 2dx)
290
2: X major move x2 to x2-M floor((2Mdy + dx + B - 1) / 2dx)
291
2b: X major move x1 to x2-M floor((2Mdy + dx + B - 1) / 2dx)
293
3: Y major move x1 to x1+M floor((2Mdy - dy + B - 1) / 2dx) + 1
294
3b: Y major move x2 to x1+M floor((2Mdy + dy + B - 1) / 2dx)
295
4: Y major move x2 to x2-M floor((2Mdy - dy - B) / 2dx) + 1
296
4b: Y major move x1 to x2-M floor((2Mdy + dy - B) / 2dx)
298
5: X major move y1 to y1+N floor((2Ndx - dx + B - 1) / 2dy) + 1
299
5b: X major move y2 to y1+N floor((2Ndx + dx + B - 1) / 2dy)
300
6: X major move y2 to y2-N floor((2Ndx - dx - B) / 2dy) + 1
301
6b: X major move y1 to y2-N floor((2Ndx + dx - B) / 2dy)
303
7: Y major move y1 to y1+N floor((2Ndx + dy - B) / 2dy)
304
7b: Y major move y2 to y1+N floor((2Ndx + dy - B) / 2dy)
305
8: Y major move y2 to y2-N floor((2Ndx + dy + B - 1) / 2dy)
306
8b: Y major move y1 to y2-N floor((2Ndx + dy + B - 1) / 2dy)
308
We have the following constraints on all of the above terms:
310
0 < M,N <= 2^15 2^15 can be imposed by miZeroClipLine
311
0 <= dx/dy <= 2^16 - 1
314
The floor in all of the above equations can be accomplished with a
315
simple C divide operation provided that both numerator and denominator
318
Since dx,dy >= 0 and since moving an X coordinate implies that dx != 0
319
and moving a Y coordinate implies dy != 0, we know that the denominators
322
For all lines, (-B) and (B-1) are both either 0 or -1, depending on the
323
bias. Thus, we have to show that the 2MNdxy +/- dxy terms are all >= 1
324
or > 0 to prove that the numerators are positive (or zero).
326
For X Major lines we know that dx > 0 and since 2Mdy is >= 0 due to the
327
constraints, the first four equations all have numerators >= 0.
329
For the second four equations, M > 0, so 2Mdy >= 2dy so (2Mdy - dy) >= dy
330
So (2Mdy - dy) > 0, since they are Y major lines. Also, (2Mdy + dy) >= 3dy
331
or (2Mdy + dy) > 0. So all of their numerators are >= 0.
333
For the third set of four equations, N > 0, so 2Ndx >= 2dx so (2Ndx - dx)
334
>= dx > 0. Similarly (2Ndx + dx) >= 3dx > 0. So all numerators >= 0.
336
For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators
339
To consider overflow, consider the case of 2 * M,N * dx,dy + dx,dy. This
340
is bounded <= 2 * 2^15 * (2^16 - 1) + (2^16 - 1)
341
<= 2^16 * (2^16 - 1) + (2^16 - 1)
342
<= 2^32 - 2^16 + 2^16 - 1
344
Since the (-B) and (B-1) terms are all 0 or -1, the maximum value of
345
the numerator is therefore (2^32 - 1), which does not overflow an unsigned
350
/* Bit codes for the terms of the 16 clipping equations defined below. */
352
#define T_2NDX (1 << 0)
353
#define T_2MDY (0) /* implicit term */
354
#define T_DXNOTY (1 << 1)
355
#define T_DYNOTX (0) /* implicit term */
356
#define T_SUBDXORY (1 << 2)
357
#define T_ADDDX (T_DXNOTY) /* composite term */
358
#define T_SUBDX (T_DXNOTY | T_SUBDXORY) /* composite term */
359
#define T_ADDDY (T_DYNOTX) /* composite term */
360
#define T_SUBDY (T_DYNOTX | T_SUBDXORY) /* composite term */
361
#define T_BIASSUBONE (1 << 3)
362
#define T_SUBBIAS (0) /* implicit term */
363
#define T_DIV2DX (1 << 4)
364
#define T_DIV2DY (0) /* implicit term */
365
#define T_ADDONE (1 << 5)
367
/* Bit masks defining the 16 equations used in miZeroClipLine. */
369
#define EQN1 (T_2MDY | T_ADDDX | T_SUBBIAS | T_DIV2DX)
370
#define EQN1B (T_2MDY | T_ADDDX | T_SUBBIAS | T_DIV2DX)
371
#define EQN2 (T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX)
372
#define EQN2B (T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX)
374
#define EQN3 (T_2MDY | T_SUBDY | T_BIASSUBONE | T_DIV2DX | T_ADDONE)
375
#define EQN3B (T_2MDY | T_ADDDY | T_BIASSUBONE | T_DIV2DX)
376
#define EQN4 (T_2MDY | T_SUBDY | T_SUBBIAS | T_DIV2DX | T_ADDONE)
377
#define EQN4B (T_2MDY | T_ADDDY | T_SUBBIAS | T_DIV2DX)
379
#define EQN5 (T_2NDX | T_SUBDX | T_BIASSUBONE | T_DIV2DY | T_ADDONE)
380
#define EQN5B (T_2NDX | T_ADDDX | T_BIASSUBONE | T_DIV2DY)
381
#define EQN6 (T_2NDX | T_SUBDX | T_SUBBIAS | T_DIV2DY | T_ADDONE)
382
#define EQN6B (T_2NDX | T_ADDDX | T_SUBBIAS | T_DIV2DY)
384
#define EQN7 (T_2NDX | T_ADDDY | T_SUBBIAS | T_DIV2DY)
385
#define EQN7B (T_2NDX | T_ADDDY | T_SUBBIAS | T_DIV2DY)
386
#define EQN8 (T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY)
387
#define EQN8B (T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY)
391
* returns: 1 for partially clipped line
392
* -1 for completely clipped line
396
miZeroClipLine(int xmin, int ymin, int xmax, int ymax,
397
int *new_x1, int *new_y1, int *new_x2, int *new_y2,
398
unsigned int adx, unsigned int ady,
399
int *pt1_clipped, int *pt2_clipped, int octant,
400
unsigned int bias, int oc1, int oc2)
407
int x1_orig, y1_orig, x2_orig, y2_orig;
409
int negslope = 0, anchorval = 0;
410
unsigned int eqn = 0;
412
x1 = x1_orig = *new_x1;
413
y1 = y1_orig = *new_y1;
414
x2 = x2_orig = *new_x2;
415
y2 = y2_orig = *new_y2;
420
xmajor = IsXMajorOctant(octant);
421
bias = ((bias >> octant) & 1);
425
if ((oc1 & oc2) != 0) /* trivial reject */
432
else if ((oc1 | oc2) == 0) /* trivial accept */
437
SWAPINT_PAIR(x1, y1, x2, y2);
438
SWAPINT(clip1, clip2);
442
else /* have to clip */
444
/* only clip one point at a time */
447
SWAPINT_PAIR(x1, y1, x2, y2);
448
SWAPINT_PAIR(x1_orig, y1_orig, x2_orig, y2_orig);
450
SWAPINT(clip1, clip2);
457
negslope = IsYDecreasingOctant(octant);
458
utmp = xmin - x1_orig;
459
if (utmp <= 32767) /* clip based on near endpt */
462
eqn = (swapped) ? EQN2 : EQN1;
464
eqn = (swapped) ? EQN4 : EQN3;
467
else /* clip based on far endpt */
469
utmp = x2_orig - xmin;
471
eqn = (swapped) ? EQN1B : EQN2B;
473
eqn = (swapped) ? EQN3B : EQN4B;
475
negslope = !negslope;
479
else if (oc1 & OUT_ABOVE)
481
negslope = IsXDecreasingOctant(octant);
482
utmp = ymin - y1_orig;
483
if (utmp <= 32767) /* clip based on near endpt */
486
eqn = (swapped) ? EQN6 : EQN5;
488
eqn = (swapped) ? EQN8 : EQN7;
491
else /* clip based on far endpt */
493
utmp = y2_orig - ymin;
495
eqn = (swapped) ? EQN5B : EQN6B;
497
eqn = (swapped) ? EQN7B : EQN8B;
499
negslope = !negslope;
503
else if (oc1 & OUT_RIGHT)
505
negslope = IsYDecreasingOctant(octant);
506
utmp = x1_orig - xmax;
507
if (utmp <= 32767) /* clip based on near endpt */
510
eqn = (swapped) ? EQN2 : EQN1;
512
eqn = (swapped) ? EQN4 : EQN3;
515
else /* clip based on far endpt */
518
* Technically since the equations can handle
519
* utmp == 32768, this overflow code isn't
520
* needed since X11 protocol can't generate
521
* a line which goes more than 32768 pixels
522
* to the right of a clip rectangle.
524
utmp = xmax - x2_orig;
526
eqn = (swapped) ? EQN1B : EQN2B;
528
eqn = (swapped) ? EQN3B : EQN4B;
530
negslope = !negslope;
534
else if (oc1 & OUT_BELOW)
536
negslope = IsXDecreasingOctant(octant);
537
utmp = y1_orig - ymax;
538
if (utmp <= 32767) /* clip based on near endpt */
541
eqn = (swapped) ? EQN6 : EQN5;
543
eqn = (swapped) ? EQN8 : EQN7;
546
else /* clip based on far endpt */
549
* Technically since the equations can handle
550
* utmp == 32768, this overflow code isn't
551
* needed since X11 protocol can't generate
552
* a line which goes more than 32768 pixels
553
* below the bottom of a clip rectangle.
555
utmp = ymax - y2_orig;
557
eqn = (swapped) ? EQN5B : EQN6B;
559
eqn = (swapped) ? EQN7B : EQN8B;
561
negslope = !negslope;
567
negslope = !negslope;
569
utmp <<= 1; /* utmp = 2N or 2M */
572
else /* (eqn & T_2MDY) */
575
if (eqn & T_SUBDXORY)
579
else /* (eqn & T_DYNOTX) */
580
if (eqn & T_SUBDXORY)
584
if (eqn & T_BIASSUBONE)
586
else /* (eqn & T_SUBBIAS) */
590
else /* (eqn & T_DIV2DY) */
598
if (eqn & T_2NDX) /* We are calculating X steps */
599
x1 = anchorval + utmp;
600
else /* else, Y steps */
601
y1 = anchorval + utmp;
604
MIOUTCODES(oc1, x1, y1, xmin, ymin, xmax, ymax);
613
*pt1_clipped = clip1;
614
*pt2_clipped = clip2;
added
removed
gdk/linux-fb/mizerclip.c
