AI-native design editor. Open-source Figma alternative.
import type { Canvas } from 'canvaskit-wasm'
import type { SceneGraph } from '@open-pencil/scene-graph'
import type { SkiaRenderer } from '#core/canvas/renderer'
import {
nodeRequiresAtomicChunk,
RenderChunkIndex,
RenderChunkPictureCache
} from '#core/canvas/renderer/chunks'
import { rendererNow } from '#core/canvas/renderer/clock'
import {
type CachedTile,
TileImageCache,
viewportTileBytes,
viewportTileCacheBudget
} from './cache'
import { TileCostModel } from './cost'
import { exactTileLevel, type TileKey, tileLevel, type TileWorldBounds } from './geometry'
import { pageBackdropPlan, type TilePlan, planTiles, type TilePlanOptions } from './planner'
import { drawPresentation, resolveVisible, type VisiblePresentation } from './presentation'
import {
childTileKeys,
deleteRenderedTile,
downsampleTile,
estimateTileCost,
recordTilePictures,
renderTile,
tileJobResult
} from './render'
import {
emptyTileSchedulerMetrics,
TileScheduler,
type TileJob,
type TileSchedulerMetrics
} from './scheduler'
import {
applyInvalidations,
applyStructureChanges,
type PageTiles,
type PendingInvalidation,
type PendingStructureChange
} from './structure'
import { TileSurfacePool } from './surface-pool'
import { emitTileCoverageComplete, emitTileFrameTrace } from './telemetry'
const TILE_FRAME_BUDGET_MS = 8
/** Tile work per frame while the viewport moves, leaving the rest to input and presentation. */
const NAVIGATION_TILE_BUDGET_MS = 2
/** The one tile a moving frame may still afford past its budget; dearer tiles wait for idle. */
const NAVIGATION_FIRST_TILE_LIMIT_MS = 4
const MAXIMUM_TILE_JOBS_PER_FRAME = 128
const TILE_OVERSCAN = 1
/** The backdrop is this many times coarser than the visible level, and reaches this far out. */
const BACKDROP_LEVEL_RATIO = 4
const BACKDROP_OVERSCAN = 1
/** How many halvings of the visible level the pyramid keeps: 2⁶ covers a 64× zoom out. */
const PYRAMID_LEVELS = 6
/**
* How long after a content change the background stages wait: an edit in progress, such as
* typing, invalidates the page copy and the backdrop under it at every keystroke, and a coarse
* tile over thousands of chunks costs a frame or more to render from the scene, so they are
* rebuilt once the content has been still for this long.
*/
const BACKGROUND_QUIET_MS = 300
export interface TiledSceneFrameResult {
/** Every visible tile exists at the current level. */
covered: boolean
/** Visible tiles are still outstanding: settlement waits for this. */
pending: boolean
/**
* Work beyond the visible tiles remains, the overscan ring, the page copy, the pyramid, or
* the backdrop ring, which only proceeds in frames, so the caller should keep scheduling them.
*/
backgroundPending: boolean
metrics: TileSchedulerMetrics
/** Tiles of other levels drawn, scaled, where the current level has none yet. */
fallbackTileCount: number
/** Visible tile areas no level covers; they show the page colour until their tiles render. */
uncoveredAreaCount: number
/** Those of the uncovered areas that lie over the page's content rather than empty canvas. */
uncoveredContentAreaCount: number
}
export interface TiledSceneControllerOptions {
/** The clock the scheduler's deadline and the tile cost model share. */
now?: () => number
/** The tile cache's byte budget for a viewport whose tiles weigh `viewportBytes`. */
tileCacheBudget?: (viewportBytes: number) => number
}
export class TiledSceneController {
/**
* Visible-level tiles rendered and kept since the controller was made, background stages left
* out; a test reads it to prove a gesture rebuilt none.
*/
visibleTilesRendered = 0
private readonly now: () => number
private index: RenderChunkIndex | null = null
private pageId: string | null = null
private contentGeneration = -1
/** The dot grid the cached tiles were painted with, which a document kind change replaces. */
private dotGrid: number | null = null
private navigationGeneration = -1
private navigationActive = false
private cancelledJobs = 0
private pendingInvalidations: PendingInvalidation[] = []
/** Layers added, removed, moved between parents, or changed in kind since the last frame. */
private pendingStructure: PendingStructureChange[] = []
private lastCoveredGeneration = ''
private lastLevel: number | null = null
/**
* The level whose visible tiles have all been presented at once. Another level's tiles are
* held back, with the nearest level scaled in their place, until every visible one exists, so
* a zoom ends with the viewport sharpening in one frame rather than tile by tile. The level
* once committed, tiles a pan reveals or an edit renews present as they land.
*/
private committedLevel: number | null = null
/**
* Set when a frame of background work evicted a tile its own plan needs: the cache cannot hold
* the plan, so the stages stop rather than render each other out until the view changes.
*/
private backgroundSaturated = false
/** When the content last changed, so the background stages wait for a quiet spell. */
private lastContentChangeAt = Number.NEGATIVE_INFINITY
/** The last frame withheld the background stages for the quiet spell: frames must go on. */
private backgroundWaiting = false
private readonly tileCacheBudget: (viewportBytes: number) => number
private readonly pictureCache = new RenderChunkPictureCache()
private readonly tileCache = new TileImageCache()
private readonly surfacePool = new TileSurfacePool()
private readonly scheduler: TileScheduler
private readonly costs = new TileCostModel()
constructor(options: TiledSceneControllerOptions = {}) {
this.now = options.now ?? rendererNow
this.tileCacheBudget = options.tileCacheBudget ?? viewportTileCacheBudget
this.scheduler = new TileScheduler({
now: this.now,
budgetMs: TILE_FRAME_BUDGET_MS,
maximumJobsPerFrame: MAXIMUM_TILE_JOBS_PER_FRAME
})
}
invalidateNode(nodeId: string, graph?: SceneGraph): void {
const chunks = this.index?.getChunksDependingOnNode(nodeId) ?? []
const owningChunks = this.index?.getChunksForNode(nodeId) ?? []
const node = graph?.getNode(nodeId)
if (
graph &&
node &&
owningChunks.some((chunk) => chunk.interruptible === nodeRequiresAtomicChunk(graph, node))
) {
this.invalidateStructure(nodeId, node.parentId)
return
}
this.pendingInvalidations.push({
nodeId,
previousBounds: chunks.map(({ minX, minY, maxX, maxY }) => ({ minX, minY, maxX, maxY }))
})
}
/**
* A structural change: `nodeId` was added, removed, moved under another parent, or changed in
* a way that reshapes its chunks. The page child whose subtree holds it is rebuilt at the next
* frame, with its pictures and the tiles it touched; the rest of the page keeps its tiles.
* Without a layer, as when a document loads or is replaced, everything is dropped.
*/
invalidateStructure(nodeId?: string, parentId?: string | null): void {
if (nodeId === undefined) {
this.invalidate()
return
}
if (!this.index) return
this.pendingStructure.push({ nodeId, parentId: parentId ?? null })
}
/**
* Whether invalidations recorded since the last frame still await it. Unlike the renderer's
* settlement flags, this is current between frames; queued background jobs do not count, as
* settlement means the visible tiles.
*/
hasPendingWork(): boolean {
return this.pendingInvalidations.length > 0 || this.pendingStructure.length > 0
}
/** The tile cache's current byte budget. */
tileCacheBytes(): number {
return this.tileCache.budget()
}
/**
* Renders due tiles within the frame's budget and presents the viewport from the cache: exact
* tiles where they exist, the nearest level's tiles scaled where they do not, and the page
* colour where no level has one, until its tile renders. Nothing is drawn straight from the
* scene, whose whole-page picture a large document cannot afford. Navigation keeps presenting
* and renders under a shorter budget: the exact level while panning or paused, and while the
* zoom level moves the quantized step at or above the scale, whose tiles outlive the frame and
* stand in, scaled by a fifth at most, until the exact level is complete; the retained backing
* plays no part. Idle time builds a pyramid of downsampled copies and a scene-rendered
* backdrop around the viewport, so a zoom out finds scaled stand-ins.
*/
renderFrame(
renderer: SkiaRenderer,
canvas: Canvas,
graph: SceneGraph,
contentGeneration: number,
navigationGeneration: number
): TiledSceneFrameResult {
this.navigationGeneration = navigationGeneration
this.navigationActive = this.isNavigationActive(renderer)
if (renderer.pageDotGrid !== this.dotGrid) {
this.invalidate()
this.dotGrid = renderer.pageDotGrid
}
this.prepareGeneration(renderer, graph, contentGeneration, navigationGeneration)
const viewport = {
minX: -renderer.panX / renderer.zoom,
minY: -renderer.panY / renderer.zoom,
maxX: (-renderer.panX + renderer.viewportWidth) / renderer.zoom,
maxY: (-renderer.panY + renderer.viewportHeight) / renderer.zoom
}
const index = this.index
if (!index || !renderer.pageId) return this.emptyResult()
// A zoom in motion changes the exact level every frame, and a tile rendered at it is obsolete
// within a few frames, so while the level moves the frame renders the quantized step at or
// above the scale instead: its tiles serve every frame until the zoom crosses the next step,
// and then stand in for the exact level, scaled down by a fifth at most. A zoom that pauses,
// and a pan, render the exact level under the moving budget.
const scale = renderer.zoom * renderer.dpr
const level = exactTileLevel(scale)
const zooming = renderer.navigationPhase === 'zoom' && level !== this.lastLevel
const renderLevel = zooming ? tileLevel(scale) : level
if (level !== this.lastLevel || this.navigationActive) this.backgroundSaturated = false
this.lastLevel = level
this.tileCache.setBudget(
this.tileCacheBudget(
viewportTileBytes(
renderer.viewportWidth * renderer.dpr,
renderer.viewportHeight * renderer.dpr
)
)
)
const { planOptions, background } = this.planFrame(
renderer,
renderer.pageId,
index,
renderLevel,
viewport,
contentGeneration,
navigationGeneration
)
const plan = planTiles(this.tileCache, planOptions)
this.scheduler.enqueue(plan.jobs)
const metrics = this.scheduler.runFrame(
(job, remainingMs) => this.executeJob(renderer, graph, index, job, remainingMs),
this.navigationActive ? NAVIGATION_TILE_BUDGET_MS : TILE_FRAME_BUDGET_MS,
this.firstJobLimit()
)
metrics.cancelledJobs += this.cancelledJobs
this.cancelledJobs = 0
// A background tile that evicted one of the plan's own levels would render in circles.
if (background && this.backgroundSaturated) {
this.cancelledJobs += this.scheduler.discard((job) => job.priority === 'overscan')
planOptions.overscanTiles = 0
delete planOptions.backdrop
delete planOptions.pageBackdrop
delete planOptions.pyramid
}
// A stage is planned only once the previous one is done, so the plan is taken again after
// the frame's work to learn whether anything remains for the next frame, and to queue it.
// While moving, only the visible tiles are planned, and the frame does not re-plan.
const next = this.navigationActive ? plan : planTiles(this.tileCache, planOptions)
if (!this.navigationActive) this.scheduler.enqueue(next.jobs)
const visible = planTiles(
this.tileCache,
{
pageId: renderer.pageId,
level,
viewport,
overscanTiles: 0,
navigationGeneration,
contentGeneration,
estimateCost: () => 0
},
true
).visible
const presentation = this.presentLevel(visible, renderer.pageId, level, index.bounds())
canvas.save()
// Snapped to device pixels, an exact tile lands texel on pixel and copies rather than samples.
canvas.translate(
Math.round(renderer.panX * renderer.dpr) / renderer.dpr,
Math.round(renderer.panY * renderer.dpr) / renderer.dpr
)
canvas.scale(renderer.zoom, renderer.zoom)
drawPresentation(renderer, canvas, presentation)
canvas.restore()
const covered = presentation.exact.length === visible.length
emitTileFrameTrace({
contentGeneration,
metrics,
tileCacheBytes: this.tileCache.byteSize(),
tileCacheEntries: this.tileCache.size(),
visibleTileCount: visible.length,
presentedTileCount: presentation.exact.length,
fallbackTileCount: presentation.fallback.length,
uncoveredAreaCount: presentation.uncovered,
uncoveredContentAreaCount: presentation.uncoveredContent,
covered
})
const settledGenerationKey = `${navigationGeneration}:${contentGeneration}`
if (covered && !this.navigationActive && this.lastCoveredGeneration !== settledGenerationKey) {
this.lastCoveredGeneration = settledGenerationKey
emitTileCoverageComplete(
level,
contentGeneration,
navigationGeneration,
this.tileCache.size(),
this.tileCache.byteSize()
)
}
const visiblePending = next.visible.some(
({ tile }) => tile?.contentGeneration !== contentGeneration
)
return {
covered,
pending: visiblePending || !covered,
backgroundPending:
!this.navigationActive && (this.scheduler.pending() > 0 || this.backgroundWaiting),
metrics,
fallbackTileCount: presentation.fallback.length,
uncoveredAreaCount: presentation.uncovered,
uncoveredContentAreaCount: presentation.uncoveredContent
}
}
/**
* A level arrives whole: until every visible tile exists, those that do stay hidden behind
* the nearest level, which the zoom just rendered, or behind the page colour when a page is
* first shown, and the level is committed once they all exist, after which tiles present as
* they land.
*/
private presentLevel(
visible: TilePlan['visible'],
pageId: string,
level: number,
content: TileWorldBounds | null
): VisiblePresentation {
if (this.committedLevel !== level && visible.every(({ tile }) => tile !== null)) {
this.committedLevel = level
}
const presented =
this.committedLevel === level ? visible : visible.map(({ key }) => ({ key, tile: null }))
return resolveVisible(this.tileCache, presented, pageId, level, content)
}
invalidate(): void {
this.cancelledJobs += this.scheduler.clear()
this.index?.dispose()
this.index = null
this.pageId = null
this.contentGeneration = -1
this.lastCoveredGeneration = ''
this.lastLevel = null
this.committedLevel = null
this.lastContentChangeAt = Number.NEGATIVE_INFINITY
this.backgroundWaiting = false
this.pendingInvalidations = []
this.pendingStructure = []
this.costs.clear()
this.pictureCache.clear()
this.tileCache.clear()
}
destroy(): void {
this.invalidate()
this.cancelledJobs = 0
this.navigationGeneration = -1
this.navigationActive = false
this.surfacePool.clear()
}
private isNavigationActive(renderer: SkiaRenderer): boolean {
return (
renderer.navigationPhase === 'pan' ||
renderer.navigationPhase === 'zoom' ||
renderer.navigationPhase === 'momentum' ||
renderer.navigationPhase === 'settling'
)
}
private prepareGeneration(
renderer: SkiaRenderer,
graph: SceneGraph,
contentGeneration: number,
navigationGeneration: number
): void {
this.cancelledJobs += this.scheduler.setGeneration(navigationGeneration, contentGeneration)
// Node changes arrive through invalidateNode() and structural ones through
// invalidateStructure(), so a new content generation on its own is a redraw request (every
// requestRender() bumps it) and the rendered tiles stay valid. Invalidations also arrive
// without a new generation, as when an image preview decodes.
if (this.index && this.pageId === renderer.pageId && this.pendingStructure.length > 0) {
this.applyPendingStructure(graph, contentGeneration)
}
if (
this.index &&
this.pageId === renderer.pageId &&
(this.contentGeneration !== contentGeneration || this.pendingInvalidations.length > 0)
) {
this.applyPendingInvalidations(graph, contentGeneration)
}
if (this.index && this.pageId !== renderer.pageId) this.invalidate()
// Without an index nothing can be shown, so a page that arrives mid-gesture builds its index
// at once; its tiles then fill in under the moving budget rather than after the gesture.
if (this.index === null && renderer.pageId) {
this.ensureIndex(graph, renderer.pageId, contentGeneration)
}
}
private applyPendingInvalidations(graph: SceneGraph, contentGeneration: number): void {
const page = this.pageTiles()
if (!page) return
applyInvalidations(page, graph, this.pendingInvalidations, contentGeneration)
if (this.pendingInvalidations.length > 0) this.lastContentChangeAt = this.now()
this.pendingInvalidations = []
this.contentGeneration = contentGeneration
}
private applyPendingStructure(graph: SceneGraph, contentGeneration: number): void {
const page = this.pageTiles()
if (!page) return
if (!applyStructureChanges(page, graph, this.pendingStructure, contentGeneration)) {
this.invalidate()
return
}
this.pendingStructure = []
this.contentGeneration = contentGeneration
this.lastContentChangeAt = this.now()
}
private pageTiles(): PageTiles | null {
if (!this.index || !this.pageId) return null
return {
index: this.index,
pageId: this.pageId,
pictureCache: this.pictureCache,
tileCache: this.tileCache
}
}
private ensureIndex(graph: SceneGraph, pageId: string | null, contentGeneration: number): void {
if (this.index && this.pageId === pageId && this.contentGeneration === contentGeneration) return
this.index?.dispose()
this.pictureCache.clear()
this.tileCache.markStale(contentGeneration)
this.pageId = pageId
this.contentGeneration = contentGeneration
// A fresh index already reflects every change recorded before it was built.
this.pendingInvalidations = []
this.index = pageId ? RenderChunkIndex.build(graph, pageId).index : null
}
/**
* How far past its budget a frame's first job may run: a moving frame keeps its fallback
* rather than a dear tile, an idle one always makes progress, or a tile dearer than any limit
* would never render and its stage never end.
*/
private firstJobLimit(): number {
return this.navigationActive ? NAVIGATION_FIRST_TILE_LIMIT_MS : Number.POSITIVE_INFINITY
}
/**
* The frame's plan options: the visible tiles and, while idle and the cache can hold them, the
* background stages; queued jobs for other levels are discarded, and the cache counts the
* evictions of the levels the plan needs.
*/
private planFrame(
renderer: SkiaRenderer,
pageId: string,
index: RenderChunkIndex,
level: number,
viewport: TileWorldBounds,
contentGeneration: number,
navigationGeneration: number
): { planOptions: TilePlanOptions; background: boolean } {
// Jobs planned at another level draw nothing the viewport shows now; a downsample is cheap
// and feeds the fallback at any level, so it stays.
const backdropLevel = tileLevel((level / BACKDROP_LEVEL_RATIO) * (1 - 1e-9))
const pageBackdrop = pageBackdropPlan(index.bounds(), level)
if (pageBackdrop) this.tileCache.touchLevel(pageId, pageBackdrop.level)
this.cancelledJobs += this.scheduler.discard(
(job) =>
job.kind !== 'downsample' &&
job.key.level !== level &&
job.key.level !== backdropLevel &&
job.key.level !== pageBackdrop?.level
)
const planOptions: TilePlanOptions = {
pageId,
level,
viewport,
overscanTiles: this.backgroundSaturated ? 0 : TILE_OVERSCAN,
navigationGeneration,
contentGeneration,
estimateCost: (key) =>
estimateTileCost(
renderer,
index,
this.pictureCache,
this.costs,
key,
this.navigationActive
),
globalFallbackAvailable: true
}
// Background stages wait for idle, a moving frame having only its budget to give, and for
// the content to have been still a while, so an edit in progress rebuilds the visible tiles
// alone.
const quiet = this.now() - this.lastContentChangeAt >= BACKGROUND_QUIET_MS
const background = !this.navigationActive && !this.backgroundSaturated && quiet
this.backgroundWaiting = !this.navigationActive && !this.backgroundSaturated && !quiet
if (background) {
planOptions.backdrop = { level: backdropLevel, overscanTiles: BACKDROP_OVERSCAN }
planOptions.pageBackdrop = pageBackdrop
planOptions.pyramid = { levels: PYRAMID_LEVELS }
}
const watched = new Set([level, backdropLevel])
if (pageBackdrop) watched.add(pageBackdrop.level)
for (let depth = 1; depth <= PYRAMID_LEVELS; depth++) watched.add(level / 2 ** depth)
this.tileCache.watchLevels(watched)
return { planOptions, background }
}
private executeJob(
renderer: SkiaRenderer,
graph: SceneGraph,
index: RenderChunkIndex,
job: TileJob,
remainingMs: number
) {
const startedAt = this.now()
if (
job.kind !== 'downsample' &&
!recordTilePictures(renderer, graph, index, this.pictureCache, job.key, {
now: this.now,
remainingMs
})
) {
return { renderMs: this.now() - startedAt, overBudget: false, deferred: true }
}
const tile =
job.kind === 'downsample'
? this.downsample(renderer, job)
: renderTile(renderer, graph, index, job.key, this.pictureCache, this.surfacePool)
if (!tile) return { renderMs: 0, overBudget: job.kind !== 'downsample' }
if (job.kind !== 'downsample') {
this.costs.record(job.key, this.now() - startedAt, tile.chunkCount)
}
if (
job.navigationGeneration !== this.navigationGeneration ||
job.contentGeneration !== this.contentGeneration
) {
deleteRenderedTile(tile)
return tileJobResult(tile, TILE_FRAME_BUDGET_MS)
}
this.tileCache.takeWatchedEvictions()
this.tileCache.install(tile, job.contentGeneration)
if (job.priority !== 'overscan') this.visibleTilesRendered++
if (job.priority === 'overscan' && this.tileCache.takeWatchedEvictions() > 0) {
this.backgroundSaturated = true
}
return tileJobResult(tile, TILE_FRAME_BUDGET_MS)
}
/** Null when a child has gone since the job was planned; the next plan decides again. */
private downsample(renderer: SkiaRenderer, job: TileJob) {
const children: CachedTile[] = []
for (const childKey of childTileKeys(job.key)) {
const child = this.tileCache.getIfPresent(childKey)
if (!child || child.contentGeneration !== job.contentGeneration) return null
children.push(child)
}
return downsampleTile(renderer, job.key, children, this.surfacePool)
}
/** Whether the cache holds a fresh tile for `key`. */
isRendered(key: TileKey): boolean {
return this.tileCache.getIfPresent(key)?.contentGeneration === this.contentGeneration
}
private emptyResult(): TiledSceneFrameResult {
return {
covered: false,
pending: false,
backgroundPending: false,
metrics: emptyTileSchedulerMetrics(),
fallbackTileCount: 0,
uncoveredAreaCount: 1,
uncoveredContentAreaCount: 1
}
}
}