From 0d29f340b9de8f6a14baa0a2c6f3c57b8d1458a5 Mon Sep 17 00:00:00 2001 From: skal Date: Wed, 4 Feb 2026 11:32:20 +0100 Subject: docs(3d): Plan BVH, Physics, and WGSL modularization (Task #49, #50) - Added detailed design for dynamic BVH and GPU traversal in 3D.md. - Outlined SDF-based collision detection and semi-implicit Euler physics loop. - Updated TODO.md with atomic tasks for physics implementation and granular WGSL refactoring. --- TODO.md | 73 ++++++++++++++++++--------------- doc/3D.md | 136 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 177 insertions(+), 32 deletions(-) diff --git a/TODO.md b/TODO.md index a9f5fa4..6a02db7 100644 --- a/TODO.md +++ b/TODO.md @@ -24,44 +24,53 @@ This file tracks prioritized tasks with detailed attack plans. - [x] **Enhanced Procedural Noise:** Implemented a multi-octave Value Noise generator for higher-quality skybox textures. - [x] **Scene Integrity:** Restored proper object indexing and removed redundant geometry, ensuring the floor grid and objects render correctly. -## Recently Completed (February 3, 2026) -- [x] **Task #20: Platform & Code Hygiene**: - - [x] **Header Consolidation:** Moved all `#ifdef` logic for WebGPU headers and platform-specific shims into `src/platform.h`. - - [x] **Refactor platform_init:** Changed `void platform_init(PlatformState* state, ...)` to `PlatformState platform_init(...)` for cleaner value-based initialization. - - [x] **Unified Poll:** Incorporated `time` and `aspect_ratio` updates into `platform_poll()`, abstracting away direct GLFW calls from main loop. - - [x] **Standard Container Removal (AssetManager):** Replaced `std::map`, `std::string`, and `std::vector` in `AssetManager` and `procedural` generators with C-style alternatives (static arrays, raw pointers, malloc/free). - -- [x] **Music System Bug Fixes & Rock Track Implementation**: - - [x] **Fixed Critical Pool Exhaustion Bug**: Tracker pool slots were never freed, causing music to stop after 8 patterns. Implemented round-robin slot allocation with proper cleanup. - - [x] **Fixed Note Name Parsing**: Added automatic note-name-to-frequency conversion (E2→82.4Hz, A4→440Hz, etc.) in `tracker_compiler.cc`. Bass and melody now play correctly. - - [x] **Fixed Timing Mismatch**: Patterns are 4 beats (2 seconds at 120 BPM), but SCORE was triggering every 4 seconds. Updated to trigger every 2 seconds for continuous playback. - - [x] **Implemented Dynamic Resource Sizing**: `tracker_compiler` now analyzes scores to determine optimal MAX_VOICES/MAX_SPECTROGRAMS values (max simultaneous patterns: 5, recommended: 10 each). - - [x] **Created Rock Demo Track**: 11 patterns (drums, bass, melody, power chords) with 49 triggers over 25 seconds, using 14 drum samples + 10 procedural notes. - - **Known Issues**: - - Audio playback quality could be improved (some artifacts/cuts remain) - - Note synthesis parameters (duration, harmonics) use default values - need tuning for better sound - - Pattern overlaps might cause voice exhaustion under heavy load - - No dynamic volume/envelope control for melodic notes - -## Recently Completed (Previous) -- [x] **Task #26: Shader Asset Testing & Validation**: - - [x] **Attack Plan - `ShaderComposer` Unit Tests**: Add tests to `test_shader_composer.cc` to verify correct snippet registration, retrieval, and composition for various WGSL shader assets. - - [x] **Attack Plan - Asset Content Validation**: Implement checks (e.g., in `test_assets.cc`) to ensure loaded WGSL shader assets are non-empty and contain expected entry points (`vs_main`, `fs_main`, `main` for compute shaders). - - [x] **Attack Plan - Runtime Shader Validation**: Integrate basic validation steps into the rendering pipeline (e.g., in `gpu.cc`) to log warnings or errors if compiled shader modules are invalid, providing earlier feedback than WebGPU validation errors. -- [x] **Asset Pipeline Improvement**: Automated audio asset conversion with a new `gen_spectrograms.sh` script and added 13 new samples to the asset list. -- [x] **Build System Consolidation (Task #25)**: Modularized the build into subsystem libraries and implemented helper macros to simplify CMake maintenance. -- [x] **Asset System Robustness**: Fixed static initialization order issues by wrapping the asset table in a singleton-style getter (`GetAssetRecordTable()`). -- [x] **Shader Asset Integration (Task #24)**: Extracted hardcoded shaders to `.wgsl` assets, updated `asset_packer` for string safety, and refactored C++ code to use `GetAsset`. -- [x] **WebGPU Stability & macOS Fixes**: Resolved surface creation failures by adding `GLFW_EXPOSE_NATIVE_COCOA` and fixed validation errors in surface configuration and render pass attachments. - ## Priority 1: 3D System Enhancements (Task #18) **Goal:** Establish a pipeline for importing complex 3D scenes to replace hardcoded geometry. - [ ] **Task #36: Blender Exporter:** Create a Python script (`tools/blender_export.py`) to export meshes/cameras/lights to a binary asset format. - [ ] **Task #37: Asset Ingestion:** Update `asset_packer` to handle the new 3D binary format. - [ ] **Task #38: Runtime Loader:** Implement a minimal C++ parser to load the scene data into the ECS/Renderer. -## Priority 2: Developer Tooling & CI +## Priority 2: WGSL Modularization (Task #50) +**Goal**: Refactor `ShaderComposer` and WGSL assets to support granular, reusable snippets and `#include` directives. + +- [ ] **Task #50.1: Recursive Composition Support**: + - [ ] Update `ShaderComposer::Compose` to parse `#include "snippet_name"` directives in shader code. + - [ ] Implement recursive resolution (with cycle detection) to assemble the final shader. + - [ ] Update `test_shader_composer.cc` to verify recursive includes. + +- [ ] **Task #50.2: Granular SDF Library**: + - [ ] Extract `sdSphere`, `sdBox`, `sdTorus`, `sdPlane` from `sdf_primitives.wgsl` into `math/sdf_shapes.wgsl`. + - [ ] Extract `get_normal_basic` into `math/sdf_utils.wgsl`. + - [ ] Extract `calc_shadow` into `render/shadows.wgsl`. + +- [ ] **Task #50.3: Scene & Material Refactor**: + - [ ] Extract `map_scene` and `get_dist` logic into `render/scene_query.wgsl`. + - [ ] Extract lighting and material logic from `fs_main` into `render/lighting_pbr.wgsl` (or similar). + +- [ ] **Task #50.4: Pipeline Update**: + - [ ] Update `Renderer3D` to use the new granular assets via `#include` in the main shader, reducing C++-side dependency lists. + +## Priority 3: Physics & Collision (Task #49) +**Goal**: Implement a lightweight physics engine using SDFs and BVH acceleration. (See `doc/3D.md` for design). + +- [ ] **Task #49.1: CPU-Side SDF Library**: + - [ ] Create `src/3d/sdf_cpu.h` implementing `sdSphere`, `sdBox`, `sdTorus`, `sdPlane` using `mini_math.h`. + - [ ] Implement `calc_normal` (numerical gradient) for these SDFs. + - [ ] Add unit tests in `src/tests/test_physics.cc` to verify CPU SDFs match ground truth. + +- [ ] **Task #49.2: BVH Construction**: + - [ ] Define `BVHNode` struct in `src/3d/bvh.h` (shared/compatible with GPU layout). + - [ ] Implement `BVHBuilder::Build(const std::vector&)` in `src/3d/bvh.cc`. + - [ ] Implement `BVH::Query(AABB)` for broad-phase collision detection. + - [ ] Visualize BVH in `src/tests/test_3d_render.cc` (using `VisualDebug`). + +- [ ] **Task #49.3: Physics Loop**: + - [ ] Create `PhysicsSystem` class in `src/3d/physics.h`. + - [ ] Implement `Update(dt)`: Integration -> Broad Phase -> Narrow Phase (SDF Probe) -> Resolution. + - [ ] Add `velocity`, `mass`, `restitution` fields to `Object3D`. + - [ ] Integrate into `test_3d_render.cc` main loop. + +## Priority 4: Developer Tooling & CI **Goal**: Improve developer workflows, code quality, and release processes. *(No active tasks)* diff --git a/doc/3D.md b/doc/3D.md index 5c5d1bd..12c7b15 100644 --- a/doc/3D.md +++ b/doc/3D.md @@ -38,6 +38,142 @@ removed with STRIP_ALL) that: This must be captured and tracked as **Task #39: Visual Debugging System**. +## Global Acceleration Structure (BVH) + +To support efficient global queries (e.g., for soft shadows via raymarching, or physics), we will implement a dynamic Bounding Volume Hierarchy (BVH). + +### Data Structures + +**CPU/GPU Common Node Layout:** +The node structure is designed to be 32-byte aligned for efficient GPU access. + +```cpp +struct BVHNode { + // 16 bytes + float min_x, min_y, min_z; + int32_t left_idx; // If < 0, this is a leaf node. + + // 16 bytes + float max_x, max_y, max_z; + int32_t right_idx; // If leaf, this holds the object_index. +}; +``` + +**WGSL Representation:** +```wgsl +struct BVHNode { + min: vec3, + left_idx: i32, + max: vec3, + obj_idx_or_right: i32, +}; +@group(0) @binding(2) var bvh_nodes: array; +``` + +### Construction (CPU) + +Since the scene is small (< 100 objects) and dynamic, we will **rebuild** the BVH from scratch every frame. This avoids the complexity of refitting and balancing. + +**Algorithm: Recursive Midpoint Split** +1. **Calculate Centroids**: Compute the center of the AABB for all active objects. +2. **Split**: + * Find the axis with the largest variance in centroid positions. + * Sort objects along that axis (or just partition based on the median). + * Create a node, assign `left` and `right` children recursively. + * Stop when a node has 1 object (Leaf). +3. **Linearize**: Flatten the tree into a `std::vector` for GPU upload. + +### Traversal (GPU/WGSL) + +Since WGSL does not support recursion, we use a fixed-size stack. + +```wgsl +fn map_scene(pos: vec3) -> f32 { + var min_dist = 10000.0; + var stack: array; + var stack_ptr = 0; + + // Push root + stack[stack_ptr] = 0; + stack_ptr++; + + while (stack_ptr > 0) { + stack_ptr--; + let node_idx = stack[stack_ptr]; + let node = bvh_nodes[node_idx]; + + // Check AABB intersection + if (aabb_sdf(pos, node.min, node.max) < min_dist) { + if (node.left_idx < 0) { + // Leaf: Evaluate Object SDF + let obj_idx = node.obj_idx_or_right; + let d = object_sdf(pos, obj_idx); + min_dist = min(min_dist, d); + } else { + // Internal: Push children + // Optimization: Push furthest child first so we pop closest first + stack[stack_ptr] = node.left_idx; + stack_ptr++; + stack[stack_ptr] = node.obj_idx_or_right; + stack_ptr++; + } + } + } + return min_dist; +} +``` + +## Physics & Collision System + +We need a lightweight physics engine that leverages our SDF representation. + +### Components +We will extend `Object3D` or add a `PhysicsBody` struct: +* **Mass/InverseMass**: For dynamic response. +* **Velocity**: Linear velocity `vec3`. +* **Restitution**: Bounciness (0.0 - 1.0). +* **Friction**: Damping factor. + +### Broad Phase: BVH Re-use +We reuse the same BVH constructed for rendering to accelerate CPU-side collision detection. +* **Query**: `QueryBVH(AABB query_box)` returns a list of potential candidates. +* This avoids $O(N^2)$ checks. + +### Narrow Phase: SDF-Based Collision +Since we don't have explicit meshes for collision, we use the analytical SDFs. + +**Algorithm: Proxy Point Probing** +Instead of full SDF-on-SDF intersection (which is expensive), we approximate dynamic objects as a set of "Probe Points" (e.g., bounding box corners, center). + +1. **Transform**: For a dynamic object $A$ and candidate neighbor $B$: + * Transform $A$'s probe points into $B$'s local space: $P_{local} = InverseModel_B * P_{world}$. +2. **Evaluate**: Calculate $d = SDF_B(P_{local})$. +3. **Collision**: If $d < 0$: + * **Penetration Depth**: $p = -d$. + * **Normal**: Compute gradient $N = \nabla SDF_B(P_{local})$ via central differences. Transform $N$ back to world space. + * **Contact Point**: $P_{contact} = P_{world} - N * p$. + +### Solver Loop (Semi-Implicit Euler) +1. **Integrate Velocity**: `vel += gravity * dt`. +2. **Broad Phase**: Find pairs using BVH. +3. **Narrow Phase & Resolution**: + * If collision detected (depth $p > 0$): + * **Positional Correction**: Move object by $N * p$ (to resolve penetration). + * **Velocity Response**: `vel = vel - (1 + restitution) * dot(vel, N) * N`. + * **Friction**: Apply tangential damping. +4. **Integrate Position**: `pos += vel * dt`. + +### Code Integration Plan + +1. **CPU-Side SDF Library**: + * Create `src/3d/sdf_cpu.h` implementing the same primitives (`sdSphere`, `sdBox`, `sdTorus`) as the WGSL shaders, using `src/util/mini_math.h`. +2. **Physics System Class**: + * Create `src/3d/physics.h/cc`. + * `PhysicsSystem::Update(Scene& scene, float dt)`. + * `PhysicsSystem::ResolveCollision(Object3D& a, Object3D& b)`. +3. **Main Loop Integration**: + * Call `PhysicsSystem::Update` before `Renderer3D::render`. + ## future step Have an exporter from Blender modelling software. That would be a converter -- cgit v1.2.3