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(©, 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))