# N-Body 模擬研究規劃：極端天文現象與效能優化
## 1. 研究動機與目標
本研究旨在探討 Barnes-Hut 演算法 在處理「極端密度梯度」與「高動態範圍」天文場景時的效能瓶頸，並透過現代硬體技術（如 SIMD、線性化樹結構）提出優化方案。
## 2. 實驗場景設計 (Experimental Scenarios)
為了驗證優化演算法的有效性，本研究將實驗分為 「基準對照組 (Baseline)」 與 「壓力測試組 (Stress Test)」。
### A. 基準對照組 (Baseline Scenarios
用於驗證演算法的正確性與基礎效能。
| 天文現象 | 物理特性 | 實驗目的 |
| :------------------------- | :----------------- | :----------------- |
| **普隆默模型 (Plummer Model)** | 標準球對稱星團分佈，學術界通用基準。 | 驗證物理正確性與基礎運算效率。 |
| **穩態螺旋星系 (Stable Spiral)** | 密度變化平緩，處於動力學平衡狀態。 | 證明優化方案在常規場景下無額外開銷。 |
| **均勻球體塌縮 (Cold Collapse)** | 從完全均勻到中心聚集的演變過程。 | 觀察效能隨密度逐漸增加的變化曲線。 |
用於展示傳統演算法的瓶頸與優化方案的突破點。

### B. 壓力測試組 (Stress Test Scenarios)
| 特殊天文景觀 | 效能挑戰 (Bottlenecks) | 預期優化方向 |
| :----------------------- | :----------------- | :-------------------------------- |
| **潮汐瓦解事件 (TDE)** | 黑洞撕碎恆星，產生極端密度梯度。 | **動態時步 (Adaptive Time-stepping)** |
| **星系碰撞 (Galaxy Merger)** | 多重力中心，產生長距離潮汐尾。 | **動態負載平衡 (Load Balancing)** |
| **球狀星團核心塌縮** | 核心密度極高，粒子頻繁近距離交互。 | **SIMD 簇化暴力計算 (Clustering)** |
| **原行星盤螺旋臂** | 高速旋轉系統，空間劃分與運動不契合。 | **Morton Code 增量更新優化** |

## 3. 技術分析與問題定義 (Problem Statement)
透過上述場景的對比，本研究將針對以下技術痛點進行深入探討：
1. 樹深度爆炸 (Tree Depth Explosion)：在高密度區（如黑洞周邊），Octree 深度劇增導致遍歷開銷過大。
2. 記憶體存取不連續：傳統指標型樹結構在處理百萬級粒子時，頻繁的 Cache Miss 限制了效能。
3. 分支預測失敗 (Branch Misprediction)：複雜的樹遍歷邏輯難以發揮現代 CPU 的 SIMD 向量化威力。
## 4. 預期貢獻
1. 實作一套基於 線性化 Quadtree/Octree 的高效能 N-Body 框架。
2. 提出針對極端分佈場景的 混合式計算核心 (Hybrid Kernel)。
3. 在保持物理準確度的前提下，於特定壓力測試場景中提升 20% - 50% 的運算效能。

# 1/28 - 2/2
## A.Barnes-hut algorithm 原理
## https://jheer.github.io/barnes-hut/
## https://observablehq.com/@jheer/the-barnes-hut-approximation
---

### 一、 核心哲學：遠略近詳 (The Core Philosophy)

Barnes-Hut 演算法之所以偉大，是因為它承認了人類（和電腦）的運算極限。

* **傳統做法 ($O(N^2)$)**：如果要算 個天體的受力，每一顆都要跟其他每一顆算一遍。當 ，就要算一億次，電腦會燒掉。
* **Barnes-Hut 做法 ($O(N \log N)$)**：它利用「空間層次」來偷懶。想像你在看遠方的星系，你不需要知道裡面每一顆恆星的位置，你只需要知道那個星系的「中心位置」和「總質量」，就能算出它對你的引力。

---

### 二、 三大運作步驟 (The Three Steps)

#### 1. 構建四元樹/八元樹 (Construct the Tree)

這是將混亂的點轉化為有序結構的過程。

