Bresenham's algorithm for bezier curves

3 files changed, 387 insertions, 0 deletions

diff --git a/509bezier.mu b/509bezier.mu
new file mode 100644
index 00000000..54c95fc5
--- /dev/null
+++ b/509bezier.mu
@@ -0,0 +1,333 @@
+# Draw a second-degree bezier curve using 3 control points.
+#
+# http://members.chello.at/easyfilter/bresenham.html says that this algorithm
+# works only if "the gradient does not change sign". Either:
+#   x0 >= x1 >= x2
+# or:
+#   x0 <= x1 <= x2
+# Similarly for y0, y1 and y2.
+#
+# This seems superficially similar to the notions of convex and concave, but I
+# think it isn't. I think it's purely a property of the frame of reference.
+# Rotating the axes can make the gradient change sign or stop changing sign
+# even as 3 points preserve fixed relative bearings to each other.
+fn draw-monotonic-bezier screen: (addr screen), x0: int, y0: int, x1: int, y1: int, x2: int, y2: int, color: int {
+  var xx: int
+  var yy: int
+  var xy: int
+  var sx: int
+  var sy: int
+  # sx = x2-x1
+  var tmp/eax: int <- copy x2
+  tmp <- subtract x1
+  copy-to sx, tmp
+  # sy = y2-y1
+  tmp <- copy y2
+  tmp <- subtract y1
+  copy-to sy, tmp
+  # xx = x0-x1
+  tmp <- copy x0
+  tmp <- subtract x1
+  copy-to xx, tmp
+  # yy = y0-y1
+  tmp <- copy y0
+  tmp <- subtract y1
+  copy-to yy, tmp
+  # cur = xx*sy - yy*sx
+  var cur-f/xmm4: float <- convert xx
+  {
+    var sy-f/xmm1: float <- convert sy
+    cur-f <- multiply sy-f
+    var tmp2-f/xmm1: float <- convert yy
+    var sx-f/xmm2: float <- convert sx
+    tmp2-f <- multiply sx-f
+    cur-f <- subtract tmp2-f
+  }
+  set-cursor-position 0/screen, 0/x, 0x1d/y
+  draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, sx, 4/fg 0/bg
+  draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 4/fg 0/bg
+  draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, sy, 4/fg 0/bg
+  draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 4/fg 0/bg
+  draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, xx, 4/fg 0/bg
+  draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 4/fg 0/bg
+  draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, yy, 4/fg 0/bg
+  draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 4/fg 0/bg
+  draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, xy, 4/fg 0/bg
+  # if (xx*sx > 0) abort
+  {
+    tmp <- copy xx
+    tmp <- multiply sx
+    compare tmp, 0
+    break-if-<=
+    abort "bezier: gradient of x changes sign"
+  }
+  # if (yy*sy > 0) abort
+  {
+    tmp <- copy yy
+    tmp <- multiply sy
+    compare tmp, 0
+    break-if-<=
+    abort "bezier: gradient of y changes sign"
+  }
+  # swap P0 and P2 if necessary
+  {
+    # dist1 = sx*sx + sy*sy
+    var dist1/ecx: int <- copy sx
+    {
+      dist1 <- multiply sx
+      {
+        break-if-not-overflow
+        abort "bezier: overflow 1"
+      }
+      tmp <- copy sy
+      tmp <- multiply sy
+      {
+        break-if-not-overflow
+        abort "bezier: overflow 2"
+      }
+      dist1 <- add tmp
+    }
+    # dist2 = xx*xx + yy*yy
+    var dist2/edx: int <- copy xx
+    {
+      dist2 <- multiply xx
+      {
+        break-if-not-overflow
+        abort "bezier: overflow 3"
+      }
+      tmp <- copy yy
+      tmp <- multiply yy
+      {
+        break-if-not-overflow
+        abort "bezier: overflow 4"
+      }
+      dist2 <- add tmp
+    }
+    # if (dist1 <= dist2) break
+    compare dist1, dist2
+    break-if-<=
+    set-cursor-position 0/screen, 0/x 0x1e/y
+    draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, "swapping P0 and P2", 4/fg 0/bg
+    # swap x0 and x2
+    tmp <- copy x0
+    copy-to x2, tmp
+    tmp <- copy sx
+    tmp <- add x1
+    copy-to x0, tmp
+    # swap y0 and y2
+    tmp <- copy y0
+    copy-to y2, tmp
+    tmp <- copy sy
+    tmp <- add y1
+    copy-to y0, tmp
+    # cur = -cur
+    var negative-1/eax: int <- copy -1
+    var negative-1-f/xmm1: float <- convert negative-1
+    cur-f <- multiply negative-1-f
+  }
+  var x/ecx: int <- copy x0
+  var y/edx: int <- copy y0
+  set-cursor-position 0/screen, 0/x 0x1f/y
+#?   printf("sx %d sy %d xx %ld yy %ld xy %ld cur %g\n", sx, sy, xx, yy, xy, cur);
+  var zero-f: float
+  # plot a curved part if necessary
+  $draw-monotonic-bezier:curve: {
+    compare cur-f, zero-f
+    break-if-=
+    # xx += sx
+    tmp <- copy sx
+    add-to xx, tmp
+    # sx = sgn(x2-x)
+    tmp <- copy x2
+    tmp <- subtract x
+    tmp <- sgn tmp
+    copy-to sx, tmp
+    # yy += sy
+    tmp <- copy sy
+    add-to yy, tmp
+    # sy = sgn(y2-y)
+    tmp <- copy y2
+    tmp <- subtract y
+    tmp <- sgn tmp
+    copy-to sy, tmp
+    # xy = 2*xx*xy
+    tmp <- copy xx
+    tmp <- multiply yy
+    {
+      break-if-not-overflow
+      abort "bezier: overflow 5"
+    }
+    tmp <- shift-left 1
+    {
+      break-if-not-overflow
+      abort "bezier: overflow 6"
+    }
+    copy-to xy, tmp
+    # xx *= xx
+    tmp <- copy xx
+    tmp <- multiply tmp
+    {
+      break-if-not-overflow
+      abort "bezier: overflow 7"
+    }
+    copy-to xx, tmp
+    # yy *= yy
+    tmp <- copy yy
+    tmp <- multiply tmp
+    {
+      break-if-not-overflow
+      abort "bezier: overflow 7"
+    }
+    copy-to yy, tmp
+    # if (cur*sx*sy < 0) negative curvature
+    {
+      var tmp-f/xmm0: float <- copy cur-f
+      var sx-f/xmm1: float <- convert sx
+      tmp-f <- multiply sx-f
+      var sy-f/xmm1: float <- convert sy
+      tmp-f <- multiply sy-f
+      compare tmp-f, zero-f
+      break-if-float>=
+      #
+      negate xx
+      negate yy
+      negate xy
+      # cur = -cur
+      var negative-1/eax: int <- copy -1
+      var negative-1-f/xmm1: float <- convert negative-1
+      cur-f <- multiply negative-1-f
+    }
+    draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, sx, 4/fg 0/bg
+    draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 4/fg 0/bg
+    draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, sy, 4/fg 0/bg
+    draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 4/fg 0/bg
+    draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, xx, 4/fg 0/bg
+    draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 4/fg 0/bg
+    draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, yy, 4/fg 0/bg
+    draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 4/fg 0/bg
+    draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, xy, 4/fg 0/bg
+    var four/ebx: int <- copy 4
+    var dx-f/xmm5: float <- convert four
+    var dy-f/xmm6: float <- convert four
+    # dx = 4*sy*cur*(x1-x0) + xx - xy
+    {
+      var tmp/xmm0: float <- convert sy
+      dx-f <- multiply tmp
+      dx-f <- multiply cur-f
+      tmp <- convert x1
+      var tmp2/xmm3: float <- convert x
+      tmp <- subtract tmp2
+      dx-f <- multiply tmp
+      tmp <- convert xx
+      dx-f <- add tmp
+      tmp <- convert xy
+      dx-f <- subtract tmp
+    }
+    # dy-f = 4*sx*cur*(y0-y1) + yy - xy
+    {
+      var tmp/xmm0: float <- convert sx
+      dy-f <- multiply tmp
+      dy-f <- multiply cur-f
+      tmp <- convert y
+      var tmp2/xmm3: float <- convert y1
+      tmp <- subtract tmp2
+      dy-f <- multiply tmp
+      tmp <- convert yy
+      dy-f <- add tmp
+      tmp <- convert xy
+      dy-f <- subtract tmp
+    }
+    # xx += xx
+    tmp <- copy xx
+    add-to xx, tmp
+    # yy += yy
+    tmp <- copy yy
+    add-to yy, tmp
+    # err = dx+dy+xy
+    var err-f/xmm7: float <- copy dx-f
+    err-f <- add dy-f
+    var xy-f/xmm0: float <- convert xy
+    err-f <- add xy-f
+    #
+#?     set-cursor-position 0, 0/x 0/y
+#?     var screen-y/esi: int <- copy 0
+    $draw-monotonic-bezier:loop: {
+#?       draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, x, 3/fg 0/bg
+#?       draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 3/fg 0/bg
+#?       draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, y, 3/fg 0/bg
+#?       draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " vs ", 3/fg 0/bg
+#?       draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, x2, 3/fg 0/bg
+#?       draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, " ", 3/fg 0/bg
+#?       draw-int32-decimal-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, y2, 3/fg 0/bg
+#?       var dummy/eax: int <- render-float-decimal 0/screen,  dx-f, 3/precision,    0/x screen-y, 3/fg 0/bg
+#?       var dummy/eax: int <- render-float-decimal 0/screen,  dy-f, 3/precision, 0x10/x screen-y, 3/fg 0/bg
+#?       var dummy/eax: int <- render-float-decimal 0/screen, err-f, 3/precision, 0x20/x screen-y, 3/fg 0/bg
+#?       move-cursor-to-left-margin-of-next-line 0/screen
+#?       screen-y <- increment
+      pixel screen, x, y, color
+#?       {
+#?         var foo/eax: byte <- read-key 0/keyboard
+#?         compare foo, 0
+#?         loop-if-=
+#?       }
+      # if (x == x2 && y == y2) return
+      {
+        compare x, x2
+        break-if-!=
+        compare y, y2
+        break-if-!=
+        return
+      }
+      # perform-y-step? = (2*err < dx)
+      var perform-y-step?/eax: boolean <- copy 0/false
+      var two-err-f/xmm0: float <- copy err-f
+      {
+        var two/ebx: int <- copy 2
+        var two-f/xmm1: float <- convert two
+        two-err-f <- multiply two-f
+        compare two-err-f, dx-f
+        break-if-float>=
+        perform-y-step? <- copy 1/true
+      }
+      # if (2*err > dy)
+      {
+        compare two-err-f, dy-f
+        break-if-float<=
+#?         draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, "x step", 3/fg 0/bg
+#?         move-cursor-to-left-margin-of-next-line 0/screen
+        # x += sx
+        x <- add sx
+        # dx -= xy
+        var xy-f/xmm0: float <- convert xy
+        dx-f <- subtract xy-f
+        # dy += yy
+        var yy-f/xmm0: float <- convert yy
+        dy-f <- add yy-f
+        # err += dy
+        err-f <- add dy-f
+      }
+      # if perform-y-step?
+      {
+        compare perform-y-step?, 0/false
+        break-if-=
+#?         draw-text-wrapping-right-then-down-from-cursor-over-full-screen 0/screen, "y step", 3/fg 0/bg
+#?         move-cursor-to-left-margin-of-next-line 0/screen
+        # y += sy
+        y <- add sy
+        # dy -= xy
+        var xy-f/xmm0: float <- convert xy
+        dy-f <- subtract xy-f
+        # dx += xx
+        var xx-f/xmm0: float <- convert xx
+        dx-f <- add xx-f
+        # err += dx
+        err-f <- add dx-f
+      }
+      # if (dy < dx) loop
+      compare dy-f, dx-f
+      loop-if-float<
+    }
+  }
+  # plot the remaining straight line
+  draw-line screen, x y, x2 y2, color
+}
diff --git a/bezier.c b/bezier.c
new file mode 100644
index 00000000..b65a9e1d
--- /dev/null
+++ b/bezier.c
@@ -0,0 +1,46 @@
+#include<assert.h>
+#include<stdio.h>
+
+void setPixel(int x, int y) {
+  printf("%d %d\n", x, y);
+}
+
+void plotQuadBezierSeg(int x0, int y0, int x1, int y1, int x2, int y2)
+{                            
+  int sx = x2-x1, sy = y2-y1;
+  long xx = x0-x1, yy = y0-y1, xy;         /* relative values for checks */
+  double dx, dy, err, cur = xx*sy-yy*sx;                    /* curvature */
+
+  assert(xx*sx <= 0 && yy*sy <= 0);  /* sign of gradient must not change */
+
+  printf("0 sx %d sy %d xx %ld yy %ld xy %ld cur %g\n", sx, sy, xx, yy, xy, cur);
+  if (sx*(long)sx+sy*(long)sy > xx*xx+yy*yy) { /* begin with longer part */ 
+    printf("swap\n");
+    x2 = x0; x0 = sx+x1; y2 = y0; y0 = sy+y1; cur = -cur;  /* swap P0 P2 */
+  }  
+  if (cur != 0) {                                    /* no straight line */
+    xx += sx; xx *= sx = x0 < x2 ? 1 : -1;           /* x step direction */
+    yy += sy; yy *= sy = y0 < y2 ? 1 : -1;           /* y step direction */
+    xy = 2*xx*yy; xx *= xx; yy *= yy;          /* differences 2nd degree */
+    if (cur*sx*sy < 0) {                           /* negated curvature? */
+      xx = -xx; yy = -yy; xy = -xy; cur = -cur;
+    }
+    printf("1 sx %d sy %d xx %ld yy %ld xy %ld cur %g\n", sx, sy, xx, yy, xy, cur);
+    dx = 4.0*sy*cur*(x1-x0)+xx-xy;             /* differences 1st degree */
+    dy = 4.0*sx*cur*(y0-y1)+yy-xy;
+    xx += xx; yy += yy; err = dx+dy+xy;                /* error 1st step */    
+    do {                              
+      printf("%d %d: dx %g dy %g err %g\n", x0, y0, dx, dy, err);
+      if (x0 == x2 && y0 == y2) return;  /* last pixel -> curve finished */
+      y1 = 2*err < dx;                  /* save value for test of y step */
+      if (2*err > dy) { x0 += sx; dx -= xy; err += dy += yy; } /* x step */
+      if (    y1    ) { y0 += sy; dy -= xy; err += dx += xx; } /* y step */
+    } while (dy < dx );           /* gradient negates -> algorithm fails */
+  }
+//?   plotLine(x0,y0, x2,y2);                  /* plot remaining part to end */
+}
+
+int main(void) {
+  plotQuadBezierSeg(1, 1, 0x80, 0x100, 0x200, 0x140);
+  return 0;
+}
diff --git a/hest-life.mu b/hest-life.mu
new file mode 100644
index 00000000..552c42ae
--- /dev/null
+++ b/hest-life.mu
@@ -0,0 +1,8 @@
+fn main screen: (addr screen), keyboard: (addr keyboard), data-disk: (addr disk) {
+  draw-line             screen,         1 1,   0x80 0x100,               7/color
+  draw-line             screen,  0x80 0x100,  0x200 0x140,               7/color
+  draw-monotonic-bezier screen,         1 1,   0x80 0x100,  0x200 0x140, 0xc/color
+  draw-disc             screen,         1 1,            3,               7/color 0xf/border
+  draw-disc             screen,  0x80 0x100,            3,               7/color 0xf/border
+  draw-disc             screen, 0x200 0x140,            3,               7/color 0xf/border
+}