path: root/src/draw/line.5c

#!/usr/bin/nickle

autoimport Cairo;
autoload PRNG;

int
sign(int x)
{
	return x == 0 ? 0 : x < 0 ? -1 : 1;
}

int X_AXIS = 0;
int Y_AXIS = 1;

typedef struct {
	int	major;
	int	minor;
	int	sign_major;
	int	sign_minor;
	int	e;
	int	e1;
	int	e3;
	bool	first;
} clip_context;

typedef struct {
	int	maj1, min1, maj2, min2;
} clip_box;

typedef struct {
	int	x1, y1, x2, y2;
} box;

typedef struct {
	int	x, y;
} point;

typedef struct {
	int	x1, y1, x2, y2;
	box	b;
	point[]	clipped;
	point[]	run;
} test;

box	bounds = { .x1 = 10, .x2 = 30, .y1 = 10, .y2 = 30 };

int
div_ceil(a, b) {
	a += b;
	assert(a >= 0 && b > 0, "bad divide args %d %d\n", a, b);
	return (a + b - 1) // b - 1;
}

int
div_floor_plus_one(a, b) {
	a += b;
	assert(a >= 0 && b > 0, "bad divide args %d %d\n", a, b);
	return a // b;
}

bool
clip(*clip_context c, *clip_box b)
{
	int	adjust_major = 0, adjust_minor = 0;

	/* Clip major axis */
	if (c->major < b->maj1) {
		if (c->sign_major <= 0)
			return false;
		adjust_major = b->maj1 - c->major;
	} else if (c->major >= b->maj2) {
		if (c->sign_major >= 0)
			return false;
		adjust_major = c->major - (b->maj2-1);
	}

	/* Clip minor axis */
	if (c->minor < b->min1) {
		if (c->sign_minor <= 0)
			return false;
		adjust_minor = b->min1 - c->minor;
	} else if (c->minor >= b->min2) {
		if (c->sign_minor >= 0)
			return false;
		adjust_minor = c->minor - (b->min2-1);
	}

	/* If unclipped, we're done */
	if (adjust_major == 0 && adjust_minor == 0)
		return true;

	/* See how much minor adjustment would happen during
	 * a major clip. This is a bit tricky because line drawing
	 * isn't symmetrical when the line passes exactly between
	 * two pixels, we have to pick which one gets drawn
	 */
	int	adj_min;

	if (!c->first)
		adj_min = div_ceil(c->e + adjust_major * c->e1, -c->e3);
	else
		adj_min = div_floor_plus_one(c->e + adjust_major * c->e1, -c->e3);

	/* Compare that to the minor clip and pick
	 * the larger amount.
	 */
	printf ("\tinitial major %d minor %d error %d e1 %d e3 %d\n", c->major, c->minor, c->e, c->e1, c->e3);

	if (adj_min < adjust_minor) {
		printf("\tminor clip dominates %d < %d. adjust major %d -> ",
		       adj_min, adjust_minor, adjust_major);
		if (c->first)
			adjust_major = div_ceil(c->e - adjust_minor * c->e3, c->e1);
		else
			adjust_major = div_floor_plus_one(c->e - adjust_minor * c->e3, c->e1);
		printf("%d\n", adjust_major);
	} else {
		printf("\tminor clip dominates %d > %d. adjust minor %d -> ",
		       adj_min, adjust_minor, adjust_minor);
		adjust_minor = adj_min;
		printf("%d\n", adjust_minor);
	}

	c->e += adjust_major * c->e1 + adjust_minor * c->e3;

	c->major += c->sign_major * adjust_major;
	c->minor += c->sign_minor * adjust_minor;

	printf ("\tadjust major %d adjust minor %d e %d e1 %d e3 %e\n",
		adjust_major, adjust_minor, c->e, c->e1, c->e3);

	if (c->e >= 0)
		printf ("error positive e %d e1 %d e3 %d\n",
			c->e, c->e1, c->e3);
	if (c->e < c->e3)
		printf ("error magnitude too large e %d e1 %d e3 %d\n", c->e, c->e1, c->e3);

	return true;
}