* **操作**：從一個包含所有點的大正方形（根節點）開始。
* **分裂規則**：每當一個格子（Cell）裡面的點超過 1 個，就將這個格子平分成 4 個小格子（3D 則是 8 個）。
* **遞迴**：這個過程會不斷重複，直到每個點都住在自己獨立的小格子裡。
* **論文補充**：你讀的論文提到，為了效能，不一定要分到「每格只有 1 點」，分到「每格 1000 點」有時在現代 CPU 上跑得更快。

#### 2. 計算質心與總質量 (Calculate Centers of Mass)

樹建好後，我們需要給每個「行政區」建立摘要。

* **由下而上 (Bottom-up)**：我們先看最底層的小格子，算出它們的質量中心。
* **數據聚合**：父節點（大格子）會直接吸收 4 個子節點（小格子）的數據。父節點的質量 = 四個子節點質量之和；父節點的質心 = 四個子節點質心的加權平均。
* **結果**：完成後，樹上的每一個節點（不論大小）都代表了該區域的一個「虛擬大天體」。

#### 3. 估算受力 (Estimate Forces & The Probe)

這是演算法真正開始跑計算的地方。當我們要算某個點（或是網站提到的探針 Probe）受到的合力時：

* **遞迴檢查**：從樹根開始。
* **接受準則 (Acceptance Criterion)**：計算兩個數值：
* **$s$**：目前格子的寬度。
* **$d$**：探針到該格子質心的距離。

* **判斷條件**：如果 $\frac{s}{d} < \theta$ (Theta)：
* **Yes (夠遠)**：我們「接受」這個近似值。直接用這個格子的「質心」算一次力，然後**停止往下看**。這一下就省掉了格子裡可能成千上萬個點的運算。
* **No (太近)**：這個格子太大了或是離我太近，不準。我們必須打開這個格子，去檢查它的四個子節點，重複上述判斷。

---

### 三、 關鍵參數：Theta ($\theta$) 的生死符

網站讓你調整 Theta，這是因為它控制了**「速度」與「精度」的拔河**：

1. **當 $\theta = 0$**：
* 條件 永遠不成立。
* 演算法被迫走訪樹的每一個葉節點，等於是強迫電腦進行暴力計算。
* **結果**：最精準，但最慢。

2. **當 $\theta = 1$ (或更高)**：
* 只要距離 大於格子寬度 ，就直接用近似值。
* **結果**：極快，但引力方向和大小會有很多誤差（鋸齒感很重）。

3. **理想狀態 ($\theta \approx 0.5$)**：
* 這是科學家常用的平衡點，計算量大幅下降，且物理誤差在可接受範圍內。

## B.Fast Octree Neighborhood Search for SPH Simulations


### **第一頁：Grid — 數據預處理與初步分類 (Data Pre-processing)**

* **主題標題：** Stage 1: Uniform Background Grid & Morton Coding
* **核心目的：** 透過網格化減少後續建樹的複雜度，並優化記憶體佈局。
* **關鍵重點：**
* **網格化分類 (Classification)：** 將所有活動粒子分配到大小為 的均勻背景網格中（$d$ 建議為 $1.5 \times$ 支援半徑 $h$）。
* **大幅減量：** 透過將粒子分組，使八元樹處理的物件數量減少至約 $1/30$，顯著提升建樹效率。
* **空間排序 (Morton Order)：** 應用 **Morton Code (Z-order)** 對單元進行排序，確保空間鄰近的粒子在記憶體中也是連續的。
* **快取優化：** 這種「聚集」機制能極大化 CPU 快取命中率，減少非連續記憶體存取的開銷。

---

### **第二頁：Octree — 自適應空間劃分 (Adaptive Spatial Partitioning)**

* **主題標題：** Stage 2: Adaptive Octree Construction
* **核心目的：** 將全域搜尋問題分解為獨立、負載平衡的子問題。
* **關鍵重點：**
* **自上而下建構 (Top-down Construction)：** 從包含所有非空單元的根節點開始，遞迴地拆分空間。
* **拆分準則 (Splitting Criterion)：** 當節點內的粒子數超過預設上限（Cap），且節點尺寸大於單元大小時，才進行拆分。
* **葉節點聚類：** 每個葉節點管理兩類單元：
* **內部單元 (Inner Cells)：** 幾何中心位於節點內的單元。
* **外部單元 (Outer Cells)：** 位於節點外但可能包含鄰居粒子的影響範圍內。

