Simplify mesh rasterizer.

Trace edges using floating point without pulling onto pixels.
Use fixedpoint for colors.

1 files changed, 98 insertions, 268 deletions

diff --git a/draw/draw_mesh.c b/draw/draw_mesh.c
index c266bfaa..100a1686 100644
--- a/draw/draw_mesh.c
+++ b/draw/draw_mesh.c
@@ -1,326 +1,156 @@
 #include "fitz-internal.h"
 
-/*
- * polygon clipping
- */
-
-enum { IN, OUT, ENTER, LEAVE };
-enum { MAXV = 3 + 4 };
 enum { MAXN = 2 + FZ_MAX_COLORS };
 
-static inline void copy_vert(float *dst, const float *src, int n)
-{
-	while (n--)
-		*dst++ = *src++;
-}
-
-static int clipx(float val, int ismax, const float *v1, const float *v2, int n, float *dst)
+static void paint_scan(fz_pixmap *restrict pix, int y, int fx0, int fx1, int cx0, int cx1, const int *restrict v0, const int *restrict v1, int n)
 {
-	float t;
-	int i;
-
-	int v1o = ismax ? v1[0] > val : v1[0] < val;
-	int v2o = ismax ? v2[0] > val : v2[0] < val;
-
-	if (v1o + v2o == 0)
-	{
-		/* Both ends of the line are valid - keep v2, v1 will be kept by another call */
-		copy_vert(dst, v2, n);
-		return 1;
-	}
-
-	if (v1o + v2o == 2)
-		/* Both ends are invalid - drop both */
-		return 0;
-
-	/* It is tempting to spot that the second intersection finding
-	 * operation below can be reversed so that it's in the same form as
-	 * the first one. Do not do this, as the vagaries of floating point
-	 * maths means we get nasty rounding problems. */
-	if (v2o)
-	{
-		/* v1 valid, v2 invalid - Keep intersection */
-		t = (val - v1[0]) / (v2[0] - v1[0]);
-		dst[0] = val;
-		dst[1] = v1[1] + t * (v2[1] - v1[1]);
-		for (i = 2; i < n; i++)
-			dst[i] = v1[i] + t * (v2[i] - v1[i]);
-		return 1;
-	}
-	else
-	{
-		/* v2 valid, v1 invalid - Keep intersection, plus v2 */
-		t = (val - v2[0]) / (v1[0] - v2[0]);
-		dst[0] = val;
-		dst[1] = v2[1] + t * (v1[1] - v2[1]);
-		dst[MAXN] = v2[0];
-		dst[MAXN+1] = v2[1];
-		for (i = 2; i < n; i++)
-		{
-			dst[i] = v2[i] + t * (v1[i] - v2[i]);
-			dst[i+MAXN] = v2[i];
-		}
-		return 2;
-	}
-}
-
-static int clipy(float val, int ismax, const float *v1, const float *v2, int n, float *dst)
-{
-	float t;
-	int i;
-
-	int v1o = ismax ? v1[1] > val : v1[1] < val;
-	int v2o = ismax ? v2[1] > val : v2[1] < val;
-
-	if (v1o + v2o == 0)
+	unsigned char *p;
+	int c[MAXN], dc[MAXN];
+	int k, w;
+	float div, mul;
+	int x0, x1;
+
+	/* Ensure that fx0 is left edge, and fx1 is right */
+	if (fx0 > fx1)
 	{
-		/* Both ends of the line are valid - keep v2, v1 will be kept by another call */
-		copy_vert(dst, v2, n);
-		return 1;
+		const int *v;
+		int t = fx0; fx0 = fx1; fx1 = t;
+		v = v0; v0 = v1; v1 = v;
 	}
+	else if (fx0 == fx1)
+		return;
 
-	if (v1o + v2o == 2)
-		/* Both ends are invalid - drop both */
-		return 0;
-
-	/* It is tempting to spot that the second intersection finding
-	 * operation below can be reversed so that it's in the same form as
-	 * the first one. Do not do this, as the vagaries of floating point
-	 * maths means we get nasty rounding problems. */
-	if (v2o)
-	{
-		/* v1 valid, v2 invalid - Keep intersection */
-		t = (val - v1[1]) / (v2[1] - v1[1]);
-		dst[0] = v1[0] + t * (v2[0] - v1[0]);
-		dst[1] = val;
-		for (i = 2; i < n; i++)
-			dst[i] = v1[i] + t * (v2[i] - v1[i]);
-		return 1;
-	}
-	else
-	{
-		/* v2 valid, v1 invalid - Keep intersection, plus v2 */
-		t = (val - v2[1]) / (v1[1] - v2[1]);
-		dst[0] = v2[0] + t * (v1[0] - v2[0]);
-		dst[1] = val;
-		dst[MAXN] = v2[0];
-		dst[MAXN+1] = v2[1];
-		for (i = 2; i < n; i++)
-		{
-			dst[i] = v2[i] + t * (v1[i] - v2[i]);
-			dst[i+MAXN] = v2[i];
-		}
-		return 2;
-	}
-}
-
-static int clip_poly(float src[MAXV][MAXN],
-	float dst[MAXV][MAXN], int len, int n,
-	float val, int isy, int ismax)
-{
-	int v1, v2, cp;
-
-	v1 = len - 1;
-	cp = 0;
-
-	if (isy)
-	{
-		for (v2 = 0; v2 < len; v2++)
-		{
-			cp += clipy(val, ismax, src[v1], src[v2], n, dst[cp]);
-			v1 = v2;
-		}
-	}
-	else
-	{
-		for (v2 = 0; v2 < len; v2++)
-		{
-			cp += clipx(val, ismax, src[v1], src[v2], n, dst[cp]);
-			v1 = v2;
-		}
-	}
-
-	return cp;
-}
-
-/*
- * gouraud shaded polygon scan conversion
- */
-
-static void paint_scan(fz_pixmap *pix, int y, int x1, int x2, int *v1, int *v2, int n)
-{
-	unsigned char *p = pix->samples + (unsigned int)(((y - pix->y) * pix->w + (x1 - pix->x)) * pix->n);
-	int v[FZ_MAX_COLORS];
-	int dv[FZ_MAX_COLORS];
-	int w = x2 - x1;
-	int k;
-
-	assert(w >= 0);
-	assert(y >= pix->y);
-	assert(y < pix->y + pix->h);
-	assert(x1 >= pix->x);
-	assert(x2 <= pix->x + pix->w);
+	/* Clip fx0, fx1 to range */
+	if (fx0 >= cx1)
+		return;
+	if (fx1 <= cx0)
+		return;
+	x0 = (fx0 > cx0 ? fx0 : cx0);
+	x1 = (fx1 < cx1 ? fx1 : cx1);
 
+	w = x1 - x0;
 	if (w == 0)
 		return;
 
+	div = 1.0f / (fx1 - fx0);
+	mul = (x0 - fx0);
 	for (k = 0; k < n; k++)
 	{
-		v[k] = v1[k];
-		dv[k] = (v2[k] - v1[k]) / w;
+		dc[k] = (v1[k] - v0[k]) * div;
+		c[k] = v0[k] + dc[k] * mul;
 	}
 
+	p = pix->samples + ((x0 - pix->x) + (y - pix->y) * pix->w) * pix->n;
 	while (w--)
 	{
 		for (k = 0; k < n; k++)
 		{
-			*p++ = v[k] >> 16;
-			v[k] += dv[k];
+			*p++ = c[k]>>16;
+			c[k] += dc[k];
 		}
 		*p++ = 255;
 	}
 }
 
