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 }