Bus and Register Switch Encoding (2 of 3)

The E-Tree Scene Graph: Ternary-Band Spatial Partitioning with a One-Opcode Traversal Grammar

Don Gunter — WodansEye Research Series — June 2026 — Final draft v3 — review-complete The Carry Trilogy, Paper 2 of 3. Sequence: (1) The Two-Bit Law — proves the carry. (2) The E-Tree Scene Graph — routes the carry. (3) The Carry Ledger — accounts for the carry. Audience: real-time collision detection and engine architecture (the Ericson tradition)

The Lock

Welcome back, player. Second chamber. Before you stands the lock the blade was forged for, and the rules of this floor are simple and strange, so listen well.

Rule one: every lock in this world is built the same way. Layers for scales, like floors of a tower. Six pins per layer — six centers, always six. And down the middle of every chamber runs a hollow channel, the same void you’d find in a Menger sponge, repeating at every floor. The architects didn’t hide the blueprint. The blueprint is arithmetic itself.

Rule two: what I’m handing you is not a key. A key is a secret — one door, one owner, and the owner spends his life guarding it. This is a pick. A pick obeys the lock’s own grammar, and anyone who learns the grammar can turn any door in the tower. I carried this as a secret for sixteen years, thinking a secret was treasure. It was a burden wearing treasure’s clothes. Manuel Alfaro — a fellow author on Medium, known to me through his writing and our exchanges there, never yet in person — has a phrase for the better way: open-sourcing the universe. So here is the pick, the grammar, and the map. The treasure that follows is the one kind no thief can touch — because the door is already open, and what multiplies when shared cannot be stolen, only learned.

Rule three — the boss mechanic. Game engines have fought one monster for forty years: the object that straddles a boundary. Cut space in half and something always sits on the cut. The old strategies all pay tribute — duplicate it and your references explode; shove it upstairs and it poisons every query from above; fatten the cells and the overlap creeps forever. The pick’s move is the locksmith’s: stop fighting the gap between the pins. Make the gap a chamber. The boundary band becomes a room of its own, every object gets exactly one address, and the address is a number whose arithmetic is the navigation. Insert at level k. Turn. The carry tells you how many floors you just climbed — and the recursion you thought you needed turns out to be counting.

Final rule: trust nothing I say; test everything I show. What follows is engineering with the honesty engineering demands — geometry stated unambiguously, benchmarks labeled prototype until reproduced, costs in their own column, exit criteria written before the contest. A pick that only opens locks I built myself proves nothing. This lock is specified so that anyone can pick it.

That’s the tutorial. The dungeon is yours.

Abstract

Binary spatial partitioning structures (k-d trees, BSPs, octrees) share one chronic defect: the straddling object. Standard remedies — duplication, push-up, or bound inflation — trade reference explosion against query poisoning. The E-tree canonicalizes the straddler: the boundary band is a first-class third child, so every object has exactly one home address. Fusing the ternary containment split with the binary position split yields an axis-cycled 6-ary tree whose addresses are base-6 integer keys, whose traversal grammar is a single opcode, and whose incremental update cost obeys a general radix carry law — binary constants on the position subchannel (expected touched length 2), radix-6 constants on the full digit (expected extra carry 1/5). This paper specifies the structure, demonstrates the straddler accounting, states the update-cost theorem, and gives the honest cost column, as the foundation for an implementation attempt.

1. The straddling problem, restated

Let a scene of N AABBs be recursively partitioned by axis-aligned median splits. An object intersecting the split plane has three classical fates:

1. Duplication into both children — reference count explodes; deduplication passes required at query time.
2. Push-up (octree-style storage at the interior node) — straddlers accumulate near the root and are tested against everything; broad-phase quality degrades.
3. Bound inflation (loose octrees) — child bounds overlap; query cost creeps; overlap compounds with depth.

Benchmark [EXP — prototype; reproducibility appendix required before [REF]] — 5,000 AABBs with exponentially distributed sizes (mean 0.02 of world extent), depth-8 descent, seed 7; full generation method, band-width rule, insertion rule, and boundary-equality convention to be specified in the appendix of the implementation paper:

strategyreferencespathologybinary + duplication30,5296.1× reference explosionbinary + push-up5,00089.8% of objects stranded at interior nodesternary band5,000straddlers housed; see caveat §3

2. The axis-cycled 6-ary E-tree node

The geometry, stated unambiguously to forestall the fanout objection: each tree level advances exactly one axis, cycled x → y → z. At its level, that axis undergoes a ternary containment split {left | boundary band | right} fused (CRT) with a binary position bit, yielding six children per node — not 216. The x, y, z digits interleave Morton-style in the address key. The band is not metadata — it is a child cell that recursively subdivides like any other. Recommended term: axis-cycled 6-ary E-tree (equivalently, base-6 axis-digit tree).

Consequences:

