Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-vector

Source of release 0.6.0

0.6.0 / src / vector / cells.lucb

#==============================================================================================
#
#   vector/cells - Which cells of a shape need drawing
#
#   DESCRIPTION:
#       A shape's outlines are segments once luce-svg has parsed it (curves flattened, the
#       transform applied), in document pixels when it is parsed over the whole canvas. A
#       cell within a band of any segment — the stroke's reach, where a miter can go, and
#       a pixel or two of anti-aliasing — is an edge cell and is drawn. Every other cell
#       the shape can reach has no edge in it, so the nonzero winding at its centre holds
#       for all of it: inside the fill, one color throughout; outside, nothing. Rows are
#       classified a row of cells at a time, from the fill's crossings with the row's
#       centre line, so the cost follows the outline and the rows, never the area.
#
#==============================================================================================

## What a cell holds.
let cell_outside: u8 = 0
pub let cell_edge: u8 = 1
pub let cell_inside: u8 = 2

## Longest piece of a segment whose box, grown by the band, marks cells.
let mark_piece: f64 = 128.0

## The cells a shape can reach, `left..<right` by `top..<bottom`.
pub struct ShapeReach:
    pub var left: u32
    pub var top: u32
    pub var right: u32
    pub var bottom: u32

## One crossing of a fill outline with a row's centre line: where, and which way.
struct Crossing:
    var x: f64
    var direction: i32

