| 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 | } |