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