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