• Proje Hakkında
• Barnes-Hut Algoritması
• Versiyon Geçmişi
• Proje Yapısı
• Kurulum ve Derleme
• Kullanım
• Görselleştirme İmkanları
• Parametreler
• Teknik Detaylar

Bu proje, N-Body problemini çözmek için Barnes-Hut algoritması kullanan bir gravitasyonel/elektromanyetik simülasyon uygulamasıdır. N-Body problemi, birbirleriyle etkileşen N adet cismin (parçacık, yıldız, galaksi vb.) zaman içindeki hareketlerini hesaplamayı amaçlar.

• Barnes-Hut Octree yapısı ile hızlandırılmış kuvvet hesaplaması
• Leapfrog entegrasyon yöntemi ile zaman adımlaması
• 3 boyutlu uzayda parçacık simülasyonu
• Coulomb veya gravitasyonel kuvvet hesaplaması
• Performans ölçümleme ve zaman takibi
• Gnuplot ile uyumlu çıktı formatı
• Özelleştirilebilir TETA ve LEAF parametreleri

Barnes-Hut algoritması, N-Body simülasyonlarında hesaplama karmaşıklığını O(N²) den O(N log N) seviyesine indiren bir hiyerarşik ağaç tabanlı yaklaşımdır.

1. Ağaç Oluşturma: 3D uzay, recursive olarak 8 alt kübe (octree) bölünür
2. Kütle Merkezi Hesaplama (Upward Pass): Her düğüm için toplam kütle ve kütle merkezi hesaplanır
3. Kuvvet Hesaplama: Uzak parçacık grupları tek bir kütle merkezi olarak yaklaşıklanır
4. TETA Kriteri: Bir hücrenin ne kadar uzakta olduğunu belirler
   • s/d < TETA ise hücre tek nokta gibi işlem görür
   • s/d >= TETA ise hücre alt parçalarına ayrılır
   • (s: hücre boyutu, d: mesafe)

• ✅ Hesaplama süresinde dramatik azalma (özellikle büyük N değerlerinde)
• ✅ Bellek kullanımında verimlilik
• ✅ Ayarlanabilir doğruluk-performans dengesi (TETA parametresi)
• ✅ Büyük ölçekli simülasyonları mümkün kılar

Yazar: Burak İNNER Tarih: 8 Mart 2017

İlk implementasyon şu özellikleri içeriyordu:

• BHtreetest.cpp: Ana program ve simülasyon döngüsü
• tree.cpp/h: Barnes-Hut ağaç yapısı ve algoritma implementasyonu
  • Octree oluşturma
  • Upward pass (kütle merkezi hesaplama)
  • Downward pass (kuvvet hesaplama)
  • Parçacık yükleme ve ağaç yönetimi
• particle.cpp/h: Parçacık sınıfı
  • Pozisyon, hız, kuvvet, kütle bilgileri
  • Leapfrog entegrasyonu
• vektor.h: 3D vektör matematik kütüphanesi
  • Vektör operatörleri (+, -, *, /)
  • Dot product, mesafe hesaplama
• file.cpp/h: Dosya I/O işlemleri
  • Parçacık verilerini okuma
  • Sonuçları yazma (pozisyon ve kuvvet)