* **並行化潛力：** 每個葉節點的任務是獨立的，非常適合多執行緒並行處理。

---

### **第三頁：Brute Force — 核心運算與過濾 (SIMD-Optimized Calculation)**

* **主題標題：** Stage 3: Brute Force Stage & Gather-Filter
* **核心目的：** 執行最終的距離比對與鄰居列表生成。
* **關鍵重點：**
* **收集與緩衝 (Gathering)：** 在計算前將非連續存儲的粒子座標收集到連續的緩衝區中，準備進行向量化運算。
* **SIMD 向量化優化：** 利用現代處理器的 SIMD 指令集同時處理多個粒子對，將暴力比對的效能推至極限。
* **無分支實作 (Branchless Implementation)：** 使用位掩碼 (Bitmask) 取代傳統的 `if` 判斷，避免分支預測失敗帶來的效能損失。
* **最終過濾：** 計算 $r^2 \leq h^2$，精確篩選出支援半徑內的鄰居，並寫入鄰居列表。

---

這三頁構成了一個**「由粗到細」**的過程：

1. **Grid** 是為了把粒子「打包」。
2. **Octree** 是為了把空間「裁切」。
3. **Brute Force** 是為了把鄰居「找出來」。

--------------------------------------------------------

## C.Finding Neighbors in a Forest: A b-tree for Smoothed Particle Hydrodynamics Simulations
# https://arxiv.org/abs/1910.02639
這篇論文 **"Finding Neighbors in a Forest: A b-tree for Smoothed Particle Hydrodynamics Simulations"** (arXiv:1910.02639) 提出了一種新型的樹狀結構 —— **b-tree**，專門用來加速 SPH 模擬中的鄰域搜尋（Neighbor Search）。

請注意，這篇論文提到的「b-tree」並非資料庫中常見的 B-Tree，而是一種具有 **「自適應分支因子（Adaptive Branching Factor）」** 的樹。以下是各段落的重點整理：

---

### 1. 摘要 (Abstract)

* **核心挑戰**：在 SPH 模擬中，尋找每個粒子的精確鄰居是效能瓶頸（通常佔總時間 60-90%）。
* **創新點**：提出 **b-tree**，其特點是分支因子（一個節點可以有多少子節點）是動態調整的，旨在降低樹的深度。
* **效能優勢**：在最佳情況下，複雜度可達 **$O(n)$**（傳統 Octree 為 $O(n \log n)$）。

### 2. 引言 (Introduction)

* **背景**：SPH 需要在一定的支撐半徑（smoothing length, $h$）內尋找鄰居粒子。
* **動機**：傳統的 Octree 分支因子固定為 8（2D 為 4），對於密度極度不均勻的數據，樹會變得非常深，導致搜尋效率下降。
* **目標**：設計一種結構，能根據空間中粒子的分佈自動調整分支，從而減少遍歷次數。

### 3. b-tree 結構與演算法 (The b-tree)

這是本論文最核心的技術部分：

* **3.1 核心概念 (Structure)**：
* b-tree 是基於 **Morton Code (Z-order curve)** 構建的。
* 它允許一個父節點擁有超過 8 個子節點。透過增加分支因子，樹的深度會變淺。

* **3.2 建構演算法 (Building the Tree)**：
* **排序 (Sorting)**：先將粒子依 Morton Code 排序。
* **自底向上 (Bottom-up)**：利用排序後的序列，直接識別出相鄰粒子所屬的節點層級，避免了重複的遞迴插入。

* **3.3 鄰域搜尋 (Finding Neighbors)**：
* 利用位元運算（Bitwise operations）快速判斷一個節點是否與搜尋範圍（球體）重疊。
* **關鍵優化**：透過 Morton Code 的範圍檢查，可以快速排除大量不相關的「森林分枝」。

