dymokomi/luce-browser-render
Source of release 0.6.2
0.6.2 / src / raster / stroker_joins.lucb
#==============================================================================================
#
# stroker_joins - stroke caps and joins, and the curve linearity tests
#
# DESCRIPTION:
# Port of tiny-skia-path stroker.rs, part 3 (lines 1010-2030): the cap procedures
# (butt, round, square), the join procedures (bevel, round, miter, miter-clip),
# set_normal_unit_normal, QuadConstruct's helpers and the quad/cubic linearity and
# intersection tests.
#
#==============================================================================================
# mark: Caps ==================================================================================
func cap_factory(cap: LineCap) -> CapProc:
match cap:
.butt: return butt_capper
.round: return round_capper
.square: return square_capper
_: return butt_capper
func butt_capper(_pivot: Point, _normal: Point, stop: Point, _other_path: const PathBuilder*?, path: PathBuilder*):
path.line_to(stop.x, stop.y)
func round_capper(pivot: Point, normal: Point, stop: Point, _other_path: const PathBuilder*?, path: PathBuilder*):
var parallel = normal
parallel.rotate_cw()
let projected_center = pivot.add(parallel)
path.conic_points_to(projected_center.add(normal), projected_center, scalar_root_2_over_2)
path.conic_points_to(projected_center.sub(normal), stop, scalar_root_2_over_2)
func square_capper(pivot: Point, normal: Point, stop: Point, other_path: const PathBuilder*?, path: PathBuilder*):
var parallel = normal
parallel.rotate_cw()
if other_path != none:
path.set_last_point(Point.from_xy(pivot.x + normal.x + parallel.x, pivot.y + normal.y + parallel.y))
path.line_to(pivot.x - normal.x + parallel.x, pivot.y - normal.y + parallel.y)
else:
path.line_to(pivot.x + normal.x + parallel.x, pivot.y + normal.y + parallel.y)
path.line_to(pivot.x - normal.x + parallel.x, pivot.y - normal.y + parallel.y)
path.line_to(stop.x, stop.y)
func fn_ptr_eq(f1: CapProc, f2: CapProc) -> bool:
return (void*)f1 == (void*)f2
# mark: Joins =================================================================================
func join_factory(join: LineJoin) -> JoinProc:
match join:
.miter: return miter_joiner
.miter_clip: return miter_clip_joiner
.round: return round_joiner
.bevel: return bevel_joiner
_: return miter_joiner
func is_clockwise(before: Point, after: Point) -> bool:
return before.x * after.y > before.y * after.x
enum AngleType as u8:
nearly180 = 0
sharp = 1
shallow = 2
nearly_line = 3
func dot_to_angle_type(dot: f32) -> AngleType:
if dot >= 0.0:
# shallow or line
if is_nearly_zero(1.0 - dot):
return .nearly_line
return .shallow
# sharp or 180
if is_nearly_zero(1.0 + dot):
return .nearly180
return .sharp
func handle_inner_join(pivot: Point, after: Point, inner: PathBuilder*):
# In the degenerate case that the stroke radius is larger than our segments just
# connecting the two inner segments may "show through" as a funny diagonal. To
# pseudo-fix this, we go through the pivot point. This adds an extra point/edge, but I
# can't see a cheap way to know when this is not needed :(
inner.line_to(pivot.x, pivot.y)
inner.line_to(pivot.x - after.x, pivot.y - after.y)
func bevel_joiner(before_unit_normal: Point, pivot: Point, after_unit_normal: Point, radius: f32, _inv_miter_limit: f32, _prev_is_line: bool, _curr_is_line: bool, builders0: SwappableBuilders):
var builders = builders0
var after = after_unit_normal.scaled(radius)
if not is_clockwise(before_unit_normal, after_unit_normal):
builders.swap()
after = after.neg()
builders.outer.line_to(pivot.x + after.x, pivot.y + after.y)
handle_inner_join(pivot, after, builders.inner)
func round_joiner(before_unit_normal: Point, pivot: Point, after_unit_normal: Point, radius: f32, _inv_miter_limit: f32, _prev_is_line: bool, _curr_is_line: bool, builders0: SwappableBuilders):
var builders = builders0
let dot_prod = before_unit_normal.dot(after_unit_normal)
let angle_type = dot_to_angle_type(dot_prod)
if angle_type == .nearly_line:
return
var before = before_unit_normal
var after = after_unit_normal
var dir = PathDirection.cw
if not is_clockwise(before, after):
builders.swap()
before = before.neg()
after = after.neg()
dir = .ccw
let ts = Transform.from_row(radius, 0.0, 0.0, radius, pivot.x, pivot.y)
var conics: Conic[5] = [Conic.zero(), Conic.zero(), Conic.zero(), Conic.zero(), Conic.zero()]
let count = Conic.build_unit_arc(before, after, dir, ts, conics)
if count > 0:
for conic in conics[..<count]:
builders.outer.conic_points_to(conic.points[1], conic.points[2], conic.weight)
after.scale(radius)
handle_inner_join(pivot, after, builders.inner)
func miter_joiner(before_unit_normal: Point, pivot: Point, after_unit_normal: Point, radius: f32, inv_miter_limit: f32, prev_is_line: bool, curr_is_line: bool, builders: SwappableBuilders):
miter_joiner_inner(before_unit_normal, pivot, after_unit_normal, radius, inv_miter_limit, false, prev_is_line, curr_is_line, builders)
func miter_clip_joiner(before_unit_normal: Point, pivot: Point, after_unit_normal: Point, radius: f32, inv_miter_limit: f32, prev_is_line: bool, curr_is_line: bool, builders: SwappableBuilders):
miter_joiner_inner(before_unit_normal, pivot, after_unit_normal, radius, inv_miter_limit, true, prev_is_line, curr_is_line, builders)
func do_blunt_or_clipped(builders: SwappableBuilders, pivot: Point, radius: f32, prev_is_line: bool, curr_is_line: bool, before0: Point, mid0: Point, after0: Point, inv_miter_limit: f32, miter_clip: bool):
var before = before0
var mid = mid0
var after = after0
after.scale(radius)
if miter_clip:
_ = mid.normalize()
let cos_beta = before.dot(mid)
let sin_beta = before.cross(mid)
let x = 1.0 / inv_miter_limit if math32.abs(sin_beta) <= scalar_nearly_zero else ((1.0 / inv_miter_limit) - cos_beta) / sin_beta
before.scale(radius)
var before_tangent = before
before_tangent.rotate_cw()
var after_tangent = after
after_tangent.rotate_ccw()
let c1 = pivot.add(before).add(before_tangent.scaled(x))
let c2 = pivot.add(after).add(after_tangent.scaled(x))
if prev_is_line:
builders.outer.set_last_point(c1)
else:
builders.outer.line_to(c1.x, c1.y)
builders.outer.line_to(c2.x, c2.y)
if not curr_is_line:
builders.outer.line_to(pivot.x + after.x, pivot.y + after.y)
handle_inner_join(pivot, after, builders.inner)
func do_miter(builders: SwappableBuilders, pivot: Point, radius: f32, prev_is_line: bool, curr_is_line: bool, mid: Point, after0: Point):
var after = after0
after.scale(radius)
if prev_is_line:
builders.outer.set_last_point(Point.from_xy(pivot.x + mid.x, pivot.y + mid.y))
else:
builders.outer.line_to(pivot.x + mid.x, pivot.y + mid.y)
if not curr_is_line:
builders.outer.line_to(pivot.x + after.x, pivot.y + after.y)
handle_inner_join(pivot, after, builders.inner)
func miter_joiner_inner(before_unit_normal: Point, pivot: Point, after_unit_normal: Point, radius: f32, inv_miter_limit: f32, miter_clip: bool, prev_is_line: bool, curr_is_line0: bool, builders0: SwappableBuilders):
var builders = builders0
var curr_is_line = curr_is_line0
# negate the dot since we're using normals instead of tangents
let dot_prod = before_unit_normal.dot(after_unit_normal)
let angle_type = dot_to_angle_type(dot_prod)
var before = before_unit_normal
var after = after_unit_normal
var mid: Point = ---
if angle_type == .nearly_line:
return
if angle_type == .nearly180:
curr_is_line = false
mid = after.sub(before).scaled(radius / 2.0)
do_blunt_or_clipped(builders, pivot, radius, prev_is_line, curr_is_line, before, mid, after, inv_miter_limit, miter_clip)
return
let ccw = not is_clockwise(before, after)
if ccw:
builders.swap()
before = before.neg()
after = after.neg()
# Before we enter the world of square-roots and divides, check if we're trying to join an
# upright right angle (common case for stroking rectangles). If so, special case that
# (for speed an accuracy). Note: we only need to check one normal if dot==0
if dot_prod == 0.0 and inv_miter_limit <= scalar_root_2_over_2:
mid = before.add(after).scaled(radius)
do_miter(builders, pivot, radius, prev_is_line, curr_is_line, mid, after)
return
# choose the most accurate way to form the initial mid-vector
if angle_type == .sharp:
mid = Point.from_xy(after.y - before.y, before.x - after.x)
if ccw:
mid = mid.neg()
else:
mid = Point.from_xy(before.x + after.x, before.y + after.y)
# midLength = radius / sinHalfAngle
# if (midLength > miterLimit * radius) abort
# if (radius / sinHalf > miterLimit * radius) abort
# if (1 / sinHalf > miterLimit) abort
# if (1 / miterLimit > sinHalf) abort
# My dotProd is opposite sign, since it is built from normals and not tangents
# hence 1 + dot instead of 1 - dot in the formula
let sin_half_angle = math32.sqrt(half(1.0 + dot_prod))
if sin_half_angle < inv_miter_limit:
curr_is_line = false
do_blunt_or_clipped(builders, pivot, radius, prev_is_line, curr_is_line, before, mid, after, inv_miter_limit, miter_clip)
return
_ = mid.set_length(radius / sin_half_angle)
do_miter(builders, pivot, radius, prev_is_line, curr_is_line, mid, after)
func set_normal_unit_normal(before: Point, after: Point, scale: f32, radius: f32, normal: Point*, unit_normal: Point*) -> bool:
if not unit_normal.set_normalize((after.x - before.x) * scale, (after.y - before.y) * scale):
return false
unit_normal.rotate_ccw()
*normal = unit_normal.scaled(radius)
return true
func set_normal_unit_normal2(vec: Point, radius: f32, normal: Point*, unit_normal: Point*) -> bool:
if not unit_normal.set_normalize(vec.x, vec.y):
return false
unit_normal.rotate_ccw()
*normal = unit_normal.scaled(radius)
return true
# mark: Linearity tests =======================================================================
func check_quad_linear(quad: const Point[]) -> (Point, ReductionType):
let degenerate_ab = degenerate_vector(quad[1].sub(quad[0]))
let degenerate_bc = degenerate_vector(quad[2].sub(quad[1]))
if degenerate_ab and degenerate_bc:
return (Point.zero(), ReductionType.point)
if degenerate_ab or degenerate_bc:
return (Point.zero(), ReductionType.line)
if not quad_in_line(quad):
return (Point.zero(), ReductionType.quad)
let t = find_quad_max_curvature(quad)
if t == 0.0 or t == 1.0:
return (Point.zero(), ReductionType.line)
return (eval_quad_at(quad, t), ReductionType.degenerate)
func degenerate_vector(v: Point) -> bool:
return not v.can_normalize()
func quad_in_line(quad: const Point[]) -> bool:
var pt_max: f32 = -1.0
var outer1: usize = 0
var outer2: usize = 0
for index: usize in 0..<2:
for inner in index + 1..<3:
let test_diff = quad[inner].sub(quad[index])
let test_max = fmax(math32.abs(test_diff.x), math32.abs(test_diff.y))
if pt_max < test_max:
outer1 = index
outer2 = inner
pt_max = test_max
let mid = outer1 ^ outer2 ^ 3
let curvature_slop: f32 = 0.000005 # this multiplier is pulled out of the air
let line_slop = pt_max * pt_max * curvature_slop
return pt_to_line(quad[mid], quad[outer1], quad[outer2]) <= line_slop
# returns the distance squared from the point to the line
func pt_to_line(pt: Point, line_start: Point, line_end: Point) -> f32:
let dxy = line_end.sub(line_start)
let ab0 = pt.sub(line_start)
let numer = dxy.dot(ab0)
let denom = dxy.dot(dxy)
let t = numer / denom
if t >= 0.0 and t <= 1.0:
let hit = Point.from_xy(line_start.x * (1.0 - t) + line_end.x * t, line_start.y * (1.0 - t) + line_end.y * t)
return hit.distance_to_sqd(pt)
return pt.distance_to_sqd(line_start)
# Returns the distance squared from the point to the line through `line_start` along
# `tangent` (m144 pt_to_tangent_line).
func pt_to_tangent_line(pt: Point, line_start: Point, tangent: Point) -> f32:
let ab0 = pt.sub(line_start)
let numer = tangent.dot(ab0)
let denom = tangent.dot(tangent)
let t = numer / denom
if t >= 0.0 and t <= 1.0:
let hit = Point.from_xy(line_start.x + tangent.x * t, line_start.y + tangent.y * t)
return hit.distance_to_sqd(pt)
return pt.distance_to_sqd(line_start)
# Intersect the line with the quad and return the t values on the quad where the line
# crosses.
func intersect_quad_ray(line: const Point[], quad: const Point[], roots: f32[]) -> usize:
let vec = line[1].sub(line[0])
var r: f32[3] = [0.0, 0.0, 0.0]
for n: usize in 0..<3:
r[n] = (quad[n].y - line[0].y) * vec.x - (quad[n].x - line[0].x) * vec.y
var a = r[2]
var b = r[1]
let c = r[0]
a += c - 2.0 * b # A = a - 2*b + c
b -= c # B = -(b - c)
return find_unit_quad_roots(a, 2.0 * b, c, roots)
func points_within_dist(near_pt: Point, far_pt: Point, limit: f32) -> bool:
return near_pt.distance_to_sqd(far_pt) <= limit * limit
func sharp_angle(quad: const Point[]) -> bool:
var smaller = quad[1].sub(quad[0])
var larger = quad[1].sub(quad[2])
let smaller_len = smaller.length_sqd()
var larger_len = larger.length_sqd()
if smaller_len > larger_len:
let tmp = smaller
smaller = larger
larger = tmp
larger_len = smaller_len
if not smaller.set_length(larger_len):
return false
let dot = smaller.dot(larger)
return dot > 0.0
# Return true if the point is close to the bounds of the quad. This is used as a quick reject.
func pt_in_quad_bounds(quad: const Point[], pt: Point, inv_res_scale: f32) -> bool:
let x_min = fmin(fmin(quad[0].x, quad[1].x), quad[2].x)
if pt.x + inv_res_scale < x_min:
return false
let x_max = fmax(fmax(quad[0].x, quad[1].x), quad[2].x)
if pt.x - inv_res_scale > x_max:
return false
let y_min = fmin(fmin(quad[0].y, quad[1].y), quad[2].y)
if pt.y + inv_res_scale < y_min:
return false
let y_max = fmax(fmax(quad[0].y, quad[1].y), quad[2].y)
if pt.y - inv_res_scale > y_max:
return false
return true
func check_cubic_linear(cubic: const Point[], reduction: Point[], tangent_pt: Point*?) -> ReductionType:
let degenerate_ab = degenerate_vector(cubic[1].sub(cubic[0]))
let degenerate_bc = degenerate_vector(cubic[2].sub(cubic[1]))
let degenerate_cd = degenerate_vector(cubic[3].sub(cubic[2]))
if degenerate_ab and degenerate_bc and degenerate_cd:
return .point
if (i32)degenerate_ab + (i32)degenerate_bc + (i32)degenerate_cd == 2:
return .line
if not cubic_in_line(cubic):
if let t = tangent_pt:
*t = cubic[2] if degenerate_ab else cubic[1]
return .quad
var t_values: f32[3] = [0.0, 0.0, 0.0]
let count = find_cubic_max_curvature(cubic, t_values)
var r_count: usize = 0
# Now loop over the t-values, and reject any that evaluate to either end-point
for t in t_values[..<count]:
if 0.0 >= t or t >= 1.0:
continue
reduction[r_count] = eval_cubic_pos_at(cubic, t)
if not points_equal(reduction[r_count], cubic[0]) and not points_equal(reduction[r_count], cubic[3]):
r_count += 1
match r_count:
0: return .line
1: return .degenerate
2: return .degenerate2
3: return .degenerate3
_: trap("unreachable")
func cubic_in_line(cubic: const Point[]) -> bool:
var pt_max: f32 = -1.0
var outer1: usize = 0
var outer2: usize = 0
for index: usize in 0..<3:
for inner in index + 1..<4:
let test_diff = cubic[inner].sub(cubic[index])
let test_max = fmax(math32.abs(test_diff.x), math32.abs(test_diff.y))
if pt_max < test_max:
outer1 = index
outer2 = inner
pt_max = test_max
let mid1: usize = ((usize)1 + ((usize)2 >> outer2)) >> outer1
let mid2 = outer1 ^ outer2 ^ mid1
let line_slop = pt_max * pt_max * 0.00001 # this multiplier is pulled out of the air
return pt_to_line(cubic[mid1], cubic[outer1], cubic[outer2]) <= line_slop and pt_to_line(cubic[mid2], cubic[outer1], cubic[outer2]) <= line_slop