## The kind of each cell in a shape's reach.
pub struct CellPlan:
    pub var reach: ShapeReach
    pub var kinds: u8[]
    pub var width: u32
    pub var height: u32

    ## Sort the cells of `reach` for `drawing` (`spec` parsed over the whole
    ## `width` by `height` canvas).
    pub static func make(drawing: const svg.Drawing*, spec: ShapeSpec, reach: ShapeReach, width: u32, height: u32) -> CellPlan!:
        return try CellPlan.make_from(drawing, 0, drawing.contour_count(), spec, reach, width, height)

    ## `make` for one element of a drawing of several: its contours `first..<last`.
    pub static func make_from(drawing: const svg.Drawing*, first: usize, last: usize, spec: ShapeSpec, reach: ShapeReach, width: u32, height: u32) -> CellPlan!:
        let columns = (usize)(reach.right - reach.left)
        let rows = (usize)(reach.bottom - reach.top)
        let kinds = try new u8[columns * rows] --- in memory.heap
        for index in 0..<kinds.length:
            kinds[index] = cell_outside
        var plan = CellPlan(reach = reach, kinds = kinds, width = width, height = height)
        errdefer plan.close()
        plan.mark_edges(drawing, first, last, band_of(spec))
        if spec.filled and spec.kind != 2:
            try plan.mark_inside(drawing, first, last)
        return plan

    ## The kind of cell (`column`, `row`), which must be in reach.
    pub func kind(column: u32, row: u32) -> u8:
        return self.kinds[self.at(column, row)]

    pub func set(column: u32, row: u32, kind: u8):
        self.kinds[self.at(column, row)] = kind

    pub func at(column: u32, row: u32) -> usize:
        return (usize)(row - self.reach.top) * (usize)(self.reach.right - self.reach.left) + (usize)(column - self.reach.left)

    ## The first inside cell in reading order, as column and row; none when there is none.
    pub func first_inside() -> u32[2]?:
        for row in self.reach.top..<self.reach.bottom:
            for column in self.reach.left..<self.reach.right:
                if self.kind(column, row) == cell_inside:
                    return [column, row]
        return none

    ## How many cells are of `kind`.
    pub func count(kind: u8) -> usize:
        var total: usize = 0
        for value in self.kinds:
            if value == kind:
                total += 1
        return total

    pub func close():
        if self.kinds.length > 0:
            free(self.kinds) in memory.heap
        var none_left: u8[]
        self.kinds = none_left

    ## Mark every cell within `band` pixels of a segment of any outline `first..<last`.
    pub func mark_edges(drawing: const svg.Drawing*, first: usize, last: usize, band: f64):
        for contour in first..<last:
            let start = drawing.contour_start(contour)
            let size = drawing.contour_size(contour)
            if size == 0:
                continue
            if size == 1:
                let point = drawing.point(start)
                self.mark_box(point.x - band, point.y - band, point.x + band, point.y + band)
                continue
            # The closing segment too: a fill closes every outline.
            for index in 0..<size:
                let a = drawing.point(start + index)
                let b = drawing.point(start + (index + 1) % size)
                self.mark_segment(a.x, a.y, b.x, b.y, band)

    ## Mark the cells a segment's steps reach, each piece's box grown by `band`.
    pub func mark_segment(x0: f64, y0: f64, x1: f64, y1: f64, band: f64):
        let length = math.hypot(x1 - x0, y1 - y0)
        let steps = math.max(1.0, math.ceil(length / mark_piece))
        var piece: f64 = 0.0
        while piece < steps:
            let ax = x0 + (x1 - x0) * piece / steps
            let ay = y0 + (y1 - y0) * piece / steps
            let bx = x0 + (x1 - x0) * (piece + 1.0) / steps
            let by = y0 + (y1 - y0) * (piece + 1.0) / steps
            self.mark_box(math.min(ax, bx) - band, math.min(ay, by) - band, math.max(ax, bx) + band, math.max(ay, by) + band)
            piece += 1.0

    ## Mark the cells of reach a document-pixel box touches.
    pub func mark_box(low_x: f64, low_y: f64, high_x: f64, high_y: f64):
        let size = (f64)tile_size
        let left = math.max((f64)self.reach.left, math.floor(low_x / size))
        let top = math.max((f64)self.reach.top, math.floor(low_y / size))
        let right = math.min((f64)self.reach.right - 1.0, math.floor(high_x / size))
        let bottom = math.min((f64)self.reach.bottom - 1.0, math.floor(high_y / size))
        if right < left or bottom < top:
            return
        for row in (u32)top..<(u32)bottom + 1:
            for column in (u32)left..<(u32)right + 1:
                self.set(column, row, cell_edge)

    ## Sort the cells no edge touches: inside the fill (nonzero winding at the centre)
    ## or out. A cell past the document's edge is drawn instead, as its clear part
    ## keeps it from being one color throughout.
    pub func mark_inside(drawing: const svg.Drawing*, first: usize, last: usize) -> !:
        var capacity: usize = 64
        var crossings = try new Crossing[capacity] --- in memory.heap
        defer free(crossings) in memory.heap
        let size = (f64)tile_size
        for row in self.reach.top..<self.reach.bottom:
            let y = ((f64)row + 0.5) * size
            # The fill outlines' crossings with the row's centre line.
            var count: usize = 0
            for contour in first..<last:
                if not drawing.contour_filled(contour) or drawing.contour_size(contour) < 3:
                    continue
                let start = drawing.contour_start(contour)
                let points = drawing.contour_size(contour)
                for index in 0..<points:
                    let a = drawing.point(start + index)
                    let b = drawing.point(start + (index + 1) % points)
                    let upward = a.y <= y and y < b.y
                    let downward = b.y <= y and y < a.y
                    if not upward and not downward:
                        continue
                    if count == capacity:
                        let grown = try new Crossing[capacity * 2] --- in memory.heap
                        memory.copy(grown, crossings, count)
                        free(crossings) in memory.heap
                        crossings = grown
                        capacity *= 2
                    crossings[count] = Crossing(x = a.x + (y - a.y) * (b.x - a.x) / (b.y - a.y), direction = 1 if upward else -1)
                    count += 1
            sort_crossings(crossings[..<count])
            # Walk the row's cells left to right, winding by the crossings passed.
            var passed: usize = 0
            var winding: i32 = 0
            for column in self.reach.left..<self.reach.right:
                let x = ((f64)column + 0.5) * size
                while passed < count and crossings[passed].x < x:
                    winding += crossings[passed].direction
                    passed += 1
                if self.kind(column, row) != cell_outside or winding == 0:
                    continue
                let partial = (column + 1) * tile_size > self.width or (row + 1) * tile_size > self.height
                self.set(column, row, cell_edge if partial else cell_inside)

## Sort crossings by x (insertion sort: a row crosses an outline a few times).
func sort_crossings(crossings: Crossing[]):
    for index in 1..<crossings.length:
        let held = crossings[index]
        var at = index
        while at > 0 and crossings[at - 1].x > held.x:
            crossings[at] = crossings[at - 1]
            at -= 1
        crossings[at] = held

## How far past its outline a shape can paint, in document pixels: a miter reaches
## four half widths (the limit luce-svg keeps), the widest the transform makes the
## stroke, and two pixels of anti-aliasing past that.
func band_of(spec: ShapeSpec) -> f64:
    let stroked = spec.stroked or spec.kind == 2
    if not stroked:
        return 2.0
    let m = spec.matrix
    let det = math.abs(m[0] * m[3] - m[1] * m[2])
    let scale = math.sqrt(det)
    # The stroke is written in shape space (shape_svg); its widest in document pixels
    # is that times the transform's largest stretch.
    let in_shape = spec.stroke_width / scale if scale > 1e-9 else spec.stroke_width
    let sum = m[0] * m[0] + m[1] * m[1] + m[2] * m[2] + m[3] * m[3]
    let stretch = math.sqrt((sum + math.sqrt(math.max(0.0, sum * sum - 4.0 * det * det))) * 0.5)
    return in_shape * stretch * 2.0 + 2.0

