Mu - 509bezier.mu

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

- 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 }