--- /dev/null
+#!/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);
projects / fw / altos / blobdiff