## The cells `spec` can reach on a `width` by `height` canvas: its box (a path's anchors
## and their handles) through its matrix, grown by twice its stroke (a miter reaches
## four half widths out) and two pixels of antialiasing. None when it misses the canvas.
pub func shape_reach(spec: ShapeSpec, width: u32, height: u32) -> ShapeReach?:
    var low_x = math.infinity
    var low_y = math.infinity
    var high_x = -math.infinity
    var high_y = -math.infinity
    let m = spec.matrix
    var corners: f64[8] = [spec.x, spec.y, spec.x + spec.width, spec.y, spec.x, spec.y + spec.height, spec.x + spec.width, spec.y + spec.height]
    if spec.kind == 4:
        for at in 0..<spec.path.length // 2:
            let px = spec.path[at * 2]
            let py = spec.path[at * 2 + 1]
            low_x = math.min(low_x, m[0] * px + m[2] * py + m[4])
            high_x = math.max(high_x, m[0] * px + m[2] * py + m[4])
            low_y = math.min(low_y, m[1] * px + m[3] * py + m[5])
            high_y = math.max(high_y, m[1] * px + m[3] * py + m[5])
    else:
        for at in 0..<(usize)4:
            let px = corners[at * 2]
            let py = corners[at * 2 + 1]
            low_x = math.min(low_x, m[0] * px + m[2] * py + m[4])
            high_x = math.max(high_x, m[0] * px + m[2] * py + m[4])
            low_y = math.min(low_y, m[1] * px + m[3] * py + m[5])
            high_y = math.max(high_y, m[1] * px + m[3] * py + m[5])
    if not math.is_finite(low_x) or not math.is_finite(high_x) or not math.is_finite(low_y) or not math.is_finite(high_y):
        return none
    let grow = band_of(spec)
    let size = (f64)tile_size
    let left = math.max(0.0, math.floor((low_x - grow) / size))
    let top = math.max(0.0, math.floor((low_y - grow) / size))
    let right = math.min((f64)tile_columns(width), math.ceil((high_x + grow) / size))
    let bottom = math.min((f64)tile_columns(height), math.ceil((high_y + grow) / size))
    if right <= left or bottom <= top:
        return none
    return ShapeReach(left = (u32)left, top = (u32)top, right = (u32)right, bottom = (u32)bottom)

## A cell drawn whole because its element's inside did not come out one color.
let cell_redraw: u8 = 3

## Which cells of the canvas grid an edit reaches, a byte a cell.
pub struct CellMask:
    pub var columns: u32
    pub var rows: u32
    pub var width: u32
    pub var height: u32
    pub var marks: u8[]

    pub static func create(width: u32, height: u32) -> CellMask!:
        let columns = tile_columns(width)
        let rows = tile_columns(height)
        let marks = try new u8[(usize)columns * (usize)rows] --- in memory.heap
        memory.set(marks, 0)
        return CellMask(columns = columns, rows = rows, width = width, height = height, marks = marks)

    pub func close():
        if self.marks.length > 0:
            free(self.marks) in memory.heap
        var none_left: u8[]
        self.marks = none_left

    pub func marked(column: u32, row: u32) -> bool:
        return self.marks[(usize)row * (usize)self.columns + (usize)column] != 0

    pub func set(column: u32, row: u32):
        self.marks[(usize)row * (usize)self.columns + (usize)column] = 1

    ## Mark the cells `element` draws in, when it is shown.
    pub func mark(element: VectorElement) -> !:
        if element.visible:
            try self.mark_spec(element.spec)

    ## Mark the cells every one of `specs` draws in, from one drawing of them all.
    pub func mark_specs(specs: const ShapeSpec[]) -> !:
        if specs.length == 0:
            return
        var set = try ShapeSet.make(specs, self.width, self.height)
        defer set.close()
        for at in 0..<specs.length:
            var plan = try set.plan(at, specs[at]) else continue
            for row in plan.reach.top..<plan.reach.bottom:
                for column in plan.reach.left..<plan.reach.right:
                    if plan.kind(column, row) != cell_outside:
                        self.set(column, row)
            plan.close()

    ## Mark the cells `spec` draws in.
    pub func mark_spec(spec: ShapeSpec) -> !:
        var plan = try spec_plan(spec, self.width, self.height) else return
        for row in plan.reach.top..<plan.reach.bottom:
            for column in plan.reach.left..<plan.reach.right:
                if plan.kind(column, row) != cell_outside:
                    self.set(column, row)
        plan.close()

    ## Whether any cell of `reach` is marked.
    pub func touches(reach: ShapeReach) -> bool:
        for row in reach.top..<reach.bottom:
            for column in reach.left..<reach.right:
                if self.marked(column, row):
                    return true
        return false

    ## Every cell marked: the whole layer is drawn again.
    pub func mark_all():
        memory.set(self.marks, 1)

    ## How many cells are marked.
    pub func count() -> usize:
        var total: usize = 0
        for value in self.marks:
            if value != 0:
                total += 1
        return total

    ## The box of the marked cells; none when none is.
    pub func bounds() -> ShapeReach?:
        var box = ShapeReach(left = self.columns, top = self.rows, right = 0, bottom = 0)
        for row in 0..<self.rows:
            for column in 0..<self.columns:
                if self.marked(column, row):
                    box.left = min_u32(box.left, column)
                    box.top = min_u32(box.top, row)
                    box.right = max_u32(box.right, column + 1)
                    box.bottom = max_u32(box.bottom, row + 1)
        if box.right <= box.left:
            return none
        return box

