extract-draw-groups-deterministic-ordering

name	extract-draw-groups-deterministic-ordering
description	extract_draw_groups uses HashMap for draw batching, making group ordering non-deterministic across frames — the GPU AABB buffer and indirect draw commands use different indices each frame, causing `back_north` to be classified as `visible` on one frame and `hzb_occluded` on another for the same camera position
source	auto-skill
extracted_at	2026-06-16T05:06:00.000Z

Deterministic Draw Group Ordering

extract_draw_groups in crates/titan-rendering-3d/src/extract.rs uses HashMap for batching primitives into draw groups:

let mut by_prim_default: HashMap<(AssetId, usize), Vec<(Entity, Mat4)>> = HashMap::new();
let mut by_prim_override: HashMap<(AssetId, usize, AssetId), Vec<(Entity, Mat4)>> = HashMap::new();

HashMap iteration order is non-deterministic in Rust (sipHash with random seed per thread). This means the order of draw groups in the returned Vec changes every run — and sometimes every frame within the same run.

Why this matters for GPU-driven culling

The scene culling pipeline builds three arrays in the same groups.iter() order:

1. AABB buffer (GPU SSBO) — per-group world-space AABBs
2. Indirect draw commands (GPU buffer) — per-group SceneIndirectCommand
3. Instance data (GPU SSBO) — per-group model matrices

All three are indexed by the draw-group order. The GPU SceneCull shader processes group i by reading AABB at index i and writing to indirect command at index i. This is self-consistent per-frame.

However, the CPU-side frustum culling also uses group indices: the visible set from cull_vs_frustum maps back to original group indices (via original_indices). The CSV readback maps group indices to entity names via the pick_table and entity_to_group mappings, which are also built from the same HashMap order.

When the order changes between frames:

• Frustum-culled groups get instance_count = 0 for different groups each frame — back_north might be culled on frame 0 but visible on frame 1
• CSV group names shift — back_north on frame 0 might be what occluder_east was on frame 1
• Depth prepass renders different geometry each frame, producing different HZB pyramids — the occlusion test results flicker

The symptom: running the culling bench twice with identical flags produces different CSV outputs. Within a single run, entries may oscillate between visible and frustum_culled for stationary camera positions.

The fix

Replace HashMap with BTreeMap for the two draw-group batching maps:

use std::collections::{BTreeMap, HashMap, HashSet};

// ...

let mut by_prim_default: BTreeMap<(AssetId, usize), Vec<(Entity, Mat4)>> = BTreeMap::new();
let mut by_prim_override: BTreeMap<(AssetId, usize, AssetId), Vec<(Entity, Mat4)>> = BTreeMap::new();

BTreeMap iteration is deterministic — sorted by key. AssetId implements Ord (it wraps a UUID), so the key (AssetId, usize) has a total ordering.

Trade-offs

• BTreeMap insert is O(log n) vs HashMap's O(1). For draw group counts (typically < 1000), the difference is negligible.
• The ordering is arbitrary (UUID comparison) but stable across runs.
• Existing code that depends on HashMap iteration order (there shouldn't be any — non-deterministic by definition) will break.

Files changed

crates/titan-rendering-3d/src/extract.rs:

• Add BTreeMap to import
• Change by_prim_default and by_prim_override types to BTreeMap