Add draw_linear_bezier_reference

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

5 files changed, 129 insertions, 5 deletions

diff --git a/Makefile b/Makefile
index 322c783..370c2fe 100644
--- a/Makefile
+++ b/Makefile
@@ -20,6 +20,7 @@ OBJ =\
 	equations.o\
 	lines.o\
 	sorting.o\
+	draw_linear_bezier_reference.o\
 	rtgrpblib_create_raster.o\
 	rtgrpblib_draw_circular_arc.o\
 	rtgrpblib_draw_linear_bezier.o\
diff --git a/common.h b/common.h
index ae9a1d7..2436a6a 100644
--- a/common.h
+++ b/common.h
@@ -83,6 +83,11 @@ iszeroish(double x)
 
 
 
+/* draw_linear_bezier_reference.c */
+#define draw_linear_bezier_reference rtgrpblib_draw_linear_bezier_reference__
+void draw_linear_bezier_reference(RASTER *restrict raster, double x1, double y1, double x2, double y2);
+
+
 /* equations.c */
 #define solve_cubic rtgrpblib_solve_cubic__
 #define solve_quadratic rtgrpblib_solve_quadratic__
diff --git a/demo.c b/demo.c
index 6157fbd..ff6ed3a 100644
--- a/demo.c
+++ b/demo.c
@@ -21,12 +21,12 @@ main(void)
 		{30, 15},
 		{20, 25},
 		{10, 15}
-#elif 0
+#elif 1
 		{20, 5},
 		{35, 15},
 		{20, 25},
 		{5, 15}
-#elif 0
+#elif 1
 		{5.25, 5.25},
 		{35.75, 5.25},
 		{35.75, 25.75},
@@ -42,16 +42,18 @@ main(void)
 	raster = rtgrpblib_create_raster(width, height);
 	image  = calloc(width * height, sizeof(*image));
 
-#if 0
+	rtgrpblib_set_draftness(raster, -1);
+
+#if 1
 	n = sizeof(points) / sizeof(*points);
 	for (i = 0; i < n; i++) {
 		j = (i + 1) % n;
 		rtgrpblib_draw_linear_bezier(raster, P(i), P(j));
 	}
-#elif 0
+#elif 1
 	rtgrpblib_draw_quadratic_bezier(raster, P(2), P(3), P(0));
 	rtgrpblib_draw_linear_bezier(raster, P(0), P(2));
-#elif 0
+#elif 1
 	rtgrpblib_draw_cubic_bezier(raster, P(0), P(1), P(2), P(3));
 	rtgrpblib_draw_linear_bezier(raster, P(3), P(0));
 #else
diff --git a/draw_linear_bezier_reference.c b/draw_linear_bezier_reference.c
new file mode 100644
index 0000000..6066946
--- /dev/null
+++ b/draw_linear_bezier_reference.c
@@ -0,0 +1,111 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+#ifndef TEST
+
+/*
+ * The implementation in this fill is not supposed to be fast,
+ * it is supposed to be absolutely correct. The implementation
+ * shall be as clear and obvious as possible. It is important
+ * that everything written to cells is as precise as possible
+ * and that the function behavious correctly when outside the
+ * raster. This implementation shall be usable to generate an
+ * as perfect as possible rasterisation and shall be usable to
+ * test the correctness and accuracy of the fast implementation.
+ */
+
+
+void
+draw_linear_bezier_reference(RASTER *restrict raster, double x1, double y1, double x2, double y2)
+{
+	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 = x == prevX ? x + xdir : x;
+		y = 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))
+				x = x2;
+			if ((ydir < 0 && y < y2) || (ydir > 0 && y > y2))
+				y = y2;
+		}
+
+		/* 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(fmax(ceil(x), ceil(prevX)) - (x + prevX) / 2.0);
+		}
+	}
+}
+
+
+#else
+
+
+int
+main(void)
+{
+	return 0; /* TODO add test */
+}
+
+
+#endif
diff --git a/rtgrpblib_draw_linear_bezier.c b/rtgrpblib_draw_linear_bezier.c
index 5c83591..ba8dc48 100644
--- a/rtgrpblib_draw_linear_bezier.c
+++ b/rtgrpblib_draw_linear_bezier.c
@@ -9,6 +9,11 @@ rtgrpblib_draw_linear_bezier(RASTER *restrict raster, double x1, double y1, doub
 	double w, h, dx, dy, x, y;
 	int xdir, ydir;
 
+	if (raster->draftness <= 0) {
+		draw_linear_bezier_reference(raster, x1, y1, x2, y2);
+		return;
+	}
+
 	dx = x2 - x1;
 	dy = y2 - y1;
 	xdir = SIGNUM(dx);