### 4. 效能評估 (Evaluation)

* **測試場景**：使用了 Sedov 爆炸波（強烈非均勻分佈）和均勻分佈等標準 SPH 測試案例。
* **結果對比**：
* **樹深度**：b-tree 的深度顯著低於傳統 Octree。
* **速度**：在大規模模擬中（超過千萬顆粒子），b-tree 的搜尋速度優於傳統 Octree 和 Linked-list 方法。
* **強擴展性**：在多核心並行環境下表現優異。

### 5. 結論 (Conclusion)

* b-tree 證明了透過**增加樹的寬度（寬度自適應）**來**換取深度縮減**，能大幅提升 SPH 鄰域搜尋的局部性與效率。
* 這種結構特別適合處理具有「高度密度差異」的流體或天文模擬。

---

# Conclusion

1. Barnes-Hut algorithm之理論基礎 (A) 確立了 Barnes-Hut 演算法的經典物理框架。其核心貢獻在於定義了「建構空間樹、聚合質心屬性、應用 $\theta$ 近似準則 (Approximation Criterion)」的標準流程。透過空間層次化處理遠程力，成功將運算複雜度由 $O(N^2)$ 降低至 $O(N \log N)$，為大規模系統模擬提供了理論可行性。

2. 文本 B 雖未直接涉及 Barnes-Hut 之力學計算，但其工程價值在於 Morton Code (Z-order) 與 Octree 的深度整合應用。該研究專注於如何加速 鄰域搜尋 (Neighbor Search) 中的空間劃分，利用位元交錯技術與記憶體局部性，優化了 Octree 的建置與檢索效率。這對解決 Barnes-Hut 在動態模擬中面臨的「每幀重建樹結構」之效能瓶頸，具備重要的技術平移價值。

3. 文本 C 進一步探討了基於 Morton Code 衍生的 b-tree (不同於傳統 B-Tree) 概念。該技術透過自適應分支因子優化了樹狀結構的深度平衡，旨在提供比傳統 Octree 更靈活的空間查詢效率。

# 2/3 - 2/8
# 2/9 - 2/15
## A. Load Balancing N-body Simulations with Highly Non-uniform Density (關於極端負載不平衡的N-body system Solution)
## https://dl.acm.org/doi/epdf/10.1145/2597652.2597659

### 1. 摘要與導論 (Abstract & Introduction)
**核心問題**：傳統的 N-body 並行方法（如簡單的空間劃分）假設粒子分佈是相對均勻的。但在模擬星系碰撞或超新星時，粒子會極度聚集。
**痛點**：在這種「高度非均勻分佈」下，某些運算節點會分配到極其繁重的計算任務（因為那裡的粒子多、交互作用複雜），而其他節點則在閒置，這導致了嚴重的負載不均 (Load Imbalance)。
**用意**：提出一種新的框架，能夠在粒子分佈動態變化時，精確預測計算負載並重新分配任務。
### 2. 背景與相關工作 (Background & Related Work)
**技術背景**：介紹了 Barnes-Hut 演算法與 Octree 結構。
**現有侷限**：指出目前的負載平衡方法（如基於空間曲線 Morton/Hilbert Curve 的劃分）只考慮了粒子的「位置」，卻忽略了「計算代價」。在 Barnes-Hut 中，不同區域的遍歷深度不同，計算量其實是不對等的。
### 3. 負載建模：超圖方法 (Hypergraph-based Load Modeling)
這是整篇論文最精華的部分：
**創新點**：作者將 N-body 的計算任務建模為一個 超圖 (Hypergraph)。
**頂點 (Vertices)**：代表 Octree 中的節點或粒子群。
**邊 (Edges/Hyperedges)**：代表它們之間的交互作用（力計算）。
**用意**：透過超圖，可以精確地量化「誰跟誰要計算」，並將這個複雜的關係矩陣交給專業的劃分工具（如 Zoltan 或 PaToH）來處理。
### 4. 演算法實作 (Implementation Details)
兩階段策略：
**提取 (Extraction)**：從現有的 Octree 中提取出計算任務的依賴關係。
**劃分 (Partitioning)**：利用超圖劃分演算法，找到一條「切割線」，使得每個運算節點分到的邊（計算量）幾乎相等，且跨節點的通訊量最小。
動態調整：因為粒子會動，所以這個超圖會定期更新，以適應新的粒子分佈。
### 5. 實驗評估 (Evaluation)
**測試環境**：在大型超級電腦上進行測試。
結果：
在粒子分佈極度不均勻的測試案例中，該方法比傳統的空間曲線劃分法快了許多。
**可擴展性**：證明了當增加 CPU 核心數時，該方法依然能保持良好的加速比。
### 6. 結論 (Conclusion)
總結：證明了「考慮計算交互作用關係」比「單純考慮空間位置」更能有效解決 N-body 的負載平衡問題。