-static int find_next(int gel[MAXV][MAXN], int len, int a, int *s, int *e, int d)
-{
-	int b;
+typedef struct edge_data_s edge_data;
 
-	while (1)
-	{
-		b = a + d;
-		if (b == len)
-			b = 0;
-		if (b == -1)
-			b = len - 1;
+struct edge_data_s
+{
+	float x;
+	float dx;
+	int v[2*MAXN];
+};
 
-		if (gel[b][1] == gel[a][1])
-		{
-			a = b;
-			continue;
-		}
+static inline void prepare_edge(const float *restrict vtop, const float *restrict vbot, edge_data *restrict edge, float y, int n)
+{
+	float r = 1.0f / (vbot[1] - vtop[1]);
+	float t = (y - vtop[1]) * r;
+	float diff = vbot[0] - vtop[0];
+	int i;
 
-		if (gel[b][1] > gel[a][1])
-		{
-			*s = a;
-			*e = b;
-			return 0;
-		}
+	edge->x = vtop[0] + diff * t;
+	edge->dx = diff * r;
 
-		return 1;
+	for (i = 0; i < n; i++)
+	{
+		diff = vbot[i+2] - vtop[i+2];
+		edge->v[i] = (int)(65536.0f * (vtop[i+2] + diff * t));
+		edge->v[i+MAXN] = (int)(65536.0f * diff * r);
 	}
 }
 
-static void load_edge(int gel[MAXV][MAXN], int s, int e, int *ael, int *del, int n)
+static inline void step_edge(edge_data *edge, int n)
 {
-	int swp, k, dy;
-
-	if (gel[s][1] > gel[e][1])
-	{
-		swp = s; s = e; e = swp;
-	}
+	int i;
 
-	dy = gel[e][1] - gel[s][1];
+	edge->x += edge->dx;
 
-	ael[0] = gel[s][0];
-	del[0] = (gel[e][0] - gel[s][0]) / dy;
-	for (k = 2; k < n; k++)
+	for (i = 0; i < n; i++)
 	{
-		ael[k] = gel[s][k];
-		del[k] = (gel[e][k] - gel[s][k]) / dy;
+		edge->v[i] += edge->v[i + MAXN];
 	}
 }
 
-static inline void step_edge(int *ael, int *del, int n)
-{
-	int k;
-	ael[0] += del[0];
-	for (k = 2; k < n; k++)
-		ael[k] += del[k];
-}
-
 static void
-fz_paint_triangle(fz_pixmap *pix, float poly_in[3][MAXN], int n, const fz_irect *bbox)
+fz_paint_triangle(fz_pixmap *pix, float v[3][MAXN], int n, const fz_irect *bbox)
 {
-	float poly[MAXV][MAXN];
-	float temp[MAXV][MAXN];
-	float cx0 = bbox->x0;
-	float cy0 = bbox->y0;
-	float cx1 = bbox->x1;
-	float cy1 = bbox->y1;
-
-	int gel[MAXV][MAXN];
-	int ael[2][MAXN];
-	int del[2][MAXN];
-	int y, s0, s1, e0, e1;
-	int top, bot, len;
-
-	int i, k;
-
-	len = clip_poly(poly_in, temp, 3, n, cx0, 0, 0);
-	len = clip_poly(temp, poly, len, n, cx1, 0, 1);
-	len = clip_poly(poly, temp, len, n, cy0, 1, 0);
-	len = clip_poly(temp, poly, len, n, cy1, 1, 1);
-
-	if (len < 3)
-		return;
-
-	for (i = 0; i < len; i++)
-	{
-		gel[i][0] = floorf(poly[i][0] + 0.5f) * 65536; /* trunc and fix */
-		gel[i][1] = floorf(poly[i][1] + 0.5f); /* y is not fixpoint */
-		for (k = 2; k < n; k++)
-			gel[i][k] = poly[i][k] * 65536; /* fix with precision */
-	}
+	edge_data e0, e1;
+	int top, mid, bot;
+	float y, y1;
+	int minx, maxx;
 
 	top = bot = 0;
-	for (i = 0; i < len; i++)
-	{
-		if (gel[i][1] < gel[top][1])
-			top = i;
-		if (gel[i][1] > gel[bot][1])
-			bot = i;
-	}
+	if (v[1][1] < v[0][1]) top = 1; else bot = 1;
+	if (v[2][1] < v[top][1]) top = 2;
+	else if (v[2][1] > v[bot][1]) bot = 2;
+	if (v[top][1] == v[bot][1]) return;
 
-	if (gel[bot][1] - gel[top][1] == 0)
-		return;
+	/* Test if the triangle is completely outside the scissor rect */
+	if (v[bot][1] < bbox->y0) return;
+	if (v[top][1] > bbox->y1) return;
 
-	y = gel[top][1];
+	/* Magic! Ensure that mid/top/bot are all different */
+	mid = 3^top^bot;
 
-	if (find_next(gel, len, top, &s0, &e0, 1))
-		return;
-	if (find_next(gel, len, top, &s1, &e1, -1))
-		return;
+	assert(top != bot && top != mid && mid != bot);
 
-	load_edge(gel, s0, e0, ael[0], del[0], n);
-	load_edge(gel, s1, e1, ael[1], del[1], n);
+	minx = fz_maxi(bbox->x0, pix->x);
+	maxx = fz_mini(bbox->x1, pix->x + pix->w);
 
-	while (1)
-	{
-		int x0 = ael[0][0] >> 16;
-		int x1 = ael[1][0] >> 16;
+	y = ceilf(fz_max(bbox->y0, v[top][1]));
+	y1 = ceilf(fz_min(bbox->y1, v[mid][1]));
 
-		if (ael[0][0] < ael[1][0])
-			paint_scan(pix, y, x0, x1, ael[0]+2, ael[1]+2, n-2);
-		else
-			paint_scan(pix, y, x1, x0, ael[1]+2, ael[0]+2, n-2);
-
-		step_edge(ael[0], del[0], n);
-		step_edge(ael[1], del[1], n);
-		y ++;
+	n -= 2;
+	prepare_edge(v[top], v[bot], &e0, y, n);
+	if (y < y1)
+	{
+		prepare_edge(v[top], v[mid], &e1, y, n);
 
-		if (y >= gel[e0][1])
+		do
 		{
-			if (find_next(gel, len, e0, &s0, &e0, 1))
-				return;
-			load_edge(gel, s0, e0, ael[0], del[0], n);
+			paint_scan(pix, y, (int)e0.x, (int)e1.x, minx, maxx, &e0.v[0], &e1.v[0], n);
+			step_edge(&e0, n);
+			step_edge(&e1, n);
+			y ++;
 		}
+		while (y < y1);
+	}
+
+	y1 = ceilf(fz_min(bbox->y1, v[bot][1]));
+	if (y < y1)
+	{
+		prepare_edge(v[mid], v[bot], &e1, y, n);
 
-		if (y >= gel[e1][1])
+		do
 		{
-			if (find_next(gel, len, e1, &s1, &e1, -1))
-				return;
-			load_edge(gel, s1, e1, ael[1], del[1], n);
+			paint_scan(pix, y, (int)e0.x, (int)e1.x, minx, maxx, &e0.v[0], &e1.v[0], n);
+			y ++;
+			if (y >= y1)
+				break;
+			step_edge(&e0, n);
+			step_edge(&e1, n);
 		}
+		while (1);
 	}
 }