pastry

truetype font renderer

settings

algorithm.pseudocode

4463 bytes raw

  1function render_bezier(beg_point, ctrl_point, end_point, output_buffer, width, height):
  2    // set up curve structure
  3    curve = Curve(beg_point, end_point, ctrl_point)
  4
  5    // set up raster buffer
  6    buffer = allocate_buffer(width, height)
  7    clear_buffer(buffer)
  8
  9    // tessellate and draw
 10    tessellate_and_draw_curve(curve, buffer, width, height)
 11
 12    // convert to final image
 13    post_process(buffer, output_buffer, width, height)
 14
 15function is_flat(beg, ctrl, end):
 16    // calculate twice the area of the triangle formed by the three points
 17    // this gives a measure of how "curvy" the curve is
 18    vector1 = (ctrl.x - beg.x, ctrl.y - beg.y)
 19    vector2 = (end.x - beg.x, end.y - beg.y)
 20    area2 = abs(vector1.x * vector2.y - vector1.y * vector2.x)
 21
 22    // if area is small enough, the curve can be approximated as a straight line
 23    return area2 <= 2.0  // threshold value
 24
 25function tessellate_and_draw_curve(curve, buffer, width, height):
 26    stack = empty stack
 27    stack.push(curve)
 28
 29    while stack is not empty:
 30        current_curve = stack.pop()
 31
 32        if is_flat(points[current_curve.beg],
 33                  points[current_curve.ctrl],
 34                  points[current_curve.end]) or stack is full:
 35            // draw as line segment if flat enough
 36            draw_line(buffer, width, height,
 37                     points[current_curve.beg],
 38                     points[current_curve.end])
 39        else:
 40            // subdivide curve at midpoint using de Casteljau's algorithm
 41            left_ctrl = midpoint(points[current_curve.beg], points[current_curve.ctrl])
 42            right_ctrl = midpoint(points[current_curve.ctrl], points[current_curve.end])
 43            center = midpoint(left_ctrl, right_ctrl)
 44
 45            // add new points to collection
 46            center_idx = add_point(center)
 47            left_ctrl_idx = add_point(left_ctrl)
 48            right_ctrl_idx = add_point(right_ctrl)
 49
 50            // push subdivided curves onto stack (right then left for proper order)
 51            stack.push(Curve(center_idx, current_curve.end, right_ctrl_idx))
 52            stack.push(Curve(current_curve.beg, center_idx, left_ctrl_idx))
 53
 54function draw_line(buffer, width, height, origin, goal):
 55    delta = (goal.x - origin.x, goal.y - origin.y)
 56    direction = (sign(delta.x), sign(delta.y))
 57
 58    // skip horizontal lines (no area contribution)
 59    if direction.y == 0:
 60        return
 61
 62    // init grid traversal
 63    init_pixel_coordinates(origin, direction, &pixel)
 64    init_crossing_distances(origin, delta, direction, pixel, &next_crossing, &crossing_incr)
 65
 66    prev_distance = 0.0
 67    num_steps = calculate_steps(origin, goal, direction)
 68    half_delta_x = 0.5 * delta.x
 69
 70    // walk through each pixel the line passes through
 71    for step = 0 to num_steps-1:
 72        next_distance = min(next_crossing.x, next_crossing.y)
 73
 74        // calculate trapezoidal area contribution to current pixel
 75        x_average = origin.x + (prev_distance + next_distance) * half_delta_x
 76        y_difference = (next_distance - prev_distance) * delta.y
 77
 78        // update coverage and area for this pixel
 79        cell = buffer[pixel.y * width + pixel.x]
 80        cell.cover += y_difference
 81        cell.area += (1.0 - (x_average - pixel.x)) * y_difference
 82        buffer[pixel.y * width + pixel.x] = cell
 83
 84            // advance to next pixel
 85        if next_crossing.x < next_crossing.y:
 86            pixel.x += direction.x
 87            next_crossing.x += crossing_incr.x
 88        else:
 89            pixel.y += direction.y
 90            next_crossing.y += crossing_incr.y
 91
 92        prev_distance = next_distance
 93
 94    // handle final segment to line endpoint
 95    next_distance = 1.0
 96    x_average = origin.x + (prev_distance + next_distance) * half_delta_x
 97    y_difference = (next_distance - prev_distance) * delta.y
 98
 99    cell = buffer[pixel.y * width + pixel.x]
100    cell.cover += y_difference
101    cell.area += (1.0 - (x_average - pixel.x)) * y_difference
102    buffer[pixel.y * width + pixel.x] = cell
103
104function post_process(buffer, output_image, width, height):
105    accumulated = 0.0
106
107    for each pixel in buffer (row-major order):
108        // combine accumulated coverage with local area
109        value = abs(accumulated + pixel.area)
110        value = clamp(value, 0.0, 1.0)
111
112        // convert to 8-bit grayscale
113        output_image[pixel_index] = round(value * 255.0)
114
115        // update accumulated coverage for next pixel
116        accumulated += pixel.cover