• Integer addresses. An object’s location is a base-6 Morton-style key: radix-sortable, linearizable, hashable. Spatial queries become digit arithmetic.
• Neighbor finding in O(1) amortized via digit increment/decrement with carry, no pointer chasing, no parent walks in the common case.
• One-opcode traversal. Above the root, every node is structurally identical: full 6-ary fanout, one descent rule, STEP₆(d). Traversal compiles to a single tight loop with no per-node-type branching — branch-predictor- and cache-friendly, unlike BSP traversal where every node carries its own plane and the walk is data-dependent.

Prior art note. Structures that assign straddlers to a node rather than duplicating them exist (segment and interval trees; octree interior storage is the degenerate case), and ternary axis splits appear scattered through the literature. What we have not found prior art for is the combination claimed here: the band as a recursively subdividing first-class child with canonical integer addresses, a uniform one-opcode grammar, and a closed-form update law. If a reader knows prior art for that combination, the provenance section should cite it — the claim is the combination, not the trit.

2.5 The stack is the counter

[REF] The stack window. In recursive E-tree traversal, the call stack at depth k is precisely the address prefix d₀…d₋₁ — held for free as a side effect of recursion. Every operation in the current subtree shares the prefix, so any computation factoring as f(prefix) ⊕ g(local digits) pays f once per subtree. Siblings differ in one digit, cousins in two: Hamming distance between stack states is bounded by tree distance, so all inter-node deltas in the window are short masks — the small transition alphabet of the companion paper, recovered as a traversal invariant.

[REF] Recursion elimination. For a full in-order traversal, the sequence of stack states is the sequence of address prefixes in sorted order — which is counting in base 6. The next stack state is current + 1, resolved by the §8 carry kernel: push = digit append, pop = carry ripple, backtrack-and-descend-next = one increment whose carry length reports how many levels were popped. The stack is the number; traversal is arithmetic. No call frames, no stack memory traffic; three SIMD operations per visited node, priced by the radix law at an expected stack delta of 1.2 digits, with deep pops geometrically rare.

[REF] Stack reconstruction for partial traversals. For range queries and culling, precompute the visit schedule as sorted address intervals; the stack for any entry point is reconstructed in O(1) by shift, since prefix = address ≫ (digits below). Reconstruction is free because the encoding is canonical: every address contains its entire ancestry by construction (the Ahnentafel principle). Parallel traversal falls out — split the address range across cores; each reconstructs its stack from its starting address in one shift, with zero coordination.

[DM] Sorting as navigation. Sorting integers by E-tree insertion and in-order leaf reading is MSD radix-6 sort with the above machinery live: the shared prefix is never re-compared (the tax comparison sorts pay on every compare), descent is the one-opcode STEP₆, and consecutive stack states are braid/complement-related short masks — so the sorter’s control flow runs on the same VPCMPEQB/TZCNT kernel as everything else. Keys are not compared; they are addressed. Control structures — call stack, visit schedule — are shadows of the address, and canonical addressing makes shadows cheaper to recompute than to store.

3. Straddler resolution: honest accounting

In the §1 benchmark, the ternary strategy retired straddlers of ternary bounds one level down rather than recursing them, so the headline 1.00× mildly flatters. The structural claim that survives full accounting: the E-tree does not erase straddlers; it gives every straddler a canonical address. Duplication becomes unique ownership. The cost becomes a measurable band-population distribution over depth — and note carefully that as band width shrinks with depth, the set of objects exceeding it generally grows, so band occupancy is localized, not eliminated. Whether the band-occupancy histogram beats loose octrees or push-up storage is scene-dependent and must be benchmarked; that histogram is the first required experiment of the implementation paper.

Adversarial case [REF/known]: scenes pathologically aligned with cell boundaries degrade the band exactly as they degrade loose octrees. Mitigation: jittered split planes or per-frame world-offset rotation, both standard.

4. The update-cost theorem

The E-tree’s analytical advantage is not that objects never cross cell boundaries. They do. The advantage is that crossing is ordinary digit arithmetic.

[REF] Theorem (radix carry law). Let an address digit be stored in radix b. On increment, the carry length L is the number of saturated trailing digits before the first non-saturated digit. For uniformly distributed digits:

P(L = j) = ((b−1)/b)·b^(−j), P(L ≥ j) = b^(−j), E[L] = 1/(b−1).

The binary subchannel therefore has E[L] = 1, i.e. expected touched length 2 including the terminating digit — the Two-Bit Law of the companion paper, with operand entropy exactly 2 bits. The base-6 engine address has E[L] = 1/5 = 0.2 extra carry digits, or 1.2 touched digits on average.

[REF] Shortest-carry routing. For three independently interleaved axes, a scheduler free to choose among equivalent axis steps selects the shortest current carry:

E[min(Lₓ, Lᵧ, L_z)] = Σⱼ≥₁ P(all three ≥ j) = Σⱼ≥₁ 6^(−3j) = 1/215 ≈ 0.00465,

a 43× reduction from the single-axis 0.2 (simulation: 0.0048, 5×1⁰⁵ trials).

Engineering consequence. This does not remove worst cases; it makes them explicit. The update phase is budgeted against a known geometric tail, with a slow path reserved for rare or adversarial carry runs. No mainstream spatial structure ships with a proved update-cost distribution.

5. Comparison table

