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 | #ifdef HAVE_DIX_CONFIG_H | |
47 | #include <dix-config.h> | |
48 | #endif | |
49 | ||
50 | #include <math.h> | |
51 | #include <X11/X.h> | |
52 | #include "gcstruct.h" | |
53 | #include "windowstr.h" | |
54 | #include "pixmapstr.h" | |
55 | #include "mifpoly.h" | |
56 | ||
57 | static int GetFPolyYBounds(SppPointPtr pts, int n, double yFtrans, | |
58 | int *by, int *ty); | |
59 | ||
60 | /* | |
61 | * Written by Todd Newman; April. 1987. | |
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 digital differencing analyzer | |
69 | * line algorithm with y as the major axis. There's some funny linear | |
70 | * interpolation involved because of the subpixel postioning. | |
71 | */ | |
72 | void | |
73 | miFillSppPoly(DrawablePtr dst, GCPtr pgc, int count, /* number of points */ | |
74 | SppPointPtr ptsIn, /* the points */ | |
75 | int xTrans, int yTrans, /* Translate each point by this */ | |
76 | double xFtrans, double yFtrans /* translate before conversion | |
77 | by this amount. This provides | |
78 | a mechanism to match rounding | |
79 | errors with any shape that must | |
80 | meet the polygon exactly. | |
81 | */ | |
82 | ) | |
83 | { | |
84 | double xl = 0.0, xr = 0.0, /* x vals of left and right edges */ | |
85 | ml = 0.0, /* left edge slope */ | |
86 | mr = 0.0, /* right edge slope */ | |
87 | dy, /* delta y */ | |
88 | i; /* loop counter */ | |
89 | int y, /* current scanline */ | |
90 | j, imin, /* index of vertex with smallest y */ | |
91 | ymin, /* y-extents of polygon */ | |
92 | ymax, *width, *FirstWidth, /* output buffer */ | |
93 | *Marked; /* set if this vertex has been used */ | |
94 | int left, right, /* indices to first endpoints */ | |
95 | nextleft, nextright; /* indices to second endpoints */ | |
96 | DDXPointPtr ptsOut, FirstPoint; /* output buffer */ | |
97 | ||
98 | if (pgc->miTranslate) { | |
99 | xTrans += dst->x; | |
100 | yTrans += dst->y; | |
101 | } | |
102 | ||
103 | imin = GetFPolyYBounds(ptsIn, count, yFtrans, &ymin, &ymax); | |
104 | ||
105 | y = ymax - ymin + 1; | |
106 | if ((count < 3) || (y <= 0)) | |
107 | return; | |
108 | ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * y); | |
109 | width = FirstWidth = malloc(sizeof(int) * y); | |
110 | Marked = malloc(sizeof(int) * count); | |
111 | ||
112 | if (!ptsOut || !width || !Marked) { | |
113 | free(Marked); | |
114 | free(width); | |
115 | free(ptsOut); | |
116 | return; | |
117 | } | |
118 | ||
119 | for (j = 0; j < count; j++) | |
120 | Marked[j] = 0; | |
121 | nextleft = nextright = imin; | |
122 | Marked[imin] = -1; | |
123 | y = ICEIL(ptsIn[nextleft].y + yFtrans); | |
124 | ||
125 | /* | |
126 | * loop through all edges of the polygon | |
127 | */ | |
128 | do { | |
129 | /* add a left edge if we need to */ | |
130 | if ((y > (ptsIn[nextleft].y + yFtrans) || | |
131 | ISEQUAL(y, ptsIn[nextleft].y + yFtrans)) && | |
132 | Marked[nextleft] != 1) { | |
133 | Marked[nextleft]++; | |
134 | left = nextleft++; | |
135 | ||
136 | /* find the next edge, considering the end conditions */ | |
137 | if (nextleft >= count) | |
138 | nextleft = 0; | |
139 | ||
140 | /* now compute the starting point and slope */ | |
141 | dy = ptsIn[nextleft].y - ptsIn[left].y; | |
142 | if (dy != 0.0) { | |
143 | ml = (ptsIn[nextleft].x - ptsIn[left].x) / dy; | |
144 | dy = y - (ptsIn[left].y + yFtrans); | |
145 | xl = (ptsIn[left].x + xFtrans) + ml * max(dy, 0); | |
146 | } | |
147 | } | |
148 | ||
149 | /* add a right edge if we need to */ | |
150 | if ((y > ptsIn[nextright].y + yFtrans) || | |
151 | (ISEQUAL(y, ptsIn[nextright].y + yFtrans) | |
152 | && Marked[nextright] != 1)) { | |
153 | Marked[nextright]++; | |
154 | right = nextright--; | |
155 | ||
156 | /* find the next edge, considering the end conditions */ | |
157 | if (nextright < 0) | |
158 | nextright = count - 1; | |
159 | ||
160 | /* now compute the starting point and slope */ | |
161 | dy = ptsIn[nextright].y - ptsIn[right].y; | |
162 | if (dy != 0.0) { | |
163 | mr = (ptsIn[nextright].x - ptsIn[right].x) / dy; | |
164 | dy = y - (ptsIn[right].y + yFtrans); | |
165 | xr = (ptsIn[right].x + xFtrans) + mr * max(dy, 0); | |
166 | } | |
167 | } | |
168 | ||
169 | /* | |
170 | * generate scans to fill while we still have | |
171 | * a right edge as well as a left edge. | |
172 | */ | |
173 | i = (min(ptsIn[nextleft].y, ptsIn[nextright].y) + yFtrans) - y; | |
174 | ||
175 | if (i < EPSILON) { | |
176 | if (Marked[nextleft] && Marked[nextright]) { | |
177 | /* Arrgh, we're trapped! (no more points) | |
178 | * Out, we've got to get out of here before this decadence saps | |
179 | * our will completely! */ | |
180 | break; | |
181 | } | |
182 | continue; | |
183 | } | |
184 | else { | |
185 | j = (int) i; | |
186 | if (!j) | |
187 | j++; | |
188 | } | |
189 | while (j > 0) { | |
190 | int cxl, cxr; | |
191 | ||
192 | ptsOut->y = (y) + yTrans; | |
193 | ||
194 | cxl = ICEIL(xl); | |
195 | cxr = ICEIL(xr); | |
196 | /* reverse the edges if necessary */ | |
197 | if (xl < xr) { | |
198 | *(width++) = cxr - cxl; | |
199 | (ptsOut++)->x = cxl + xTrans; | |
200 | } | |
201 | else { | |
202 | *(width++) = cxl - cxr; | |
203 | (ptsOut++)->x = cxr + xTrans; | |
204 | } | |
205 | y++; | |
206 | ||
207 | /* increment down the edges */ | |
208 | xl += ml; | |
209 | xr += mr; | |
210 | j--; | |
211 | } | |
212 | } while (y <= ymax); | |
213 | ||
214 | /* Finally, fill the spans we've collected */ | |
215 | (*pgc->ops->FillSpans) (dst, pgc, | |
216 | ptsOut - FirstPoint, FirstPoint, FirstWidth, 1); | |
217 | free(Marked); | |
218 | free(FirstWidth); | |
219 | free(FirstPoint); | |
220 | } | |
221 | \f | |
222 | /* Find the index of the point with the smallest y.also return the | |
223 | * smallest and largest y */ | |
224 | static | |
225 | int | |
226 | GetFPolyYBounds(SppPointPtr pts, int n, double yFtrans, int *by, int *ty) | |
227 | { | |
228 | SppPointPtr ptMin; | |
229 | double ymin, ymax; | |
230 | SppPointPtr ptsStart = pts; | |
231 | ||
232 | ptMin = pts; | |
233 | ymin = ymax = (pts++)->y; | |
234 | ||
235 | while (--n > 0) { | |
236 | if (pts->y < ymin) { | |
237 | ptMin = pts; | |
238 | ymin = pts->y; | |
239 | } | |
240 | if (pts->y > ymax) | |
241 | ymax = pts->y; | |
242 | ||
243 | pts++; | |
244 | } | |
245 | ||
246 | *by = ICEIL(ymin + yFtrans); | |
247 | *ty = ICEIL(ymax + yFtrans - 1); | |
248 | return ptMin - ptsStart; | |
249 | } |