Geometry Homework

Drawing arcs is a common task in computer graphics. Arcs are typically drawn using an approximation by set of cubic Bezier splines. These splines are passed through the regular rendering pipeline where they are usually subdivided into a set of line segments and then rasterized. A circle, for example, can be represented by four cubic splines: one for each 90 degree arc.

An arc of up to 90 degrees can be approximated by a single cubic Bezier spline reasonably well. To find an appropriate approximating spline we set the start and end points of the ! spline to match the arc and then can find the middle two points using the following formula, where A is the start angle and B is the end angle:

h = 4/3 * tan ((B - A)/4)

pt1 = {center.x + r*cos(A), center.y + r*sin(A)}
pt2 = {center.x + r*cos(A) - h*r*sin(A), center.y + r*sin(A) + h*r*cos(A)}
pt3 = {center.x + r*cos(A) + h*r*sin(B), center.y + r*sin(A) - h*r*cos(B)}
pt4 = {center.x + r*cos(B), center.y + r*sin(B)}

This approach works quite well and is currently used by cairo. However, the problem with this approach is that it requires converting to polar coordinates and then back to Cartesian ones. This conversion is slow because it requires the use of trigonometric functions.

Fortunately, this paper gives a solution that avoids the conversion to polar coordinates:

ax = pt1.x - center.! x
ay = pt1.y - center.y
bx = pt4.x - center.x
b! y = pt4. y - center.y

q1 = ax*ax + ay*ay
q2 = q1 + ax*bx + ay*by

k2 = 4/3 (sqrt(2*q1*q2) - q2) / (ax*by - ay*bx)

pt2.x = pt1.x - k2*ay
pt2.y = pt1.y + k2*ax
pt3.x = pt4.x + k2*bx
pt3.y = pt4.y - k2*by

Unfortunately, there is no explanation, derivation or proof for this formula. Even more problematic, the formula for k2 becomes less stable as pt1 approaches pt4, becoming NaN when pt1 equals pt4.

Therefore, the homework problem has two parts:

1. Give an explanation or derivation for the formula for k2 provided above.
2. Provide a similar formulation for pt2 and pt3 that doesn't degenerate as pt1 and pt4 become close or prove that one doesn't exist.

The best answer will be credited in the new cairo stroking code.

geometry homework help free