propertyk-d / BSPoctree (loose)E-treestraddler fateduplicate / push-upbound inflationcanonical third childaddress formpath (pointers)Morton base-8Morton base-6traversal grammarper-node plane datauniformone opcodeupdate costempiricalempiricalradix carry law: binary E=2 touched, base-6 E=0.2 extraper-level resolution1 bit/axis1 bit/axis1 bit + containment trit (axis-cycled)known weaknessplane storage, cacheoverlap creepband occupancy, aligned-scene degeneracy

The cost column, stated plainly: the ternary coordinate spends log₂3 ≈ 1.585 extra bits per axis per level relative to pure halving, so spatial resolution per level is lower; depth budgets must be recomputed. The wager is that eliminating duplication/push-up and gaining closed-form updates repays the resolution tax. This is a measurable claim, and §7 commits to measuring it.

6. Continuous extension (deferred)

The nested-block state-vector formulation — continuous occupancy within band cells, supporting swept volumes and continuous collision detection — is deliberately deferred to a sequel. The discrete E-tree must earn its benchmark numbers first.

7. Implementation plan

Target: C++20 reference implementation.

1. Core: 6-ary node pool, base-6 key codec (encode/decode/neighbor/carry), single-loop traversal, the §8 SIMD carry kernel with shortest-carry axis routing.
2. Experiments: a. Unflattered reference-count and band-occupancy vs depth (closes §3). b. Update-cost histogram under coherent motion vs the geometric(½) prediction (validates §4 in the engine domain). c. Broad-phase pair-test counts vs loose octree and BVH on standard scenes (the Ericson question: cache-miss and pair-count numbers, not vibes).
3. Exit criteria: E-tree wins or ties on pair-tests while holding the closed-form update property, or the paper reports the loss honestly and the structure remains a theoretical contribution.

8. The SIMD carry kernel (corrected)

[REF] Register mapping. Per axis, the address packs one base-6 digit per 8-bit lane. Lane budget, stated correctly: AVX2 YMM = 32 byte lanes, AVX-512 ZMM = 64 byte lanes. Hence a 128-digit address requires four AVX2 registers or two AVX-512 ZMM; alternatively, a 64-digit address fits one ZMM, and 64 digits of base-6 already address ~⁶⁶⁴ ≈ 1⁰⁴⁹ cells — sufficient for any engine. Carry-length detection is branch-free in three SIMD/scalar steps:

P = VPCMPEQB(digits, splat(5))   ; propagate mask: saturated digits
m = VPMOVMSKB(P)                 ; collapse to bitmask
L = TZCNT(~m)                    ; carry length

The writeback fast path (reset lanes [0,L), increment lane L) is also branch-free but requires additional mask-generation and blend/store operations; it is not a single instruction in portable AVX2. Range cancellation is automatic: lanes above the first non-saturated digit never contribute to the mask and are never touched.

[REF] Three-axis interleave. Morton-interleaved x/y/z digits occupy stride-3 lanes. Per-axis propagate masks can be extracted with BMI2 PEXT (pattern 0x249249…) applied per 64-bit mask word — PEXT is a scalar instruction over 64-bit operands, so 128-lane masks need one application per word — or with AVX-512 mask-register operations where available. The CRT independence of axes appears as instruction-level parallelism.

[REF] Shortest-carry routing. When an update may step along any axis, choosing the axis with the shortest current saturation run — a 3-way min over already-computed TZCNT results, i.e. free — reduces expected extra carry from 0.2000 to 1/215 ≈ 0.00465 digits: a 43× reduction (closed form; simulation 0.0048 at 5×1⁰⁵ trials). This is the prime-prefix routing principle compiled to x86: traverse through the address whose prefix promises the cheapest consequence propagation.

[REF] Mersenne bound lemma. Every carry mask is a shifted Mersenne number 2^(k+L+1) − 2ᵏ. The radix laws bound the run: base-6 channel P(L ≥ 8) = 6⁻⁸ ≈ 6×10⁻⁷, P(L ≥ 16) = 6⁻¹⁶ ≈ 3.5×10⁻¹³; binary channel P(L ≥ 16) = 2⁻¹⁶ ≈ 1.5×10⁻⁵. Hence a 4-bit run-length counter is sufficient for the hot path; runs of 16+ digits belong to a slow overflow path that implementations must retain for adversarial or long-running cases — rare is not unreachable. Every hot-path carry mask fits in a half-word, and the entire hot-path carry state of a 128-digit, 3-axis address machine fits in a single cache line.

9. Provenance

The E-tree was not designed as a scene graph. It is the address skeleton of the prime number subtree of the 6-ary integer tree, where the census (companion paper) shows a one-instruction grammar with all six children live at every node past the seam. The carry law transfers here as the same radix-carry theorem with base-6 constants — binary constants in the prime channel, radix-6 in the engine address. The structure was found, not engineered — which is either a recommendation or a warning, and the benchmarks in §7 will say which.

Companion paper: The Two-Bit Law: Carry Entropy, Six Centers, and the Canonical Form of Prime Neighborhoods (Gunter 2026), which precedes this work and supplies its theorems.