Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-vector

Source of release 0.6.0

0.6.0 / src / graph / eval.lucb

#==============================================================================================
#
#   graph/eval - A node graph evaluated into shapes, again only downstream of an edit
#
#   DESCRIPTION:
#       Evaluation starts at the Output node and pulls what it needs. Each node gets a stamp,
#       a hash of its kind, its values and the stamps of what feeds it (and, for a Path node,
#       the element it takes): a node whose stamp matches the one its cached value was made
#       under is not computed again. An edit to one node changes its stamp and those
#       downstream of it, so only they run; the rest hand back what they made last time.
#
#       The cache belongs to the layer, keyed by node id, and is never saved or recorded:
#       after an undo, or on a document just opened, the first evaluation fills it again.
#       The output is the Output node's shapes through the graph's placement, each a spec a
#       vector element could hold.
#
#==============================================================================================

## The most shapes or points a node may make: past this an edit is refused, not drawn.
let graph_item_limit: usize = 500000

## One node's value and the stamp it was made under.
struct CacheEntry:
    var id: u32
    var stamp: u64
    var ready: bool
    var value: NodeValue

## A layer's node values from its last evaluation, one entry a node.
pub struct GraphCache:
    pub var entries: CacheEntry[]

    pub func release():
        for at in 0..<self.entries.length:
            self.entries[at].value.release()
        if self.entries.length > 0:
            free(self.entries) in memory.heap
        var none_left: CacheEntry[]
        self.entries = none_left

## One evaluation under way.
struct Evaluation:
    var graph: const Graph*
    var elements: const VectorElement[]
    ## One entry a node, in the graph's order; nothing reallocates them while evaluating.
    var entries: CacheEntry[]
    ## 0 not reached, 1 being computed, 2 done.
    var states: u8[]
    var scratch: Outline
    ## How many nodes were computed rather than taken from the cache.
    var computed: usize

## `graph`'s output shapes (through its placement) into `out`, which must be
## empty, reusing and refreshing `cache`. How many nodes were computed.
pub func evaluate_graph(graph: const Graph*, elements: const VectorElement[], cache: GraphCache*, out: ShapeList*) -> usize!:
    let count = graph.nodes.length
    if count == 0:
        cache.release()
        return 0
    # Carry each node's cached value over by id; what no node claims is freed.
    let entries = try new CacheEntry[count] --- in memory.heap
    for at in 0..<count:
        entries[at] = CacheEntry(id = graph.nodes[at].id, stamp = 0, ready = false, value = NodeValue())
        for old in 0..<cache.entries.length:
            if cache.entries[old].id == graph.nodes[at].id and cache.entries[old].ready:
                entries[at] = cache.entries[old]
                cache.entries[old].ready = false
                cache.entries[old].id = 0
                var emptied: NodeValue
                cache.entries[old].value = emptied
                break
    cache.release()
    cache.entries = entries
    let states = try new u8[count] --- in memory.heap
    defer free(states) in memory.heap
    memory.set(states, 0)
    var run = Evaluation(graph = graph, elements = elements, entries = entries, states = states, scratch = Outline(), computed = 0)
    defer run.scratch.release()
    var output: usize = count
    for at in 0..<count:
        if graph.nodes[at].kind == node_output:
            output = at
            break
    if output == count:
        return 0
    let source = try source_of(&run, output, 0)
    if source < 0:
        return 0
    let shapes = run.entries[(usize)source].value.shapes.view()
    let m = graph.placement_matrix()
    try out.reserve(shapes.length)
    for spec in shapes:
        try out.push_copy(spec_mapped(spec, m) if graph.placed else spec)
    return run.computed

## The node feeding input `port` of node `at`, evaluated; -1 when it is not wired.
func source_of(run: Evaluation*, at: usize, port: u32) -> i64!:
    let link = run.graph.link_into(run.graph.nodes[at].id, port) else return -1
    let source_id = run.graph.slot_of(run.graph.links[link].source_id) else return -1
    try evaluate_node(run, source_id)
    return (i64)source_id

