CS 248: Final Solutions

Question 1: Spline Approximation to an Arc

Grader: Pat Hanrahan

Very efficient algorithms exist to draw cubic Bezier curves. In fact, these algorithms are so efficient that other types of curves are often converted to Bezier curves. For example, it is possible to approximate a 90 degree circular arc with a Bezier curve.

Recall that a cubic Bezier curve has four control points. Derive the coordinates of the four control points of a Bezier curve that approximates this circular arc. This approximation should touch and be tangent to the arc at both endpoints as well as the midpoint. Hint: Find control points such that the midpoint of the Bezier curve (t=1/2) lies on the midpoint of the circular arc.


Let P0, P1, P2 and P3 be the four control points of the Bezier curve.

P0 and P3 must be coincident with the endpoints. Thus, P0 = (0,1) and P3 = (1,0).

P1 and P2 must be chosen so that the curve is tangent to the arc. The tangent to the arc at (0,1) is (1,0); thus, P1 must have the same y coordinate as P0. Similarly, the tangent at (1,0) is (0,1), and thus P2 must have the same x coordinate as P3. Since the arc is symmetric, the best approximating Bezier curve should also be symmetric. Thus, P1 = (a,1) and P2 = (1,a).

The final unknown a can be found by requiring the midpoint of the Bezier curve to like at the midpoint of the arc, (sqrt(2)/2,sqrt(2)/2). Using the midpoint subdivision rule, we arrive at the following:

	P0		P1		P2		P3
	(0,1)		(a,1)		(1,a)		(1,0)

		1/2(a,2)	1/2(1+a,1+a)	1/2(2,a)

			1/4(1+2a,3+a)	1/4(3+a,1+2a)	


Seting 1/4(4+3a)=sqrt(2)/2 and solving for a we get a = 4(sqrt(2)-1)/3 = .552.

Grading Criteria

+6 points for getting the endpoints right.

+6 points for getting the tangent contraints right.

+4 points for noticing the symmetric and reducing the problem to a single unknown.

+4 points for knowing the correct subdivision rules, for being able to evaulate the Bezier curve at the midpoint.

Certain errors resulted in the following deductions:

-2 for formulating the problem correctly but making a math error in the final answer.

There were lots of answers that we almost right. Most of these received 14 points. They were wrong in that they did not satisfy the constraints that the curve should go through the endpoints and touch the midpoint.

One common solution was to compute the intersection of a 45 degree downward sloping line with the y=1 and x=1 lines and setting P1 and P2 to the points of intersections.

Several bisected the 45 degree angle and computed the intersection of a line through the origin at 22.5 with the x=1 and y=1 lines, and used those intersection points as the control points.

Another common error was to use a quadratic Bezier curve; or to use subdivision rules that reduced to the quadratic case.

Another approach was to reduce the problem to Hermite interpolation by setting the endpoint and tangent conditions. This can be made to work, but you must find a way to constrain the curve to go through the midpoint.

A clever approach was to try to set the tangent of the Bezier curve at the midpoint to have a slope of -1 and try to find separate Bezier curves for top and bottom part of the arc.