dymokomi/luce-vector
Source of release 0.6.0
0.6.0 / src / vector / bins.lucb
#==============================================================================================
#
# vector/bins - A layer's elements sorted into bins, so a window draws only its own
#
# DESCRIPTION:
# luce-svg draws a window of a drawing by visiting every element in it. For a layer of a
# few elements that is nothing; for a graph's thousands of clones it is thousands of
# visits per window, most of them far away. So the canvas grid is cut into bins a few
# cells on a side, each element listed in the bins its reach touches, and each bin's
# elements parsed as one drawing: a window is drawn from its bin's, and each element's
# cells are sorted from the drawing of the bin its reach starts in. The cost follows
# what is near a cell, never the layer's count, and nothing is parsed twice but an
# element that straddles bins.
#
#==============================================================================================
## Cells a bin spans on a side.
let bin_cells: u32 = 4
## A cell whose sample is drawn to learn whether its element's inside is one color.
let cell_sample: u8 = 4
## The elements of a layer, by the bins of cells their reaches touch.
struct Bins:
var columns: u32
var rows: u32
var width: u32
var height: u32
## Bin b lists `members[offsets[b]..<offsets[b + 1]]`, bottom first, and draws
## from `sets[b]` when it lists any.
var offsets: u32[]
var members: u32[]
var sets: ShapeSet[]
var parsed: bool[]
## Each element's place in the first bin that lists it.
var home: u32[]
## `specs` (each drawable and reaching the canvas) sorted into the bins of a
## `width` by `height` canvas, and each bin's parsed.
static func make(specs: const ShapeSpec[], width: u32, height: u32) -> Bins!:
let columns = (tile_columns(width) + bin_cells - 1) // bin_cells
let rows = (tile_columns(height) + bin_cells - 1) // bin_cells
let count = (usize)columns * (usize)rows
var bins = Bins(columns = columns, rows = rows, width = width, height = height)
errdefer bins.close()
bins.offsets = try new u32[count + 1] --- in memory.heap
for at in 0..<bins.offsets.length:
bins.offsets[at] = 0
bins.sets = try new ShapeSet[count] --- in memory.heap
bins.parsed = try new bool[count] --- in memory.heap
for at in 0..<count:
bins.parsed[at] = false
bins.home = try new u32[specs.length + 1] --- in memory.heap
for spec in specs:
let reach = shape_reach(spec, width, height) else continue
for row in reach.top // bin_cells..<(reach.bottom - 1) // bin_cells + 1:
for column in reach.left // bin_cells..<(reach.right - 1) // bin_cells + 1:
bins.offsets[(usize)row * (usize)columns + (usize)column + 1] += 1
for at in 1..<bins.offsets.length:
bins.offsets[at] += bins.offsets[at - 1]
bins.members = try new u32[(usize)bins.offsets[count] + 1] --- in memory.heap
let filled = try new u32[count] --- in memory.heap
defer free(filled) in memory.heap
for at in 0..<count:
filled[at] = 0
for at in 0..<specs.length:
bins.home[at] = 0
let reach = shape_reach(specs[at], width, height) else continue
for row in reach.top // bin_cells..<(reach.bottom - 1) // bin_cells + 1:
for column in reach.left // bin_cells..<(reach.right - 1) // bin_cells + 1:
let place = (usize)row * (usize)columns + (usize)column
if row == reach.top // bin_cells and column == reach.left // bin_cells:
bins.home[at] = filled[place]
bins.members[(usize)bins.offsets[place] + (usize)filled[place]] = (u32)at
filled[place] += 1
# Each bin's elements as one drawing.
let listed = try new ShapeSpec[specs.length + 1] --- in memory.heap
defer free(listed) in memory.heap
for place in 0..<count:
let first = (usize)bins.offsets[place]
let size = (usize)bins.offsets[place + 1] - first
if size == 0:
continue
for at in 0..<size:
listed[at] = specs[(usize)bins.members[first + at]]
bins.sets[place] = try ShapeSet.make(listed[..<size], width, height)
bins.parsed[place] = true
return bins
## The cells spec `at` of the list the bins were made from (`spec`) sorts
## into, from its home bin's drawing; none when it draws nothing.
func plan(at: usize, spec: ShapeSpec) -> CellPlan?!:
let reach = shape_reach(spec, self.width, self.height) else return none
let place = (usize)(reach.top // bin_cells) * (usize)self.columns + (usize)(reach.left // bin_cells)
if not self.parsed[place]:
return none
return try self.sets[place].plan((usize)self.home[at], spec)
func close():
for place in 0..<self.parsed.length:
if self.parsed[place]:
self.sets[place].close()
if self.offsets.length > 0:
free(self.offsets) in memory.heap
if self.members.length > 0:
free(self.members) in memory.heap
if self.sets.length > 0:
free(self.sets) in memory.heap
if self.parsed.length > 0:
free(self.parsed) in memory.heap
if self.home.length > 0:
free(self.home) in memory.heap
var no_parsed: bool[]
self.parsed = no_parsed
## Draw every cell of `kind` in `kinds` (the canvas grid, `columns` by `rows`) bin
## by bin, a wave of windows at a time. When `uniform` is given, each cell drawn
## says there whether it came out one pixel throughout.
func draw_binned(painter: WindowPainter*, bins: const Bins*, kinds: const u8[], columns: u32, rows: u32, kind: u8, tiles: Tiles*, uniform: u8[]?) -> !:
var runs: CellRun[16] = ---
var count: usize = 0
for bin_row in 0..<bins.rows:
for bin_column in 0..<bins.columns:
let place = (usize)bin_row * (usize)bins.columns + (usize)bin_column
if not bins.parsed[place]:
continue
let left = bin_column * bin_cells
let right = min_u32(left + bin_cells, columns)
for row in bin_row * bin_cells..<min_u32(bin_row * bin_cells + bin_cells, rows):
var column = left
while column < right:
if kinds[(usize)row * (usize)columns + (usize)column] != kind:
column += 1
continue
var across: u32 = 1
while across < window_cells and column + across < right and kinds[(usize)row * (usize)columns + (usize)(column + across)] == kind:
across += 1
runs[count] = CellRun(column = column, row = row, across = across)
painter.windows[count].drawing = bins.sets[place].parsed.value()
count += 1
column += across
if count == painter.workers:
try flush_wave(painter, runs[..<count], columns, tiles, uniform)
count = 0
try flush_wave(painter, runs[..<count], columns, tiles, uniform)
## Draw a wave's runs, noting which cells came out one pixel.
func flush_wave(painter: WindowPainter*, runs: const CellRun[], columns: u32, tiles: Tiles*, uniform: u8[]?) -> !:
if runs.length == 0:
return
try painter.draw(runs, tiles)
if let flags = uniform:
for index in 0..<runs.length:
let window = &painter.windows[index]
for cell in 0..<(usize)window.across:
flags[(usize)window.row * (usize)columns + (usize)window.column + cell] = 1 if window.uniform[cell] else 0