## The cell plan of `spec` alone on a `width` by `height` canvas; none when it
## draws nothing there.
func spec_plan(spec: ShapeSpec, width: u32, height: u32) -> CellPlan?!:
    if not drawable(spec):
        return none
    let reach = shape_reach(spec, width, height) else return none
    var text: collections.Buffer
    defer text.destroy()
    try shape_svg(&text, spec, 0, 0, width, height)
    let parsed = try svg.parse(text.text())
    defer parsed.release()
    return try CellPlan.make(parsed.value(), spec, reach, width, height)

## Several specs parsed as one drawing over the whole canvas, and where each one's
## contours begin in it (luce-svg numbers a drawing's shapes in order, one a spec):
## one parse sorts every spec's cells and draws them all, where a parse each would
## cost thousands for a graph's clones.
struct ShapeSet:
    var parsed: interop.Reference[svg.Drawing]
    var starts: usize[]
    var width: u32
    var height: u32

    ## `specs`, those that cannot draw left out of the drawing but kept in their places.
    static func make(specs: const ShapeSpec[], width: u32, height: u32) -> ShapeSet!:
        var text: collections.Buffer
        defer text.destroy()
        try svg_open(&text, 0, 0, width, height)
        for spec in specs:
            try shape_group(&text, spec if drawable(spec) else empty_shape())
        try text.put_text("</svg>")
        let parsed = try svg.parse(text.text())
        errdefer parsed.release()
        let drawing = parsed.value()
        let starts = try new usize[specs.length + 1] --- in memory.heap
        var contour: usize = 0
        for element in 0..<specs.length:
            starts[element] = contour
            while contour < drawing.contour_count() and drawing.contour_element(contour) <= element:
                contour += 1
        starts[specs.length] = drawing.contour_count()
        return ShapeSet(parsed = parsed, starts = starts, width = width, height = height)

    ## The cells spec `at` (which is `spec`) sorts into; none when it draws nothing.
    func plan(at: usize, spec: ShapeSpec) -> CellPlan?!:
        if not drawable(spec):
            return none
        let reach = shape_reach(spec, self.width, self.height) else return none
        return try CellPlan.make_from(self.parsed.value(), self.starts[at], self.starts[at + 1], spec, reach, self.width, self.height)

    func close():
        free(self.starts) in memory.heap
        self.parsed.release()

## A rectangle of no size: a stand-in keeping a spec that cannot draw in its place.
func empty_shape() -> ShapeSpec:
    return ShapeSpec(kind = 0, filled = false)

## Whether two boxes of cells share a cell.
func reaches_overlap(a: ShapeReach, b: ShapeReach) -> bool:
    return a.left < b.right and b.left < a.right and a.top < b.bottom and b.top < a.bottom

## One element's plan merged into the layer's kinds, bottom up, in the marked cells
## (every cell when `dirty` is none): its edge makes an edge cell; its inside, an opaque
## fill over what is below, makes the cell its own.
func merge_plan(plan: const CellPlan*, dirty: CellMask*?, kinds: u8[], owners: u32[], columns: u32, owner: u32):
    for row in plan.reach.top..<plan.reach.bottom:
        for column in plan.reach.left..<plan.reach.right:
            if let cells = dirty:
                if not cells.marked(column, row):
                    continue
            let at = (usize)row * (usize)columns + (usize)column
            let kind = plan.kind(column, row)
            if kind == cell_edge:
                kinds[at] = cell_edge
            elif kind == cell_inside:
                kinds[at] = cell_inside
                owners[at] = owner