[PATCH 2/3] Add support for triangles to pixman.

[Søren Sandmann Pedersen]

The Render X extension can draw triangles as well as trapezoids, but
the implementation has always converted them to trapezoids. This patch
moves the X server's triangle conversion code into pixman, where we
can reuse the pixman_composite_trapezoid() code.
---
 pixman/pixman-trap.c |  136 ++++++++++++++++++++++++++++++++++++++++++++++++++
 pixman/pixman.h      |   15 ++++++
 2 files changed, 151 insertions(+), 0 deletions(-)

diff --git a/pixman/pixman-trap.c b/pixman/pixman-trap.c
index a924326..31144c4 100644
--- a/pixman/pixman-trap.c
+++ b/pixman/pixman-trap.c
@@ -1,4 +1,5 @@
 /*
+ * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
  * Copyright © 2004 Keith Packard
  *
  * Permission to use, copy, modify, distribute, and sell this software and its
@@ -25,6 +26,7 @@
 #endif
 
 #include <stdio.h>
+#include <stdlib.h>
 #include "pixman-private.h"
 
 /*
@@ -477,3 +479,137 @@ pixman_composite_trapezoids (pixman_op_t		op,
 
     pixman_image_unref (tmp);
 }
+
+static int
+greater_y (pixman_point_fixed_t *a, pixman_point_fixed_t *b)
+{
+    if (a->y == b->y)
+	return a->x > b->x;
+    return a->y > b->y;
+}
+
+/*
+ * Note that the definition of this function is a bit odd because
+ * of the X coordinate space (y increasing downwards).
+ */
+static int
+clockwise (pixman_point_fixed_t *ref,
+	   pixman_point_fixed_t *a,
+	   pixman_point_fixed_t *b)
+{
+    pixman_point_fixed_t	ad, bd;
+
+    ad.x = a->x - ref->x;
+    ad.y = a->y - ref->y;
+    bd.x = b->x - ref->x;
+    bd.y = b->y - ref->y;
+
+    return ((pixman_fixed_32_32_t) bd.y * ad.x -
+	    (pixman_fixed_32_32_t) ad.y * bd.x) < 0;
+}
+
+static void
+triangle_to_trapezoids (pixman_triangle_t *tri, pixman_trapezoid_t *traps)
+{
+    pixman_point_fixed_t *top, *left, *right, *tmp;
+
+    top = &tri->p1;
+    left = &tri->p2;
+    right = &tri->p3;
+
+    if (greater_y (top, left))
+    {
+	tmp = left;
+	left = top;
+	top = tmp;
+    }
+
+    if (greater_y (top, right))
+    {
+	tmp = right;
+	right = top;
+	top = tmp;
+    }
+
+    if (clockwise (top, right, left))
+    {
+	tmp = right;
+	right = left;
+	left = tmp;
+    }
+    
+    /*
+     * Two cases:
+     *
+     *		+		+
+     *	       / \             / \
+     *	      /   \           /	  \
+     *	     /     +         +	   \
+     *      /    --           --    \
+     *     /   --               --   \
+     *    / ---                   --- \
+     *	 +--                         --+
+     */
+
+    traps->top = top->y;
+    traps->left.p1 = *top;
+    traps->left.p2 = *left;
+    traps->right.p1 = *top;
+    traps->right.p2 = *right;
+
+    if (right->y < left->y)
+	traps->bottom = right->y;
+    else
+	traps->bottom = left->y;
+
+    traps++;
+
+    *traps = *(traps - 1);
+    
+    if (right->y < left->y)
+    {
+	traps->top = right->y;
+	traps->bottom = left->y;
+	traps->right.p1 = *right;
+	traps->right.p2 = *left;
+    }
+    else
+    {
+	traps->top = left->y;
+	traps->bottom = right->y;
+	traps->left.p1 = *left;
+	traps->left.p2 = *right;
+    }
+}
+
+PIXMAN_EXPORT void
+pixman_composite_triangles (pixman_op_t			op,
+			    pixman_image_t *		src,
+			    pixman_image_t *		dst,
+			    pixman_format_code_t	mask_format,
+			    int				x_src,
+			    int				y_src,
+			    int				x_dst,
+			    int				y_dst,
+			    int				n_tris,
+			    pixman_triangle_t *		tris)
+{
+    pixman_trapezoid_t *trapezoids;
+    int i;
+
+    if (n_tris <= 0)
+	return;
+    
+    trapezoids = malloc (2 * n_tris * sizeof (pixman_trapezoid_t));
+    if (!trapezoids)
+	return;
+
+    for (i = 0; i < n_tris; ++i)
+	triangle_to_trapezoids (&(tris[i]), trapezoids + 2 * i);
+    
+    pixman_composite_trapezoids (op, src, dst, mask_format,
+				 x_src, y_src, x_dst, y_dst,
+				 n_tris * 2, trapezoids);
+	    
+    free (trapezoids);
+}
diff --git a/pixman/pixman.h b/pixman/pixman.h
index c2f7da3..582d9cf 100644
--- a/pixman/pixman.h
+++ b/pixman/pixman.h
@@ -868,6 +868,7 @@ typedef struct pixman_edge pixman_edge_t;
 typedef struct pixman_trapezoid pixman_trapezoid_t;
 typedef struct pixman_trap pixman_trap_t;
 typedef struct pixman_span_fix pixman_span_fix_t;
+typedef struct pixman_triangle pixman_triangle_t;
 
 /*
  * An edge structure.  This represents a single polygon edge
@@ -895,6 +896,10 @@ struct pixman_trapezoid
     pixman_line_fixed_t	left, right;
 };
 
+struct pixman_triangle
+{
+    pixman_point_fixed_t p1, p2, p3;
+};
 
 /* whether 't' is a well defined not obviously empty trapezoid */
 #define pixman_trapezoid_valid(t)				   \
@@ -960,6 +965,16 @@ void          pixman_composite_trapezoids (pixman_op_t		       op,
 					   int			       y_dst,
 					   int			       n_traps,
 					   pixman_trapezoid_t *	       traps);
+void          pixman_composite_triangles (pixman_op_t		       op,
+					  pixman_image_t *	       src,
+					  pixman_image_t *	       dst,
+					  pixman_format_code_t	       mask_format,
+					  int			       x_src,
+					  int			       y_src,
+					  int			       x_dst,
+					  int			       y_dst,
+					  int			       n_tris,
+					  pixman_triangle_t *	       tris);
     
 PIXMAN_END_DECLS
 
-- 
1.7.3.1