---

### 1. 核心技術挑戰：為什麼傳統方法會失效？
在高度非均勻分佈（如星系核心）中，傳統的 SFC (Space-Filling Curves, 如 Morton/Hilbert Curve) 劃分法有兩個致命傷：
**工作量估計錯誤：** SFC 假設每個粒子的計算量是常數，但在 Barnes-Hut 中，高密度區的粒子需要遍歷更深的樹，計算量遠大於邊緣粒子。
**通訊開銷忽略：** SFC 只保證空間鄰近性，但不保證「交互作用」的鄰近性。這導致節點間需要頻繁交換遠方節點的資料（Ghost Cells），產生巨大的網路延遲。
### 2. 關鍵技術創新：超圖建模 (Hypergraph Formulation)
這是論文最核心的技術貢獻。作者將計算任務定義為 $H = (V, E)$：
**頂點 (Vertices, $V$)：**
作者將 Octree 劃分為多個 「子樹 (Subtrees)」 或 「任務塊 (Task Blocks)」。每個頂點代表一個計算單元。
每個頂點都有一個 權重 (Weight)，代表處理該子樹所需的 CPU 時間。
**超邊 (Hyperedges, $E$)：**
這是最精妙的地方。如果子樹 A 需要讀取子樹 B 的資料來計算力，那麼 A 和 B 就被連在一條超邊上。
用意：超邊代表了「數據依賴」。如果 A 和 B 被分配到不同的 CPU 核心，這條超邊就會產生「通訊成本」。
### 3. 負載平衡演算法流程 (The Balancing Pipeline)
論文提出了一個自動化的優化流程：
**任務分解 (Decomposition)**：
將全域 Octree 拆解成數千個小型的 「森林 (Forest of subtrees)」。這些小樹是分配的基本單位。
**交互作用追蹤 (Interaction Tracking)**：
在一次模擬迭代中，記錄哪些子樹與哪些節點發生了交互作用（即 Barnes-Hut 的樹遍歷路徑）。
**超圖劃分 (Partitioning)**：
使用 多層級劃分演算法 (Multi-level Partitioning)。目標是：
- **最小化邊切割 (Minimize Edge Cut)**：減少跨節點的數據交換。
- **平衡頂點權重 (Balance Vertex Weights)**：確保每個 CPU 核心的總計算時間一致。
- **動態遷移 (Data Migration)**：
根據劃分結果，將粒子數據在網路中重新分配。
### 4. 實驗中的技術發現
**強縮放性 (Strong Scaling)**：論文展示了在處理 10^7 等級的粒子時，使用超圖方法可以讓系統在核心數增加時，依然保持接近線性的加速比。
**對抗極端分佈**：在「冷塌縮 (Cold Collapse)」模擬中（粒子會迅速向中心聚集），超圖方法比傳統 SFC 方法快了 2 倍以上，因為它能精確捕捉到中心區域暴增的計算量。
### 5. 對你研究的技術啟發 (Technical Takeaways)
如果你要參考這篇論文，你可以關注以下技術點：
**權重預測**：你可以思考如何利用 SIMD 的執行週期 來更精確地估計頂點權重。
混合策略：這篇論文用超圖處理「宏觀」的負載分配，而你可以結合你之前看的 2022 論文，在「微觀」的子樹內部使用 SIMD 簇化。
**動態頻率**：超圖劃分本身也有開銷。論文提到不需要每一幀都重新劃分，這與你之前想的「增量更新」不謀而合。
**總結來說**：這篇論文教你如何用「數據依賴圖」來取代「空間幾何圖」。這在處理黑洞或超新星這種「局部極度複雜」的場景時，是目前已知最科學的解決方案。

