nx_gsplat_tile_lib.nx source
↩ module page · 322 lines · 16074 B
1// nx_gsplat_tile_lib.nx -- ★TILED RASTERIZATION: a second POLICY over the SAME three rasterizer stages,
2// not a second rasterizer. It calls gs_project_sort, gs_blend_rect and gs_resolve -- the identical
3// projection, the identical conic blend, the identical resolve that the full-screen path uses. Nothing
4// about the maths is restated here, so the two renderers CANNOT drift.
5//
6// ★★THE ACCEPT RULE, DECLARED BEFORE THE EXPERIMENT (and enforced by nx_gsplat_tile_gate):
7// CORRECTNESS -- the tiled frame must be BYTE-IDENTICAL to the full-screen frame. Not "close", not
8// "within tolerance": identical. This optimisation is only allowed to change COST.
9// COST -- it must perform STRICTLY FEWER conic evaluations on a scene with occlusion.
10// If either fails, it does not ship. A tiled renderer that is merely as fast, or that differs by a
11// rounding nobody can see, is not an improvement -- it is a second ruler.
12//
13// WHY BYTE-IDENTITY IS ACHIEVABLE RATHER THAN LUCKY: every pixel belongs to exactly one tile; within a
14// tile the splats are visited in the SAME global depth order (the list is built by walking the sorted
15// order and appending); and the early-out skips a splat only when EVERY pixel of the tile is already
16// saturated -- pixels the blend would have skipped anyway on its own `tr > 1` test. So no contribution
17// is dropped and none is reordered. The saving is work that provably could not have changed a pixel.
18//
19// ⚠WHAT IS AND IS NOT CLAIMED: this is a serial CPU renderer. Tiling here buys OCCLUSION SKIPPING and
20// memory locality; it does NOT buy parallelism, because there is no thread or GPU to spread tiles across.
21// The parallel dispatch that tiling exists for on a GPU is a NAMED GAP with a named blocker.
22// license_tier: ORIGINAL No hw writes (Rule 26).
23import "nx_syscalls.nx"
24import "nx_gsplat.nx"
25
26const GT_ERRFD: i64 = 2
27const GT_W64: i64 = 8
28// A tile must be at least one pixel across, or it partitions nothing. Structural floor, not a tuning knob:
29// THE TILE EDGE IS THE CALLER'S CHOICE, and nx_gsplat_tile_gate sweeps it and publishes the measured curve
30// rather than this file naming a favourite number.
31const GT_EDGE_MIN: i64 = 1
32const GT_E_TILE: i64 = 3
33const GT_E_ENTRIES: i64 = 4
34const GT_E_INIT: i64 = 5
35
36static GT_TE: i64
37static GT_TX: i64
38static GT_TY: i64
39// ★THE VIEWPORT THE TILE GRID WAS BUILT FOR. Until 2026-08-23 this file read gs_w()/gs_h() -- the MODULE
40// DEFAULTS -- in six places, so the tiled policy could only ever partition a 512x384 frame even after the
41// rasterizer's own viewport became a parameter. That is why the tiled path could not render the 4K frame
42// the full-screen policy is measured on: not a limitation of tiling, a viewport that was never plumbed
43// through. Holding it here means the grid, the blend clip and the resolve all read ONE source, so a
44// caller cannot init at one size and render at another.
45static GT_VW: i64
46static GT_VH: i64
47static GT_MAXE: i64
48// a structural floor, not a tuning knob: fewer than one worker renders nothing.
49const GT_WORKERS_MIN: i64 = 1
50const GT_E_WORKERS: i64 = 6
51
52static GT_TCNT: i64
53static GT_TOFF: i64
54static GT_TLIST: i64
55static GT_SAT: i64
56static GT_MAXW: i64
57static GT_WEVAL: i64
58static GT_ALLOC: i64
59static GT_EVALS: i64
60static GT_ENT: i64
61static GT_SKIP: i64
62
63func gt_slen(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } return n }
64func gt_err(s: *u8) -> i64 { sys_write(GT_ERRFD, s, gt_slen(s)); return 0 }
65// every allocation is counted as a side effect of allocating, so gt_bytes() cannot drift from reality.
66func gt_alloc(n: i64) -> i64 { GT_ALLOC = GT_ALLOC + n; return sys_mmap(n) as i64 }
67
68// tile_edge and max_entries are BOTH the caller's declared budget. max_entries is a real ceiling: a splat
69// that straddles many tiles occupies one list slot per tile, so the total is scene-dependent and MUST be
70// declared rather than assumed. Exceeding it REFUSES -- it never silently truncates, because a truncated
71// tile list renders a frame that is subtly and invisibly wrong.
72func gt_init_at(tile_edge: i64, max_entries: i64, max_workers: i64, vw: i64, vh: i64) -> i64 {
73 if max_workers < GT_WORKERS_MIN { gt_err("GSPLAT-TILE-REFUSE worker budget must be at least one\n" as *u8); return 0 - GT_E_WORKERS }
74 if tile_edge < GT_EDGE_MIN { gt_err("GSPLAT-TILE-REFUSE tile edge must be at least one pixel\n" as *u8); return 0 - GT_E_TILE }
75 if tile_edge > vw { gt_err("GSPLAT-TILE-REFUSE tile edge exceeds the framebuffer width\n" as *u8); return 0 - GT_E_TILE }
76 if tile_edge > vh { gt_err("GSPLAT-TILE-REFUSE tile edge exceeds the framebuffer height\n" as *u8); return 0 - GT_E_TILE }
77 if max_entries < 1 { gt_err("GSPLAT-TILE-REFUSE entry budget must be positive\n" as *u8); return 0 - GT_E_INIT }
78 GT_ALLOC = 0
79 GT_TE = tile_edge
80 GT_VW = vw
81 GT_VH = vh
82 // ceiling division: a framebuffer that does not divide evenly still gets full coverage, with the edge
83 // tiles clipped at render time. Rounding down here would silently drop the right and bottom margins.
84 GT_TX = (vw + tile_edge - 1) / tile_edge
85 GT_TY = (vh + tile_edge - 1) / tile_edge
86 GT_MAXE = max_entries
87 let nt: i64 = GT_TX * GT_TY
88 GT_TCNT = gt_alloc((nt+1)*GT_W64)
89 GT_TOFF = gt_alloc((nt+1)*GT_W64)
90 GT_TLIST = gt_alloc(max_entries*GT_W64)
91 GT_SAT = gt_alloc(GT_W64)
92 // ★PER-WORKER EVAL COUNTERS LIVE IN *SHARED* MEMORY. After a fork the statics are copy-on-write, so a
93 // child incrementing GT_EVALS would increment its OWN copy and the parent would read zero -- work would
94 // look like it never happened. One shared slot per worker is what makes the distribution measurable.
95 GT_MAXW = max_workers
96 GT_WEVAL = sys_mmap_shared(max_workers*2*GT_W64) as i64
97 GT_ALLOC = GT_ALLOC + max_workers*2*GT_W64
98 GT_EVALS = 0
99 GT_ENT = 0
100 GT_SKIP = 0
101 return 0
102}
103// The historic entry point: the viewport IS the module default. Byte-identical for every existing caller
104// -- gs_focal_for(GH) is GFOCAL by construction, and a 512x384 grid is what this file always built -- so
105// nx_gsplat_tile_gate's byte-identity oracle continues to measure exactly what it measured before.
106func gt_init(tile_edge: i64, max_entries: i64, max_workers: i64) -> i64 {
107 return gt_init_at(tile_edge, max_entries, max_workers, gs_w(), gs_h())
108}
109func gt_tiles_x() -> i64 { return GT_TX }
110func gt_tiles_y() -> i64 { return GT_TY }
111func gt_tiles() -> i64 { return GT_TX * GT_TY }
112func gt_edge() -> i64 { return GT_TE }
113func gt_edge_min() -> i64 { return GT_EDGE_MIN }
114func gt_bytes() -> i64 { return GT_ALLOC }
115// the cost currency, in the SAME unit gs_blend_rect reports: conic evaluations.
116func gt_evals() -> i64 { return GT_EVALS }
117// list slots actually used, so the caller can size its budget from a measurement instead of a guess.
118func gt_entries() -> i64 { return GT_ENT }
119// splat-tile pairs skipped because the tile was already fully opaque -- the whole point of the policy.
120func gt_skipped() -> i64 { return GT_SKIP }
121
122// composite ONE tile, through the SAME gs_blend_rect the full-screen policy uses. Returns conic
123// evaluations; skipout[0] accumulates splat-tile pairs declined because the tile went fully opaque.
124// ★EXTRACTED SO THE SERIAL AND PARALLEL POLICIES SHARE ONE IMPLEMENTATION -- if the parallel path had its
125// own copy of this loop, "byte-identical" would be a coincidence maintained by hand instead of a property.
126func gt_blend_tile(ti: i64, gauss: *i64, sxb: *i64, syb: *i64, pa: *i64, pb: *i64, pc: *i64, pdet: *i64, acc: *i64, trans: *i64, explut: *i64, W: i64, H: i64, satp: *i64, skipout: *i64) -> i64 {
127 let toff: *i64 = GT_TOFF as *i64
128 let tcnt: *i64 = GT_TCNT as *i64
129 let tl: *i64 = GT_TLIST as *i64
130 let tx: i64 = ti % GT_TX
131 let ty: i64 = ti / GT_TX
132 let px0: i64 = tx*GT_TE
133 var px1: i64 = px0 + GT_TE - 1
134 if px1 >= W { px1 = W - 1 }
135 let py0: i64 = ty*GT_TE
136 var py1: i64 = py0 + GT_TE - 1
137 if py1 >= H { py1 = H - 1 }
138 var live: i64 = (px1 - px0 + 1)*(py1 - py0 + 1)
139 var evals: i64 = 0
140 var e: i64 = toff[ti]
141 let eend: i64 = tcnt[ti]
142 while e < eend {
143 if live > 0 {
144 let g: i64 = tl[e]
145 let sx: i64 = sxb[g]
146 let sy: i64 = syb[g]
147 let ca: i64 = pa[g]
148 let cc: i64 = pc[g]
149 let rx: i64 = gs_splat_rx(ca)
150 let ry: i64 = gs_splat_ry(cc)
151 var bx0: i64 = sx - rx
152 if bx0 < px0 { bx0 = px0 }
153 var bx1: i64 = sx + rx
154 if bx1 > px1 { bx1 = px1 }
155 var by0: i64 = sy - ry
156 if by0 < py0 { by0 = py0 }
157 var by1: i64 = sy + ry
158 if by1 > py1 { by1 = py1 }
159 satp[0] = 0
160 evals = evals + gs_blend_rect(gauss, g, sx, sy, ca, pb[g], cc, pdet[g], bx0, bx1, by0, by1, acc, trans, explut, W, satp)
161 live = live - satp[0]
162 e = e + 1
163 } else {
164 // record the work avoided BEFORE leaving, so the cursor never carries the only copy of
165 // the answer -- a loop that exits by clobbering its cursor cannot report where it stopped.
166 skipout[0] = skipout[0] + (eend - e)
167 e = eend
168 }
169 }
170 return evals
171}
172func gt_workers() -> i64 { return GT_MAXW }
173// per-worker conic evaluations, read from SHARED memory so the parent can see what the children did.
174func gt_worker_evals(w: i64) -> i64 { let a: *i64 = GT_WEVAL as *i64; return a[w*2] }
175func gt_worker_skipped(w: i64) -> i64 { let a: *i64 = GT_WEVAL as *i64; return a[w*2+1] }
176
177func gt_render(gauss: *i64, ng: i64, yaw: i64, camz: i64, fb: *i64, acc: *i64, trans: *i64, depth: *i64, sxb: *i64, syb: *i64, pa: *i64, pb: *i64, pc: *i64, pdet: *i64, order: *i64, count: *i64, explut: *i64, bgr: i64, bgg: i64, bgb: i64, workers: i64) -> i64 {
178 if GT_TE < GT_EDGE_MIN { gt_err("GSPLAT-TILE-REFUSE render before a successful gt_init\n" as *u8); return 0 - GT_E_INIT }
179 // The viewport comes from init, so the grid, the clip and the resolve cannot disagree about the frame
180 // they are working on. Focal is DERIVED from that height rather than passed beside it -- a focal that
181 // disagrees with its own viewport is the second ruler this file refuses everywhere else.
182 let W: i64 = GT_VW
183 let H: i64 = GT_VH
184 let focal: i64 = gs_focal_for(H)
185 GT_EVALS = 0
186 GT_ENT = 0
187 GT_SKIP = 0
188 // STAGE 1 -- the SAME projection and depth sort the full-screen path uses, at the declared viewport.
189 let vis: i64 = gs_project_sort_at(gauss, ng, yaw, camz, depth, sxb, syb, pa, pb, pc, pdet, order, count, W/2, H/2, focal)
190 if vis == 0 { return 0 }
191 let tcnt: *i64 = GT_TCNT as *i64
192 let toff: *i64 = GT_TOFF as *i64
193 let tl: *i64 = GT_TLIST as *i64
194 let nt: i64 = GT_TX * GT_TY
195 var t: i64 = 0
196 while t <= nt { tcnt[t] = 0; t = t + 1 }
197 // PASS A -- count how many tiles each splat touches, so the budget is checked BEFORE anything is
198 // written. Counting first is what makes the refusal total rather than partial.
199 var need: i64 = 0
200 var oi: i64 = 0
201 while oi < vis {
202 let g: i64 = order[oi]
203 let rx: i64 = gs_splat_rx(pa[g])
204 let ry: i64 = gs_splat_ry(pc[g])
205 var x0: i64 = sxb[g] - rx
206 if x0 < 0 { x0 = 0 }
207 var x1: i64 = sxb[g] + rx
208 if x1 >= W { x1 = W - 1 }
209 var y0: i64 = syb[g] - ry
210 if y0 < 0 { y0 = 0 }
211 var y1: i64 = syb[g] + ry
212 if y1 >= H { y1 = H - 1 }
213 // a splat whose box lies wholly off screen touches NO tile. Without this guard a negative
214 // coordinate divides toward zero and claims tile 0, adding work for a splat that cannot draw.
215 if x0 <= x1 { if y0 <= y1 {
216 var ty: i64 = y0/GT_TE
217 let tye: i64 = y1/GT_TE
218 while ty <= tye {
219 var tx: i64 = x0/GT_TE
220 let txe: i64 = x1/GT_TE
221 while tx <= txe {
222 tcnt[ty*GT_TX + tx] = tcnt[ty*GT_TX + tx] + 1
223 need = need + 1
224 tx = tx + 1
225 }
226 ty = ty + 1
227 }
228 } }
229 oi = oi + 1
230 }
231 if need > GT_MAXE {
232 gt_err("GSPLAT-TILE-REFUSE this scene needs more tile-list slots than the declared budget -- refusing rather than rendering a truncated frame\n" as *u8)
233 return 0 - GT_E_ENTRIES
234 }
235 GT_ENT = need
236 // prefix sum: toff holds each tile's start, tcnt becomes the fill cursor.
237 var pre: i64 = 0
238 t = 0
239 while t < nt { let c: i64 = tcnt[t]; toff[t] = pre; tcnt[t] = pre; pre = pre + c; t = t + 1 }
240 toff[nt] = pre
241 // PASS B -- fill. Walking the SORTED order means each tile's list comes out in depth order for free.
242 oi = 0
243 while oi < vis {
244 let g: i64 = order[oi]
245 let rx: i64 = gs_splat_rx(pa[g])
246 let ry: i64 = gs_splat_ry(pc[g])
247 var x0: i64 = sxb[g] - rx
248 if x0 < 0 { x0 = 0 }
249 var x1: i64 = sxb[g] + rx
250 if x1 >= W { x1 = W - 1 }
251 var y0: i64 = syb[g] - ry
252 if y0 < 0 { y0 = 0 }
253 var y1: i64 = syb[g] + ry
254 if y1 >= H { y1 = H - 1 }
255 if x0 <= x1 { if y0 <= y1 {
256 var ty: i64 = y0/GT_TE
257 let tye: i64 = y1/GT_TE
258 while ty <= tye {
259 var tx: i64 = x0/GT_TE
260 let txe: i64 = x1/GT_TE
261 while tx <= txe {
262 let ti: i64 = ty*GT_TX + tx
263 tl[tcnt[ti]] = g
264 tcnt[ti] = tcnt[ti] + 1
265 tx = tx + 1
266 }
267 ty = ty + 1
268 }
269 } }
270 oi = oi + 1
271 }
272 // STAGE 2 -- composite tile by tile, through the SAME blend, stopping a tile the moment every pixel
273 // in it is opaque.
274 gs_clear_at(acc, trans, W*H)
275 let satp: *i64 = GT_SAT as *i64
276 let wev: *i64 = GT_WEVAL as *i64
277 var wz: i64 = 0
278 while wz < GT_MAXW*2 { wev[wz] = 0; wz = wz + 1 }
279 var nw: i64 = workers
280 if nw < GT_WORKERS_MIN { nw = GT_WORKERS_MIN }
281 if nw > GT_MAXW { nw = GT_MAXW }
282 if nw == 1 {
283 // SERIAL: every tile, in order. This is the path the byte-identity oracle was established on.
284 var ti: i64 = 0
285 while ti < nt {
286 GT_EVALS = GT_EVALS + gt_blend_tile(ti, gauss, sxb, syb, pa, pb, pc, pdet, acc, trans, explut, W, H, satp, wev)
287 ti = ti + 1
288 }
289 GT_SKIP = wev[0]
290 } else {
291 // ★PARALLEL: one process per worker, tiles dealt round-robin. This is SAFE BY CONSTRUCTION rather
292 // than by locking: every pixel belongs to exactly ONE tile, so two workers never touch the same
293 // acc/trans word and there is nothing to race over. That property is what tiling bought -- the
294 // partition IS the synchronisation. acc/trans MUST be MAP_SHARED (see the header contract); the
295 // per-tile saturation scratch is deliberately NOT, because each child wants its own.
296 var w: i64 = 0
297 while w < nw {
298 let pid: i64 = sys_fork()
299 if pid == 0 {
300 var ti: i64 = w
301 var mine: i64 = 0
302 while ti < nt {
303 mine = mine + gt_blend_tile(ti, gauss, sxb, syb, pa, pb, pc, pdet, acc, trans, explut, W, H, satp, ((GT_WEVAL as i64) + (w*2+1)*GT_W64) as *i64)
304 ti = ti + nw
305 }
306 wev[w*2] = mine
307 sys_exit(0)
308 }
309 w = w + 1
310 }
311 // reap every child before reading the frame: a parent that resolves while a worker is still
312 // blending publishes a half-composited image and calls it a render.
313 let st: *i64 = sys_mmap(16) as *i64
314 var r: i64 = 0
315 while r < nw { sys_wait4(0 - 1, st, 0); r = r + 1 }
316 var sw: i64 = 0
317 while sw < nw { GT_EVALS = GT_EVALS + wev[sw*2]; GT_SKIP = GT_SKIP + wev[sw*2+1]; sw = sw + 1 }
318 }
319 // STAGE 3 -- the SAME resolve.
320 gs_resolve(fb, acc, trans, W*H, bgr, bgg, bgb)
321 return vis
322}