dymokomi/luce-browser-render
Source of release 0.6.2
0.6.2 / src / raster / dash.lucb
#==============================================================================================
#
# dash - path dashing: SkDashPath, SkDashPathEffect, SkContourMeasure, SkPathMeasure
#
# DESCRIPTION:
# Port of tiny-skia-path dash.rs: StrokeDash (the dash array, owned; `release()`
# frees it; SkDashImpl's parameters) and the contour measuring (ContourMeasureIter,
# ContourMeasure, Segment, the curve length subdivision and segment_to), checked
# against Skia m144's SkContourMeasure.cpp. The dashing itself is dash_filter.lucb.
#
#==============================================================================================
## A stroke dashing properties. Contains an array of pairs, where the first number indicates
## an "on" interval and the second one indicates an "off" interval; a dash offset
## (sometimes also called "phase"). Guarantees that the dash array has an even number of
## non-negative values, their sum is positive and finite, and the offset is finite.
pub struct StrokeDash:
var array: Vec[f32]
var offset: f32
var interval_len: f32
var first_len: f32 # TODO: PositiveF32
var first_index: usize
## Creates a new stroke dashing object (the dash array is copied).
pub static func new_(dash_array: const f32[], dash_offset: f32) -> StrokeDash?:
if not math32.is_finite(dash_offset):
return none
if dash_array.length < 2 or dash_array.length % 2 != 0:
return none
for n in dash_array:
if n < 0.0:
return none
var interval_len: f32 = 0.0
for n in dash_array:
interval_len += n
if not (math32.is_finite(interval_len) and interval_len > 0.0):
return none
let offset = adjust_dash_offset(dash_offset, interval_len)
let (first_len, first_index) = find_first_interval(dash_array, offset)
var array: Vec[f32]
array.extend(dash_array)
return StrokeDash(array = array, offset = offset, interval_len = interval_len, first_len = first_len, first_index = first_index)
## A copy with its own storage.
pub func clone() -> StrokeDash:
return StrokeDash(array = self.array.clone(), offset = self.offset, interval_len = self.interval_len, first_len = self.first_len, first_index = self.first_index)
## Frees the dash array.
pub func release():
self.array.release()
# Adjust phase to be between 0 and len, "flipping" phase if negative.
# e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80.
func adjust_dash_offset(offset0: f32, len: f32) -> f32:
var offset = offset0
if offset < 0.0:
offset = -offset
if offset > len:
offset = math32.mod(offset, len)
offset = len - offset
# Due to finite precision, it's possible that phase == len, even after the subtract
# (if len >>> phase), so fix that here.
if offset == len:
offset = 0.0
return offset
elif offset >= len:
return math32.mod(offset, len)
return offset
func find_first_interval(dash_array: const f32[], dash_offset0: f32) -> (f32, usize):
var dash_offset = dash_offset0
for (i, gap) in dash_array.indexed():
if dash_offset > gap or (dash_offset == gap and gap != 0.0):
dash_offset -= gap
else:
return (gap - dash_offset, i)
# If we get here, phase "appears" to be larger than our length. This shouldn't happen
# with perfect precision, but we can accumulate errors during the initial length
# computation (rounding can make our sum be too big or too small. In that event, we just
# have to eat the error here.
return (dash_array[0], 0)
func is_even(x: usize) -> bool:
return x % 2 == 0
let max_t_value: u32 = 0x3FFFFFFF
struct ContourMeasureIter:
var iter: PathSegmentsIter
var tolerance: f32
static func new_(path: const Path*, res_scale: f32) -> ContourMeasureIter:
# can't use tangents, since we need [0..1..................2] to be seen as definitely
# not a line (it is when drawn, but not parametrically) so we compare midpoints
let cheap_dist_limit: f32 = 0.5 # just made this value up
return ContourMeasureIter(iter = path.segments(), tolerance = cheap_dist_limit * invert(res_scale))
## SkContourMeasureIter::next: the next contour with a length (zero-length contours are
## skipped).
func next() -> ContourMeasure?:
while let _ = self.iter.next_verb():
if let contour = self.build_segments():
return contour
return none
## SkContourMeasureIter::Impl::buildSegments: the segments of the contour at the iterator,
## none when it has no length.
func build_segments() -> ContourMeasure?:
# Note: as we accumulate distance, we have to check that the result of += actually
# made it larger, since a very small delta might be > 0, but still have no effect on
# distance (if distance >>> delta).
#
# We do this check below, and in compute_quad_segs and compute_cubic_segs
var contour: ContourMeasure
var point_index: usize = 0
var distance: f32 = 0.0
var have_seen_close = false
var prev_p = Point.zero()
while let seg = self.iter.next():
match seg:
.move_to(p0):
contour.points.push(p0)
prev_p = p0
.line_to(p0):
let prev_d = distance
distance = contour.compute_line_seg(prev_p, p0, distance, point_index)
if distance > prev_d:
contour.points.push(p0)
point_index += 1
prev_p = p0
.quad_to(p0, p1):
let prev_d = distance
distance = contour.compute_quad_segs(prev_p, p0, p1, distance, 0, max_t_value, point_index, self.tolerance, 0)
if distance > prev_d:
contour.points.push(p0)
contour.points.push(p1)
point_index += 2
prev_p = p1
.conic_to(p0, p1, weight):
let prev_d = distance
let conic = Conic.new_(prev_p, p0, p1, weight)
distance = contour.compute_conic_segs(&conic, distance, 0, prev_p, max_t_value, p1, point_index, self.tolerance, 0)
if distance > prev_d:
# we store the conic weight in our next point, followed by the last 2
# pts thus to reconstitue a conic, you'd need to say
# Conic(pts[0], pts[2], pts[3], weight = pts[1].x)
contour.points.push(Point.from_xy(weight, 0.0))
contour.points.push(p0)
contour.points.push(p1)
point_index += 3
prev_p = p1
.cubic_to(p0, p1, p2):
let prev_d = distance
distance = contour.compute_cubic_segs(prev_p, p0, p1, p2, distance, 0, max_t_value, point_index, self.tolerance, 0)
if distance > prev_d:
contour.points.push(p0)
contour.points.push(p1)
contour.points.push(p2)
point_index += 3
prev_p = p2
.close:
have_seen_close = true
# TODO: to contour iter?
if let next_verb = self.iter.next_verb():
if next_verb == .move:
break
if not math32.is_finite(distance) or contour.segments.is_empty():
contour.release()
return none
if have_seen_close:
let prev_d = distance
let first_pt = contour.points.data[0]
distance = contour.compute_line_seg(contour.points.data[point_index], first_pt, distance, point_index)
if distance > prev_d:
contour.points.push(first_pt)
contour.length = distance
contour.is_closed = have_seen_close
if contour.points.is_empty():
contour.release()
return none
return contour
enum SegmentType as u8:
line = 0
quad = 1
cubic = 2
conic = 3
struct Segment:
var distance: f32 # total distance up to this point
var point_index: usize # index into the ContourMeasure::points array
var t_value: u32
var kind: SegmentType
func scalar_t() -> f32:
# 1/kMaxTValue can't be represented as a float, but it's close and the limits work
# fine.
let max_t_reciprocal: f32 = 1.0 / (f32)max_t_value
return (f32)self.t_value * max_t_reciprocal
struct ContourMeasure:
var segments: Vec[Segment]
var points: Vec[Point]
var length: f32
var is_closed: bool
func release():
self.segments.release()
self.points.release()
func push_segment(start_d0: f32, stop_d0: f32, start_with_move_to: bool, pb: PathBuilder*):
var start_d = start_d0
var stop_d = stop_d0
if start_d < 0.0:
start_d = 0.0
if stop_d > self.length:
stop_d = self.length
if not (start_d <= stop_d):
# catch NaN values as well
return
if self.segments.is_empty():
return
let start_pair = self.distance_to_segment(start_d) else return
let seg_index = start_pair.0
var start_t = start_pair.1
var seg = self.segments.data[seg_index]
let stop_pair = self.distance_to_segment(stop_d) else return
let stop_seg_index = stop_pair.0
let stop_t = stop_pair.1
let stop_seg = self.segments.data[stop_seg_index]
let points = self.points.view()
var p = Point.zero()
if start_with_move_to:
compute_pos_tan(points[seg.point_index..], seg.kind, start_t, &p, none)
pb.move_to(p.x, p.y)
if seg.point_index == stop_seg.point_index:
segment_to(points[seg.point_index..], seg.kind, start_t, stop_t, pb)
else:
var new_seg_index = seg_index
while true:
segment_to(points[seg.point_index..], seg.kind, start_t, 1.0, pb)
let old_point_index = seg.point_index
while true:
new_seg_index += 1
if self.segments.data[new_seg_index].point_index != old_point_index:
break
seg = self.segments.data[new_seg_index]
start_t = 0.0
if seg.point_index >= stop_seg.point_index:
break
segment_to(points[seg.point_index..], seg.kind, 0.0, stop_t, pb)
func distance_to_segment(distance: f32) -> (usize, f32)?:
var index = find_segment(self.segments.view(), distance)
# don't care if we hit an exact match or not, so we xor index if it is negative
index ^= index >> 31
let seg_index = (usize)index
let seg = self.segments.data[seg_index]
# now interpolate t-values with the prev segment (if possible)
var start_t: f32 = 0.0
var start_d: f32 = 0.0
# check if the prev segment is legal, and references the same set of points
if seg_index > 0:
start_d = self.segments.data[seg_index - 1].distance
if self.segments.data[seg_index - 1].point_index == seg.point_index:
start_t = self.segments.data[seg_index - 1].scalar_t()
let t = start_t + (seg.scalar_t() - start_t) * (distance - start_d) / (seg.distance - start_d)
# getSegment refuses only a t that is not finite.
if not math32.is_finite(t):
return none
return (seg_index, t)
func compute_line_seg(p0: Point, p1: Point, distance0: f32, point_index: usize) -> f32:
var distance = distance0
let d = p0.distance(p1)
let prev_d = distance
distance += d
if distance > prev_d:
self.segments.push(Segment(distance = distance, point_index = point_index, t_value = max_t_value, kind = .line))
return distance
func compute_quad_segs(p0: Point, p1: Point, p2: Point, distance0: f32, min_t: u32, max_t: u32, point_index: usize, tolerance: f32, depth: i32) -> f32:
var distance = distance0
if depth < max_recursion_depth and t_span_big_enough(max_t - min_t) != 0 and quad_too_curvy(p0, p1, p2, tolerance):
var tmp: Point[5] = [Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero()]
let half_t = (min_t + max_t) >> 1
chop_quad_at([p0, p1, p2], normalized_exclusive_half, tmp)
distance = self.compute_quad_segs(tmp[0], tmp[1], tmp[2], distance, min_t, half_t, point_index, tolerance, depth + 1)
distance = self.compute_quad_segs(tmp[2], tmp[3], tmp[4], distance, half_t, max_t, point_index, tolerance, depth + 1)
else:
let d = p0.distance(p2)
let prev_d = distance
distance += d
if distance > prev_d:
self.segments.push(Segment(distance = distance, point_index = point_index, t_value = max_t, kind = .quad))
return distance
## compute_conic_segs of SkContourMeasure.cpp: the conic split at t values until each
## piece is flat enough.
func compute_conic_segs(conic: const Conic*, distance0: f32, min_t: u32, min_pt: Point, max_t: u32, max_pt: Point, point_index: usize, tolerance: f32, depth: i32) -> f32:
var distance = distance0
let half_t = (min_t + max_t) >> 1
let half_pt = conic.eval_at((f32)half_t * (1.0 / (f32)max_t_value))
if not half_pt.is_finite():
return distance
if depth < max_recursion_depth and t_span_big_enough(max_t - min_t) != 0 and conic_too_curvy(min_pt, half_pt, max_pt, tolerance):
distance = self.compute_conic_segs(conic, distance, min_t, min_pt, half_t, half_pt, point_index, tolerance, depth + 1)
distance = self.compute_conic_segs(conic, distance, half_t, half_pt, max_t, max_pt, point_index, tolerance, depth + 1)
else:
let d = min_pt.distance(max_pt)
let prev_d = distance
distance += d
if distance > prev_d:
self.segments.push(Segment(distance = distance, point_index = point_index, t_value = max_t, kind = .conic))
return distance
func compute_cubic_segs(p0: Point, p1: Point, p2: Point, p3: Point, distance0: f32, min_t: u32, max_t: u32, point_index: usize, tolerance: f32, depth: i32) -> f32:
var distance = distance0
if depth < max_recursion_depth and t_span_big_enough(max_t - min_t) != 0 and cubic_too_curvy(p0, p1, p2, p3, tolerance):
var tmp: Point[7] = [Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero()]
let half_t = (min_t + max_t) >> 1
chop_cubic_at2([p0, p1, p2, p3], normalized_exclusive_half, tmp)
distance = self.compute_cubic_segs(tmp[0], tmp[1], tmp[2], tmp[3], distance, min_t, half_t, point_index, tolerance, depth + 1)
distance = self.compute_cubic_segs(tmp[3], tmp[4], tmp[5], tmp[6], distance, half_t, max_t, point_index, tolerance, depth + 1)
else:
let d = p0.distance(p3)
let prev_d = distance
distance += d
if distance > prev_d:
self.segments.push(Segment(distance = distance, point_index = point_index, t_value = max_t, kind = .cubic))
return distance
## SkContourMeasure's kMaxRecursionDepth: puts a cap on the total size of our output, since
## the client can pass in arbitrarily large values for res_scale.
let max_recursion_depth: i32 = 8
func find_segment(base: const Segment[], key: f32) -> i32:
var lo: u32 = 0
var hi = (u32)(base.length - 1)
while lo < hi:
let mid = (hi + lo) >> 1
if base[(usize)mid].distance < key:
lo = mid + 1
else:
hi = mid
if base[(usize)hi].distance < key:
hi += 1
hi = ~hi
elif key < base[(usize)hi].distance:
hi = ~hi
return (i32)hi
func compute_pos_tan(points: const Point[], seg_kind: SegmentType, t: f32, pos: Point*?, tangent: Point*?):
match seg_kind:
.line:
if let p = pos:
*p = Point.from_xy(dash_interp(points[0].x, points[1].x, t), dash_interp(points[0].y, points[1].y, t))
if let tg = tangent:
_ = tg.set_normalize(points[1].x - points[0].x, points[1].y - points[0].y)
.quad:
if let p = pos:
*p = eval_quad_at(points, t)
if let tg = tangent:
*tg = eval_quad_tangent_at(points, t)
_ = tg.normalize()
.conic:
let conic = Conic.new_(points[0], points[2], points[3], points[1].x)
if let p = pos:
*p = conic.eval_at(t)
if let tg = tangent:
*tg = conic.eval_tangent_at(t)
_ = tg.normalize()
.cubic:
if let p = pos:
*p = eval_cubic_pos_at(points, t)
if let tg = tangent:
*tg = eval_cubic_tangent_at(points, t)
_ = tg.normalize()
_:
return
func segment_to(points: const Point[], seg_kind: SegmentType, start_t: f32, stop_t: f32, pb: PathBuilder*):
if start_t == stop_t:
if let pt = pb.last_point():
# If the dash as a zero-length on segment, add a corresponding zero-length line.
# The stroke code will add end caps to zero length lines as appropriate.
pb.line_to(pt.x, pt.y)
return
match seg_kind:
.line:
if stop_t == 1.0:
pb.line_to(points[1].x, points[1].y)
else:
pb.line_to(dash_interp(points[0].x, points[1].x, stop_t), dash_interp(points[0].y, points[1].y, stop_t))
.quad:
var tmp0: Point[5] = [Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero()]
var tmp1: Point[5] = [Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero()]
if start_t == 0.0:
if stop_t == 1.0:
pb.quad_to_pt(points[1], points[2])
else:
let stop_tt = normalized_exclusive_new_bounded(stop_t)
chop_quad_at(points, stop_tt, tmp0)
pb.quad_to_pt(tmp0[1], tmp0[2])
else:
let start_tt = normalized_exclusive_new_bounded(start_t)
chop_quad_at(points, start_tt, tmp0)
if stop_t == 1.0:
pb.quad_to_pt(tmp0[3], tmp0[4])
else:
let new_t = normalized_exclusive_new_bounded((stop_t - start_t) / (1.0 - start_t))
chop_quad_at(tmp0[2..], new_t, tmp1)
pb.quad_to_pt(tmp1[1], tmp1[2])
.conic:
let conic = Conic.new_(points[0], points[2], points[3], points[1].x)
if start_t == 0.0:
if stop_t == 1.0:
pb.conic_to(conic.points[1].x, conic.points[1].y, conic.points[2].x, conic.points[2].y, conic.weight)
elif let pair = conic.chop_at(stop_t):
pb.conic_to(pair.0.points[1].x, pair.0.points[1].y, pair.0.points[2].x, pair.0.points[2].y, pair.0.weight)
else:
if stop_t == 1.0:
if let pair = conic.chop_at(start_t):
pb.conic_to(pair.1.points[1].x, pair.1.points[1].y, pair.1.points[2].x, pair.1.points[2].y, pair.1.weight)
else:
let part = conic.chop_between(start_t, stop_t)
pb.conic_to(part.points[1].x, part.points[1].y, part.points[2].x, part.points[2].y, part.weight)
.cubic:
var tmp0: Point[7] = [Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero()]
var tmp1: Point[7] = [Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero(), Point.zero()]
if start_t == 0.0:
if stop_t == 1.0:
pb.cubic_to_pt(points[1], points[2], points[3])
else:
let stop_tt = normalized_exclusive_new_bounded(stop_t)
chop_cubic_at2(points, stop_tt, tmp0)
pb.cubic_to_pt(tmp0[1], tmp0[2], tmp0[3])
else:
let start_tt = normalized_exclusive_new_bounded(start_t)
chop_cubic_at2(points, start_tt, tmp0)
if stop_t == 1.0:
pb.cubic_to_pt(tmp0[4], tmp0[5], tmp0[6])
else:
let new_t = normalized_exclusive_new_bounded((stop_t - start_t) / (1.0 - start_t))
chop_cubic_at2(tmp0[3..], new_t, tmp1)
pb.cubic_to_pt(tmp1[1], tmp1[2], tmp1[3])
_:
return
func t_span_big_enough(t_span: u32) -> u32:
return t_span >> 10
func quad_too_curvy(p0: Point, p1: Point, p2: Point, tolerance: f32) -> bool:
# diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
# diff = -a/4 + b/2 - c/4
let dx = half(p1.x) - half(half(p0.x + p2.x))
let dy = half(p1.y) - half(half(p0.y + p2.y))
let dist = fmax(math32.abs(dx), math32.abs(dy))
return dist > tolerance
func conic_too_curvy(first_pt: Point, mid_t_pt: Point, last_pt: Point, tolerance: f32) -> bool:
let mid_ends_x = (first_pt.x + last_pt.x) * 0.5
let mid_ends_y = (first_pt.y + last_pt.y) * 0.5
let dist = fmax(math32.abs(mid_t_pt.x - mid_ends_x), math32.abs(mid_t_pt.y - mid_ends_y))
return dist > tolerance
func cubic_too_curvy(p0: Point, p1: Point, p2: Point, p3: Point, tolerance: f32) -> bool:
let n0 = cheap_dist_exceeds_limit(p1, interp_safe(p0.x, p3.x, 1.0 / 3.0), interp_safe(p0.y, p3.y, 1.0 / 3.0), tolerance)
let n1 = cheap_dist_exceeds_limit(p2, interp_safe(p0.x, p3.x, 2.0 / 3.0), interp_safe(p0.y, p3.y, 2.0 / 3.0), tolerance)
return n0 or n1
func cheap_dist_exceeds_limit(pt: Point, x: f32, y: f32, tolerance: f32) -> bool:
let dist = fmax(math32.abs(x - pt.x), math32.abs(y - pt.y))
# just made up the 1/2
return dist > tolerance
func dash_interp(a: f32, b: f32, t: f32) -> f32:
return a + (b - a) * t
func interp_safe(a: f32, b: f32, t: f32) -> f32:
return a + (b - a) * t