1 files changed, 317 insertions, 0 deletions
diff --git a/src/vertex-clipping.c b/src/vertex-clipping.c
new file mode 100644
index 00000000..603ce6f4
--- /dev/null
+++ b/src/vertex-clipping.c
@@ -0,0 +1,317 @@
+/*
+ * Copyright © 2012 Intel Corporation
+ *
+ * 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 the copyright holders not be used in
+ * advertising or publicity pertaining to distribution of the software
+ * without specific, written prior permission.  The copyright holders make
+ * no representations about the suitability of this software for any
+ * purpose.  It is provided "as is" without express or implied warranty.
+ *
+ * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS
+ * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS, IN NO EVENT SHALL THE COPYRIGHT HOLDERS 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 <assert.h>
+#include <float.h>
+#include <math.h>
+
+#include <GLES2/gl2.h>
+
+#include "vertex-clipping.h"
+
+GLfloat
+float_difference(GLfloat a, GLfloat b)
+{
+	/* http://www.altdevblogaday.com/2012/02/22/comparing-floating-point-numbers-2012-edition/ */
+	static const GLfloat max_diff = 4.0f * FLT_MIN;
+	static const GLfloat max_rel_diff = 4.0e-5;
+	GLfloat diff = a - b;
+	GLfloat adiff = fabsf(diff);
+
+	if (adiff <= max_diff)
+		return 0.0f;
+
+	a = fabsf(a);
+	b = fabsf(b);
+	if (adiff <= (a > b ? a : b) * max_rel_diff)
+		return 0.0f;
+
+	return diff;
+}
+
+/* A line segment (p1x, p1y)-(p2x, p2y) intersects the line x = x_arg.
+ * Compute the y coordinate of the intersection.
+ */
+static GLfloat
+clip_intersect_y(GLfloat p1x, GLfloat p1y, GLfloat p2x, GLfloat p2y,
+		 GLfloat x_arg)
+{
+	GLfloat a;
+	GLfloat diff = float_difference(p1x, p2x);
+
+	/* Practically vertical line segment, yet the end points have already
+	 * been determined to be on different sides of the line. Therefore
+	 * the line segment is part of the line and intersects everywhere.
+	 * Return the end point, so we use the whole line segment.
+	 */
+	if (diff == 0.0f)
+		return p2y;
+
+	a = (x_arg - p2x) / diff;
+	return p2y + (p1y - p2y) * a;
+}
+
+/* A line segment (p1x, p1y)-(p2x, p2y) intersects the line y = y_arg.
+ * Compute the x coordinate of the intersection.
+ */
+static GLfloat
+clip_intersect_x(GLfloat p1x, GLfloat p1y, GLfloat p2x, GLfloat p2y,
+		 GLfloat y_arg)
+{
+	GLfloat a;
+	GLfloat diff = float_difference(p1y, p2y);
+
+	/* Practically horizontal line segment, yet the end points have already
+	 * been determined to be on different sides of the line. Therefore
+	 * the line segment is part of the line and intersects everywhere.
+	 * Return the end point, so we use the whole line segment.
+	 */
+	if (diff == 0.0f)
+		return p2x;
+
+	a = (y_arg - p2y) / diff;
+	return p2x + (p1x - p2x) * a;
+}
+
+enum path_transition {
+	PATH_TRANSITION_OUT_TO_OUT = 0,
+	PATH_TRANSITION_OUT_TO_IN = 1,
+	PATH_TRANSITION_IN_TO_OUT = 2,
+	PATH_TRANSITION_IN_TO_IN = 3,
+};
+
+static void
+clip_append_vertex(struct clip_context *ctx, GLfloat x, GLfloat y)
+{
+	*ctx->vertices.x++ = x;
+	*ctx->vertices.y++ = y;
+}
+
+static enum path_transition
+path_transition_left_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
+{
+	return ((ctx->prev.x >= ctx->clip.x1) << 1) | (x >= ctx->clip.x1);
+}
+
+static enum path_transition
+path_transition_right_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
+{
+	return ((ctx->prev.x < ctx->clip.x2) << 1) | (x < ctx->clip.x2);
+}
+
+static enum path_transition
+path_transition_top_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
+{
+	return ((ctx->prev.y >= ctx->clip.y1) << 1) | (y >= ctx->clip.y1);
+}
+
+static enum path_transition
+path_transition_bottom_edge(struct clip_context *ctx, GLfloat x, GLfloat y)
+{
+	return ((ctx->prev.y < ctx->clip.y2) << 1) | (y < ctx->clip.y2);
+}
+
+static void
+clip_polygon_leftright(struct clip_context *ctx,
+		       enum path_transition transition,
+		       GLfloat x, GLfloat y, GLfloat clip_x)
+{
+	GLfloat yi;
+
+	switch (transition) {
+	case PATH_TRANSITION_IN_TO_IN:
+		clip_append_vertex(ctx, x, y);
+		break;
+	case PATH_TRANSITION_IN_TO_OUT:
+		yi = clip_intersect_y(ctx->prev.x, ctx->prev.y, x, y, clip_x);
+		clip_append_vertex(ctx, clip_x, yi);
+		break;
+	case PATH_TRANSITION_OUT_TO_IN:
+		yi = clip_intersect_y(ctx->prev.x, ctx->prev.y, x, y, clip_x);
+		clip_append_vertex(ctx, clip_x, yi);
+		clip_append_vertex(ctx, x, y);
+		break;
+	case PATH_TRANSITION_OUT_TO_OUT:
+		/* nothing */
+		break;
+	default:
+		assert(0 && "bad enum path_transition");
+	}
+
+	ctx->prev.x = x;
+	ctx->prev.y = y;
+}
+
+static void
+clip_polygon_topbottom(struct clip_context *ctx,
+		       enum path_transition transition,
+		       GLfloat x, GLfloat y, GLfloat clip_y)
+{
+	GLfloat xi;
+
+	switch (transition) {
+	case PATH_TRANSITION_IN_TO_IN:
+		clip_append_vertex(ctx, x, y);
+		break;
+	case PATH_TRANSITION_IN_TO_OUT:
+		xi = clip_intersect_x(ctx->prev.x, ctx->prev.y, x, y, clip_y);
+		clip_append_vertex(ctx, xi, clip_y);
+		break;
+	case PATH_TRANSITION_OUT_TO_IN:
+		xi = clip_intersect_x(ctx->prev.x, ctx->prev.y, x, y, clip_y);
+		clip_append_vertex(ctx, xi, clip_y);
+		clip_append_vertex(ctx, x, y);
+		break;
+	case PATH_TRANSITION_OUT_TO_OUT:
+		/* nothing */
+		break;
+	default:
+		assert(0 && "bad enum path_transition");
+	}
+
+	ctx->prev.x = x;
+	ctx->prev.y = y;
+}
+
+static void
+clip_context_prepare(struct clip_context *ctx, const struct polygon8 *src,
+		      GLfloat *dst_x, GLfloat *dst_y)
+{
+	ctx->prev.x = src->x[src->n - 1];
+	ctx->prev.y = src->y[src->n - 1];
+	ctx->vertices.x = dst_x;
+	ctx->vertices.y = dst_y;
+}
+
+static int
+clip_polygon_left(struct clip_context *ctx, const struct polygon8 *src,
+		  GLfloat *dst_x, GLfloat *dst_y)
+{
+	enum path_transition trans;
+	int i;
+
+	clip_context_prepare(ctx, src, dst_x, dst_y);
+	for (i = 0; i < src->n; i++) {
+		trans = path_transition_left_edge(ctx, src->x[i], src->y[i]);
+		clip_polygon_leftright(ctx, trans, src->x[i], src->y[i],
+				       ctx->clip.x1);
+	}
+	return ctx->vertices.x - dst_x;
+}
+
+static int
+clip_polygon_right(struct clip_context *ctx, const struct polygon8 *src,
+		   GLfloat *dst_x, GLfloat *dst_y)
+{
+	enum path_transition trans;
+	int i;
+
+	clip_context_prepare(ctx, src, dst_x, dst_y);
+	for (i = 0; i < src->n; i++) {
+		trans = path_transition_right_edge(ctx, src->x[i], src->y[i]);
+		clip_polygon_leftright(ctx, trans, src->x[i], src->y[i],
+				       ctx->clip.x2);
+	}
+	return ctx->vertices.x - dst_x;
+}
+
+static int
+clip_polygon_top(struct clip_context *ctx, const struct polygon8 *src,
+		 GLfloat *dst_x, GLfloat *dst_y)
+{
+	enum path_transition trans;
+	int i;
+
+	clip_context_prepare(ctx, src, dst_x, dst_y);
+	for (i = 0; i < src->n; i++) {
+		trans = path_transition_top_edge(ctx, src->x[i], src->y[i]);
+		clip_polygon_topbottom(ctx, trans, src->x[i], src->y[i],
+				       ctx->clip.y1);
+	}
+	return ctx->vertices.x - dst_x;
+}
+
+static int
+clip_polygon_bottom(struct clip_context *ctx, const struct polygon8 *src,
+		    GLfloat *dst_x, GLfloat *dst_y)
+{
+	enum path_transition trans;
+	int i;
+
+	clip_context_prepare(ctx, src, dst_x, dst_y);
+	for (i = 0; i < src->n; i++) {
+		trans = path_transition_bottom_edge(ctx, src->x[i], src->y[i]);
+		clip_polygon_topbottom(ctx, trans, src->x[i], src->y[i],
+				       ctx->clip.y2);
+	}
+	return ctx->vertices.x - dst_x;
+}
+
+#define max(a, b) (((a) > (b)) ? (a) : (b))
+#define min(a, b) (((a) > (b)) ? (b) : (a))
+#define clip(x, a, b)  min(max(x, a), b)
+
+int
+clip_simple(struct clip_context *ctx,
+	    struct polygon8 *surf,
+	    GLfloat *ex,
+	    GLfloat *ey)
+{
+	int i;
+	for (i = 0; i < surf->n; i++) {
+		ex[i] = clip(surf->x[i], ctx->clip.x1, ctx->clip.x2);
+		ey[i] = clip(surf->y[i], ctx->clip.y1, ctx->clip.y2);
+	}
+	return surf->n;
+}
+
+int
+clip_transformed(struct clip_context *ctx,
+		 struct polygon8 *surf,
+		 GLfloat *ex,
+		 GLfloat *ey)
+{
+	struct polygon8 polygon;
+	int i, n;
+
+	polygon.n = clip_polygon_left(ctx, surf, polygon.x, polygon.y);
+	surf->n = clip_polygon_right(ctx, &polygon, surf->x, surf->y);
+	polygon.n = clip_polygon_top(ctx, surf, polygon.x, polygon.y);
+	surf->n = clip_polygon_bottom(ctx, &polygon, surf->x, surf->y);
+
+	/* Get rid of duplicate vertices */
+	ex[0] = surf->x[0];
+	ey[0] = surf->y[0];
+	n = 1;
+	for (i = 1; i < surf->n; i++) {
+		if (float_difference(ex[n - 1], surf->x[i]) == 0.0f &&
+		    float_difference(ey[n - 1], surf->y[i]) == 0.0f)
+			continue;
+		ex[n] = surf->x[i];
+		ey[n] = surf->y[i];
+		n++;
+	}
+	if (float_difference(ex[n - 1], surf->x[0]) == 0.0f &&
+	    float_difference(ey[n - 1], surf->y[0]) == 0.0f)
+		n--;
+
+	return n;
+}