## Node `at` evaluated: taken from the cache when its stamp is unchanged.
func evaluate_node(run: Evaluation*, at: usize) -> !:
    if run.states[at] == 2:
        return
    if run.states[at] == 1:
        error(invalid, "the node graph has a loop")
    run.states[at] = 1
    let node = run.graph.nodes[at]
    let info = node_info(node.kind)
    var sources: i64[6] = [-1, -1, -1, -1, -1, -1]
    var stamp = mix(0xcbf29ce484222325, (u64)node.kind)
    for slot in 0..<node_slots:
        stamp = mix(stamp, node.values[slot].bits())
    for port in 0..<info.input_count:
        sources[port] = try source_of(run, at, (u32)port)
        stamp = mix(stamp, run.entries[(usize)sources[port]].stamp if sources[port] >= 0 else 0x5bd1e995)
    if node.kind == node_path:
        stamp = mix(stamp, element_stamp(run.elements, node.values[slot_special]))
    if run.entries[at].ready and run.entries[at].stamp == stamp:
        run.states[at] = 2
        return
    run.entries[at].value.release()
    run.entries[at].ready = false
    var value: NodeValue
    compute_node(run, at, sources, &value) catch failure:
        value.release()
        error(failure.code, failure.message)
    run.entries[at].value = value
    run.entries[at].stamp = stamp
    run.entries[at].ready = true
    run.computed += 1
    run.states[at] = 2

func mix(stamp: u64, value: u64) -> u64:
    var h = (stamp ^ value) *% 0x100000001b3
    h = h ^ (h >> 29)
    return h *% 0xbf58476d1ce4e5b9

## A hash of the element a Path node takes, so an edit to it reaches the node.
func element_stamp(elements: const VectorElement[], index: f64) -> u64:
    let at = (i64)index
    if at < 0 or at >= (i64)elements.length:
        return 1
    let spec = elements[(usize)at].spec
    var stamp: u64 = 7
    for value in shape_values(spec):
        stamp = mix(stamp, value.bits())
    for value in spec.path:
        stamp = mix(stamp, value.bits())
    for size in spec.subpaths:
        stamp = mix(stamp, (u64)size)
    return mix(stamp, 1 if spec.closed else 2)

# mark: The nodes ===============================================================================

## Node `at`'s value from its inputs (`sources`, node places or -1) into `value`.
func compute_node(run: Evaluation*, at: usize, sources: i64[6], value: NodeValue*) -> !:
    let node = run.graph.nodes[at]
    let kind = node.kind
    if kind == node_rectangle or kind == node_ellipse or kind == node_polygon or kind == node_star:
        try value.shapes.push(try generated_shape(run, node, sources))
    elif kind == node_path:
        try path_shape(run, node, sources, value)
    elif kind == node_grid:
        try grid_points(run, node, sources, value)
    elif kind == node_circle:
        try circle_points(run, node, sources, value)
    elif kind == node_line:
        try line_points(run, node, sources, value)
    elif kind == node_scatter:
        try scatter_points(run, node, sources, value)
    elif kind == node_outline:
        try outline_points(run, node, sources, value)
    elif kind == node_clone:
        try clone_shapes(run, node, sources, value)
    elif kind == node_transform:
        try transform_shapes(run, node, sources, value)
    elif kind == node_merge:
        for port in 0..<(usize)4:
            if sources[port] >= 0:
                for spec in run.entries[(usize)sources[port]].value.shapes.view():
                    try value.shapes.push_copy(spec)
    elif kind == node_number:
        value.field = constant_field(node.values[0])
    elif kind == node_random:
        value.field = Field(mode = 1, a = [node.values[0], node.values[0], node.values[0]], b = [node.values[1], node.values[1], node.values[1]], seed = (u64)node.values[2])
    elif kind == node_gradient:
        value.field = Field(mode = 1 if node.values[6] != 0.0 else 2, a = [node.values[0], node.values[1], node.values[2]], b = [node.values[3], node.values[4], node.values[5]], seed = (u64)node.values[7])

