1/***********************************************************
2
3Copyright 1987, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in this Software without prior written authorization from The Open Group.
24
25
26Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
27
28                        All Rights Reserved
29
30Permission to use, copy, modify, and distribute this software and its
31documentation for any purpose and without fee is hereby granted,
32provided that the above copyright notice appear in all copies and that
33both that copyright notice and this permission notice appear in
34supporting documentation, and that the name of Digital not be
35used in advertising or publicity pertaining to distribution of the
36software without specific, written prior permission.
37
38DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
39ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
40DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
41ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
42WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
43ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
44SOFTWARE.
45
46******************************************************************/
47#ifdef HAVE_DIX_CONFIG_H
48#include <dix-config.h>
49#endif
50
51#include <math.h>
52#include <X11/X.h>
53#include "gcstruct.h"
54#include "windowstr.h"
55#include "pixmapstr.h"
56#include "mifpoly.h"
57
58static int GetFPolyYBounds(SppPointPtr pts, int n, double yFtrans,
59			   int *by, int *ty);
60
61/*
62 *	Written by Todd Newman; April. 1987.
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 digital differencing analyzer
70 *	line algorithm with y as the major axis. There's some funny linear
71 *	interpolation involved because of the subpixel postioning.
72 */
73void
74miFillSppPoly(
75    DrawablePtr		dst,
76    GCPtr		pgc,
77    int			count,          /* number of points */
78    SppPointPtr		ptsIn,          /* the points */
79    int			xTrans, int yTrans,	/* Translate each point by this */
80    double		xFtrans,
81    double		yFtrans                 /* translate before conversion
82						   by this amount.  This provides
83						   a mechanism to match rounding
84						   errors with any shape that must
85						   meet the polygon exactly.
86						 */
87    )
88{
89    double		xl = 0.0, xr = 0.0,	/* x vals of left and right edges */
90          		ml = 0.0,      	/* left edge slope */
91          		mr = 0.0,       /* right edge slope */
92          		dy,             /* delta y */
93    			i;              /* loop counter */
94    int			y,              /* current scanline */
95    			j,
96    			imin,           /* index of vertex with smallest y */
97    			ymin,           /* y-extents of polygon */
98    			ymax,
99    			*width,
100    			*FirstWidth,    /* output buffer */
101    	 		*Marked;	/* set if this vertex has been used */
102    int			left, right,	/* indices to first endpoints */
103    			nextleft,
104                 	nextright;	/* indices to second endpoints */
105    DDXPointPtr 	ptsOut,
106    			FirstPoint;	/* output buffer */
107
108    if (pgc->miTranslate)
109    {
110	xTrans += dst->x;
111	yTrans += dst->y;
112    }
113
114    imin = GetFPolyYBounds(ptsIn, count, yFtrans, &ymin, &ymax);
115
116    y = ymax - ymin + 1;
117    if ((count < 3) || (y <= 0))
118	return;
119    ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * y);
120    width = FirstWidth = malloc(sizeof(int) * y);
121    Marked = malloc(sizeof(int) * count);
122
123    if(!ptsOut || !width || !Marked)
124    {
125	free(Marked);
126	free(width);
127	free(ptsOut);
128	return;
129    }
130
131    for(j = 0; j < count; j++)
132	Marked[j] = 0;
133    nextleft = nextright = imin;
134    Marked[imin] = -1;
135    y = ICEIL(ptsIn[nextleft].y + yFtrans);
136
137    /*
138     *  loop through all edges of the polygon
139     */
140    do
141    {
142        /* add a left edge if we need to */
143        if ((y > (ptsIn[nextleft].y + yFtrans) ||
144 	     ISEQUAL(y, ptsIn[nextleft].y + yFtrans)) &&
145	     Marked[nextleft] != 1)
146	{
147	    Marked[nextleft]++;
148            left = nextleft++;
149
150            /* find the next edge, considering the end conditions */
151            if (nextleft >= count)
152                nextleft = 0;
153
154            /* now compute the starting point and slope */
155	    dy = ptsIn[nextleft].y - ptsIn[left].y;
156	    if (dy != 0.0)
157	    {
158		ml = (ptsIn[nextleft].x - ptsIn[left].x) / dy;
159		dy = y - (ptsIn[left].y + yFtrans);
160		xl = (ptsIn[left].x + xFtrans) + ml * max(dy, 0);
161	    }
162        }
163
164        /* add a right edge if we need to */
165        if ((y > ptsIn[nextright].y + yFtrans) ||
166 	     (ISEQUAL(y, ptsIn[nextright].y + yFtrans)
167	     && Marked[nextright] != 1))
168	{
169	    Marked[nextright]++;
170            right = nextright--;
171
172            /* find the next edge, considering the end conditions */
173            if (nextright < 0)
174                nextright = count - 1;
175
176            /* now compute the starting point and slope */
177	    dy = ptsIn[nextright].y - ptsIn[right].y;
178	    if (dy != 0.0)
179	    {
180		mr = (ptsIn[nextright].x - ptsIn[right].x) / dy;
181		dy = y - (ptsIn[right].y + yFtrans);
182		xr = (ptsIn[right].x + xFtrans) + mr * max(dy, 0);
183	    }
184        }
185
186
187        /*
188         *  generate scans to fill while we still have
189         *  a right edge as well as a left edge.
190         */
191        i = (min(ptsIn[nextleft].y, ptsIn[nextright].y) + yFtrans) - y;
192
193	if (i < EPSILON)
194	{
195	    if(Marked[nextleft] && Marked[nextright])
196	    {
197	        /* Arrgh, we're trapped! (no more points)
198	         * Out, we've got to get out of here before this decadence saps
199	         * our will completely! */
200	        break;
201	    }
202	    continue;
203	}
204	else
205	{
206		j = (int) i;
207		if(!j)
208		    j++;
209	}
210        while (j > 0)
211        {
212	    int cxl, cxr;
213
214            ptsOut->y = (y) + yTrans;
215
216	    cxl = ICEIL(xl);
217	    cxr = ICEIL(xr);
218            /* reverse the edges if necessary */
219            if (xl < xr)
220            {
221                *(width++) = cxr - cxl;
222                (ptsOut++)->x = cxl + xTrans;
223            }
224            else
225            {
226                *(width++) = cxl - cxr;
227                (ptsOut++)->x = cxr + xTrans;
228            }
229            y++;
230
231            /* increment down the edges */
232	    xl += ml;
233	    xr += mr;
234	    j--;
235        }
236    }  while (y <= ymax);
237
238    /* Finally, fill the spans we've collected */
239    (*pgc->ops->FillSpans)(dst, pgc,
240		      ptsOut-FirstPoint, FirstPoint, FirstWidth, 1);
241    free(Marked);
242    free(FirstWidth);
243    free(FirstPoint);
244}
245
246
247/* Find the index of the point with the smallest y.also return the
248 * smallest and largest y */
249static
250int
251GetFPolyYBounds(
252    SppPointPtr			pts,
253    int 			n,
254    double			yFtrans,
255    int 			*by,
256    int				*ty)
257{
258    SppPointPtr			ptMin;
259    double 			ymin, ymax;
260    SppPointPtr			ptsStart = pts;
261
262    ptMin = pts;
263    ymin = ymax = (pts++)->y;
264
265    while (--n > 0) {
266        if (pts->y < ymin)
267	{
268            ptMin = pts;
269            ymin = pts->y;
270        }
271	if(pts->y > ymax)
272            ymax = pts->y;
273
274        pts++;
275    }
276
277    *by = ICEIL(ymin + yFtrans);
278    *ty = ICEIL(ymax + yFtrans - 1);
279    return ptMin-ptsStart;
280}
281