# 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.

## the idea

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:

   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).

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<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)

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<BVHNode>` 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>) -> 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++;
            }
        }
    }
    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
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**.