## B.GOTHIC: Gravitational oct-tree code accelerated by hierarchical time stepping
## https://arxiv.org/pdf/1610.07279
1. 研究背景與動機 (Motivation)
- 核心問題：在天文模擬中，不同區域的粒子受力情況差異極大。核心區域粒子受力劇烈，需要極小的時間步長 ($\Delta t$)；邊緣粒子受力平緩，可以用較大的步長。
傳統做法的缺點：如果所有粒子都用最小的步長（Global Time Stepping），會浪費大量計算資源在那些運動緩慢的粒子上。
- GOTHIC 的目標：開發一個能完全在 GPU 上運行、支援層級時步，且能處理數百萬到數億個粒子的重力 N-body 代碼。
2. 核心技術：層級時步 (Hierarchical Time Stepping)
這是論文最關鍵的演算法部分：
- 時步劃分：將時間步長設定為 $2^n$ 的形式（例如 $\Delta t_{max}, \Delta t_{max}/2, \Delta t_{max}/4 \dots$）。
- 粒子分組：根據粒子的加速度與速度，將粒子分配到不同的「時步層級」中。
- 同步機制：只有當較大步長的粒子到達其更新時間點時，才會與較小步長的粒子進行同步計算。這大幅減少了總體的力計算次數。
3. GPU 架構下的優化 (GPU Implementation)
這部分對資工系的你最有參考價值：
- 完全 GPU 化 (Entirely on GPU)：與許多「CPU 建樹、GPU 算力」的代碼不同，GOTHIC 的 Octree 構建、重心計算、力計算、以及時步更新 全部都在 GPU 上完成，消除了 CPU-GPU 之間頻繁的資料傳輸瓶頸。
- WARP 層級的並行：利用 GPU 的 WARP 特性來優化樹遍歷，減少了分支發散（Warp Divergence）帶來的效能損失。
- 記憶體佈局：使用 Morton Code 對粒子進行排序，確保在 GPU 存取記憶體時具有極高的合併存取（Coalesced Access）效率。
4. 效能表現與結果 (Performance)
- 加速比：在單張 GPU 上，GOTHIC 的表現優於當時許多知名的 CPU 並行代碼。
- 精確度：論文證明了層級時步在大幅提升速度的同時，透過適當的誤差控制（如使用 Hermite 積分器），依然能保持極高的軌道計算精確度。
5. 論文重點大綱總結

| 章節 | 重點內容 |
| :--------------------- | :------------------------------------------------------- |
| **Introduction** | 提出 N-body 模擬中「時間尺度差異」導致的效能瓶頸。 |
| **Algorithm** | 詳細描述 **Hierarchical Time Stepping** 的邏輯與 Hermite 積分器的應用。 |
| **GPU Implementation** | 介紹如何在 GPU 上高效構建 **Octree** 與執行 **Tree Traversal**。 |
| **Performance Test** | 透過星團模擬（Star Cluster）驗證代碼在極端動態範圍下的穩定性。 |
| **Conclusion** | 總結 GOTHIC 作為一個高效、開源的天文模擬工具的價值。 |

6. 對你研究的啟發
這篇論文與你之前看的 Load Balancing (2014) 剛好形成互補：
- 空間 vs 時間：2014 的論文關注「空間分佈不均」，而 GOTHIC 關注「時間尺度不均」。
- 硬體轉向：GOTHIC 展示了如何將複雜的樹演算法完全搬到 GPU 上。
- 你的切入點：你可以思考，如果將 GOTHIC 的「層級時步」思想，應用到你之前討論的「超新星/黑洞」場景，並結合 SIMD 優化，是否能創造出一個在 CPU 和 GPU 上都能跑得極快的混合架構？
# 2/16 - 2/22

## A. https://github.com/DeadlockCode/barnes-hut

### body.rs
1. **積分方法 (Integration Method)**：
這段程式碼使用的是 Explicit Euler（顯式歐拉法）。它的優點是簡單，但缺點是能量不守恆（長期模擬星系會慢慢散開或坍縮）。
研究點：如果你的 Baseline 跑出來發現星系不穩定，你可以考慮將其升級為 Leapfrog Integration（蛙跳法），這是天文物理模擬的標準做法。
2. **數據對齊 (Data Alignment)**：
在 C++ 中，如果你之後要做 SIMD，你會發現把 pos.x 和 pos.y 分開存儲（SoA, Structure of Arrays）會比現在這種存在一起（AoS, Array of Structures）快得多。
建議：現在先用 AoS（即上面的 C++ 代碼）跑通 Baseline，等 3 月優化階段再改。
### simulation.rs
1. **theta 的影響：**
- theta = 0：Barnes-Hut 退化為暴力解 $O(N^2)$。
- theta 越大：計算越快，但誤差越大。
- 研究點：你的 Baseline 應該測試不同 theta 值對「執行時間」與「模擬準確度」的影響。
2. **軟化因子 (Softening)：**
- 公式通常是：$F = G \frac{m_1 m_2}{r^2 + \epsilon^2}$。
- 這在 simulation.rs 中雖然只是個參數，但在實作 calculate_force 時非常重要，能避免數值不穩定。
3. **記憶體管理：**
- Rust 版每一幀都重新 build 一棵樹。在 C++ 中，頻繁的 new 和 delete 會很慢。
- 優化點：之後你可以研究如何「重複使用」記憶體池（Memory Pool），這也是一個很好的研究小點。
### quadtree.rs
**1. 核心函式**
- **update_mass(&mut self, node_idx: usize)**
用途：由下而上（Bottom-up）計算每個節點的總質量與質心。
邏輯：如果是葉子，質心就是粒子位置；如果是內部節點，則將四個子節點的質量加權平均。這就是你之前「恍然大悟」的那個物理公式！
- **insert(&mut self, node_idx: usize, body_idx: usize, bodies: &[Body])**
用途：動態建樹。
邏輯：
如果節點是空的，直接放入粒子。
如果節點已有粒子，則「分裂（Subdivide）」成四個子節點，並將新舊粒子重新分配。
這與你 LeetCode 的靜態建樹不同，這是動態插入，能處理不均勻分佈。
- **calculate_force(&self, body: &Body, ...)**
用途：計算單個粒子受到的總引力。
邏輯（Barnes-Hut 靈魂）：
計算 s / d（節點寬度 / 距離）。
如果 s / d < theta：代表節點夠遠，直接把整個節點當作一個大粒子計算（$O(1)$）。
否則：遞迴進入子節點計算更精確的受力。

**2. 研究者的深度筆記：**
- **扁平化存儲 (Flat Array)**：
Rust 版使用 Vec<Node> 而不是 Box<Node>。這是一個非常高級的優化，能減少記憶體碎片。你的 C++ 版本也應該使用 std::vector<Node> 並透過索引存取。
- **s / d < theta 的物理意義**：
這是論文的核心。它將 $O(N^2)$ 降到 $O(N \log N)$。在你的論文中，這張遞迴示意圖是必畫的。
- **軟化因子 (Softening)**：
在 calculate_force 中，當 dist 非常小時，eps 能防止引力爆炸。這對模擬的穩定性至關重要。
### renderer.rs
1. 研究者的深度筆記：
- **渲染不是研究重點，但數據導出是：**
在你的 C++ Baseline 階段，建議先寫一個 exportData() 函式，將粒子的座標存成 .csv。你可以用 Python 的 matplotlib 畫圖，這比寫 C++ 渲染器快得多。
- **多執行緒的複雜性：**
Rust 版為了渲染流暢使用了多執行緒。但在你的 C++ Baseline 中，建議先用單執行緒（計算完一幀 -> 畫一幀）。這樣 Debug 會容易得多，等 3 月要做並行優化時再考慮多執行緒。
- **GPU 加速的伏筆：**
雖然你現在的研究重點是 CPU 優化（SIMD），但這份 renderer.rs 使用 GPU 繪圖提醒了我們：如果未來 $N$ 達到百萬級別，連繪圖都會變成瓶頸。