## The field wired into input `port`; none when it is not wired.
func field_of(run: const Evaluation*, sources: i64[6], port: usize) -> Field?:
    if sources[port] < 0:
        return none
    return run.entries[(usize)sources[port]].value.field

## Parameter `slot` of `node`, or what the socket `port` driving it gives at `index` of `count`.
func driven(run: const Evaluation*, node: GraphNode, sources: i64[6], port: usize, slot: usize, index: usize, count: usize) -> f64:
    if let field = field_of(run, sources, port):
        return field.at(index, count, 0)
    return node.values[slot]

## A whole-number count held to the item limit.
func count_of(value: f64) -> usize!:
    if not math.is_finite(value) or value < 0.0:
        return 0
    let count = (usize)math.round(value)
    if count > graph_item_limit:
        error(limit, "a node may make at most 500000 items")
    return count

## A Rectangle, Ellipse, Polygon or Star: centred on the origin of its own space,
## turned and put at its position by its matrix.
func generated_shape(run: const Evaluation*, node: GraphNode, sources: i64[6]) -> ShapeSpec!:
    let v = node.values
    let width = math.abs(v[slot_width])
    let height = math.abs(v[slot_height])
    var spec = ShapeSpec(kind = 0, x = -width * 0.5, y = -height * 0.5, width = width, height = height)
    try node_paint(run, node, sources, 0, &spec)
    spec.matrix = placed_matrix(v[slot_x], v[slot_y], v[slot_rotation], 1.0, 1.0)
    if node.kind == node_rectangle:
        spec.radius = math.max(0.0, v[slot_special])
    elif node.kind == node_ellipse:
        spec.kind = 1
    elif node.kind == node_polygon:
        spec.kind = 3
        spec.sides = (i64)math.clamp(v[slot_special], 3.0, 64.0)
    else:
        try star_path(&spec, (usize)math.clamp(v[slot_special], 2.0, 64.0), math.clamp(v[slot_special_2], 0.05, 1.0))
    return spec

## `spec`'s fill and stroke from `node`'s paint values, the Fill socket (input
## `port`) giving the fill color when wired.
func node_paint(run: const Evaluation*, node: GraphNode, sources: i64[6], port: usize, spec: ShapeSpec*) -> !:
    let v = node.values
    spec.filled = v[slot_filled] != 0.0
    spec.fill_red = v[slot_fill]
    spec.fill_green = v[slot_fill + 1]
    spec.fill_blue = v[slot_fill + 2]
    if let field = field_of(run, sources, port):
        spec.fill_red = field.at(0, 1, 0)
        spec.fill_green = field.at(0, 1, 1)
        spec.fill_blue = field.at(0, 1, 2)
    spec.stroked = v[slot_stroked] != 0.0
    spec.stroke_red = v[slot_stroke]
    spec.stroke_green = v[slot_stroke + 1]
    spec.stroke_blue = v[slot_stroke + 2]
    spec.stroke_width = math.max(0.0, v[slot_stroke_width])

## `spec` (its box set) made a closed path of `points` tips and as many inner
## corners at `inner` of the way out.
func star_path(spec: ShapeSpec*, points: usize, inner: f64) -> !:
    let corners = points * 2
    let path = try new f64[corners * anchor_values] --- in memory.heap
    for corner in 0..<corners:
        let angle = -math.pi / 2.0 + (f64)corner * math.pi / (f64)points
        let reach = 1.0 if corner % 2 == 0 else inner
        let x = math.cos(angle) * spec.width * 0.5 * reach
        let y = math.sin(angle) * spec.height * 0.5 * reach
        for field in 0..<(usize)3:
            path[corner * anchor_values + field * 2] = x
            path[corner * anchor_values + field * 2 + 1] = y
    spec.kind = 4
    spec.path = path
    spec.closed = true

