1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
# 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**.
|
