dymokomi/luce-browser-render
Source of release 0.6.2
0.6.2 / src / raster / path_convexity.lucb
#==============================================================================================
#
# path_convexity - whether a path is convex, and whether it is a rectangle
#
# DESCRIPTION:
# Port of Skia m144 src/core/SkPathPriv.cpp: ComputeConvexity with its Convexicator
# (the scan converters take faster, differently rounding paths for convex paths, so
# the answer must be Skia's) and IsRectContour with trivial_rect (SkPathRaw::isRect,
# which lets the analytic AA converter blit a fat rectangle directly).
#
# Copyright (c) 2006 The Android Open Source Project
# Copyright (c) 2026 the luce-browser authors.
# SPDX-License-Identifier: BSD-3-Clause (see LICENSE-skia)
#
#==============================================================================================
# mark: ComputeConvexity ======================================================================
enum DirChange as u8:
unknown = 0
left = 1
right = 2
straight = 3
## if double back, allow simple lines to be convex
backwards = 4
invalid = 5
## SkPathFirstDirection.
enum FirstDirection as u8:
cw = 0
ccw = 1
unknown = 2
## Only valid for a single contour.
struct Convexicator:
## The first point of the contour, e.g. moveTo(x,y).
var first_pt: Point
## The direction leaving first_pt to the next vertex.
var first_vec: Point
## The last point passed to add_pt().
var last_pt: Point
## The direction that brought the path to last_pt.
var last_vec: Point
var expected_dir: DirChange = .invalid
var first_direction: FirstDirection = .unknown
var reversals: i32 = 0
var is_finite: bool = true
func set_move_pt(pt: Point):
self.first_pt = pt
self.last_pt = pt
self.expected_dir = .invalid
func add_pt(pt: Point) -> bool:
if self.last_pt.x == pt.x and self.last_pt.y == pt.y:
return true
# should only be true for first non-zero vector after set_move_pt was called. It is
# possible we doubled backed at the start so need to check if last_vec is zero or not.
if self.first_pt.x == self.last_pt.x and self.first_pt.y == self.last_pt.y and self.expected_dir == .invalid and self.last_vec.x == 0.0 and self.last_vec.y == 0.0:
self.last_vec = Point.from_xy(pt.x - self.last_pt.x, pt.y - self.last_pt.y)
self.first_vec = self.last_vec
elif not self.add_vec(Point.from_xy(pt.x - self.last_pt.x, pt.y - self.last_pt.y)):
return false
self.last_pt = pt
return true
## If this was an explicit close, there was already a lineTo to first_pt, so this
## add_pt() is a no-op. Otherwise, the add_pt implicitly closes the contour. In either
## case, we have to check the direction change along the first vector in case it is
## concave.
func close() -> bool:
return self.add_pt(self.first_pt) and self.add_vec(self.first_vec)
func direction_change(cur_vec: Point) -> DirChange:
let cross = self.last_vec.x * cur_vec.y - self.last_vec.y * cur_vec.x
if not is_finite(cross):
return .unknown
if cross == 0.0:
if self.last_vec.x * cur_vec.x + self.last_vec.y * cur_vec.y < 0.0:
return .backwards
return .straight
return .right if cross > 0.0 else .left
func add_vec(cur_vec: Point) -> bool:
let dir = self.direction_change(cur_vec)
match dir:
.left, .right:
if self.expected_dir == .invalid:
self.expected_dir = dir
self.first_direction = .cw if dir == .right else .ccw
elif dir != self.expected_dir:
self.first_direction = .unknown
return false
self.last_vec = cur_vec
.straight:
return true
.backwards:
# allow path to reverse direction twice
# Given path.moveTo(0, 0); path.lineTo(1, 1);
# - 1st reversal: direction change formed by line (0,0 1,1), line (1,1 0,0)
# - 2nd reversal: direction change formed by line (1,1 0,0), line (0,0 1,1)
self.last_vec = cur_vec
self.reversals += 1
return self.reversals < 3
.unknown:
self.is_finite = false
return false
_:
trap("raster: Use of invalid direction change flag")
return true
func sign_of(x: f32) -> i32:
return 1 if x < 0.0 else 0
## Convexicator::IsConcaveBySign: whether the path changes direction more than three times.
func is_concave_by_sign(points: const Point[]) -> bool:
let count = points.length
if count <= 3:
# point, line, or triangle are always convex
return false
var index: usize = 1
var curr_pt = points[0]
let first_pt = curr_pt
var dxes: i32 = 0
var dyes: i32 = 0
var last_sx: i32 = 2 # a value never returned by sign_of
var last_sy: i32 = 2
for outer_loop in 0..<2:
while true:
# the second pass visits the first point only
var pt = first_pt
if outer_loop == 0:
if index == count:
break
pt = points[index]
let vx = pt.x - curr_pt.x
let vy = pt.y - curr_pt.y
if not (vx == 0.0 and vy == 0.0):
# give up if vector construction failed
if not is_finite(vx) or not is_finite(vy):
return true # treat as concave
let sx = sign_of(vx)
let sy = sign_of(vy)
dxes += 1 if sx != last_sx else 0
dyes += 1 if sy != last_sy else 0
if dxes > 3 or dyes > 3:
return true
last_sx = sx
last_sy = sy
curr_pt = pt
index += 1
if outer_loop == 1:
break
return false # that is, it may be convex, don't know yet
## SkPathPriv::ComputeConvexity, reduced to what the scan converters ask: is it convex.
func path_is_convex(path: const Path*) -> bool:
var verbs = path.verbs.view()
var points = path.points.view()
# trim_trailing_moves
while verbs.length > 0 and verbs[verbs.length - 1] == .move:
verbs = verbs[..<verbs.length - 1]
points = points[..<points.length - 1]
if verbs.length == 0:
return true # kConvex_Degenerate
# Check to see if path changes direction more than three times as quick concave test
if is_concave_by_sign(points):
return false
var contour_count: i32 = 0
var needs_close = false
var state = Convexicator()
var p: usize = 0
for verb in verbs:
var pts_in_verb: usize = 0
match verb:
.line: pts_in_verb = 1
.quad: pts_in_verb = 2
.conic: pts_in_verb = 2
.cubic: pts_in_verb = 3
_: pts_in_verb = 0
# Looking for the last moveTo before non-move verbs start
if contour_count == 0:
if verb == .move:
state.set_move_pt(points[p])
else:
# Starting the actual contour, fall through to c=1 to add the points
contour_count += 1
needs_close = true
# Accumulating points into the Convexicator until we hit a close or another move
if contour_count == 1:
if verb == .close or verb == .move:
if not state.close():
return false
needs_close = false
contour_count += 1
else:
# lines add 1 point, cubics add 3, quads add 2
for i in 0..<pts_in_verb:
if not state.add_pt(points[p + i]):
return false
else:
# The first contour has closed and anything other than spurious trailing moves
# means there's multiple contours and the path can't be convex
if verb != .move:
return false
if verb == .move:
p += 1
else:
p += pts_in_verb
# If the path isn't explicitly closed do so implicitly
if needs_close and not state.close():
return false
if state.first_direction == .unknown and state.reversals >= 3:
return false
return true
# mark: IsRectContour =========================================================================
## rect_make_dir: 0x1 is set if the segment is horizontal, 0x2 if it moves right or down.
func rect_make_dir(dx: f32, dy: f32) -> i32:
let horizontal: i32 = 1 if dx != 0.0 else 0
let forward: i32 = 2 if (dx > 0.0 or dy > 0.0) else 0
return horizontal | forward
func axis_aligned_orthogonal(a: Point, b: Point) -> bool:
return ((a.x == 0.0) != (b.x == 0.0)) and ((a.y == 0.0) != (b.y == 0.0))
## SkPathPriv::RectContour: the rectangle a path is, whether its contour is closed, and its
## direction.
pub struct RectContour:
pub var rect: Rect
pub var is_closed: bool
pub var clockwise: bool
## SkPathPriv::IsRectContour(..., allowPartial = false): the rectangle the path is, if any
## (SkPath::isRect).
func path_is_rect_contour(path: const Path*) -> RectContour?:
let verbs = path.verbs.view()
let pts = path.points.view()
for v in verbs:
if v == .quad or v == .cubic or v == .conic:
return none
if pts.length < 4 or verbs.length < 4:
return none
# Quick check for a "trivial" rect, i.e. a rect created via SkPath::Rect(),
# SkPathBuilder::addRect(), etc.
if pts.length == 4 and verbs.length == 5 and verbs[0] == .move and verbs[1] == .line and verbs[2] == .line and verbs[3] == .line and verbs[4] == .close:
let v0 = Point.from_xy(pts[1].x - pts[0].x, pts[1].y - pts[0].y)
let v1 = Point.from_xy(pts[2].x - pts[1].x, pts[2].y - pts[1].y)
let v2 = Point.from_xy(pts[3].x - pts[2].x, pts[3].y - pts[2].y)
let v3 = Point.from_xy(pts[0].x - pts[3].x, pts[0].y - pts[3].y)
# We have a rect iff the side vectors are axis aligned and form 3 right corners.
if ((v0.x == 0.0) != (v0.y == 0.0)) and axis_aligned_orthogonal(v0, v1) and axis_aligned_orthogonal(v1, v2) and axis_aligned_orthogonal(v2, v3):
let rect = rect_sorted(pts[0], pts[2]) else return none
return RectContour(rect = rect, is_closed = true, clockwise = v0.x * v1.y - v0.y * v1.x > 0.0)
var corners: i32 = 0
var line_start = Point.from_xy(0.0, 0.0)
var first_pt: usize = 0 # first point in the rect (last of first moves)
var last_pt: usize = 0 # last point in the rect (last of lines or first if closed)
var first_corner = Point.zero()
var third_corner = Point.zero()
var p: usize = 0
var directions: i32[5] = [-1, -1, -1, -1, -1]
var closed_or_moved = false
var auto_close = false
for verb in verbs:
match verb:
.close, .line:
if verb == .close:
auto_close = true
else:
last_pt = p
var line_end = pts[first_pt]
if verb != .close:
line_end = pts[p]
p += 1
let dx = line_end.x - line_start.x
let dy = line_end.y - line_start.y
if dx != 0.0 and dy != 0.0:
return none # diagonal
if not is_finite(dx) or not is_finite(dy):
return none # path contains infinity or NaN
if line_start.x == line_end.x and line_start.y == line_end.y:
continue # single point on side OK
let next_direction = rect_make_dir(dx, dy) # 0 to 3
if corners == 0:
directions[0] = next_direction
corners = 1
closed_or_moved = false
line_start = line_end
continue
if closed_or_moved:
return none # closed followed by a line
if auto_close and next_direction == directions[0]:
continue # colinear with first
closed_or_moved = auto_close
if directions[(usize)(corners - 1)] == next_direction:
if corners == 3 and verb == .line:
third_corner = line_end
line_start = line_end
continue # colinear segment
if corners >= 5:
return none
directions[(usize)corners] = next_direction
corners += 1
# opposite lines must point in opposite directions; xoring them should equal 2
if corners == 2:
first_corner = line_start
elif corners == 3:
if (directions[0] ^ directions[2]) != 2:
return none
third_corner = line_end
elif corners == 4:
if (directions[1] ^ directions[3]) != 2:
return none
else:
return none # too many direction changes
line_start = line_end
.move:
if corners == 0:
first_pt = p
else:
let cx = pts[first_pt].x - pts[last_pt].x
let cy = pts[first_pt].y - pts[last_pt].y
if cx != 0.0 and cy != 0.0:
return none # we're diagonal, abort
line_start = pts[p]
p += 1
closed_or_moved = true
_:
return none # quadratic, cubic not allowed
# Success if 4 corners and first point equals last
if corners < 3 or corners > 4:
return none
# check if close generates diagonal
let cx = pts[first_pt].x - pts[last_pt].x
let cy = pts[first_pt].y - pts[last_pt].y
if cx != 0.0 and cy != 0.0:
return none
let rect = rect_sorted(first_corner, third_corner) else return none
return RectContour(rect = rect, is_closed = auto_close, clockwise = directions[0] == ((directions[1] + 1) & 3))
## SkRect::set(a, b) / makeSorted: the rectangle with corners a and b.
func rect_sorted(a: Point, b: Point) -> Rect?:
let l = a.x if a.x < b.x else b.x
let r = a.x if a.x > b.x else b.x
let t = a.y if a.y < b.y else b.y
let bb = a.y if a.y > b.y else b.y
return Rect.from_ltrb(l, t, r, bb)