### main.rs

### utils.rs
1. 研究者的深度筆記：
- **為什麼要排序？**
在計算 $v = \sqrt{GM/r}$ 時，根據高斯定律（Gauss's Law for Gravity），粒子只會受到「半徑比它小」的質量吸引。排序是為了能用 $O(N)$ 的時間算出每個位置對應的內部總質量。
- **穩定性驗證：**
如果你的 C++ Baseline 跑起來後，粒子立刻像爆炸一樣飛散，通常是因為這裡的 v 算錯了。這個 utils.rs 提供的公式是確保星系能「轉起來」的關鍵。
- **無因次單位 (Dimensionless Units)：**
注意到這裡 $G$ 被隱含地設為 $1.0$。這在模擬中很常見，可以簡化計算。

# 2/23 - 3/1
既然你的 **核心數據結構 (`Body`)** 與 **核心演算法 (`Octree`)** 已經到位，這意味著你的「大腦」已經長好了。接下來的下一步，是為這個系統建立「身體」與「眼睛」，讓它能夠運作、測試並展示成果。

為了讓你的專題在推甄時看起來像一個專業的「高效能模擬系統」，建議增加以下幾個模組：

---

### 1. `Integrator.h` (時間步進器)

這是物理模擬的「動力」。單純計算出加速度是不夠的，你需要決定如何根據加速度更新速度與位置。

* **為什麼重要**：直接使用 `pos += v * dt` (Euler Method) 會導致能量不守恆，星星會很快飛散。
* **建議實作**：**Leapfrog Integration** 或 **Runge-Kutta (RK4)**。Leapfrog 是天文物理模擬的標配，因為它具有可逆性且能量穩定。
* **功能**：處理 與 的交替更新。

### 2. `Simulator.h / .cpp` (模擬管理器)

這是一個高層級的控制類別，用來整合 `Body` 和 `Octree`。

* **職責**：
* 管理所有的 `std::vector<Body>`。
* 每一幀（Frame）呼叫 `Octree::clear`、`Octree::insert`、`Octree::propagate`。
* 計算所有粒子的受力並呼叫 `Integrator` 更新狀態。

* **推甄亮點**：在這裡實作 **多執行緒 (OpenMP)**。因為每個粒子的加速度計算是獨立的，只要加一行 `#pragma omp parallel for`，你的效能就能翻倍。

### 3. `DataLoader.h` (數據讀取與轉換)

這是你對接 **NASA API** 的橋樑。

* **功能**：
* 讀取 CSV 或 JSON 格式的天文數據。
* **座標轉換**：將天文單位的數據轉換成你的模擬單位（例如將 AU 轉為模擬中的單位 1.0）。
* **場景生成**：例如寫一個 `generate_spiral_galaxy()` 函式來隨機生成幾萬顆星星的初始位置。

### 4. `Renderer.h` (視覺化引擎)

專題展最重要的「門面」。

* **技術選擇**：
* **簡單快速**：SFML (2D 視角) 或簡單的 OpenGL。
* **進階專業**：使用 **Vulkan** 或 **Modern OpenGL (Shader-based)** 來繪製「星光點點」的效果。

* **功能**：
* 把 `Body` 的 畫在螢幕上。
* **Debug Mode**：在畫面上畫出 Octree 的方框（Bounding Boxes），這在展示演算法時非常有說服力。

---

### 📂 建議的專案目錄結構

/NBodyProject
  ├── /include
  │    ├── body.h
  │    ├── octree.h
  │    ├── integrator.h    <-- 下一步：物理公式
  │    ├── simulator.h     <-- 下一步：邏輯中樞
  │    ├── data_loader.h   <-- 下一步：接軌 NASA
  │    └── renderer.h      <-- 下一步：視覺效果
  ├── /src
  │    ├── main.cpp        <-- 程式入口
  │    └── simulator.cpp
  └── /data
       └── nasa_stars.csv  <-- 存放 API 抓下來的數據

---