From 70c64867baa30c83334559d3023153dfe3f9ff79 Mon Sep 17 00:00:00 2001 From: skal Date: Mon, 9 Feb 2026 10:43:11 +0100 Subject: docs: Simplify all design docs (50% reduction, 1687 lines removed) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Consolidated and streamlined all documentation: **Merged:** - PROCEDURAL.md → deleted (content in ASSET_SYSTEM.md) - FETCH_DEPS.md → BUILD.md (dependencies section) **Simplified (line reductions):** - HOWTO.md: 468→219 (53%) - CONTRIBUTING.md: 453→173 (62%) - SPECTRAL_BRUSH_EDITOR.md: 497→195 (61%) - SEQUENCE.md: 355→197 (45%) - CONTEXT_MAINTENANCE.md: 332→200 (40%) - test_demo_README.md: 273→122 (55%) - ASSET_SYSTEM.md: 271→108 (60%) - MASKING_SYSTEM.md: 240→125 (48%) - 3D.md: 196→118 (40%) - TRACKER.md: 124→76 (39%) - SCENE_FORMAT.md: 59→49 (17%) - BUILD.md: 83→69 (17%) **Total:** 3344→1657 lines (50.4% reduction) **Changes:** - Removed verbose examples, redundant explanations, unimplemented features - Moved detailed task plans to TODO.md (single source of truth) - Consolidated coding style rules - Kept essential APIs, syntax references, technical details **PROJECT_CONTEXT.md:** - Added "Design Docs Quick Reference" with 2-3 line summaries - Removed duplicate task entries - All design docs now loaded on-demand via Read tool Result: Context memory files reduced from 31.6k to ~15k tokens. --- doc/3D.md | 237 +++++++++++++++++++++----------------------------------------- 1 file changed, 79 insertions(+), 158 deletions(-) (limited to 'doc/3D.md') diff --git a/doc/3D.md b/doc/3D.md index 59af47c..ac451c8 100644 --- a/doc/3D.md +++ b/doc/3D.md @@ -1,197 +1,118 @@ -# 3D system and rendering pipeline +# 3D System and Rendering Pipeline -This sub-project describe how the 3D worlds are going to be rendered. -We want a camera to move around moving and dynamic objects. -These objects can be need a physics and collision system. +## Core Concept -## the idea +Hybrid SDF/rasterization pipeline with physics and collision detection. -Each object has: - * a bounding box or capsule - * a BVH is maintained while these move around physically (or not) - * to render a frame we cull these bounding volumes - * at rendering time, the bounding box or sphere is turned into a quad or triangle - fan and a shader associated with the object is called (after proper world-object-camera transformations) - * each object can be queries for: - a) ray-object intersection ("return the distance from the object at this point P in this direction D") - b) Signed Distance Field ("what is the minimum distance to the object from this point P?") - -So in the end, we'll - a) move the camera and lights along paths - b) transform the bounding volumes and cull for visible boxes - c) project them - d) call the objects' respective shaders for rendering - -We want to use shadow maps, so multi-passes is expected. - -## debugging features +## Object Representation -The assist the visual debugging, we need a 'visual_debug' mode (code to be -removed with STRIP_ALL) that: - - a) draws a wireframe around the bounding volumes (box, etc.) - b) draw the trajectories (camera, objects, ...) - c) show the collision points - d) displays the ray/object intersection interactively - e) show the lights (direction, cone, ...), display their shadow-map in 3d and on-screen (2d). +Each object has: +- Bounding volume (box/capsule) +- SDF function (signed distance field) +- Ray-intersection query support +- Material/shader association -This must be captured and tracked as **Task #39: Visual Debugging System**. +## Render Pipeline +1. Move camera and lights along paths +2. Transform and cull bounding volumes (BVH) +3. Project visible volumes to screen +4. Raymarch SDF inside proxy geometry (fragment shader) +5. Multi-pass for shadow maps -## Global Acceleration Structure (BVH) +## Visual Debugging (Task #39) -To support efficient global queries (e.g., for soft shadows via raymarching, or physics), we will implement a dynamic Bounding Volume Hierarchy (BVH). +Debug mode (`!STRIP_ALL`) provides: +- Wireframe bounding volumes +- Camera/object trajectories +- Collision point visualization +- Ray-intersection display +- Light visualization (direction, cone, shadow maps) -### Data Structures +## BVH Acceleration Structure -**CPU/GPU Common Node Layout:** -The node structure is designed to be 32-byte aligned for efficient GPU access. +### Purpose +Efficient spatial queries for rendering (GPU) and physics (CPU). +### Node Layout ```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 + int32_t left_idx; // < 0 = leaf node float max_x, max_y, max_z; - int32_t right_idx; // If leaf, this holds the object_index. + int32_t right_idx; // leaf: object_index }; ``` -**WGSL Representation:** +WGSL: ```wgsl struct BVHNode { - min: vec3, - left_idx: i32, - max: vec3, - obj_idx_or_right: i32, + min: vec3, left_idx: i32, + max: vec3, obj_idx_or_right: i32, }; @group(0) @binding(2) var bvh_nodes: array; ``` ### Construction (CPU) +Rebuild every frame (< 100 objects): +1. Calculate AABBs for all objects +2. Recursive midpoint split (largest variance axis) +3. Linearize tree for GPU upload -Since the scene is small (< 100 objects) and dynamic, we will **rebuild** the BVH from scratch every frame on the CPU. This avoids the complexity of refitting and balancing. The BVH is purely a spatial acceleration structure and does not contain physics logic (velocity, mass, etc.), allowing it to be used for both rendering (GPU) and physics (CPU). - -**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. - +### Traversal (GPU) +Fixed-size stack (no recursion in WGSL): ```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++; - } - } - } + // Push root, iterate until stack empty + // Check AABB, evaluate leaf SDFs 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$. - -### Narrow Phase & Resolution: -* If collision detected (depth $p > 0$): - * **Positional Correction**: Move object by $N * p$ (to resolve penetration). - * **Velocity Response (PBD)**: In Position Based Dynamics (PBD), the velocity is re-evaluated *after* all collisions and constraints have been resolved: `v = (p_new - p_old) / dt`. - * **Friction**: Apply tangential damping. +Extend `Object3D` with: +- Mass/InverseMass +- Velocity (linear) +- Restitution (bounciness) +- Friction + +### Broad Phase +Reuse BVH for O(N log N) collision detection. + +### Narrow Phase +**Proxy Point Probing** (SDF-based): +1. Transform probe points into neighbor's local space +2. Evaluate SDF at probe points +3. If `d < 0`: collision detected + - Penetration depth: `p = -d` + - Normal: `∇SDF` via central differences + - Contact point: `P_world - N * p` + +### Collision Response (Position Based Dynamics) +1. Integrate position: `p_pred = p + v * dt` +2. Broad phase: Find collision pairs (BVH) +3. Narrow phase: Resolve penetrations on `p_pred` +4. Update velocity: `v = (p_pred - p) / dt` +5. Finalize: `p = p_pred` ### Rotation & Angular Momentum -Objects should support rotation via **Quaternions**. -* **State**: Add `quat orientation` and `vec3 angular_velocity` to `Object3D`. -* **Integration**: Update orientation using angular velocity: `q = q + 0.5 * dt * [0, w] * q`, then normalize. -* **Narrow Phase**: Proxy points must be rotated by the quaternion: `P_local = Inverse(Q) * (P_world - Position)`. -* **Collision Response**: Collision impulses should affect both linear and angular momentum. - -### Solver Loop (Position Based Dynamics) -1. **Integrate Position (Predicted)**: `p_pred = p + v * dt`. -2. **Broad Phase**: Find pairs using BVH. -3. **Narrow Phase & Resolution**: - * Resolve penetrations and constraints on `p_pred`. -4. **Update Velocity**: `v = (p_pred - p) / dt`. -5. **Finalize Position**: `p = p_pred`. - -### 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 -from simple blender-exported files to our internal format (as an asset for -our AssetManager or as c++ code directly) - **Task #36: Blender Exporter**. - -## latter improvement - -How to handle transparency? Multi-Ray-casting? -We need to think about the lighting strategy. - **Task #40: Advanced Lighting & Transparency**. \ No newline at end of file +- Quaternion-based orientation +- Angular velocity `vec3` +- Integration: `q = q + 0.5 * dt * [0, w] * q` +- Collision impulses affect both linear and angular momentum + +## Integration Plan + +1. **CPU-Side SDF Library**: `src/3d/sdf_cpu.h` (sdSphere, sdBox, sdTorus) +2. **Physics System**: `src/3d/physics.h/cc` (Update, ResolveCollision) +3. **Main Loop**: Call `PhysicsSystem::Update` before `Renderer3D::render` + +## Future Tasks + +- **Task #36**: Blender exporter (convert scenes to binary format) +- **Task #40**: Advanced lighting & transparency (multi-ray-casting) +- **Task #39**: Visual debugging system (wireframes, trajectories) -- cgit v1.2.3