diff options
Diffstat (limited to 'doc/3D.md')
| -rw-r--r-- | doc/3D.md | 223 |
1 files changed, 72 insertions, 151 deletions
@@ -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 - -The assist the visual debugging, we need a 'visual_debug' mode (code to be -removed with STRIP_ALL) that: +## Object Representation - 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<f32>, - left_idx: i32, - max: vec3<f32>, - obj_idx_or_right: i32, + min: vec3<f32>, left_idx: i32, + max: vec3<f32>, obj_idx_or_right: i32, }; @group(0) @binding(2) var<storage, read> bvh_nodes: array<BVHNode>; ``` ### 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<BVHNode>` 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>) -> f32 { var min_dist = 10000.0; var stack: array<i32, 32>; - 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. +Extend `Object3D` with: +- Mass/InverseMass +- Velocity (linear) +- Restitution (bounciness) +- Friction -### Narrow Phase: SDF-Based Collision -Since we don't have explicit meshes for collision, we use the analytical SDFs. +### Broad Phase +Reuse BVH for O(N log N) collision detection. -**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). +### 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` -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. +### 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`. +- Quaternion-based orientation +- Angular velocity `vec3` +- Integration: `q = q + 0.5 * dt * [0, w] * q` +- Collision impulses affect both linear and angular momentum -## future step +## Integration Plan -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**. +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` -## latter improvement +## Future Tasks -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 +- **Task #36**: Blender exporter (convert scenes to binary format) +- **Task #40**: Advanced lighting & transparency (multi-ray-casting) +- **Task #39**: Visual debugging system (wireframes, trajectories) |