Poly.c revision 1f0ac6a5 
1/*
2 *
3 * Copyright © 2002 Keith Packard
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, and that the name of Keith Packard not be used in
10 * advertising or publicity pertaining to distribution of the software without
11 * specific, written prior permission.  Keith Packard makes no
12 * representations about the suitability of this software for any purpose.  It
13 * is provided "as is" without express or implied warranty.
14 *
15 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
17 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
18 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
19 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
20 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
21 * PERFORMANCE OF THIS SOFTWARE.
22 */
23
24#ifdef HAVE_CONFIG_H
25#include <config.h>
26#endif
27#include "Xrenderint.h"
28
29typedef struct _Edge Edge;
30
31struct _Edge {
32    XLineFixed	edge;
33    XFixed	current_x;
34    Bool	clockWise;
35    Edge	*next, *prev;
36};
37
38static int
39CompareEdge (const void *o1, const void *o2)
40{
41    const Edge	*e1 = o1, *e2 = o2;
42
43    return e1->edge.p1.y - e2->edge.p1.y;
44}
45
46static XFixed
47XRenderComputeX (XLineFixed *line, XFixed y)
48{
49    XFixed  dx = line->p2.x - line->p1.x;
50    double  ex = (double) (y - line->p1.y) * (double) dx;
51    XFixed  dy = line->p2.y - line->p1.y;
52
53    return (XFixed) line->p1.x + (XFixed) (ex / dy);
54}
55
56static double
57XRenderComputeInverseSlope (XLineFixed *l)
58{
59    return (XFixedToDouble (l->p2.x - l->p1.x) /
60	    XFixedToDouble (l->p2.y - l->p1.y));
61}
62
63static double
64XRenderComputeXIntercept (XLineFixed *l, double inverse_slope)
65{
66    return XFixedToDouble (l->p1.x) - inverse_slope * XFixedToDouble (l->p1.y);
67}
68
69static XFixed
70XRenderComputeIntersect (XLineFixed *l1, XLineFixed *l2)
71{
72    /*
73     * x = m1y + b1
74     * x = m2y + b2
75     * m1y + b1 = m2y + b2
76     * y * (m1 - m2) = b2 - b1
77     * y = (b2 - b1) / (m1 - m2)
78     */
79    double  m1 = XRenderComputeInverseSlope (l1);
80    double  b1 = XRenderComputeXIntercept (l1, m1);
81    double  m2 = XRenderComputeInverseSlope (l2);
82    double  b2 = XRenderComputeXIntercept (l2, m2);
83
84    return XDoubleToFixed ((b2 - b1) / (m1 - m2));
85}
86
87static int
88XRenderComputeTrapezoids (Edge		*edges,
89			  int		nedges,
90			  int		winding,
91			  XTrapezoid	*traps)
92{
93    int		ntraps = 0;
94    int		inactive;
95    Edge	*active;
96    Edge	*e, *en, *next;
97    XFixed	y, next_y, intersect;
98
99    qsort (edges, nedges, sizeof (Edge), CompareEdge);
100
101    y = edges[0].edge.p1.y;
102    active = 0;
103    inactive = 0;
104    while (active || inactive < nedges)
105    {
106	/* insert new active edges into list */
107	while (inactive < nedges)
108	{
109	    e = &edges[inactive];
110	    if (e->edge.p1.y > y)
111		break;
112	    /* move this edge into the active list */
113	    inactive++;
114	    e->next = active;
115	    e->prev = 0;
116	    if (active)
117		active->prev = e;
118	    active = e;
119	}
120	/* compute x coordinates along this group */
121	for (e = active; e; e = e->next)
122	    e->current_x = XRenderComputeX (&e->edge, y);
123
124	/* sort active list */
125	for (e = active; e; e = next)
126	{
127	    next = e->next;
128	    /*
129	     * Find one later in the list that belongs before the
130	     * current one
131	     */
132	    for (en = next; en; en = en->next)
133	    {
134		if (en->current_x < e->current_x ||
135		    (en->current_x == e->current_x &&
136		     en->edge.p2.x < e->edge.p2.x))
137		{
138		    /*
139		     * insert en before e
140		     *
141		     * extract en
142		     */
143		    en->prev->next = en->next;
144		    if (en->next)
145			en->next->prev = en->prev;
146		    /*
147		     * insert en
148		     */
149		    if (e->prev)
150			e->prev->next = en;
151		    else
152			active = en;
153		    en->prev = e->prev;
154		    e->prev = en;
155		    en->next = e;
156		    /*
157		     * start over at en
158		     */
159		    next = en;
160		    break;
161		}
162	    }
163	}
164#if 0
165	printf ("y: %6.3g:", y / 65536.0);
166	for (e = active; e; e = e->next)
167	{
168	    printf (" %6.3g", e->current_x / 65536.0);
169	}
170	printf ("\n");
171#endif
172	/* find next inflection point */
173	next_y = active->edge.p2.y;
174	for (e = active; e; e = en)
175	{
176	    if (e->edge.p2.y < next_y)
177		next_y = e->edge.p2.y;
178	    en = e->next;
179	    /* check intersect */
180	    if (en && e->edge.p2.x > en->edge.p2.x)
181	    {
182		intersect = XRenderComputeIntersect (&e->edge, &e->next->edge);
183		/* make sure this point is below the actual intersection */
184		intersect = intersect + 1;
185		if (intersect < next_y)
186		    next_y = intersect;
187	    }
188	}
189	/* check next inactive point */
190	if (inactive < nedges && edges[inactive].edge.p1.y < next_y)
191	    next_y = edges[inactive].edge.p1.y;
192
193	/* walk the list generating trapezoids */
194	for (e = active; e && (en = e->next); e = en->next)
195	{
196	    traps->top = y;
197	    traps->bottom = next_y;
198	    traps->left = e->edge;
199	    traps->right = en->edge;
200	    traps++;
201	    ntraps++;
202	}
203
204	y = next_y;
205
206	/* delete inactive edges from list */
207	for (e = active; e; e = next)
208	{
209	    next = e->next;
210	    if (e->edge.p2.y <= y)
211	    {
212		if (e->prev)
213		    e->prev->next = e->next;
214		else
215		    active = e->next;
216		if (e->next)
217		    e->next->prev = e->prev;
218	    }
219	}
220    }
221    return ntraps;
222}
223
224void
225XRenderCompositeDoublePoly (Display		    *dpy,
226			    int			    op,
227			    Picture		    src,
228			    Picture		    dst,
229			    _Xconst XRenderPictFormat	*maskFormat,
230			    int			    xSrc,
231			    int			    ySrc,
232			    int			    xDst,
233			    int			    yDst,
234			    _Xconst XPointDouble    *fpoints,
235			    int			    npoints,
236			    int			    winding)
237{
238    Edge	    *edges;
239    XTrapezoid	    *traps;
240    int		    i, nedges, ntraps;
241    XFixed	    x, y, prevx = 0, prevy = 0, firstx = 0, firsty = 0;
242    XFixed	    top = 0, bottom = 0;	/* GCCism */
243
244    edges = (Edge *) Xmalloc (npoints * sizeof (Edge) +
245			      (npoints * npoints * sizeof (XTrapezoid)));
246    if (!edges)
247	return;
248    traps = (XTrapezoid *) (edges + npoints);
249    nedges = 0;
250    for (i = 0; i <= npoints; i++)
251    {
252	if (i == npoints)
253	{
254	    x = firstx;
255	    y = firsty;
256	}
257	else
258	{
259	    x = XDoubleToFixed (fpoints[i].x);
260	    y = XDoubleToFixed (fpoints[i].y);
261	}
262	if (i)
263	{
264	    if (y < top)
265		top = y;
266	    else if (y > bottom)
267		bottom = y;
268	    if (prevy < y)
269	    {
270		edges[nedges].edge.p1.x = prevx;
271		edges[nedges].edge.p1.y = prevy;
272		edges[nedges].edge.p2.x = x;
273		edges[nedges].edge.p2.y = y;
274		edges[nedges].clockWise = True;
275		nedges++;
276	    }
277	    else if (prevy > y)
278	    {
279		edges[nedges].edge.p1.x = x;
280		edges[nedges].edge.p1.y = y;
281		edges[nedges].edge.p2.x = prevx;
282		edges[nedges].edge.p2.y = prevy;
283		edges[nedges].clockWise = False;
284		nedges++;
285	    }
286	    /* drop horizontal edges */
287	}
288	else
289	{
290	    top = y;
291	    bottom = y;
292	    firstx = x;
293	    firsty = y;
294	}
295	prevx = x;
296	prevy = y;
297    }
298    ntraps = XRenderComputeTrapezoids (edges, nedges, winding, traps);
299    /* XXX adjust xSrc/xDst */
300    XRenderCompositeTrapezoids (dpy, op, src, dst, maskFormat, xSrc, ySrc, traps, ntraps);
301    Xfree (edges);
302}
303