| 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 <X11/X.h> |
| 51 | #include "gcstruct.h" |
| 52 | #include "miscanfill.h" |
| 53 | #include "mipoly.h" |
| 54 | #include "pixmap.h" |
| 55 | #include "mi.h" |
| 56 | |
| 57 | /* |
| 58 | * |
| 59 | * Written by Brian Kelleher; Oct. 1985 |
| 60 | * |
| 61 | * Routine to fill a polygon. Two fill rules are |
| 62 | * supported: frWINDING and frEVENODD. |
| 63 | * |
| 64 | * See fillpoly.h for a complete description of the algorithm. |
| 65 | */ |
| 66 | |
| 67 | Bool |
| 68 | miFillGeneralPoly(DrawablePtr dst, GCPtr pgc, int count, /* number of points */ |
| 69 | DDXPointPtr ptsIn /* the points */ |
| 70 | ) |
| 71 | { |
| 72 | EdgeTableEntry *pAET; /* the Active Edge Table */ |
| 73 | int y; /* the current scanline */ |
| 74 | int nPts = 0; /* number of pts in buffer */ |
| 75 | EdgeTableEntry *pWETE; /* Winding Edge Table */ |
| 76 | ScanLineList *pSLL; /* Current ScanLineList */ |
| 77 | DDXPointPtr ptsOut; /* ptr to output buffers */ |
| 78 | int *width; |
| 79 | DDXPointRec FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */ |
| 80 | int FirstWidth[NUMPTSTOBUFFER]; |
| 81 | EdgeTableEntry *pPrevAET; /* previous AET entry */ |
| 82 | EdgeTable ET; /* Edge Table header node */ |
| 83 | EdgeTableEntry AET; /* Active ET header node */ |
| 84 | EdgeTableEntry *pETEs; /* Edge Table Entries buff */ |
| 85 | ScanLineListBlock SLLBlock; /* header for ScanLineList */ |
| 86 | int fixWAET = 0; |
| 87 | |
| 88 | if (count < 3) |
| 89 | return TRUE; |
| 90 | |
| 91 | if (!(pETEs = malloc(sizeof(EdgeTableEntry) * count))) |
| 92 | return FALSE; |
| 93 | ptsOut = FirstPoint; |
| 94 | width = FirstWidth; |
| 95 | if (!miCreateETandAET(count, ptsIn, &ET, &AET, pETEs, &SLLBlock)) { |
| 96 | free(pETEs); |
| 97 | return FALSE; |
| 98 | } |
| 99 | pSLL = ET.scanlines.next; |
| 100 | |
| 101 | if (pgc->fillRule == EvenOddRule) { |
| 102 | /* |
| 103 | * for each scanline |
| 104 | */ |
| 105 | for (y = ET.ymin; y < ET.ymax; y++) { |
| 106 | /* |
| 107 | * Add a new edge to the active edge table when we |
| 108 | * get to the next edge. |
| 109 | */ |
| 110 | if (pSLL && y == pSLL->scanline) { |
| 111 | miloadAET(&AET, pSLL->edgelist); |
| 112 | pSLL = pSLL->next; |
| 113 | } |
| 114 | pPrevAET = &AET; |
| 115 | pAET = AET.next; |
| 116 | |
| 117 | /* |
| 118 | * for each active edge |
| 119 | */ |
| 120 | while (pAET) { |
| 121 | ptsOut->x = pAET->bres.minor; |
| 122 | ptsOut++->y = y; |
| 123 | *width++ = pAET->next->bres.minor - pAET->bres.minor; |
| 124 | nPts++; |
| 125 | |
| 126 | /* |
| 127 | * send out the buffer when its full |
| 128 | */ |
| 129 | if (nPts == NUMPTSTOBUFFER) { |
| 130 | (*pgc->ops->FillSpans) (dst, pgc, |
| 131 | nPts, FirstPoint, FirstWidth, 1); |
| 132 | ptsOut = FirstPoint; |
| 133 | width = FirstWidth; |
| 134 | nPts = 0; |
| 135 | } |
| 136 | EVALUATEEDGEEVENODD(pAET, pPrevAET, y) |
| 137 | EVALUATEEDGEEVENODD(pAET, pPrevAET, y); |
| 138 | } |
| 139 | miInsertionSort(&AET); |
| 140 | } |
| 141 | } |
| 142 | else { /* default to WindingNumber */ |
| 143 | |
| 144 | /* |
| 145 | * for each scanline |
| 146 | */ |
| 147 | for (y = ET.ymin; y < ET.ymax; y++) { |
| 148 | /* |
| 149 | * Add a new edge to the active edge table when we |
| 150 | * get to the next edge. |
| 151 | */ |
| 152 | if (pSLL && y == pSLL->scanline) { |
| 153 | miloadAET(&AET, pSLL->edgelist); |
| 154 | micomputeWAET(&AET); |
| 155 | pSLL = pSLL->next; |
| 156 | } |
| 157 | pPrevAET = &AET; |
| 158 | pAET = AET.next; |
| 159 | pWETE = pAET; |
| 160 | |
| 161 | /* |
| 162 | * for each active edge |
| 163 | */ |
| 164 | while (pAET) { |
| 165 | /* |
| 166 | * if the next edge in the active edge table is |
| 167 | * also the next edge in the winding active edge |
| 168 | * table. |
| 169 | */ |
| 170 | if (pWETE == pAET) { |
| 171 | ptsOut->x = pAET->bres.minor; |
| 172 | ptsOut++->y = y; |
| 173 | *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor; |
| 174 | nPts++; |
| 175 | |
| 176 | /* |
| 177 | * send out the buffer |
| 178 | */ |
| 179 | if (nPts == NUMPTSTOBUFFER) { |
| 180 | (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, |
| 181 | FirstWidth, 1); |
| 182 | ptsOut = FirstPoint; |
| 183 | width = FirstWidth; |
| 184 | nPts = 0; |
| 185 | } |
| 186 | |
| 187 | pWETE = pWETE->nextWETE; |
| 188 | while (pWETE != pAET) |
| 189 | EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET); |
| 190 | pWETE = pWETE->nextWETE; |
| 191 | } |
| 192 | EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET); |
| 193 | } |
| 194 | |
| 195 | /* |
| 196 | * reevaluate the Winding active edge table if we |
| 197 | * just had to resort it or if we just exited an edge. |
| 198 | */ |
| 199 | if (miInsertionSort(&AET) || fixWAET) { |
| 200 | micomputeWAET(&AET); |
| 201 | fixWAET = 0; |
| 202 | } |
| 203 | } |
| 204 | } |
| 205 | |
| 206 | /* |
| 207 | * Get any spans that we missed by buffering |
| 208 | */ |
| 209 | (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, FirstWidth, 1); |
| 210 | free(pETEs); |
| 211 | miFreeStorage(SLLBlock.next); |
| 212 | return TRUE; |
| 213 | } |