From 6e3cfc5bc8ca969856e4d56dec01870df709d75a Mon Sep 17 00:00:00 2001 From: marha Date: Wed, 19 Jan 2011 10:06:48 +0000 Subject: Added libXft-2.2.0 fontconfig-2.8.0 libXrender-0.9.6 --- libXrender/src/Poly.c | 302 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 302 insertions(+) create mode 100644 libXrender/src/Poly.c (limited to 'libXrender/src/Poly.c') diff --git a/libXrender/src/Poly.c b/libXrender/src/Poly.c new file mode 100644 index 000000000..16599b22e --- /dev/null +++ b/libXrender/src/Poly.c @@ -0,0 +1,302 @@ +/* + * + * Copyright © 2002 Keith Packard + * + * Permission to use, copy, modify, distribute, and sell this software and its + * documentation for any purpose is hereby granted without fee, provided that + * the above copyright notice appear in all copies and that both that + * copyright notice and this permission notice appear in supporting + * documentation, and that the name of Keith Packard not be used in + * advertising or publicity pertaining to distribution of the software without + * specific, written prior permission. Keith Packard makes no + * representations about the suitability of this software for any purpose. It + * is provided "as is" without express or implied warranty. + * + * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO + * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, + * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER + * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR + * PERFORMANCE OF THIS SOFTWARE. + */ + +#ifdef HAVE_CONFIG_H +#include +#endif +#include "Xrenderint.h" + +typedef struct _Edge Edge; + +struct _Edge { + XLineFixed edge; + XFixed current_x; + Bool clockWise; + Edge *next, *prev; +}; + +static int +CompareEdge (const void *o1, const void *o2) +{ + const Edge *e1 = o1, *e2 = o2; + + return e1->edge.p1.y - e2->edge.p1.y; +} + +static XFixed +XRenderComputeX (XLineFixed *line, XFixed y) +{ + XFixed dx = line->p2.x - line->p1.x; + double ex = (double) (y - line->p1.y) * (double) dx; + XFixed dy = line->p2.y - line->p1.y; + + return (XFixed) line->p1.x + (XFixed) (ex / dy); +} + +static double +XRenderComputeInverseSlope (XLineFixed *l) +{ + return (XFixedToDouble (l->p2.x - l->p1.x) / + XFixedToDouble (l->p2.y - l->p1.y)); +} + +static double +XRenderComputeXIntercept (XLineFixed *l, double inverse_slope) +{ + return XFixedToDouble (l->p1.x) - inverse_slope * XFixedToDouble (l->p1.y); +} + +static XFixed +XRenderComputeIntersect (XLineFixed *l1, XLineFixed *l2) +{ + /* + * x = m1y + b1 + * x = m2y + b2 + * m1y + b1 = m2y + b2 + * y * (m1 - m2) = b2 - b1 + * y = (b2 - b1) / (m1 - m2) + */ + double m1 = XRenderComputeInverseSlope (l1); + double b1 = XRenderComputeXIntercept (l1, m1); + double m2 = XRenderComputeInverseSlope (l2); + double b2 = XRenderComputeXIntercept (l2, m2); + + return XDoubleToFixed ((b2 - b1) / (m1 - m2)); +} + +static int +XRenderComputeTrapezoids (Edge *edges, + int nedges, + int winding, + XTrapezoid *traps) +{ + int ntraps = 0; + int inactive; + Edge *active; + Edge *e, *en, *next; + XFixed y, next_y, intersect; + + qsort (edges, nedges, sizeof (Edge), CompareEdge); + + y = edges[0].edge.p1.y; + active = NULL; + inactive = 0; + while (active || inactive < nedges) + { + /* insert new active edges into list */ + while (inactive < nedges) + { + e = &edges[inactive]; + if (e->edge.p1.y > y) + break; + /* move this edge into the active list */ + inactive++; + e->next = active; + e->prev = NULL; + if (active) + active->prev = e; + active = e; + } + /* compute x coordinates along this group */ + for (e = active; e; e = e->next) + e->current_x = XRenderComputeX (&e->edge, y); + + /* sort active list */ + for (e = active; e; e = next) + { + next = e->next; + /* + * Find one later in the list that belongs before the + * current one + */ + for (en = next; en; en = en->next) + { + if (en->current_x < e->current_x || + (en->current_x == e->current_x && + en->edge.p2.x < e->edge.p2.x)) + { + /* + * insert en before e + * + * extract en + */ + en->prev->next = en->next; + if (en->next) + en->next->prev = en->prev; + /* + * insert en + */ + if (e->prev) + e->prev->next = en; + else + active = en; + en->prev = e->prev; + e->prev = en; + en->next = e; + /* + * start over at en + */ + next = en; + break; + } + } + } +#if 0 + printf ("y: %6.3g:", y / 65536.0); + for (e = active; e; e = e->next) + { + printf (" %6.3g", e->current_x / 65536.0); + } + printf ("\n"); +#endif + /* find next inflection point */ + next_y = active->edge.p2.y; + for (e = active; e; e = en) + { + if (e->edge.p2.y < next_y) + next_y = e->edge.p2.y; + en = e->next; + /* check intersect */ + if (en && e->edge.p2.x > en->edge.p2.x) + { + intersect = XRenderComputeIntersect (&e->edge, &e->next->edge); + /* make sure this point is below the actual intersection */ + intersect = intersect + 1; + if (intersect < next_y) + next_y = intersect; + } + } + /* check next inactive point */ + if (inactive < nedges && edges[inactive].edge.p1.y < next_y) + next_y = edges[inactive].edge.p1.y; + + /* walk the list generating trapezoids */ + for (e = active; e && (en = e->next); e = en->next) + { + traps->top = y; + traps->bottom = next_y; + traps->left = e->edge; + traps->right = en->edge; + traps++; + ntraps++; + } + + y = next_y; + + /* delete inactive edges from list */ + for (e = active; e; e = next) + { + next = e->next; + if (e->edge.p2.y <= y) + { + if (e->prev) + e->prev->next = e->next; + else + active = e->next; + if (e->next) + e->next->prev = e->prev; + } + } + } + return ntraps; +} + +void +XRenderCompositeDoublePoly (Display *dpy, + int op, + Picture src, + Picture dst, + _Xconst XRenderPictFormat *maskFormat, + int xSrc, + int ySrc, + int xDst, + int yDst, + _Xconst XPointDouble *fpoints, + int npoints, + int winding) +{ + Edge *edges; + XTrapezoid *traps; + int i, nedges, ntraps; + XFixed x, y, prevx = 0, prevy = 0, firstx = 0, firsty = 0; + XFixed top = 0, bottom = 0; /* GCCism */ + + edges = (Edge *) Xmalloc (npoints * sizeof (Edge) + + (npoints * npoints * sizeof (XTrapezoid))); + if (!edges) + return; + traps = (XTrapezoid *) (edges + npoints); + nedges = 0; + for (i = 0; i <= npoints; i++) + { + if (i == npoints) + { + x = firstx; + y = firsty; + } + else + { + x = XDoubleToFixed (fpoints[i].x); + y = XDoubleToFixed (fpoints[i].y); + } + if (i) + { + if (y < top) + top = y; + else if (y > bottom) + bottom = y; + if (prevy < y) + { + edges[nedges].edge.p1.x = prevx; + edges[nedges].edge.p1.y = prevy; + edges[nedges].edge.p2.x = x; + edges[nedges].edge.p2.y = y; + edges[nedges].clockWise = True; + nedges++; + } + else if (prevy > y) + { + edges[nedges].edge.p1.x = x; + edges[nedges].edge.p1.y = y; + edges[nedges].edge.p2.x = prevx; + edges[nedges].edge.p2.y = prevy; + edges[nedges].clockWise = False; + nedges++; + } + /* drop horizontal edges */ + } + else + { + top = y; + bottom = y; + firstx = x; + firsty = y; + } + prevx = x; + prevy = y; + } + ntraps = XRenderComputeTrapezoids (edges, nedges, winding, traps); + /* XXX adjust xSrc/xDst */ + XRenderCompositeTrapezoids (dpy, op, src, dst, maskFormat, xSrc, ySrc, traps, ntraps); + Xfree (edges); +} -- cgit v1.2.3