Computer Science 237
No formal lab meetings this week.
This week's task is to write an efficient assembly language function to draw a Bezier curve. If you have used drawing programs you probably have some familiarity with these curves. This week we will use them as part of the game Red-Blue Hackenbush, an invention of John Conway and others. The rules to Hackenbush are discussed at the end of this document.
Hackenbush, at start of play
In the file
/usr/cs-local/share/cs237/labs/hack/hack.tar.gz you will find the support code you need. To untar this, type:
tar xvfz /usr/cs-local/share/cs237/labs/hack/hack.tar.gz
This will create a subdirectory, hack. You are to complete the construction of the assembly file bezier.s by adding the code to compute one coordinate of a point on a Bezier curve. Build your program by typing "make". The result is found in hack.prc. In the starter kit, the BezierPt subroutine returns zero, so nothing exciting will happen. A working version of Hackenbush is found in whack.prc.
All Bezier functions are described by the formula: a(1-t)^3+3b(1-t)^2t+3c(1-t)t^2+dt^3 where 0 <= t <= 1. Note that at time 0 (t=0), all of the terms disappear save the first, which evaluates to a. At time 1, only the last coefficient, d, remains. We can think of the curve as taking us from a to d over time. In fact, the curve leaves a heading toward b and arrives at d coming in from c. On the plane we can use two functions x(t) = a_x(1-t)^3+3b_x(1-t)^2t+3c_x(1-t)t^2+d_xt^3 y(t) = a_y(1-t)^3+3b_y(1-t)^2t+3c_y(1-t)t^2+d_yt^3 to compute the curve from a=(ax,ay), toward b, arriving at d from c. It is sometimes useful to know that the curve always resides in the interior of quadrilateral a-b-c-d.
The C function to perform this computation has the following prototype:
int BezierPt(int a, int b, int c, int d, int st);
It is important to realize that the pixels on the display are nonnegative integers. Furthermore, the support for floating point computations is, effectively, nonexistent on the palm. For this reason, the st that is passed in is a scaled t value between 0 and 8 (inclusive). These represent times between 0 and 1 (0, (1)/(8), (2)/(8), ..., 1). Write a tight assembly implementation of BezierPt that accurately computes the Bezier function. You may find the following useful:
When you are finished, submit your well-documented implementation of BezierPt in the file bezier.s.
While you will write only the BezierPt routine, you will use it in a program that plays the full red-blue hackenbush game. If you are having trouble getting started with the program (maybe can't even get to the point where BezierPt gets called), note that you must begin the drawing of a segment by clicking on the "sky" or the "ground". The four points that define the Bezier curve to be drawn are the points where you press down ("pen down" on the Palm) the first time, where you release ("pen up") the first time, where you press down the second time, and where you release the second time.
Here are the rules for game play: