Skip to main content

qualia_extensions/webgpu_extension/
particles.rs

1//! Gravitational N-body simulation by **velocity-Verlet** (symplectic), 2D.
2//!
3//! Pairwise softened gravity `a_i = G·Σ_{j≠i} m_j (r_j−r_i)/(|r_j−r_i|²+ε²)^{3/2}`.
4//!
5//! Validation: a symplectic integrator conserves total energy
6//! `E = ½Σm|v|² − ½ΣΣ G m_i m_j /√(|r_i−r_j|²+ε²)`. The test runs a small
7//! cluster and asserts the energy drift stays well under 1%.
8
9use super::{dim, uniform, SolverReport, WebGpuJobParams};
10use std::collections::HashMap;
11use std::f64::consts::PI;
12
13struct System {
14    px: Vec<f64>,
15    py: Vec<f64>,
16    vx: Vec<f64>,
17    vy: Vec<f64>,
18    m: Vec<f64>,
19    g: f64,
20    soft2: f64,
21}
22
23impl System {
24    fn accel(&self, ax: &mut [f64], ay: &mut [f64]) {
25        let n = self.px.len();
26        for a in ax.iter_mut() {
27            *a = 0.0;
28        }
29        for a in ay.iter_mut() {
30            *a = 0.0;
31        }
32        for i in 0..n {
33            for j in (i + 1)..n {
34                let dx = self.px[j] - self.px[i];
35                let dy = self.py[j] - self.py[i];
36                let r2 = dx * dx + dy * dy + self.soft2;
37                let inv_r3 = 1.0 / (r2 * r2.sqrt());
38                let fx = self.g * dx * inv_r3;
39                let fy = self.g * dy * inv_r3;
40                ax[i] += self.m[j] * fx;
41                ay[i] += self.m[j] * fy;
42                ax[j] -= self.m[i] * fx;
43                ay[j] -= self.m[i] * fy;
44            }
45        }
46    }
47
48    fn energy(&self) -> f64 {
49        let n = self.px.len();
50        let mut ke = 0.0;
51        for i in 0..n {
52            ke += 0.5 * self.m[i] * (self.vx[i] * self.vx[i] + self.vy[i] * self.vy[i]);
53        }
54        let mut pe = 0.0;
55        for i in 0..n {
56            for j in (i + 1)..n {
57                let dx = self.px[j] - self.px[i];
58                let dy = self.py[j] - self.py[i];
59                let r = (dx * dx + dy * dy + self.soft2).sqrt();
60                pe -= self.g * self.m[i] * self.m[j] / r;
61            }
62        }
63        ke + pe
64    }
65}
66
67/// Solves.
68pub fn solve(params: &WebGpuJobParams) -> SolverReport {
69    let n = dim(params.grid_size.0, 16).max(2);
70    let g = uniform(params, "gravity", 1.0) as f64;
71    let soft = uniform(params, "softening", 0.5).max(1e-3) as f64;
72    let dt = if params.dispatch_params.time_step > 0.0 {
73        params.dispatch_params.time_step
74    } else {
75        0.001
76    };
77    let steps = if params.dispatch_params.iterations > 0 {
78        params.dispatch_params.iterations
79    } else {
80        500
81    };
82
83    // Deterministic initial condition: a ring of equal masses with a small
84    // tangential velocity (caller may override via input fields).
85    let mut sys = System {
86        px: vec![0.0; n],
87        py: vec![0.0; n],
88        vx: vec![0.0; n],
89        vy: vec![0.0; n],
90        m: vec![1.0; n],
91        g,
92        soft2: soft * soft,
93    };
94    if let (Some(pos), Some(vel)) = (
95        params.input_data.get("positions"),
96        params.input_data.get("velocities"),
97    ) {
98        for i in 0..n.min(pos.len() / 2) {
99            sys.px[i] = pos[2 * i] as f64;
100            sys.py[i] = pos[2 * i + 1] as f64;
101        }
102        for i in 0..n.min(vel.len() / 2) {
103            sys.vx[i] = vel[2 * i] as f64;
104            sys.vy[i] = vel[2 * i + 1] as f64;
105        }
106    } else {
107        let r = 1.0;
108        let vt = 0.2;
109        for i in 0..n {
110            let theta = 2.0 * PI * i as f64 / n as f64;
111            sys.px[i] = r * theta.cos();
112            sys.py[i] = r * theta.sin();
113            sys.vx[i] = -vt * theta.sin();
114            sys.vy[i] = vt * theta.cos();
115        }
116    }
117
118    let e0 = sys.energy();
119
120    let mut ax = vec![0.0f64; n];
121    let mut ay = vec![0.0f64; n];
122    let mut ax_new = vec![0.0f64; n];
123    let mut ay_new = vec![0.0f64; n];
124    sys.accel(&mut ax, &mut ay);
125
126    for _ in 0..steps {
127        // r += v·Δt + ½a·Δt²
128        for i in 0..n {
129            sys.px[i] += sys.vx[i] * dt + 0.5 * ax[i] * dt * dt;
130            sys.py[i] += sys.vy[i] * dt + 0.5 * ay[i] * dt * dt;
131        }
132        sys.accel(&mut ax_new, &mut ay_new);
133        // v += ½(a_old + a_new)·Δt
134        for i in 0..n {
135            sys.vx[i] += 0.5 * (ax[i] + ax_new[i]) * dt;
136            sys.vy[i] += 0.5 * (ay[i] + ay_new[i]) * dt;
137        }
138        std::mem::swap(&mut ax, &mut ax_new);
139        std::mem::swap(&mut ay, &mut ay_new);
140    }
141
142    let e1 = sys.energy();
143    let residual = if e0.abs() > 0.0 {
144        ((e1 - e0) / e0).abs() as f32
145    } else {
146        (e1 - e0).abs() as f32
147    };
148
149    let mut positions_out = Vec::with_capacity(n * 2);
150    let mut velocities_out = Vec::with_capacity(n * 2);
151    for i in 0..n {
152        positions_out.push(sys.px[i] as f32);
153        positions_out.push(sys.py[i] as f32);
154        velocities_out.push(sys.vx[i] as f32);
155        velocities_out.push(sys.vy[i] as f32);
156    }
157    let mut output = HashMap::new();
158    output.insert("positions_out".to_string(), positions_out);
159    output.insert("velocities_out".to_string(), velocities_out);
160
161    let threshold = params.dispatch_params.convergence_threshold.max(0.01);
162    let flops = steps as u64 * (n as u64) * (n as u64) * 15;
163    SolverReport {
164        output,
165        iterations_used: steps,
166        final_residual: residual,
167        converged: residual <= threshold,
168        flops,
169    }
170}
171
172#[cfg(test)]
173mod tests {
174    use super::*;
175    use crate::webgpu_extension::DispatchParams;
176
177    #[test]
178    fn symplectic_integrator_conserves_energy() {
179        let p = WebGpuJobParams {
180            shader_name: "nbody_verlet".to_string(),
181            grid_size: (16, 1, 1),
182            input_data: HashMap::new(),
183            uniform_data: HashMap::new(),
184            dispatch_params: DispatchParams {
185                iterations: 1000,
186                time_step: 0.002,
187                convergence_threshold: 0.01,
188                max_execution_time_ms: 30_000,
189            },
190        };
191        let r = solve(&p);
192        assert!(
193            r.final_residual < 0.01,
194            "energy drift too large: {}",
195            r.final_residual
196        );
197        assert!(r.converged);
198    }
199
200    #[test]
201    fn two_body_orbit_stays_bounded() {
202        // Two equal masses given a circular-ish velocity should stay near their
203        // initial separation (no runaway), with conserved energy.
204        let mut pos = HashMap::new();
205        pos.insert("positions".to_string(), vec![-1.0f32, 0.0, 1.0, 0.0]);
206        pos.insert("velocities".to_string(), vec![0.0f32, -0.3, 0.0, 0.3]);
207        let p = WebGpuJobParams {
208            shader_name: "nbody_verlet".to_string(),
209            grid_size: (2, 1, 1),
210            input_data: pos,
211            uniform_data: HashMap::new(),
212            dispatch_params: DispatchParams {
213                iterations: 2000,
214                time_step: 0.001,
215                convergence_threshold: 0.02,
216                max_execution_time_ms: 30_000,
217            },
218        };
219        let r = solve(&p);
220        assert!(
221            r.final_residual < 0.02,
222            "orbit energy drift {}",
223            r.final_residual
224        );
225        let pos = &r.output["positions_out"];
226        let sep = (((pos[0] - pos[2]).powi(2) + (pos[1] - pos[3]).powi(2)) as f64).sqrt();
227        assert!(sep > 0.2 && sep < 5.0, "orbit separation ran away: {sep}");
228    }
229}