• Fast Multipole Method (FMM) yaklaşımı
• Coulomb kuvveti hesaplaması
• Zaman ölçümleme (#define showtime)
• Leapfrog entegrasyon şeması
• Parametrik TETA ve particleLEAF değerleri

• 07-02-2005: Kod gözden geçirildi
• 01-03-2005:
  • TETA ve particleLEAF global değişkenler yapıldı
  • LEAF yapısı STL::vector kullanmaya başladı
  • Nodelist STL::vector'e dönüştürüldü
• 26-08-2004: TETA parametresi static'ten fonksiyon argümanına çevrildi

Yazar: yapbenzet Tarih: 11 Nisan 2018

• generate_data.cpp: Rastgele test verisi üreteci eklendi
  • Kullanıcı tanımlı parçacık sayısı
  • Rastgele kütle, pozisyon ve hız değerleri
  • Simülasyon parametrelerini tanımlama
  • Standart veri formatında dosya oluşturma

BarnesHut/
│
├── BHtreetest.cpp          # Ana program (main fonksiyonu)
├── tree.cpp / tree.h       # Barnes-Hut ağaç implementasyonu
├── particle.cpp / particle.h   # Parçacık sınıfı tanımı
├── vektor.h                # 3D vektör matematik kütüphanesi
├── file.cpp / file.h       # Dosya I/O işlemleri
├── stdinc.cpp / stdinc.h   # Standart include ve sabitler
├── generate_data.cpp       # Rastgele veri üreteci
└── ncb                     # Derlenmiş binary (executable)

• Program giriş noktası
• Komut satırı argümanlarını işler
• Ana simülasyon döngüsü
• Zaman adımlarını yönetir
• Performans metrikleri toplar

• Octree veri yapısı
• Parçacık yükleme (loadparticles)
• Upward pass (upwardpass): Kütle merkezi hesaplama
• Downward pass (downwardpass): Multipole-to-local dönüşümü
• Kuvvet hesaplama (calculateforces)
• Ağaç oluşturma ve temizleme

• Particle sınıfı: Kütle, pozisyon, hız, kuvvet
• Node struct: Octree düğüm yapısı
• Leapfrog entegrasyon (calcVelPos)
• Parçacık bilgilerini görüntüleme

• 3D vektör sınıfı
• Matematiksel operatörler
• Dot product, mesafe fonksiyonları
• Inline optimizasyonlar

• readfilePart: Parçacık verilerini dosyadan okuma
• putsnapshotfilePos: Pozisyon snapshot'ları
• putsnapshotfileForce: Kuvvet snapshot'ları
• Gnuplot uyumlu format

• İnteraktif veri üretici
• Rastgele kütle ataması (5000-15000 arası)
• Rastgele pozisyon (0-10 arası)
• Rastgele hız (0-100 arası)

• C++ Derleyici: g++ (GCC 4.x veya üzeri)
• Standart Kütüphaneler: STL (vector, iostream, fstream)
• İşletim Sistemi: Linux, macOS veya Windows (MinGW)

# Tüm kaynak dosyaları birlikte derle
g++ -o bh_simulation BHtreetest.cpp tree.cpp particle.cpp file.cpp stdinc.cpp -lm -O3

# veya optimize edilmiş versiyon
g++ -o bh_simulation BHtreetest.cpp tree.cpp particle.cpp file.cpp stdinc.cpp \
    -lm -O3 -march=native -funroll-loops

g++ -o generate_data generate_data.cpp -O2

• -O3: Maksimum optimizasyon
• -march=native: İşlemciye özel optimizasyon
• -funroll-loops: Döngü açma optimizasyonu
• -lm: Matematik kütüphanesi

İki yöntem mevcuttur:

./generate_data

Program sizden şu bilgileri isteyecektir:

• Dosya adı (örn: test_data.dat)
• Parçacık sayısı (örn: 1000)
• Başlangıç zamanı (örn: 0.0)
• Bitiş zamanı (örn: 10.0)
• Zaman adımı (örn: 0.01)

Veri otomatik olarak oluşturulur.

input.dat dosyası şu formatta olmalıdır:

N                           # Parçacık sayısı
t_start                     # Başlangıç zamanı
t_end                       # Bitiş zamanı
dt                          # Zaman adımı
mass[1] x[1] y[1] z[1] vx[1] vy[1] vz[1]
mass[2] x[2] y[2] z[2] vx[2] vy[2] vz[2]
...
mass[N] x[N] y[N] z[N] vx[N] vy[N] vz[N]

./bh_simulation <veri_dosyası> <TETA> <particleLEAF>

# Küçük sistem, yüksek doğruluk
./bh_simulation test_data.dat 0.5 1

# Orta ölçek, dengeli parametreler
./bh_simulation test_data.dat 0.7 8

# Büyük sistem, hızlı hesaplama
./bh_simulation test_data.dat 1.0 16

Program şu bilgileri görüntüler:

Starting a BARNES HUT algorithm with Lepfrog integration for a
1000-body system, from time t=0 to t=10 with time step=0.01
and number of max. particle in a LEAF 8 TETA=0.7

load particles takes 0.023 seconds
upward pass (without load particles) takes 0.015 seconds
calculate forces take (without load particles) 0.087 seconds
all takes 0.125 seconds
number of step = 1

Proje, sonuçları Gnuplot ile görselleştirmek için uygun formatta çıktılar üretir.

Program iki tür snapshot dosyası oluşturur:

putsnapshotfilePos(N, partList, message, TETA);

Format: x y z (her satırda bir parçacık)

putsnapshotfileForce(N, partList, timetakes);

Format: fx fy fz (her satırda bir parçacığın kuvveti)

# Gnuplot betiği - plot_positions.gnu
set terminal png size 1024,768
set output 'particle_distribution.png'

splot 'positions.dat' using 1:2:3 with points pt 7 ps 0.5 title 'Particles'

Çalıştırma:

gnuplot plot_positions.gnu

# XY düzlemi
plot 'positions.dat' using 1:2 with points

# XZ düzlemi
plot 'positions.dat' using 1:3 with points

# YZ düzlemi
plot 'positions.dat' using 2:3 with points

# Her zaman adımında snapshot al
# Gnuplot ile frame'leri birleştir

set terminal gif animate delay 10
set output 'simulation.gif'

do for [i=0:100] {
    splot sprintf('snapshot_%03d.dat', i) using 1:2:3 with points
}

# Kuvvet vektörlerini oklar olarak göster
plot 'data.dat' using 1:2:3:4 with vectors

Kinetik ve potansiyel enerjileri izleyerek sistemin korunumunu kontrol edin.

Belirli parçacıkların yörüngelerini zaman içinde takip edin.

Parçacık dağılımının zaman içindeki evrimini inceleyin.

Barnes-Hut algoritmasının doğruluk-performans dengesini belirler.

Açıklama:

• TETA = s/d (s: hücre boyutu, d: mesafe)
• Küçük TETA → Daha fazla direkt hesaplama → Daha doğru
• Büyük TETA → Daha fazla yaklaşıklama → Daha hızlı

Bir LEAF düğümünde bulunabilecek maksimum parçacık sayısı.

Açıklama:

• Küçük değer → Daha derin ağaç → Daha iyi kuvvet yaklaşıklaması
• Büyük değer → Daha sığ ağaç → Daha az bellek kullanımı

Simülasyon zaman çözünürlüğü.

dt = 0.001    # Çok küçük adım - kararlı ama yavaş
dt = 0.01     # Orta - çoğu durum için uygun
dt = 0.1      # Büyük adım - hızlı ama kararsızlık riski

Kural: dt < 0.1 * (karakteristik zaman ölçeği)

# Hassas bilimsel hesaplama
./bh_simulation data.dat 0.5 1

# Genel amaçlı (1K-10K parçacık)
./bh_simulation data.dat 0.7 8

# Büyük ölçekli (>100K parçacık)
./bh_simulation data.dat 0.9 16

1. Başlangıç
   ├── Veri dosyasından parçacık bilgilerini oku
   ├── TETA ve particleLEAF parametrelerini al
   └── Tree nesnesini oluştur

2. Ana Simülasyon Döngüsü (her zaman adımı için)
   ├── loadparticles()
   │   ├── Ağacı temizle
   │   ├── Root'u bul (tüm parçacıkları içeren küp)
   │   └── Her parçacığı ağaca ekle (addparticle)
   │
   ├── upwardpass()
   │   ├── Yapraktan köke doğru git
   │   └── Her düğüm için kütle merkezi hesapla
   │
   ├── calculateforces()
   │   ├── Her parçacık için
   │   │   ├── Ağacı traverse et
   │   │   ├── TETA kriterine göre karar ver
   │   │   │   ├── Yakın ise → direkt hesaplama
   │   │   │   └── Uzak ise → kütle merkezi yaklaşımı
   │   │   └── Toplam kuvveti hesapla
   │   └── Leapfrog entegrasyonu ile pozisyon/hız güncelle
   │
   ├── emptytree()
   │   └── Ağaç yapısını temizle
   │
   └── Çıktıları dosyaya yaz

3. Sonlandırma
   └── Performans metriklerini raporla

struct Node {
    long index;              // Düğüm indeksi
    _type Type;              // EMPTY, NODE veya LEAF
    vektor geocenter;        // Geometrik merkez
    double rsize;            // Küp kenar uzunluğu
    vektor masscenter;       // Kütle merkezi
    double mass;             // Toplam kütle
    vector<particle*> plist; // LEAF ise parçacık listesi
    int Nparticle;           // Parçacık sayısı
    long level;              // Ağaç seviyesi
    Node* child[8];          // 8 alt düğüm (octree)
    Node* parent;            // Ebeveyn düğüm
};

class particle {
    double data;       // Kütle veya yük
    vektor pos;        // Pozisyon (x,y,z)
    vektor vel;        // Hız (vx,vy,vz)
    vektor force;      // Kuvvet (fx,fy,fz)
    unsigned int Id;   // Parçacık kimliği
    Node* parent;      // Bağlı olduğu düğüm
};

Parçacık pozisyon ve hızları şu şekilde güncellenir:

v(t+dt/2) = v(t) + a(t) * dt/2
x(t+dt)   = x(t) + v(t+dt/2) * dt
v(t+dt)   = v(t+dt/2) + a(t+dt) * dt/2

Avantajları:

• Simplektik (enerji korunumu)
• İkinci mertebe doğruluk
• Uzun süreli kararlılık

F = G * m1 * m2 / r² * r̂

F ≈ G * m_particle * M_cell / R² * R̂

(M_cell: Hücrenin toplam kütlesi, R: Kütle merkezine mesafe)

• Her Node: ~120 byte
• Her Particle: ~80 byte
• Toplam ağaç düğümleri: yaklaşık N/particleLEAF * 1.3 (overhead)

Örnek: 10,000 parçacık, particleLEAF=8

• Parçacıklar: 10,000 * 80 = 800 KB
• Düğümler: ~1,600 * 120 = 192 KB
• Toplam: ~1 MB

1. Barnes, J. & Hut, P. (1986). "A hierarchical O(N log N) force-calculation algorithm". Nature, 324, 446-449.
2. Aarseth, S. J. (2003). "Gravitational N-Body Simulations". Cambridge University Press.
3. Dehnen, W. (2002). "A Hierarchical O(N) Force Calculation Algorithm". Journal of Computational Physics, 179, 27-42.

Burak İNNER Email: [email protected] Tarih: 6-7 Temmuz 2004 (ilk geliştirme)

• Mart 2017: Ana implementasyon
• Nisan 2018: Veri üreteci eklendi ([email protected])

Kocaeli Üniversitesi

Bu proje eğitim ve araştırma amaçlıdır.

Projeyi geliştirmek isterseniz:

1. Repository'yi fork edin
2. Feature branch oluşturun (git checkout -b feature/AmazingFeature)
3. Değişikliklerinizi commit edin (git commit -m 'Add some AmazingFeature')
4. Branch'inizi push edin (git push origin feature/AmazingFeature)
5. Pull Request açın

• Başlangıç için 0.7 önerilir. Daha hassas sonuçlar için 0.5'e düşürün, hız için 1.0'a çıkarın.

• TETA değerini artırın (0.9-1.0)
• particleLEAF değerini artırın (16-32)
• Derleme optimizasyonlarını kullanın (-O3)

• Zaman adımını (dt) küçültün
• TETA değerini düşürün
• Parçacık başlangıç koşullarını kontrol edin

• Çıktı dosyalarını Gnuplot ile açın (yukarıdaki örneklere bakın)
• Python matplotlib ile de görselleştirme yapılabilir

Son Güncelleme: Kasım 2025