## A Path node: the layer's element it names, moved, scaled and turned about its
## middle, in its own paint or the node's.
func path_shape(run: Evaluation*, node: GraphNode, sources: i64[6], value: NodeValue*) -> !:
    let v = node.values
    let at = (i64)v[slot_special]
    if at < 0 or at >= (i64)run.elements.length:
        return
    let original = run.elements[(usize)at].spec
    if not drawable(original):
        return
    try spec_outline(original, false, &run.scratch)
    var low_x = math.infinity
    var low_y = math.infinity
    var high_x = -math.infinity
    var high_y = -math.infinity
    for point in 0..<run.scratch.count:
        low_x = math.min(low_x, run.scratch.points[point * 2])
        high_x = math.max(high_x, run.scratch.points[point * 2])
        low_y = math.min(low_y, run.scratch.points[point * 2 + 1])
        high_y = math.max(high_y, run.scratch.points[point * 2 + 1])
    let cx = (low_x + high_x) * 0.5 if run.scratch.count > 0 else 0.0
    let cy = (low_y + high_y) * 0.5 if run.scratch.count > 0 else 0.0
    let turn = placed_matrix(cx + v[slot_x], cy + v[slot_y], v[slot_rotation], v[slot_width], v[slot_width])
    # The element is in document pixels; the output goes through the placement
    # after, so it is taken back through the placement's inverse first.
    let back = inverse_matrix(run.graph.placement_matrix()) else return
    var spec = spec_mapped(original, compose(back, compose(turn, [1.0, 0.0, 0.0, 1.0, -cx, -cy])))
    if v[slot_keep_paint] == 0.0:
        try node_paint(run, node, sources, 0, &spec)
    try value.shapes.push_copy(spec)

func grid_points(run: const Evaluation*, node: GraphNode, sources: i64[6], value: NodeValue*) -> !:
    let v = node.values
    let columns = try count_of(driven(run, node, sources, 0, 0, 0, 1))
    let rows = try count_of(driven(run, node, sources, 1, 1, 0, 1))
    if columns * rows > graph_item_limit:
        error(limit, "a node may make at most 500000 items")
    for row in 0..<rows:
        for column in 0..<columns:
            let x = v[4] + ((f64)column - (f64)(columns - 1) * 0.5) * v[2]
            let y = v[5] + ((f64)row - (f64)(rows - 1) * 0.5) * v[3]
            try value.points.push(x, y, 0.0, 1.0)

## Points round a circle from its top, clockwise, each turned along it.
func circle_points(run: const Evaluation*, node: GraphNode, sources: i64[6], value: NodeValue*) -> !:
    let v = node.values
    let count = try count_of(driven(run, node, sources, 0, 0, 0, 1))
    let radius = driven(run, node, sources, 1, 1, 0, 1)
    for index in 0..<count:
        let degrees = v[2] - 90.0 + (f64)index * 360.0 / (f64)count
        let turn = degrees * math.pi / 180.0
        try value.points.push(v[3] + math.cos(turn) * radius, v[4] + math.sin(turn) * radius, degrees + 90.0, 1.0)

func line_points(run: const Evaluation*, node: GraphNode, sources: i64[6], value: NodeValue*) -> !:
    let v = node.values
    let count = try count_of(driven(run, node, sources, 0, 0, 0, 1))
    let angle = math.atan2(v[4] - v[2], v[3] - v[1]) * 180.0 / math.pi
    for index in 0..<count:
        let t = (f64)index / (f64)(count - 1) if count > 1 else 0.5
        try value.points.push(v[1] + (v[3] - v[1]) * t, v[2] + (v[4] - v[2]) * t, angle, 1.0)

