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 in | |
12 | all copies or substantial portions of the Software. | |
13 | ||
14 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
15 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
16 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
17 | OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN | |
18 | AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | |
19 | CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |
20 | ||
21 | Except as contained in this notice, the name of The Open Group shall not be | |
22 | used in advertising or otherwise to promote the sale, use or other dealings | |
23 | in this Software without prior written authorization from The Open Group. | |
24 | ||
25 | Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. | |
26 | ||
27 | All Rights Reserved | |
28 | ||
29 | Permission to use, copy, modify, and distribute this software and its | |
30 | documentation for any purpose and without fee is hereby granted, | |
31 | provided that the above copyright notice appear in all copies and that | |
32 | both that copyright notice and this permission notice appear in | |
33 | supporting documentation, and that the name of Digital not be | |
34 | used in advertising or publicity pertaining to distribution of the | |
35 | software without specific, written prior permission. | |
36 | ||
37 | DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING | |
38 | ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL | |
39 | DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR | |
40 | ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, | |
41 | WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, | |
42 | ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS | |
43 | SOFTWARE. | |
44 | ||
45 | ******************************************************************/ | |
46 | ||
47 | #ifdef HAVE_DIX_CONFIG_H | |
48 | #include <dix-config.h> | |
49 | #endif | |
50 | ||
51 | #include "gcstruct.h" | |
52 | #include "pixmap.h" | |
53 | #include "mi.h" | |
54 | #include "miscanfill.h" | |
55 | ||
56 | static int getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty); | |
57 | ||
58 | /* | |
59 | * convexpoly.c | |
60 | * | |
61 | * Written by Brian Kelleher; Dec. 1985. | |
62 | * | |
63 | * Fill a convex polygon. If the given polygon | |
64 | * is not convex, then the result is undefined. | |
65 | * The algorithm is to order the edges from smallest | |
66 | * y to largest by partitioning the array into a left | |
67 | * edge list and a right edge list. The algorithm used | |
68 | * to traverse each edge is an extension of Bresenham's | |
69 | * line algorithm with y as the major axis. | |
70 | * For a derivation of the algorithm, see the author of | |
71 | * this code. | |
72 | */ | |
73 | Bool | |
74 | miFillConvexPoly(DrawablePtr dst, GCPtr pgc, int count, /* number of points */ | |
75 | DDXPointPtr ptsIn /* the points */ | |
76 | ) | |
77 | { | |
78 | int xl = 0, xr = 0; /* x vals of left and right edges */ | |
79 | int dl = 0, dr = 0; /* decision variables */ | |
80 | int ml = 0, m1l = 0; /* left edge slope and slope+1 */ | |
81 | int mr = 0, m1r = 0; /* right edge slope and slope+1 */ | |
82 | int incr1l = 0, incr2l = 0; /* left edge error increments */ | |
83 | int incr1r = 0, incr2r = 0; /* right edge error increments */ | |
84 | int dy; /* delta y */ | |
85 | int y; /* current scanline */ | |
86 | int left, right; /* indices to first endpoints */ | |
87 | int i; /* loop counter */ | |
88 | int nextleft, nextright; /* indices to second endpoints */ | |
89 | DDXPointPtr ptsOut, FirstPoint; /* output buffer */ | |
90 | int *width, *FirstWidth; /* output buffer */ | |
91 | int imin; /* index of smallest vertex (in y) */ | |
92 | int ymin; /* y-extents of polygon */ | |
93 | int ymax; | |
94 | ||
95 | /* | |
96 | * find leftx, bottomy, rightx, topy, and the index | |
97 | * of bottomy. Also translate the points. | |
98 | */ | |
99 | imin = getPolyYBounds(ptsIn, count, &ymin, &ymax); | |
100 | ||
101 | dy = ymax - ymin + 1; | |
102 | if ((count < 3) || (dy < 0)) | |
103 | return TRUE; | |
104 | ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * dy); | |
105 | width = FirstWidth = malloc(sizeof(int) * dy); | |
106 | if (!FirstPoint || !FirstWidth) { | |
107 | free(FirstWidth); | |
108 | free(FirstPoint); | |
109 | return FALSE; | |
110 | } | |
111 | ||
112 | nextleft = nextright = imin; | |
113 | y = ptsIn[nextleft].y; | |
114 | ||
115 | /* | |
116 | * loop through all edges of the polygon | |
117 | */ | |
118 | do { | |
119 | /* | |
120 | * add a left edge if we need to | |
121 | */ | |
122 | if (ptsIn[nextleft].y == y) { | |
123 | left = nextleft; | |
124 | ||
125 | /* | |
126 | * find the next edge, considering the end | |
127 | * conditions of the array. | |
128 | */ | |
129 | nextleft++; | |
130 | if (nextleft >= count) | |
131 | nextleft = 0; | |
132 | ||
133 | /* | |
134 | * now compute all of the random information | |
135 | * needed to run the iterative algorithm. | |
136 | */ | |
137 | BRESINITPGON(ptsIn[nextleft].y - ptsIn[left].y, | |
138 | ptsIn[left].x, ptsIn[nextleft].x, | |
139 | xl, dl, ml, m1l, incr1l, incr2l); | |
140 | } | |
141 | ||
142 | /* | |
143 | * add a right edge if we need to | |
144 | */ | |
145 | if (ptsIn[nextright].y == y) { | |
146 | right = nextright; | |
147 | ||
148 | /* | |
149 | * find the next edge, considering the end | |
150 | * conditions of the array. | |
151 | */ | |
152 | nextright--; | |
153 | if (nextright < 0) | |
154 | nextright = count - 1; | |
155 | ||
156 | /* | |
157 | * now compute all of the random information | |
158 | * needed to run the iterative algorithm. | |
159 | */ | |
160 | BRESINITPGON(ptsIn[nextright].y - ptsIn[right].y, | |
161 | ptsIn[right].x, ptsIn[nextright].x, | |
162 | xr, dr, mr, m1r, incr1r, incr2r); | |
163 | } | |
164 | ||
165 | /* | |
166 | * generate scans to fill while we still have | |
167 | * a right edge as well as a left edge. | |
168 | */ | |
169 | i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y; | |
170 | /* in case we're called with non-convex polygon */ | |
171 | if (i < 0) { | |
172 | free(FirstWidth); | |
173 | free(FirstPoint); | |
174 | return TRUE; | |
175 | } | |
176 | while (i-- > 0) { | |
177 | ptsOut->y = y; | |
178 | ||
179 | /* | |
180 | * reverse the edges if necessary | |
181 | */ | |
182 | if (xl < xr) { | |
183 | *(width++) = xr - xl; | |
184 | (ptsOut++)->x = xl; | |
185 | } | |
186 | else { | |
187 | *(width++) = xl - xr; | |
188 | (ptsOut++)->x = xr; | |
189 | } | |
190 | y++; | |
191 | ||
192 | /* increment down the edges */ | |
193 | BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l); | |
194 | BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r); | |
195 | } | |
196 | } while (y != ymax); | |
197 | ||
198 | /* | |
199 | * Finally, fill the <remaining> spans | |
200 | */ | |
201 | (*pgc->ops->FillSpans) (dst, pgc, | |
202 | ptsOut - FirstPoint, FirstPoint, FirstWidth, 1); | |
203 | free(FirstWidth); | |
204 | free(FirstPoint); | |
205 | return TRUE; | |
206 | } | |
207 | \f | |
208 | /* | |
209 | * Find the index of the point with the smallest y. | |
210 | */ | |
211 | static int | |
212 | getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty) | |
213 | { | |
214 | DDXPointPtr ptMin; | |
215 | int ymin, ymax; | |
216 | DDXPointPtr ptsStart = pts; | |
217 | ||
218 | ptMin = pts; | |
219 | ymin = ymax = (pts++)->y; | |
220 | ||
221 | while (--n > 0) { | |
222 | if (pts->y < ymin) { | |
223 | ptMin = pts; | |
224 | ymin = pts->y; | |
225 | } | |
226 | if (pts->y > ymax) | |
227 | ymax = pts->y; | |
228 | ||
229 | pts++; | |
230 | } | |
231 | ||
232 | *by = ymin; | |
233 | *ty = ymax; | |
234 | return ptMin - ptsStart; | |
235 | } |