https://github.com/akkartik/mu/blob/main/509bezier.mu

      1 # Draw a second-degree bezier curve using 3 control points.
      2 #
      3 # http://members.chello.at/easyfilter/bresenham.html says that this algorithm
      4 # works only if "the gradient does not change sign". Either:
      5 #   x0 >= x1 >= x2
      6 # or:
      7 #   x0 <= x1 <= x2
      8 # Similarly for y0, y1 and y2.
      9 #
     10 # This seems superficially similar to the notions of convex and concave, but I
     11 # think it isn't. I think it's purely a property of the frame of reference.
     12 # Rotating the axes can make the gradient change sign or stop changing sign
     13 # even as 3 points preserve fixed relative bearings to each other.
     14 fn draw-monotonic-bezier screen: (addr screen), x0: int, y0: int, x1: int, y1: int, x2: int, y2: int, color: int {
     15   var xx: int
     16   var yy: int
     17   var xy: int
     18   var sx: int
     19   var sy: int
     20   # sx = x2-x1
     21   var tmp/eax: int <- copy x2
     22   tmp <- subtract x1
     23   copy-to sx, tmp
     24   # sy = y2-y1
     25   tmp <- copy y2
     26   tmp <- subtract y1
     27   copy-to sy, tmp
     28   # xx = x0-x1
     29   tmp <- copy x0
     30   tmp <- subtract x1
     31   copy-to xx, tmp
     32   # yy = y0-y1
     33   tmp <- copy y0
     34   tmp <- subtract y1
     35   copy-to yy, tmp
     36   # cur = xx*sy - yy*sx
     37   var cur-f/xmm4: float <- convert xx
     38   {
     39     var sy-f/xmm1: float <- convert sy
     40     cur-f <- multiply sy-f
     41     var tmp2-f/xmm1: float <- convert yy
     42     var sx-f/xmm2: float <- convert sx
     43     tmp2-f <- multiply sx-f
     44     cur-f <- subtract tmp2-f
     45   }
     46   # if (xx*sx > 0) abort
     47   {
     48     tmp <- copy xx
     49     tmp <- multiply sx
     50     compare tmp, 0
     51     break-if-<=
     52     abort "bezier: gradient of x changes sign"
     53   }
     54   # if (yy*sy > 0) abort
     55   {
     56     tmp <- copy yy
     57     tmp <- multiply sy
     58     compare tmp, 0
     59     break-if-<=
     60     abort "bezier: gradient of y changes sign"
     61   }
     62   # swap P0 and P2 if necessary
     63   {
     64     # dist1 = sx*sx + sy*sy
     65     var dist1/ecx: int <- copy sx
     66     {
     67       dist1 <- multiply sx
     68       {
     69         break-if-not-overflow
     70         abort "bezier: overflow 1"
     71       }
     72       tmp <- copy sy
     73       tmp <- multiply sy
     74       {
     75         break-if-not-overflow
     76         abort "bezier: overflow 2"
     77       }
     78       dist1 <- add tmp
     79     }
     80     # dist2 = xx*xx + yy*yy
     81     var dist2/edx: int <- copy xx
     82     {
     83       dist2 <- multiply xx
     84       {
     85         break-if-not-overflow
     86         abort "bezier: overflow 3"
     87       }
     88       tmp <- copy yy
     89       tmp <- multiply yy
     90       {
     91         break-if-not-overflow
     92         abort "bezier: overflow 4"
     93       }
     94       dist2 <- add tmp
     95     }
     96     # if (dist1 <= dist2) break
     97     compare dist1, dist2
     98     break-if-<=
     99     # swap x0 and x2
    100     tmp <- copy x0
    101     copy-to x2, tmp
    102     tmp <- copy sx
    103     tmp <- add x1
    104     copy-to x0, tmp
    105     # swap y0 and y2
    106     tmp <- copy y0
    107     copy-to y2, tmp
    108     tmp <- copy sy
    109     tmp <- add y1
    110     copy-to y0, tmp
    111     # cur = -cur
    112     var negative-1/eax: int <- copy -1
    113     var negative-1-f/xmm1: float <- convert negative-1
    114     cur-f <- multiply negative-1-f
    115   }
    116   var x/ecx: int <- copy x0
    117   var y/edx: int <- copy y0
    118   var zero-f: float
    119   # plot a curved part if necessary
    120   $draw-monotonic-bezier:curve: {
    121     compare cur-f, zero-f
    122     break-if-=
    123     # xx += sx
    124     tmp <- copy sx
    125     add-to xx, tmp
    126     # sx = sgn(x2-x)
    127     tmp <- copy x2
    128     tmp <- subtract x
    129     tmp <- sgn tmp
    130     copy-to sx, tmp
    131     # xx *= sx
    132     tmp <- copy sx
    133     tmp <- multiply xx
    134     copy-to xx, tmp
    135     # yy += sy
    136     tmp <- copy sy
    137     add-to yy, tmp
    138     # sy = sgn(y2-y)
    139     tmp <- copy y2
    140     tmp <- subtract y
    141     tmp <- sgn tmp
    142     copy-to sy, tmp
    143     # yy *= sy
    144     tmp <- copy sy
    145     tmp <- multiply yy
    146     copy-to yy, tmp
    147     # xy = 2*xx*xy
    148     tmp <- copy xx
    149     tmp <- multiply yy
    150     {
    151       break-if-not-overflow
    152       abort "bezier: overflow 5"
    153     }
    154     tmp <- shift-left 1
    155     {
    156       break-if-not-overflow
    157       abort "bezier: overflow 6"
    158     }
    159     copy-to xy, tmp
    160     # xx *= xx
    161     tmp <- copy xx
    162     tmp <- multiply tmp
    163     {
    164       break-if-not-overflow
    165       abort "bezier: overflow 7"
    166     }
    167     copy-to xx, tmp
    168     # yy *= yy
    169     tmp <- copy yy
    170     tmp <- multiply tmp
    171     {
    172       break-if-not-overflow
    173       abort "bezier: overflow 7"
    174     }
    175     copy-to yy, tmp
    176     # if (cur*sx*sy < 0) negative curvature
    177     {
    178       var tmp-f/xmm0: float <- copy cur-f
    179       var sx-f/xmm1: float <- convert sx
    180       tmp-f <- multiply sx-f
    181       var sy-f/xmm1: float <- convert sy
    182       tmp-f <- multiply sy-f
    183       compare tmp-f, zero-f
    184       break-if-float>=
    185       #
    186       negate xx
    187       negate yy
    188       negate xy
    189       # cur = -cur
    190       var negative-1/eax: int <- copy -1
    191       var negative-1-f/xmm1: float <- convert negative-1
    192       cur-f <- multiply negative-1-f
    193     }
    194     var four/ebx: int <- copy 4
    195     var dx-f/xmm5: float <- convert four
    196     var dy-f/xmm6: float <- convert four
    197     # dx = 4*sy*cur*(x1-x0) + xx - xy
    198     {
    199       var tmp/xmm0: float <- convert sy
    200       dx-f <- multiply tmp
    201       dx-f <- multiply cur-f
    202       tmp <- convert x1
    203       var tmp2/xmm3: float <- convert x
    204       tmp <- subtract tmp2
    205       dx-f <- multiply tmp
    206       tmp <- convert xx
    207       dx-f <- add tmp
    208       tmp <- convert xy
    209       dx-f <- subtract tmp
    210     }
    211     # dy-f = 4*sx*cur*(y0-y1) + yy - xy
    212     {
    213       var tmp/xmm0: float <- convert sx
    214       dy-f <- multiply tmp
    215       dy-f <- multiply cur-f
    216       tmp <- convert y
    217       var tmp2/xmm3: float <- convert y1
    218       tmp <- subtract tmp2
    219       dy-f <- multiply tmp
    220       tmp <- convert yy
    221       dy-f <- add tmp
    222       tmp <- convert xy
    223       dy-f <- subtract tmp
    224     }
    225     # xx += xx
    226     tmp <- copy xx
    227     add-to xx, tmp
    228     # yy += yy
    229     tmp <- copy yy
    230     add-to yy, tmp
    231     # err = dx+dy+xy
    232     var err-f/xmm7: float <- copy dx-f
    233     err-f <- add dy-f
    234     var xy-f/xmm0: float <- convert xy
    235     err-f <- add xy-f
    236     #
    237     $draw-monotonic-bezier:loop: {
    238       pixel screen, x, y, color
    239       # if (x == x2 && y == y2) return
    240       {
    241         compare x, x2
    242         break-if-!=
    243         compare y, y2
    244         break-if-!=
    245         return
    246       }
    247       # perform-y-step? = (2*err < dx)
    248       var perform-y-step?/eax: boolean <- copy 0/false
    249       var two-err-f/xmm0: float <- copy err-f
    250       {
    251         var two/ebx: int <- copy 2
    252         var two-f/xmm1: float <- convert two
    253         two-err-f <- multiply two-f
    254         compare two-err-f, dx-f
    255         break-if-float>=
    256         perform-y-step? <- copy 1/true
    257       }
    258       # if (2*err > dy)
    259       {
    260         compare two-err-f, dy-f
    261         break-if-float<=
    262         # x += sx
    263         x <- add sx
    264         # dx -= xy
    265         var xy-f/xmm0: float <- convert xy
    266         dx-f <- subtract xy-f
    267         # dy += yy
    268         var yy-f/xmm0: float <- convert yy
    269         dy-f <- add yy-f
    270         # err += dy
    271         err-f <- add dy-f
    272       }
    273       # if perform-y-step?
    274       {
    275         compare perform-y-step?, 0/false
    276         break-if-=
    277         # y += sy
    278         y <- add sy
    279         # dy -= xy
    280         var xy-f/xmm0: float <- convert xy
    281         dy-f <- subtract xy-f
    282         # dx += xx
    283         var xx-f/xmm0: float <- convert xx
    284         dx-f <- add xx-f
    285         # err += dx
    286         err-f <- add dx-f
    287       }
    288       # if (dy < dx) loop
    289       compare dy-f, dx-f
    290       loop-if-float<
    291     }
    292   }
    293   # plot the remaining straight line
    294   draw-line screen, x y, x2 y2, color
    295 }
    296
    297 # 0 <= u <= 1
    298 fn bezier-point u: float, x0: int, x1: int, x2: int -> _/eax: int {
    299   var one/eax: int <- copy 1
    300   var u-prime/xmm0: float <- convert one
    301   u-prime <- subtract u
    302   var result/xmm1: float <- convert x0
    303   result <- multiply u-prime
    304   result <- multiply u-prime
    305   var term2/xmm2: float <- convert x1
    306   term2 <- multiply u
    307   term2 <- multiply u-prime
    308   result <- add term2
    309   result <- add term2
    310   var term3/xmm2: float <- convert x2
    311   term3 <- multiply u
    312   term3 <- multiply u
    313   result <- add term3
    314   var result/eax: int <- convert result
    315   return result
    316 }