## Points at random in the node's box, or inside the shapes wired in (within
## their box), from its seed.
func scatter_points(run: Evaluation*, node: GraphNode, sources: i64[6], value: NodeValue*) -> !:
    let v = node.values
    let count = try count_of(driven(run, node, sources, 1, 0, 0, 1))
    let seed = (u64)math.max(0.0, v[1])
    var box: f64[4] = [v[2], v[3], v[2] + v[4], v[3] + v[5]]
    if sources[0] < 0:
        for index in 0..<count:
            let x = box[0] + (box[2] - box[0]) * unit_hash(seed, (u64)index, 1)
            let y = box[1] + (box[3] - box[1]) * unit_hash(seed, (u64)index, 2)
            try value.points.push(x, y, 0.0, 1.0)
        return
    let shapes = run.entries[(usize)sources[0]].value.shapes.view()
    box = try shapes_box(shapes, &run.scratch) else return
    # Each shape's outline once, then tries until enough land inside one.
    var outlines = try new Outline[shapes.length] --- in memory.heap
    for at in 0..<shapes.length:
        outlines[at] = Outline()
    defer:
        for at in 0..<outlines.length:
            outlines[at].release()
        free(outlines) in memory.heap
    for at in 0..<shapes.length:
        try spec_outline(shapes[at], true, &outlines[at])
    var tried: u64 = 0
    let tries = (u64)count * 64 + 64
    while value.points.count < count and tried < tries:
        let x = box[0] + (box[2] - box[0]) * unit_hash(seed, tried, 1)
        let y = box[1] + (box[3] - box[1]) * unit_hash(seed, tried, 2)
        tried += 1
        for at in 0..<outlines.length:
            if outline_contains(&outlines[at], x, y):
                try value.points.push(x, y, 0.0, 1.0)
                break

## Points of each shape wired in: its corners, or `count` spaced evenly along
## its outline; each turned along the outline there.
func outline_points(run: Evaluation*, node: GraphNode, sources: i64[6], value: NodeValue*) -> !:
    if sources[0] < 0:
        return
    let along = node.values[0] != 0.0
    let count = try count_of(driven(run, node, sources, 1, 1, 0, 1))
    for spec in run.entries[(usize)sources[0]].value.shapes.view():
        try spec_outline(spec, along, &run.scratch)
        let outline = &run.scratch
        for line in 0..<outline.runs:
            let first = outline.starts[line]
            let end = outline.run_end(line)
            if end == first:
                continue
            if along:
                try spaced_points(outline, first, end, count, value)
                continue
            for at in first..<end:
                let before = at - 1 if at > first else (end - 1 if outline.closed else at)
                let after = at + 1 if at + 1 < end else (first if outline.closed else at)
                let angle = math.atan2(outline.points[after * 2 + 1] - outline.points[before * 2 + 1], outline.points[after * 2] - outline.points[before * 2]) * 180.0 / math.pi
                try value.points.push(outline.points[at * 2], outline.points[at * 2 + 1], angle, 1.0)
        if value.points.count > graph_item_limit:
            error(limit, "a node may make at most 500000 items")

## `count` points spaced evenly along the run `first..<end` of `outline`.
func spaced_points(outline: const Outline*, first: usize, end: usize, count: usize, value: NodeValue*) -> !:
    let closed = outline.closed and end - first > 2
    let segments = end - first if closed else end - first - 1
    var total = 0.0
    for at in 0..<segments:
        total += segment_length(outline, first, end, at)
    if count == 0 or total <= 0.0:
        return
    let spacing = total / (f64)count if closed else (total / (f64)(count - 1) if count > 1 else 0.0)
    var segment: usize = 0
    var walked = 0.0
    for index in 0..<count:
        let wanted = spacing * (f64)index + (0.0 if count > 1 or closed else total * 0.5)
        while segment + 1 < segments and walked + segment_length(outline, first, end, segment) < wanted:
            walked += segment_length(outline, first, end, segment)
            segment += 1
        let a = first + segment
        let b = first + (segment + 1) % (end - first)
        let length = segment_length(outline, first, end, segment)
        let t = math.clamp((wanted - walked) / length, 0.0, 1.0) if length > 0.0 else 0.0
        let ax = outline.points[a * 2]
        let ay = outline.points[a * 2 + 1]
        let bx = outline.points[b * 2]
        let by = outline.points[b * 2 + 1]
        try value.points.push(ax + (bx - ax) * t, ay + (by - ay) * t, math.atan2(by - ay, bx - ax) * 180.0 / math.pi, 1.0)

func segment_length(outline: const Outline*, first: usize, end: usize, segment: usize) -> f64:
    let a = first + segment
    let b = first + (segment + 1) % (end - first)
    return math.hypot(outline.points[b * 2] - outline.points[a * 2], outline.points[b * 2 + 1] - outline.points[a * 2 + 1])

