dymokomi/luce-browser-render
Source of release 0.6.1
0.6.1 / src / raster / stroker_curves.lucb
#==============================================================================================
#
# stroker_curves - approximating the offset of quads and cubics with quads
#
# DESCRIPTION:
# Port of tiny-skia-path stroker.rs, part 2 (PathStroker's curve methods, lines
# 460-1010): cubic_stroke, quad_stroke, the perpendicular rays, compare_quad_cubic /
# compare_quad_quad, stroke_close_enough, intersect_ray and QuadConstruct. The methods
# are free functions over `s: PathStroker*` to keep PathStroker's body in one fragment
# of reasonable size; their names and bodies are tiny-skia's.
#
#==============================================================================================
func cubic_stroke(s: PathStroker*, cubic: const Point[], quad_points: QuadConstruct*) -> bool:
if not s.found_tangents:
let result_type = tangents_meet(s, cubic, quad_points)
if result_type != .quad:
let ok = points_within_dist(quad_points.quad[0], quad_points.quad[2], s.inv_res_scale)
if (result_type == .degenerate or ok) and cubic_mid_on_line(s, cubic, quad_points):
add_degenerate_line(s, quad_points)
return true
else:
s.found_tangents = true
if s.found_tangents:
let result_type = compare_quad_cubic(s, cubic, quad_points)
if result_type == .quad:
let stroke = quad_points.quad
if s.stroke_type == .outer:
s.outer.quad_to(stroke[1].x, stroke[1].y, stroke[2].x, stroke[2].y)
else:
s.inner.quad_to(stroke[1].x, stroke[1].y, stroke[2].x, stroke[2].y)
return true
if result_type == .degenerate:
if not quad_points.opposite_tangents:
add_degenerate_line(s, quad_points)
return true
if not math32.is_finite(quad_points.quad[2].x) or not math32.is_finite(quad_points.quad[2].x):
return false # just abort if projected quad isn't representable
s.recursion_depth += 1
if s.recursion_depth > recursive_limits[(usize)s.found_tangents]:
return false # just abort if projected quad isn't representable
var half_quad = QuadConstruct.default()
if not half_quad.init_with_start(quad_points):
add_degenerate_line(s, quad_points)
s.recursion_depth -= 1
return true
if not cubic_stroke(s, cubic, &half_quad):
return false
if not half_quad.init_with_end(quad_points):
add_degenerate_line(s, quad_points)
s.recursion_depth -= 1
return true
if not cubic_stroke(s, cubic, &half_quad):
return false
s.recursion_depth -= 1
return true
func cubic_mid_on_line(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*) -> bool:
var stroke_mid = Point.zero()
cubic_quad_mid(s, cubic, quad_points, &stroke_mid)
let dist = pt_to_line(stroke_mid, quad_points.quad[0], quad_points.quad[2])
return dist < s.inv_res_scale_squared
func cubic_quad_mid(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*, mid: Point*):
var cubic_mid_pt = Point.zero()
cubic_perp_ray(s, cubic, quad_points.mid_t, &cubic_mid_pt, mid, none)
# Given a cubic and t, return the point on curve, its perpendicular, and the perpendicular
# tangent.
func cubic_perp_ray(s: const PathStroker*, cubic: const Point[], t: f32, t_pt: Point*, on_pt: Point*, tangent: Point*?):
*t_pt = eval_cubic_pos_at(cubic, t)
var dxy = eval_cubic_tangent_at(cubic, t)
var chopped: Point[7] = [Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero()]
if dxy.x == 0.0 and dxy.y == 0.0:
var c_points = cubic
if is_nearly_zero(t):
dxy = cubic[2].sub(cubic[0])
elif is_nearly_zero(1.0 - t):
dxy = cubic[3].sub(cubic[1])
else:
# If the cubic inflection falls on the cusp, subdivide the cubic to find the
# tangent at that point.
#
# Unwrap never fails, because we already checked that `t` is not 0/1,
let tt = normalized_exclusive_new(t) else trap("unreachable")
chop_cubic_at2(cubic, tt, chopped)
dxy = chopped[3].sub(chopped[2])
if dxy.x == 0.0 and dxy.y == 0.0:
dxy = chopped[3].sub(chopped[1])
c_points = chopped
if dxy.x == 0.0 and dxy.y == 0.0:
dxy = c_points[3].sub(c_points[0])
set_ray_points(s, *t_pt, &dxy, on_pt, tangent)
func set_cubic_end_normal(s: const PathStroker*, cubic: const Point[], normal_ab: Point, unit_normal_ab: Point, normal_cd: Point*, unit_normal_cd: Point*):
var ab = cubic[1].sub(cubic[0])
var cd = cubic[3].sub(cubic[2])
var degenerate_ab = degenerate_vector(ab)
var degenerate_cb = degenerate_vector(cd)
if degenerate_ab and degenerate_cb:
*normal_cd = normal_ab
*unit_normal_cd = unit_normal_ab
return
if degenerate_ab:
ab = cubic[2].sub(cubic[0])
degenerate_ab = degenerate_vector(ab)
if degenerate_cb:
cd = cubic[3].sub(cubic[1])
degenerate_cb = degenerate_vector(cd)
if degenerate_ab or degenerate_cb:
*normal_cd = normal_ab
*unit_normal_cd = unit_normal_ab
return
_ = set_normal_unit_normal2(cd, s.radius, normal_cd, unit_normal_cd)
func compare_quad_cubic(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*) -> ResultType:
# get the quadratic approximation of the stroke
cubic_quad_ends(s, cubic, quad_points)
let result_type = intersect_ray(s, .ctrl_pt, quad_points)
if result_type != .quad:
return result_type
# project a ray from the curve to the stroke
# points near midpoint on quad, midpoint on cubic
var ray0 = Point.zero()
var ray1 = Point.zero()
cubic_perp_ray(s, cubic, quad_points.mid_t, &ray1, &ray0, none)
let stroke = quad_points.quad
return stroke_close_enough(s, stroke, [ray0, ray1], quad_points)
# Given a cubic and a t range, find the start and end if they haven't been found already.
func cubic_quad_ends(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*):
if not quad_points.start_set:
var cubic_start_pt = Point.zero()
cubic_perp_ray(s, cubic, quad_points.start_t, &cubic_start_pt, &quad_points.quad[0], &quad_points.tangent_start)
quad_points.start_set = true
if not quad_points.end_set:
var cubic_end_pt = Point.zero()
cubic_perp_ray(s, cubic, quad_points.end_t, &cubic_end_pt, &quad_points.quad[2], &quad_points.tangent_end)
quad_points.end_set = true
func init_quad(s: PathStroker*, stroke_type: StrokeType, start: f32, end: f32, quad_points: QuadConstruct*):
s.stroke_type = stroke_type
s.found_tangents = false
_ = quad_points.init_(start, end)
func quad_stroke(s: PathStroker*, quad: const Point[], quad_points: QuadConstruct*) -> bool:
let result_type = compare_quad_quad(s, quad, quad_points)
if result_type == .quad:
let path: PathBuilder* = &s.outer if s.stroke_type == .outer else &s.inner
path.quad_to(quad_points.quad[1].x, quad_points.quad[1].y, quad_points.quad[2].x, quad_points.quad[2].y)
return true
if result_type == .degenerate:
add_degenerate_line(s, quad_points)
return true
s.recursion_depth += 1
if s.recursion_depth > recursive_limits[quad_recursive_limit]:
# If we stop making progress, just emit a line and move on
add_degenerate_line(s, quad_points)
return true
var half_quad = QuadConstruct.default()
_ = half_quad.init_with_start(quad_points)
if not quad_stroke(s, quad, &half_quad):
return false
_ = half_quad.init_with_end(quad_points)
if not quad_stroke(s, quad, &half_quad):
return false
s.recursion_depth -= 1
return true
func compare_quad_quad(s: PathStroker*, quad: const Point[], quad_points: QuadConstruct*) -> ResultType:
# get the quadratic approximation of the stroke
if not quad_points.start_set:
var quad_start_pt = Point.zero()
quad_perp_ray(s, quad, quad_points.start_t, &quad_start_pt, &quad_points.quad[0], &quad_points.tangent_start)
quad_points.start_set = true
if not quad_points.end_set:
var quad_end_pt = Point.zero()
quad_perp_ray(s, quad, quad_points.end_t, &quad_end_pt, &quad_points.quad[2], &quad_points.tangent_end)
quad_points.end_set = true
let result_type = intersect_ray(s, .ctrl_pt, quad_points)
if result_type != .quad:
return result_type
# project a ray from the curve to the stroke
var ray0 = Point.zero()
var ray1 = Point.zero()
quad_perp_ray(s, quad, quad_points.mid_t, &ray1, &ray0, none)
let stroke = quad_points.quad
return stroke_close_enough(s, stroke, [ray0, ray1], quad_points)
# Given a point on the curve and its derivative, scale the derivative by the radius, and
# compute the perpendicular point and its tangent.
func set_ray_points(s: const PathStroker*, tp: Point, dxy: Point*, on_p: Point*, tangent: Point*?):
if not dxy.set_length(s.radius):
*dxy = Point.from_xy(s.radius, 0.0)
let axis_flip = (f32)(i32)(i8)s.stroke_type # go opposite ways for outer, inner
on_p.x = tp.x + axis_flip * dxy.y
on_p.y = tp.y - axis_flip * dxy.x
if let t = tangent:
*t = *dxy
# Given a quad and t, return the point on curve, its perpendicular, and the perpendicular
# tangent.
func quad_perp_ray(s: const PathStroker*, quad: const Point[], t: f32, tp: Point*, on_p: Point*, tangent: Point*?):
*tp = eval_quad_at(quad, t)
var dxy = eval_quad_tangent_at(quad, t)
if dxy.is_zero():
dxy = quad[2].sub(quad[0])
set_ray_points(s, *tp, &dxy, on_p, tangent)
func add_degenerate_line(s: PathStroker*, quad_points: const QuadConstruct*):
if s.stroke_type == .outer:
s.outer.line_to(quad_points.quad[2].x, quad_points.quad[2].y)
else:
s.inner.line_to(quad_points.quad[2].x, quad_points.quad[2].y)
func stroke_close_enough(s: const PathStroker*, stroke: Point[3], ray: Point[2], quad_points: QuadConstruct*) -> ResultType:
let half_t = normalized_clamped(0.5)
let stroke_mid = eval_quad_at(stroke, half_t)
# measure the distance from the curve to the quad-stroke midpoint, compare to radius
if points_within_dist(ray[0], stroke_mid, s.inv_res_scale):
# if the difference is small
if sharp_angle(quad_points.quad):
return .split
return .quad
# measure the distance to quad's bounds (quick reject)
# an alternative : look for point in triangle
if not pt_in_quad_bounds(stroke, ray[0], s.inv_res_scale):
# if far, subdivide
return .split
# measure the curve ray distance to the quad-stroke
var roots = new_t_values()
let roots_len = intersect_quad_ray(ray, stroke, roots)
if roots_len != 1:
return .split
let quad_pt = eval_quad_at(stroke, roots[0])
let err = s.inv_res_scale * (1.0 - math32.abs(roots[0] - 0.5) * 2.0)
if points_within_dist(ray[0], quad_pt, err):
# if the difference is small, we're done
if sharp_angle(quad_points.quad):
return .split
return .quad
# otherwise, subdivide
return .split
# Find the intersection of the stroke tangents to construct a stroke quad. Return whether the
# stroke is a degenerate (a line), a quad, or must be split. Optionally compute the quad's
# control point.
func intersect_ray(s: const PathStroker*, intersect_ray_type: IntersectRayType, quad_points: QuadConstruct*) -> ResultType:
let start = quad_points.quad[0]
let end = quad_points.quad[2]
let a_len = quad_points.tangent_start
let b_len = quad_points.tangent_end
# Slopes match when denom goes to zero:
# axLen / ayLen == bxLen / byLen
# (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
# byLen * axLen == ayLen * bxLen
# byLen * axLen - ayLen * bxLen ( == denom )
let denom = a_len.cross(b_len)
if denom == 0.0 or not math32.is_finite(denom):
quad_points.opposite_tangents = a_len.dot(b_len) < 0.0
return .degenerate
quad_points.opposite_tangents = false
let ab0 = start.sub(end)
var numer_a = b_len.cross(ab0)
let numer_b = a_len.cross(ab0)
if (numer_a >= 0.0) == (numer_b >= 0.0):
# if the control point is outside the quad ends
# if the perpendicular distances from the quad points to the opposite tangent line
# are small, a straight line is good enough
let dist1 = pt_to_tangent_line(start, end, quad_points.tangent_end)
let dist2 = pt_to_tangent_line(end, start, quad_points.tangent_start)
if fmax(dist1, dist2) <= s.inv_res_scale_squared:
return .degenerate
return .split
# check to see if the denominator is teeny relative to the numerator
# if the offset by one will be lost, the ratio is too large
numer_a /= denom
let valid_divide = numer_a > numer_a - 1.0
if valid_divide:
if intersect_ray_type == .ctrl_pt:
# the intersection of the tangents need not be on the tangent segment
# so 0 <= numer_a <= 1 is not necessarily true
quad_points.quad[1] = Point.from_xy(start.x + quad_points.tangent_start.x * numer_a, start.y + quad_points.tangent_start.y * numer_a)
return .quad
quad_points.opposite_tangents = a_len.dot(b_len) < 0.0
# if the lines are parallel, straight line is good enough
return .degenerate
# Given a cubic and a t-range, determine if the stroke can be described by a quadratic.
func tangents_meet(s: const PathStroker*, cubic: const Point[], quad_points: QuadConstruct*) -> ResultType:
cubic_quad_ends(s, cubic, quad_points)
return intersect_ray(s, .result_type, quad_points)
# mark: QuadConstruct =========================================================================
struct QuadConstruct:
# The state of the quad stroke under construction.
var quad: Point[3] # the stroked quad parallel to the original curve
var tangent_start: Point # the tangent vector at quad[0]
var tangent_end: Point # the tangent vector at quad[2]
var start_t: f32 # a segment of the original curve
var mid_t: f32
var end_t: f32
var start_set: bool # state to share common points across structs
var end_set: bool
var opposite_tangents: bool # set if coincident tangents have opposite directions
static func default() -> QuadConstruct:
var q: QuadConstruct
return q
# return false if start and end are too close to have a unique middle
func init_(start: f32, end: f32) -> bool:
self.start_t = start
self.mid_t = normalized_clamped(half(start + end))
self.end_t = end
self.start_set = false
self.end_set = false
return self.start_t < self.mid_t and self.mid_t < self.end_t
func init_with_start(parent: const QuadConstruct*) -> bool:
if not self.init_(parent.start_t, parent.mid_t):
return false
self.quad[0] = parent.quad[0]
self.tangent_start = parent.tangent_start
self.start_set = true
return true
func init_with_end(parent: const QuadConstruct*) -> bool:
if not self.init_(parent.mid_t, parent.end_t):
return false
self.quad[2] = parent.quad[2]
self.tangent_end = parent.tangent_end
self.end_set = true
return true