Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-canvas

Source of release 0.5.1

0.5.1 / src / pyramid.lucb

#==============================================================================================
#
#   pyramid - A store's coarser levels
#
#   DESCRIPTION:
#       Level 0 of a store is its own tiles. Level L covers 2^L by 2^L of them in one 256 by
#       256 tile, each texel the average of the 2x2 texels below it, taken in premultiplied
#       space so soft edges keep their color. A zoomed-out view composites every layer at
#       its level, so drawing costs what is on screen rather than what the document holds.
#
#       Levels are derived: a level tile's key is made from the keys of the tiles it was
#       made from (at level 0, their stamps), so painting a tile changes the keys of just
#       the chain above it, and undo brings the old keys, and often the old tiles, back.
#       They live in a TileCache, are dropped when space is short, and are made again when
#       asked for — at most one downsample per level for each tile that changed. A store's
#       coarsest levels are precious (`precious_level`): few, and each made from everything
#       under it, so they go last. Keeping them bounds what a change costs to show when zoomed
#       out: the chain above a changed tile, and the finer siblings of that chain.
#
#==============================================================================================

from luce_gpu import gpu
import memory
from tiles import Gathering, Tiles, tile_size, min_u32, tile_texture, transient_mark, release_transients
from cache import TileCache
from shaders import halve_frag_words, halve_frag_msl
from half import from_half
from luce_raster.errors import invalid

## Bytes of one rgba16_float tile.
pub let tile_bytes: usize = 256 * 256 * 8