## Every shape wired in copied to every point: turned to the point's angle and
## scaled by its scale when asked, by the Scale and Rotation parameters (or
## what their sockets give at the copy's index), jittered by the seed, and
## recolored by the Fill socket.
func clone_shapes(run: const Evaluation*, node: GraphNode, sources: i64[6], value: NodeValue*) -> !:
    if sources[0] < 0 or sources[1] < 0:
        return
    let v = node.values
    let shapes = run.entries[(usize)sources[0]].value.shapes.view()
    let points = &run.entries[(usize)sources[1]].value.points
    let total = shapes.length * points.count
    if total > graph_item_limit:
        error(limit, "a Clone may make at most 500000 shapes")
    try value.shapes.reserve(total)
    let seed = (u64)math.max(0.0, v[5])
    let fill = field_of(run, sources, 4)
    for index in 0..<points.count:
        let rotation = (points.angle(index) if v[0] != 0.0 else 0.0) + driven(run, node, sources, 3, 7, index, points.count) + v[2] * (2.0 * unit_hash(seed, (u64)index, 3) - 1.0)
        let scale = (points.scale(index) if v[1] != 0.0 else 1.0) * driven(run, node, sources, 2, 6, index, points.count) * (1.0 + v[3] * (2.0 * unit_hash(seed, (u64)index, 4) - 1.0))
        let m = placed_matrix(points.x(index), points.y(index), rotation, scale, scale)
        for spec in shapes:
            var copy = spec_mapped(spec, m)
            if let colors = fill:
                let red = colors.at(index, points.count, 0)
                let green = colors.at(index, points.count, 1)
                let blue = colors.at(index, points.count, 2)
                if copy.filled or copy.kind == 2 or not copy.stroked:
                    copy.fill_red = red
                    copy.fill_green = green
                    copy.fill_blue = blue
                else:
                    copy.stroke_red = red
                    copy.stroke_green = green
                    copy.stroke_blue = blue
            if v[4] > 0.0:
                jitter_color(&copy, v[4], seed, (u64)index)
            try value.shapes.push_copy(copy)

## Each channel of `spec`'s paint moved by up to half of `amount` either way, from the seed.
func jitter_color(spec: ShapeSpec*, amount: f64, seed: u64, index: u64):
    let red = amount * (unit_hash(seed, index, 5) - 0.5)
    let green = amount * (unit_hash(seed, index, 6) - 0.5)
    let blue = amount * (unit_hash(seed, index, 7) - 0.5)
    spec.fill_red = math.clamp(spec.fill_red + red, 0.0, 1.0)
    spec.fill_green = math.clamp(spec.fill_green + green, 0.0, 1.0)
    spec.fill_blue = math.clamp(spec.fill_blue + blue, 0.0, 1.0)
    spec.stroke_red = math.clamp(spec.stroke_red + red, 0.0, 1.0)
    spec.stroke_green = math.clamp(spec.stroke_green + green, 0.0, 1.0)
    spec.stroke_blue = math.clamp(spec.stroke_blue + blue, 0.0, 1.0)

## The shapes wired in, scaled and turned about the middle of their box, then moved.
func transform_shapes(run: Evaluation*, node: GraphNode, sources: i64[6], value: NodeValue*) -> !:
    if sources[0] < 0:
        return
    let v = node.values
    let shapes = run.entries[(usize)sources[0]].value.shapes.view()
    let box = try shapes_box(shapes, &run.scratch) else return
    let cx = (box[0] + box[2]) * 0.5
    let cy = (box[1] + box[3]) * 0.5
    let turn = placed_matrix(cx + v[0], cy + v[1], driven(run, node, sources, 1, 2, 0, 1), v[3], v[4])
    let m = compose(turn, [1.0, 0.0, 0.0, 1.0, -cx, -cy])
    try value.shapes.reserve(shapes.length)
    for spec in shapes:
        try value.shapes.push_copy(spec_mapped(spec, m))