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 }