Commit | Line | Data |
---|---|---|
a09e091a JB |
1 | /* |
2 | ||
3 | Copyright 1987, 1998 The Open Group | |
4 | ||
5 | Permission to use, copy, modify, distribute, and sell this software and its | |
6 | documentation for any purpose is hereby granted without fee, provided that | |
7 | the above copyright notice appear in all copies and that both that | |
8 | copyright notice and this permission notice appear in supporting | |
9 | documentation. | |
10 | ||
11 | The above copyright notice and this permission notice shall be included | |
12 | in all copies or substantial portions of the Software. | |
13 | ||
14 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS | |
15 | OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | |
16 | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. | |
17 | IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR | |
18 | OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, | |
19 | ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR | |
20 | OTHER DEALINGS IN THE SOFTWARE. | |
21 | ||
22 | Except as contained in this notice, the name of The Open Group shall | |
23 | not be used in advertising or otherwise to promote the sale, use or | |
24 | other dealings in this Software without prior written authorization | |
25 | from The Open Group. | |
26 | ||
27 | */ | |
28 | ||
29 | #ifdef HAVE_DIX_CONFIG_H | |
30 | #include <dix-config.h> | |
31 | #endif | |
32 | ||
33 | #ifndef SCANFILLINCLUDED | |
34 | #define SCANFILLINCLUDED | |
35 | /* | |
36 | * scanfill.h | |
37 | * | |
38 | * Written by Brian Kelleher; Jan 1985 | |
39 | * | |
40 | * This file contains a few macros to help track | |
41 | * the edge of a filled object. The object is assumed | |
42 | * to be filled in scanline order, and thus the | |
43 | * algorithm used is an extension of Bresenham's line | |
44 | * drawing algorithm which assumes that y is always the | |
45 | * major axis. | |
46 | * Since these pieces of code are the same for any filled shape, | |
47 | * it is more convenient to gather the library in one | |
48 | * place, but since these pieces of code are also in | |
49 | * the inner loops of output primitives, procedure call | |
50 | * overhead is out of the question. | |
51 | * See the author for a derivation if needed. | |
52 | */ | |
53 | \f | |
54 | /* | |
55 | * In scan converting polygons, we want to choose those pixels | |
56 | * which are inside the polygon. Thus, we add .5 to the starting | |
57 | * x coordinate for both left and right edges. Now we choose the | |
58 | * first pixel which is inside the pgon for the left edge and the | |
59 | * first pixel which is outside the pgon for the right edge. | |
60 | * Draw the left pixel, but not the right. | |
61 | * | |
62 | * How to add .5 to the starting x coordinate: | |
63 | * If the edge is moving to the right, then subtract dy from the | |
64 | * error term from the general form of the algorithm. | |
65 | * If the edge is moving to the left, then add dy to the error term. | |
66 | * | |
67 | * The reason for the difference between edges moving to the left | |
68 | * and edges moving to the right is simple: If an edge is moving | |
69 | * to the right, then we want the algorithm to flip immediately. | |
70 | * If it is moving to the left, then we don't want it to flip until | |
71 | * we traverse an entire pixel. | |
72 | */ | |
73 | #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \ | |
74 | int dx; /* local storage */ \ | |
75 | \ | |
76 | /* \ | |
77 | * if the edge is horizontal, then it is ignored \ | |
78 | * and assumed not to be processed. Otherwise, do this stuff. \ | |
79 | */ \ | |
80 | if ((dy) != 0) { \ | |
81 | xStart = (x1); \ | |
82 | dx = (x2) - xStart; \ | |
83 | if (dx < 0) { \ | |
84 | m = dx / (dy); \ | |
85 | m1 = m - 1; \ | |
86 | incr1 = -2 * dx + 2 * (dy) * m1; \ | |
87 | incr2 = -2 * dx + 2 * (dy) * m; \ | |
88 | d = 2 * m * (dy) - 2 * dx - 2 * (dy); \ | |
89 | } else { \ | |
90 | m = dx / (dy); \ | |
91 | m1 = m + 1; \ | |
92 | incr1 = 2 * dx - 2 * (dy) * m1; \ | |
93 | incr2 = 2 * dx - 2 * (dy) * m; \ | |
94 | d = -2 * m * (dy) + 2 * dx; \ | |
95 | } \ | |
96 | } \ | |
97 | } | |
98 | \f | |
99 | #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \ | |
100 | if (m1 > 0) { \ | |
101 | if (d > 0) { \ | |
102 | minval += m1; \ | |
103 | d += incr1; \ | |
104 | } \ | |
105 | else { \ | |
106 | minval += m; \ | |
107 | d += incr2; \ | |
108 | } \ | |
109 | } else {\ | |
110 | if (d >= 0) { \ | |
111 | minval += m1; \ | |
112 | d += incr1; \ | |
113 | } \ | |
114 | else { \ | |
115 | minval += m; \ | |
116 | d += incr2; \ | |
117 | } \ | |
118 | } \ | |
119 | } | |
120 | \f | |
121 | /* | |
122 | * This structure contains all of the information needed | |
123 | * to run the bresenham algorithm. | |
124 | * The variables may be hardcoded into the declarations | |
125 | * instead of using this structure to make use of | |
126 | * register declarations. | |
127 | */ | |
128 | typedef struct { | |
129 | int minor; /* minor axis */ | |
130 | int d; /* decision variable */ | |
131 | int m, m1; /* slope and slope+1 */ | |
132 | int incr1, incr2; /* error increments */ | |
133 | } BRESINFO; | |
134 | ||
135 | #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \ | |
136 | BRESINITPGON(dmaj, min1, min2, bres.minor, bres.d, \ | |
137 | bres.m, bres.m1, bres.incr1, bres.incr2) | |
138 | ||
139 | #define BRESINCRPGONSTRUCT(bres) \ | |
140 | BRESINCRPGON(bres.d, bres.minor, bres.m, bres.m1, bres.incr1, bres.incr2) | |
141 | ||
142 | #endif |