test
line(int x1, int y1, int x2, int y2, *box b) {

	int	dx = x2 - x1;
	int	dy = y2 - y1;
	int	signdx = sign(dx);
	int	signdy = sign(dy);
	int	adx = abs(dx);
	int	ady = abs(dy);
	int	axis;
	int	e, e1, e2, e3;
	int	len;
	clip_context	clip_1, clip_2;
	clip_box	c;
	bool		clipped = false;
	test		t = {
		.x1 = x1,
		.y1 = y1,
		.x2 = x2,
		.y2 = y2,
		.b = *b,
		.clipped = (point[...]) {},
		.run = (point[...]) {}
	};

	if (adx >= ady) {
		axis = X_AXIS;
		e1 = ady << 1;
		e2 = e1 - (adx << 1);
		e = e1 - adx;
		len = adx;

		clip_1.major = x1;
		clip_1.minor = y1;
		clip_2.major = x2;
		clip_2.minor = y2;
		clip_1.sign_major = signdx;
		clip_1.sign_minor = signdy;

		c.maj1 = b->x1;
		c.maj2 = b->x2;
		c.min1 = b->y1;
		c.min2 = b->y2;
	} else {
		axis = Y_AXIS;
		e1 = adx << 1;
		e2 = e1 - (ady << 1);
		e = e1 - ady;
		len = ady;

		clip_1.major = y1;
		clip_1.minor = x1;
		clip_2.major = y2;
		clip_2.minor = x2;
		clip_1.sign_major = signdy;
		clip_1.sign_minor = signdx;
		c.maj1 = b->y1;
		c.maj2 = b->y2;
		c.min1 = b->x1;
		c.min2 = b->x2;
	}

	e3 = e2 - e1;
	e = e - e1;

	clip_1.first = true;
	clip_2.first = false;
	clip_2.e = clip_1.e = e;
	clip_2.e1 = clip_1.e1 = e1;
	clip_2.e3 = clip_1.e3 = e3;
	clip_2.sign_major = -clip_1.sign_major;
	clip_2.sign_minor = -clip_1.sign_minor;

	printf ("clip start:\n");
	if (!clip(&clip_1, &c))
		clipped = true;

	printf("clip end:\n");
	if (!clip(&clip_2, &c))
		clipped = true;

	int	clip_len;
	int	clip_x, clip_y;
	int	clip_e;
	int	x_major, x_minor;
	int	y_major, y_minor;

	clip_len = clip_1.sign_major * (clip_2.major - clip_1.major);
	if (clip_len < 0)
		clipped = true;

	int x, y;

	if (axis == X_AXIS) {
		x = clip_1.major;
		y = clip_1.minor;
		x_major = clip_1.sign_major;
		x_minor = 0;
		y_major = 0;
		y_minor = clip_1.sign_minor;
	} else {
		x = clip_1.minor;
		y = clip_1.major;
		x_major = 0;
		x_minor = clip_1.sign_minor;
		y_major = clip_1.sign_major;
		y_minor = 0;
	}

	clip_e = clip_1.e;

	if (clipped)
		clip_len = -1;

	while (clip_len-- >= 0) {
		t.clipped[dim(t.clipped)] = (point) { .x = x, .y = y };
		x += x_major;
		y += y_major;
		clip_e += e1;
		if (clip_e >= 0) {
			x += x_minor;
			y += y_minor;
			clip_e += e3;
		}
	}

	x = x1;
	y = y1;

	while (len-- >= 0) {
		if (bounds.x1 <= x && x < bounds.x2 &&
		    bounds.y1 <= y && y < bounds.y2) {
			t.run[dim(t.run)] = (point) { .x = x, .y = y };
		}
		x += x_major;
		y += y_major;
		e += e1;
		if (e >= 0) {
			x += x_minor;
			y += y_minor;
			e += e3;
		}
	}
	return t;
}

void read_events (Cairo::cairo_t cr)
{
	file	event = Cairo::open_event(cr);

	while (!File::end(event)) {
		string	event_line = File::fgets(event);
		if (String::index(event_line, "delete") >= 0)
			exit(0);
	}
}

#for (int y = 0; y < 20; y++)

void
show(cairo_t cr, test t)
{
	rectangle(cr, 0, 0, 40, 40);
	set_source_rgba(cr, 1, 1, 1, 1);
	fill(cr);

	set_source_rgba(cr, 0, 1, 0, .2);
	set_line_width(cr, 0.1);
	for (int x = 0; x < 40; x++) {
		move_to(cr, 0, x);
		line_to(cr, 40, x);
		move_to(cr, x, 0);
		line_to(cr, x, 40);
	}
	stroke(cr);

	rectangle(cr, t.b.x1, t.b.y1, t.b.x2 - t.b.x1, t.b.y2 - t.b.y1);
	set_line_width(cr, 0.1);
	set_source_rgba(cr, 0, 0, 0, 1);
	stroke(cr);

	move_to(cr, t.x1+.5, t.y1+.5);
	line_to(cr, t.x2+.5, t.y2+.5);
	move_to(cr, t.x2, t.y2);
	line_to(cr, t.x2+1, t.y2+1);
	move_to(cr, t.x2+1, t.y2);
	line_to(cr, t.x2, t.y2+1);
	stroke(cr);

	void pixels(point[] pt) {
		for (int i = 0; i < dim(pt); i++) {
			rectangle(cr, pt[i].x, pt[i].y, 1, 1);
		}
		fill(cr);
	}

	set_source_rgba(cr, 1, 0, 0, .5);
	pixels(t.clipped);

	set_source_rgba(cr, 0, 0, 1, .5);
	pixels(t.run);
}

bool
compare(test t)
{
	if (dim(t.clipped) != dim(t.run))
		return false;

	for (int i = 0; i < dim(t.clipped); i++)
		if (t.clipped[i] != t.run[i])
			return false;
	return true;
}

void
doit(int i)
{
	int	n;
	*box	b = &bounds;

	cairo_t cr = new(800, 800);

	scale(cr, 20, 20);

	for (;;) {
		PRNG::srandom(i);
		int	x1 = PRNG::randint(40);
		int	x2 = PRNG::randint(40);
		int	y1 = PRNG::randint(40);
		int	y2 = PRNG::randint(40);

		test t = line (x1, y1, x2, y2, &bounds);
		show(cr, t);
		if (!compare(t)) {
			printf("line %d -- %d x %d - %d x %d\n", i, x1, y1, x2, y2);
			gets();
		}
		i++;
	}

	read_events(cr);
}

int i = 0;
if (dim(argv) > 1)
	i = atoi(argv[1]);

doit(i);