pub struct Pyramid:
    var owner: gpu.Device
    var shader: gpu.Shader
    var pipeline: gpu.Pipeline
    var cache: TileCache
    ## Level tiles made rather than found, for tests and tuning.
    pub var renders: u64

    ## Levels for stores on `device`, keeping at most `budget` bytes of them.
    pub static func create(device: gpu.Device, budget: usize) -> Pyramid!:
        var shader = try gpu.Shader.create(device, halve_frag_words, halve_frag_msl)
        errdefer shader.destroy()
        var pipeline = try gpu.Pipeline.create(device, shader, gpu.Blend.replace, gpu.Format.rgba16_float)
        errdefer pipeline.destroy()
        var cache = try TileCache.create(budget, tile_bytes)
        return Pyramid(owner = device, shader = shader, pipeline = pipeline, cache = cache, renders = 0)

    ## Begin a request: every level tile it gets stays until the next one.
    pub func hold():
        self.cache.hold()

    ## Cell (`column`, `row`) of `tiles` at `level`, borrowed until the next
    ## `hold`; none where nothing is (transparent, or for a `mask`, white).
    pub func texture(tiles: const Tiles*, column: u32, row: u32, level: u32, mask: bool = false) -> gpu.Texture?!:
        return try self.level_tile(tiles, column, row, level, mask, true)

    ## As `texture`, for one pass making a derived tile: at level 0 a tile kept
    ## in RAM gets a transient upload (see `Tiles.pass_texture`) the caller
    ## releases once its pass is submitted.
    pub func pass_texture(tiles: const Tiles*, column: u32, row: u32, level: u32, mask: bool = false) -> gpu.Texture?!:
        if level == 0:
            return try tiles.pass_texture(column, row)
        return try self.level_tile(tiles, column, row, level, mask, true)

    ## `texture`, `wanted` for itself or only on the way to a coarser tile. A
    ## tile made on the way is kept as least wanted, so building one coarse tile
    ## (a level-4 tile makes 84 finer ones) does not push out the coarse tiles
    ## every frame needs.
    func level_tile(tiles: const Tiles*, column: u32, row: u32, level: u32, mask: bool, wanted: bool) -> gpu.Texture?!:
        if level == 0:
            return try tiles.texture(column, row)
        if level > 16:
            error(invalid, "pyramid levels go up to 16")
        let key = level_key(tiles, column, row, level, mask)
        if key == 0:
            return none
        if let found = self.cache.find(key):
            return found
        # The four finer tiles first, all held, then one pass over them; level-0
        # parts kept in RAM come up for this pass alone.
        let mark = transient_mark()
        defer release_transients(mark)
        var parts: gpu.Texture[4]
        var present: bool[4] = [false, false, false, false]
        var covered: u32[8]
        for quarter in 0..<(usize)4:
            let fine_column = column * 2 + (u32)(quarter % 2)
            let fine_row = row * 2 + (u32)(quarter // 2)
            if cell_exists(tiles, fine_column, fine_row, level - 1):
                let found = (try tiles.pass_texture(fine_column, fine_row)) if level == 1 else (try self.level_tile(tiles, fine_column, fine_row, level - 1, mask, false))
                if let part = found:
                    parts[quarter] = part
                    present[quarter] = true
                covered[quarter * 2] = covered_at(tiles.width(), fine_column, level - 1)
                covered[quarter * 2 + 1] = covered_at(tiles.height(), fine_row, level - 1)
        var texture = try tile_texture(self.owner)
        errdefer texture.destroy()
        let frame = try texture.frame()
        defer frame.release()
        let target = try frame.value().target()
        defer target.release()
        let half = (f64)tile_size * 0.5
        for quarter in 0..<(usize)4:
            if not present[quarter]:
                continue
            let part = parts[quarter]
            let x = half * (f64)(quarter % 2)
            let y = half * (f64)(quarter // 2)
            var params: f32[5] = [(f32)x, (f32)y, (f32)covered[quarter * 2], (f32)covered[quarter * 2 + 1], 1.0 if mask else 0.0]
            try gpu.shade(target.value(), self.pipeline, gpu.Rect(x, y, half, half), u8[]((u8*)&params[0], 20), [part], gpu.Filter.nearest)
        # A quarter with nothing finer is empty: clear to what empty means.
        _ = try frame.value().present(gpu.Color(1.0, 1.0, 1.0, 1.0) if mask else gpu.Color(0.0, 0.0, 0.0, 0.0))
        self.renders += 1
        try self.cache.put(key, texture, tile_bytes, recent = wanted, precious = precious_level(tiles.width(), tiles.height(), level))
        return texture

    ## Add to `pending` the level-0 tiles that making cell (`column`, `row`) of
    ## `level` would otherwise bring back one at a time: those under the level
    ## tiles not kept (tiles/gathering). A draw gathers them first, from every
    ## store it shows, then brings them back together.
    pub func gather(tiles: const Tiles*, column: u32, row: u32, level: u32, mask: bool, pending: Gathering*) -> !:
        if not cell_exists(tiles, column, row, level):
            return
        if level == 0:
            try pending.add(tiles, column, row)
            return
        let key = level_key(tiles, column, row, level, mask)
        if key == 0 or self.cache.has(key):
            return
        for quarter in 0..<(u32)4:
            try self.gather(tiles, column * 2 + quarter % 2, row * 2 + quarter // 2, level - 1, mask, pending)

    ## Forget the level tiles over row `row` of `tiles`' cells, at every level,
    ## before that row changes: as a picture loads a band at a time, the tiles
    ## made from the rows so far would otherwise fill the cache.
    pub func forget_band(tiles: const Tiles*, row: u32, mask: bool):
        var level: u32 = 1
        while level <= 16:
            let span = (u64)tile_size << level
            let columns = (u32)(((u64)tiles.width() + span - 1) // span)
            for column in 0..<columns:
                let key = level_key(tiles, column, row >> level, level, mask)
                if key != 0:
                    self.cache.forget(key)
            if (u64)tiles.width() <= span and (u64)tiles.height() <= span:
                return
            level += 1

    ## What the level tiles keep, in bytes.
    pub func bytes() -> usize:
        return self.cache.bytes()

    pub func set_budget(budget: usize):
        self.cache.set_budget(budget)

    ## Forget every level tile.
    pub func clear():
        self.cache.clear()

    pub func destroy():
        self.cache.destroy()
        self.pipeline.destroy()
        self.shader.destroy()

## How many of a store's coarsest levels are precious: a level-L tile covers
## 4^L tiles below it, so the top ones are few and each costly to make again.
let precious_levels: u32 = 4

## Whether `level` is one of the coarsest levels of a `width` by `height`
## store: those at or above the level where the store fits one tile, less
## `precious_levels` - 1. At 15000 by 24000 that is levels 4 and up, about a
## hundred tiles a layer.
pub func precious_level(width: u32, height: u32, level: u32) -> bool:
    var top: u32 = 0
    while top < 16 and ((u64)width > ((u64)tile_size << top) or (u64)height > ((u64)tile_size << top)):
        top += 1
    return level + precious_levels > top

## Whether cell (`column`, `row`) at `level` lies on the store.
pub func cell_exists(tiles: const Tiles*, column: u32, row: u32, level: u32) -> bool:
    let span = (u64)tile_size << level
    return (u64)column * span < (u64)tiles.width() and (u64)row * span < (u64)tiles.height()

## The texels cell `cell` covers along an axis of `extent` pixels at `level`.
pub func covered_at(extent: u32, cell: u32, level: u32) -> u32:
    let span = 1u64 << level
    let first = (u64)cell * (u64)tile_size * span
    if first >= (u64)extent:
        return 0
    return min_u32(tile_size, (u32)(((u64)extent - first + span - 1) // span))

## The key of cell (`column`, `row`) at `level`: its tile's stamp at level 0,
## else a digest of the four finer keys and where the cell ends; 0 when
## nothing is under it.
pub func level_key(tiles: const Tiles*, column: u32, row: u32, level: u32, mask: bool) -> u64:
    if not cell_exists(tiles, column, row, level):
        return 0
    if level == 0:
        return tiles.stamp(column, row)
    var digest: u64 = 14695981039346656037
    var any = false
    for quarter in 0..<(u32)4:
        let key = level_key(tiles, column * 2 + quarter % 2, row * 2 + quarter // 2, level - 1, mask)
        any = any or key != 0
        digest = (digest ^ key) *% 1099511628211
    if not any:
        return 0
    # Two cells made of the same tiles differ where the store's edge cuts them.
    digest = (digest ^ (u64)level) *% 1099511628211
    digest = (digest ^ ((u64)covered_at(tiles.width(), column, level) << 16 | (u64)covered_at(tiles.height(), row, level))) *% 1099511628211
    digest = (digest ^ (1 if mask else 2)) *% 1099511628211
    return digest | 1

test "a level averages in premultiplied space, is cached, and follows a painted tile":
    var device = gpu.Device.open() catch failure:
        assert(failure.code == gpu.unavailable)
        return
    defer device.destroy()
    # 600 by 300: 3 by 2 cells; level 1 is 2 by 1, level 2 one cell.
    var tiles = try Tiles.create(device, 600, 300)
    defer tiles.destroy()
    let count = (usize)600 * 300 * 4
    let pixels = try new f32[count] --- in memory.heap
    defer free(pixels) in memory.heap
    for index in 0..<count:
        pixels[index] = 0.0
    # Opaque red at (10, 10), half-transparent red at (11, 10), nothing at (10, 11), (11, 11).
    pixels[(10 * 600 + 10) * 4] = 1.0
    pixels[(10 * 600 + 10) * 4 + 3] = 1.0
    pixels[(10 * 600 + 11) * 4] = 1.0
    pixels[(10 * 600 + 11) * 4 + 3] = 0.5
    try tiles.write(pixels)
    var pyramid = try Pyramid.create(device, 64 * tile_bytes)
    defer pyramid.destroy()
    pyramid.hold()
    let level = try pyramid.texture(&tiles, 0, 0, 1) else trap("a painted cell has a level")
    var bytes: u8[8]
    try level.read(bytes, gpu.Region(5, 5, 1, 1))
    # Straight red stays red (a straight average would give 0.75); alpha is 1.5 / 4.
    assert(channel(bytes, 0) > 0.99 and channel(bytes, 1) < 0.01 and channel(bytes, 3) > 0.37 and channel(bytes, 3) < 0.38)
    # Empty cells have no level tile; the same request again is found.
    assert((try pyramid.texture(&tiles, 1, 0, 1)) == none and pyramid.renders == 1)
    _ = try pyramid.texture(&tiles, 0, 0, 1)
    assert(pyramid.renders == 1)
    # Level 2 covers everything through level 1.
    _ = try pyramid.texture(&tiles, 0, 0, 2)
    assert(pyramid.renders == 2)
    # Painting a tile changes its chain's keys.
    let before = level_key(&tiles, 0, 0, 2, false)
    try tiles.set(0, 0, try tiles.blank())
    assert(level_key(&tiles, 0, 0, 2, false) != before)
    # A mask's empty cells are white; its level of nothing is none (white too).
    assert((try pyramid.texture(&tiles, 1, 0, 1, true)) == none)
    assert(covered_at(600, 1, 1) == 44 and covered_at(300, 0, 1) == 150 and covered_at(600, 2, 1) == 0)

## Channel `index` of an rgba16_float texel's bytes.
func channel(bytes: const u8[], index: usize) -> f32:
    return from_half((u16)bytes[index * 2] | ((u16)bytes[index * 2 + 1] << 8))