Fix and test line drawing

Signed-off-by: Mattias Andrée <maandree@kth.se>

5 files changed, 140 insertions, 95 deletions

diff --git a/common.h b/common.h
index 80f807c..1c589be 100644
--- a/common.h
+++ b/common.h
@@ -145,12 +145,6 @@ tolerant_eq(double a, double b)
 	return iszeroish((a - b) / 100.0);
 }
 
-static inline int
-intolerant_eq(double a, double b)
-{
-	return fabs(a - b) < 1e-11;
-}
-
 # define ASSERT(ASSERTION)\
 	do {\
 		if (!(ASSERTION)) {\
diff --git a/draw_linear_bezier_reference.c b/draw_linear_bezier_reference.c
index dbfb87f..b7dab11 100644
--- a/draw_linear_bezier_reference.c
+++ b/draw_linear_bezier_reference.c
@@ -14,86 +14,94 @@
  */
 
 
+static void
+draw_cell(RASTER *restrict raster, double x1, double y1, double x2, double y2, double dx, double dy,
+          double cxmin, double cxmax, double rxmin, double rxmax, double rymin, double rymax, ssize_t x, size_t cellY)
+{
+	double cy1, cy2, ydir = (double)SIGNUM(dy);
+	double rightedge, opposite, midadjacent;
+	size_t cell;
+
+	rightedge = cxmax;
+	cxmin = fmax(cxmin, rxmin);
+	cxmax = fmin(cxmax, rxmax);
+	cy1 = dx ? y1 + (cxmin - x1) * dy / dx : y1;
+	cy2 = dx ? y2 + (cxmax - x2) * dy / dx : y2;
+	cy1 = fmin(fmax(cy1, rymin), rymax);
+	cy2 = fmin(fmax(cy2, rymin), rymax);
+
+	opposite = ydir * fabs(cy2 - cy1);
+	midadjacent = (cxmin + cxmax) / 2.0;
+
+	if (x < 0) {
+		raster->cells[cellY].opposite_coverage += opposite;
+		raster->cells[cellY].cell_coverage += opposite;
+	} else if ((size_t)x >= raster->width) {
+		cell = cellY + (raster->width - 1);
+		raster->cells[cell].opposite_coverage += opposite;
+	} else {
+		cell = cellY + (size_t)x;
+		raster->cells[cell].opposite_coverage += opposite;
+		raster->cells[cell].cell_coverage += opposite * fabs(rightedge - midadjacent);
+	}
+}
+
 void
 draw_linear_bezier_reference(RASTER *restrict raster, double x1, double y1, double x2, double y2)
 {
+	ssize_t iwidth = (ssize_t)raster->width;
+	double width = (double)raster->width;
+	double height = (double)raster->height;
 	double dx = x2 - x1;
 	double dy = y2 - y1;
-	int xdir = SIGNUM(dx);
-	int ydir = SIGNUM(dy);
-	double kx = dx / dy;
-	double ky = dy / dx;
-	double prevX, prevY, x, y, cx, cy, h2x, h2y;
-	double xfloor, yfloor;
-	ssize_t cellX, cellY;
-	size_t cell;
-
-	prevX = x1;
-	prevY = y1;
-
-	for (; prevX != x2 || prevY != y2; prevX = x, prevY = y) {
-		/* Find next vertical and next hozitonal grid line */
-		x = xdir < 0 ? floor(prevX) : xdir > 0 ? ceil(prevX) : prevX;
-		y = ydir < 0 ? floor(prevY) : ydir > 0 ? ceil(prevY) : prevY;
-		x = iszeroish(x - prevX) ? x + xdir : x;
-		y = iszeroish(y - prevY) ? y + ydir : y;
-
-		/* Limit to the extend of the drawn line segment */
-		if ((xdir < 0 && x < x2) || (xdir > 0 && x > x2))
-			x = x2;
-		if ((ydir < 0 && y < y2) || (ydir > 0 && y > y2))
-			y = y2;
-
-		/* Find next cell edge */
-		if (xdir && ydir) {
-			cy = y1 + (x - x1) * ky;
-			cx = x1 + (y - y1) * kx;
-			h2x = (cy - prevY) * (cy - prevY) + (x - prevX) * (x - prevX);
-			h2y = (cx - prevX) * (cx - prevX) + (y - prevY) * (y - prevY);
-			if (h2x < h2y)
-				y = cy;
-			else
-				x = cx;
-
-			/* Make sure loop will exit when we reach the end */
-			if ((xdir < 0 && x <= x2) || (xdir > 0 && x >= x2) ||
-			    (ydir < 0 && y <= y2) || (ydir > 0 && y >= y2)) {
-				x = x2;
-				y = y2;
-			}
+	double fymin = fmin(fmax(fmin(y1, y2), 0.0), height);
+	double fymax = fmin(fmax(fmax(y1, y2), 0.0), height);
+	double floor_fymin = floor(fymin);
+	double ceil_fymax = ceil(fymax);
+	size_t ymin = (size_t)floor_fymin;
+	size_t ymax = (size_t)ceil_fymax;
+	size_t y, cellY;
+	double rowx1, rowx2;
+	double rxmin, rxmax, floor_rxmin;
+	double rymax, rymin, ceil_rxmax;
+	ssize_t x, xmin, xmax, xmin_cropped, xmax_cropped;
+	double cxmin, cxmax;
+
+	ymax += (size_t)(ymax == ymin);
+	for (y = ymin; y < ymax; y++) {
+		rymin = (double)y;
+		rymax = (double)y + 1.0;
+		rymin = fmax(rymin, fymin);
+		rymax = fmin(rymax, fymax);
+		rowx1 = dy ? x1 + (rymin - y1) * dx / dy : x1;
+		rowx2 = dy ? x2 + (rymax - y2) * dx / dy : x2;
+		rxmin = fmin(rowx1, rowx2);
+		rxmax = fmax(rowx1, rowx2);
+		cellY = y * raster->width;
+
+		floor_rxmin = floor(rxmin);
+		ceil_rxmax = ceil(rxmax);
+		xmin = (ssize_t)floor_rxmin;
+		xmax = (ssize_t)ceil_rxmax;
+		xmax += (ssize_t)(xmax == xmin);
+		xmin_cropped = xmin;
+		xmax_cropped = xmax;
+		if (xmin < 0.0) {
+			cxmin = (double)xmin;
+			cxmax = xmax < 0 ? (double)(xmax + 1) : 0.0;
+			draw_cell(raster, x1, y1, x2, y2, dx, dy, cxmin, cxmax, rxmin, rxmax, rymin, rymax, xmin, cellY);
+			xmin_cropped = 0;
 		}
-
-		/* Select cell to draw in */
-		xfloor = xdir >= 0 ? floor(prevX) : floor(x);
-		yfloor = ydir >= 0 ? floor(prevY) : floor(y);
-		cellX = (ssize_t)xfloor;
-		cellY = (ssize_t)yfloor;
-
-		/* Do not draw if above or below the raster */
-		if (cellY < 0 || (size_t)cellY >= raster->height)
-			continue;
-
-		if (cellX < 0) {
-			/* Draw on first column in raster of outside of raster on the left side,
-			 * with full horizontal coverage, `.opposite_coverage` one the actual
-			 * cell (outside of the raster) will contribute to the first column's
-			 * `.cell_coverage` */
-			cell = (size_t)cellY * raster->width;
-			raster->cells[cell].opposite_coverage += y - prevY;
-			raster->cells[cell].cell_coverage += y - prevY;
-
-		} else if ((size_t)cellX >= raster->width) {
-			/* If outside of the raster, on the right side, add to the last
-			 * columns contributions to the next column, so that the ink level
-			 * balances out to zero */
-			cell = (size_t)cellY * raster->width + (raster->width - 1);
-			raster->cells[cell].opposite_coverage += y - prevY;
-
-		} else {
-			/* If inside the raster, just draw the line */
-			cell = (size_t)cellY * raster->width + (size_t)cellX;
-			raster->cells[cell].opposite_coverage += y - prevY;
-			raster->cells[cell].cell_coverage += (y - prevY) * fabs(xfloor + 1.0 - (x + prevX) / 2.0);
+		if (xmax > iwidth) {
+			cxmin = fmax(floor_rxmin, width);
+			cxmax = (double)xmax;
+			draw_cell(raster, x1, y1, x2, y2, dx, dy, cxmin, cxmax, rxmin, rxmax, rymin, rymax, (ssize_t)cxmin, cellY);
+			xmax_cropped = iwidth;
+		}
+		for (x = xmin_cropped; x < xmax_cropped; x++) {
+			cxmin = (double)x;
+			cxmax = (double)x + 1.0;
+			draw_cell(raster, x1, y1, x2, y2, dx, dy, cxmin, cxmax, rxmin, rxmax, rymin, rymax, x, cellY);
 		}
 	}
 }
diff --git a/equations.c b/equations.c
index 571fc26..2cf8bc9 100644
--- a/equations.c
+++ b/equations.c
@@ -302,6 +302,8 @@ check_cubic(double r1, double i1, double r2, double i2, double r3, double i3, do
 	for (i = 0; i < sizeof(found) / sizeof(*found); i++)
 		found[i] = (i >= nexpected || expected[i] < 0.0 + TOLERANCE || expected[i] > 1.0 - TOLERANCE);
 	if (!nexpected) {
+		if (!ngot) /* FIXME */
+			fprintf(stderr, "%lg, %lg, %lg, %lg, %lg, %lg, %lg, %i\n", r1, i1, r2, i2, r3, i3, k, strict_real);
 		ASSERT(!ngot);
 		return;
 	}
diff --git a/lines.c b/lines.c
index 4ac624a..a2e87be 100644
--- a/lines.c
+++ b/lines.c
@@ -242,8 +242,8 @@ check_against_reference(double x1, double y1, double x2, double y2)
 	draw_linear_bezier_reference(refraster, x1, y1, x2, y2);
 	alarm(0);
 	for (i = 0; i < 100; i++) {
-		ASSERT(intolerant_eq(raster->cells[i].cell_coverage, refraster->cells[i].cell_coverage));
-		ASSERT(intolerant_eq(raster->cells[i].opposite_coverage, refraster->cells[i].opposite_coverage));
+		ASSERT(eq(raster->cells[i].cell_coverage, refraster->cells[i].cell_coverage));
+		ASSERT(eq(raster->cells[i].opposite_coverage, refraster->cells[i].opposite_coverage));
 	}
 }
 
diff --git a/rtgrpblib_draw_linear_bezier.c b/rtgrpblib_draw_linear_bezier.c
index bf9d41e..a2af58f 100644
--- a/rtgrpblib_draw_linear_bezier.c
+++ b/rtgrpblib_draw_linear_bezier.c
@@ -127,24 +127,65 @@ static RASTER *raster;
 static RASTER *refraster;
 
 
+#ifdef ROWWISE_RESET_INKLEVEL
 static void
-check_draw_linear_bezier(double x1, double y1, double x2, double y2)
+draw_right_edge_shadow(double x1, double y1, double x2, double y2)
+{
+	if (raster->draftness <= 0)
+		return;
+
+	if (x1 >= 10.0 && x2 >= 10.0) {
+		draw_linear_bezier_reference(raster, x1, y1, x2, y2);
+
+	} else if (x1 >= 10.0) {
+		y2 = y2 + (10.0 - x2) * (y2 - y1) / (x2 - x1);
+		x2 = 10.0;
+		draw_linear_bezier_reference(raster, x1, y1, x2, y2);
+
+	} else if (x2 >= 10.0) {
+		y1 = y1 + (10.0 - x1) * (y2 - y1) / (x2 - x1);
+		x1 = 10.0;
+		draw_linear_bezier_reference(raster, x1, y1, x2, y2);
+	}
+}
+#endif
+
+
+static void
+proper_check_draw_linear_bezier(double x1, double y1, double x2, double y2)
 {
 	size_t i;
+
 	alarm(5);
 	rtgrpblib_draw_linear_bezier(raster, x1, y1, x2, y2);
+#ifdef ROWWISE_RESET_INKLEVEL
+	draw_right_edge_shadow(x1, y1, x2, y2);
+#endif
+
 	alarm(5);
 	draw_linear_bezier_reference(refraster, x1, y1, x2, y2);
+
 	alarm(0);
+
 	for (i = 0; i < 100; i++) {
-		ASSERT(intolerant_eq(raster->cells[i].cell_coverage, refraster->cells[i].cell_coverage));
-		ASSERT(intolerant_eq(raster->cells[i].opposite_coverage, refraster->cells[i].opposite_coverage));
+		ASSERT(eq(raster->cells[i].cell_coverage, refraster->cells[i].cell_coverage));
+		ASSERT(eq(raster->cells[i].opposite_coverage, refraster->cells[i].opposite_coverage));
 	}
 	rtgrpblib_reset_raster(raster, 10, 10);
 	rtgrpblib_reset_raster(refraster, 10, 10);
 }
 
 
+static void
+check_draw_linear_bezier(double x1, double y1, double x2, double y2)
+{
+	proper_check_draw_linear_bezier(floor(x1), floor(y1), floor(x2), floor(y2));
+	proper_check_draw_linear_bezier(floor(x1), y1, floor(x2), y2);
+	proper_check_draw_linear_bezier(x1, floor(y1), x2, floor(y2));
+	proper_check_draw_linear_bezier(x1, y1, x2, y2);
+}
+
+
 static double
 frand(double a, double b)
 {
@@ -169,26 +210,26 @@ main(void)
 	ASSERT(refraster);
 	srand((unsigned)(uintptr_t)raster);
 
-	for (i = 0; i < 10000UL; i++) {
-#ifndef ROWWISE_RESET_INKLEVEL
+	for (i = 0; i < 50000UL; i++) {
 		x1 = frand(-5, 15);
 		y1 = frand(-5, 15);
 		x2 = frand(-5, 15);
 		y2 = frand(-5, 15);
-#else
-		/* TODO add tests the support higher upper bound */
-		x1 = frand(0, 10); /* TODO fix lower bound */
-		y1 = frand(-5, 15);
-		x2 = frand(-5, 10);
-		y2 = frand(-5, 15);
-#endif
 
 		check_draw_linear_bezier(x1, y1, x2, y2);
 		check_draw_linear_bezier(x1, x1, x2, x2);
+		check_draw_linear_bezier(x1, y1, x2, y1);
 		check_draw_linear_bezier(x1, x2, x2, x1);
+		check_draw_linear_bezier(x1, y1, x1, y2);
+		check_draw_linear_bezier(x1, x1, x1, x1);
+		raster->draftness = -1;
+		check_draw_linear_bezier(x1, y1, x2, y2);
+		check_draw_linear_bezier(x1, x1, x2, x2);
 		check_draw_linear_bezier(x1, y1, x2, y1);
+		check_draw_linear_bezier(x1, x2, x2, x1);
 		check_draw_linear_bezier(x1, y1, x1, y2);
-		/* TODO test with zero draftness */
+		check_draw_linear_bezier(x1, x1, x1, x1);
+		raster->draftness = 0.5;
 	}
 
 	free(raster);