summaryrefslogtreecommitdiff
path: root/src/Poly.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/Poly.c')
-rw-r--r--src/Poly.c300
1 files changed, 300 insertions, 0 deletions
diff --git a/src/Poly.c b/src/Poly.c
new file mode 100644
index 0000000..a6856fb
--- /dev/null
+++ b/src/Poly.c
@@ -0,0 +1,300 @@
+/*
+ * $XFree86: xc/lib/Xrender/Poly.c,v 1.7 2002/06/04 23:22:36 keithp Exp $
+ *
+ * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
+ *
+ * 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.
+ */
+
+#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 = 0;
+ 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 = 0;
+ 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);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 22:04:05 +0000