GPU で飛ぶ 10 万羽の鳥：アルゴリズムと自然に関する探求

長い間、私は一つの疑問に悩まされてきました。なぜこの世界の人々やモノは、異なる規模で異なる集団を形成し、反発し合うのでしょうか。人々は互いに近づき合いながらも、群衆と群衆の間で競争や敵対関係が生まれ、原子や分子は互いに近づきながらも、物体として分離し、さらには惑星や銀河にまで至るのです。

この素朴な考えを胸に、私はアート専攻の壁を乗り越え、Complex System、Swarm Intelligence、Metaheuristics、Self-Organization、Emergence、Agent-Based Modeling (ABM) といった、かつては遠く感じていた概念の研究を始めました。これらの研究と発見をアート作品として制作し、人生初めての App Store / Steam アプリケーションをリリースしました。

興味がありましたら、この物語を知り、私たちと一緒に探求してみませんか...

最初のインスピレーション

私はあまりゲームをプレイしない人間ですが、『Frost』とその続編『Lifelike』は特に強い印象を残しました。ゲームの公式サイトによると、現在の CPU ではこのような高性能な群集シミュレーションは不可能で、このゲームは Metal を使用して GPU アルゴリズムを開発したとのことでした。

後に Unity Visual Effect Graph を学び、これは先進的で使いやすい GPU パーティクルシステムでしたが、パーティクル間の相互作用をシミュレートすることができませんでした。これは私の疑問をさらに深めました。Frost はどのように実現したのでしょうか？

呂先生と私の疑問を共有

鳥の群れから始める

学術界では、群集システムの先駆的な作品は 1986 年の生体模倣プログラム Boids です。これは鳥の群れの動きを、個体の運動の 3 つの基本法則：分離（Separation）、整列（Alignment）、結合（Cohesion）に帰納し、各個体は一定範囲内もしくは一定の視野内の他の個体しか観察できないというものでした。

，時長00:27

古典的な群れアルゴリズム Boids

Processing 公式サイトの Boids アルゴリズム例、https://processing.org/examples/flocking.html

2 つの群れの出会い

プロジェクトサイト：https://bingweb.binghamton.edu/~sayama/SwarmChemistry/

この研究を発見した時、私は瞬時に興奮しました。パーティクルシステムは群れモデルの 3 つの基本法則を継承し、より多くの行動法則を追加し、同時に一つのシーンに異なる群れを追加しました。多様性が一瞬のうちに現れました。

プロジェクトの公式サイトでは Java プログラムをダウンロードでき、同時にコードもオープンソースで公開されています。

しかし、プログラムはパーティクルの数を 300 に制限していました。私たちが明確に理解していることは、CPU の（シングルスレッド、反復）近傍探索アルゴリズムの複雑度が O(N²) であり、つまりパーティクル数が 2 倍になると計算時間は 4 倍になるということです。シミュレーションのボトルネックがすぐに現れました。

GPU：1 万倍のパフォーマンス向上

NVIDIA の Jensen Huang は、ムーアの法則によると、GPU は CPU と比較して、10 年後の計算リソースを現在の研究者に提供するのに相当すると述べました。これが GPU 計算の明らかな向上を感じる理由でしょう。

YouTube のある投稿者、ゲーム Headmaster の制作者は、50 万パーティクルの Boids シミュレーションを実現しました。原理は Processing の Pixel Flow ライブラリの例と同じで、実際の近傍探索ではなく、パーティクルの情報をベクトルテクスチャに書き込むことで、各パーティクルの位置を変更するものでした。

ベクトルフィールドテクスチャに基づくシミュレーションでは、10 万レベルの Boids 近似シミュレーションを容易に実現できますが、この方法は私が実現したい複雑なモデルには適していません

最初の試み

Python + Numba

私の最初の実験は、Python で Numba ライブラリを使用して CUDA にバインドし加速することでした。Python の極めて低い敷居と Numba の魔法のような構文のおかげで、私たちはすぐに CPU アルゴリズムを GPU プラットフォームに移植し、OpenGL で描画することができました。

Numba ライブラリ、数行のコードを追加するだけで関数を GPU 上で並列実行できます

初めてアルゴリズムが動作した時、画面はまだ白黒でした

，時長00:27

OpenGL でレンダリングしたプログラム

教室でのテスト実行

展示効果図

二回目の試み

TouchDesigner

TouchDesigner を初めて使用した時、多くのエフェクトの作り方がわかりませんでしたが、少なくとも動作はしました

授業の発表時には、すでに 60 倍のパフォーマンス向上を達成していました

残念ながら、TouchDesigner で直接 OpenGL コンピュートシェーダーを呼び出すことはできませんでした（macOS がサポートしていないため）。すべての計算は依然として Python の Numba で行われ、描画部分のみを OpenGL から TouchDesigner に移行しました。

さらに、Python（Numba）には構造体やベクトル型がないため、すべてのデータを配列に格納する必要があり、x、y 座標の計算はすべて 2 回書く必要があり、非常に面倒でした。

三回目の試み

Houdini

Houdini を学んだ後、新しい世界が開かれました。OpenCL のサポートにより、低レベルの GPU プログラムを書く機会を得ました（CUDA C++ は私にとって本当に難しすぎました）。便利なデータバインディング、超高性能により、わずか数個のノードと数回の接続で、アルゴリズムを完全に移植することができました。

Houdini で OpenCL ノードを使用してシミュレーションを加速し、ベクトル構文で簡単に 3D に書き換え

Redshift でレンダリング（ピントが合っていないのがアート的です）

Houdini OpenCL のパフォーマンスは、さらなる最適化への意欲を与えてくれました。クロスプラットフォームアプリケーションを作りたいという考えも生まれました。オフラインエフェクトソフトウェアなのに、異常に流暢なリアルタイムパフォーマンスを持っていて、Python の Numba とは比べものになりませんでした...

最後の集大成

Unity

数多くの困難を乗り越えた後、ついに最適なプラットフォームを見つけました。

コンピュートシェーダー：相互運用の問題を解決し、マルチプラットフォームでコンパイル

これまでの Python / Houdini プログラムでは、すべてのパーティクルデータの計算とレンダリングは CPU と GPU の間でコピーする必要がありました。従来のアーキテクチャではメモリが共有されていないため、これは計算性能に大きな影響を与えました。実際には、GPU の計算プログラムと描画プログラムは相互運用が可能で、同じデータ（Buffer）にアクセスできます。

Unity は、HLSL Compute Shader という完璧なソリューションを提供しています。Unity は作成した HLSL プログラムを Metal、DirectX、Vulkan、OpenGL にコンパイルし、マルチプラットフォームでコードを書き直す手間を省きます。通常の Shader プログラムと同様に、GPU 内の Buffer の読み取りをサポートしています。

最適化を何もしなくても、数倍のパフォーマンス向上を簡単に実現でき、パーティクル数が多い場合は特に顕著です。

極限を追求する最適化：空間分割アルゴリズム

これまで、すべてのパーティクルの近傍探索は完全な総当たり探索でしたが、各パーティクルが周囲のパーティクルのみを探索できるようにする素晴らしい方法がいくつかあります。その中で最も理解しやすく、このシーンに最適な方法が空間分割です。

各パーティクルの最大観察半径が 40 なので、1280 × 720 の活動領域を 32 × 18 個の一辺 40 の正方形グリッドに分割できます。これにより、各パーティクルは自身が存在するグリッドの周囲 9 個のグリッドのみを探索すれば良くなります。理由は、1 つのグリッドを挟んだパーティクル間の距離は必ず 40 を超えるからです。

空間分割による最適化後、パフォーマンスは最適化前と比較して平均 3 倍向上しました。

この他にも、ソートアルゴリズムや K-D Tree 分割など、探求する価値のあるものがあります。

基本的なグリッド空間分割後、20 万パーティクルで 60FPS のパフォーマンスを達成、3070Ti、Processing の CPU プログラムと比較して 1 万倍のパフォーマンス向上

新しい発見：パーティクルシステムによるシマウマ模様の生成

偶然の試みで、パーティクルに小さな仕組みを追加するだけで：敵味方の識別、つまり種類に応じて近隣のパーティクルを区別して扱うことで、非常に不思議な自己組織化パターンを生成できることを発見しました。小さな花かもしれませんし、シマウマ模様かもしれません。

これまでシマウマ模様は Reaction-Diffusion アルゴリズムや Multi-Neighborhood Cellular Automata アルゴリズムでしか実現できませんでしたが、今では、パーティクルベースのモデルでも可能になりました。これは生命科学の新しい視点を開く可能性があります。なぜなら、生命の基礎は細胞であり、ピクセルではないからです。

，時長01:16

パーティクルの動きで咲いた小さな花、現在のアプリケーションアイコンにもなっています

ミミズのような効果、完全にパーティクルの自己組織化によるもので、破壊後も復元可能です

独特なシマウマ模様

MIDI キーボードを接続した後の効果、24 個のパラメータが AKAI MPD218 の 24 個のノブに完璧に対応し、素晴らしい体験です

学院でテスト時に撮影した写真

作品用に制作したモバイル UI、面白いプリセットを選択し、スクリーンショットを撮影、パラメータをコピー＆ペーストできます

VR バージョン、開発中～

アイデアからリリースまで

いくつかの小さな経験

第一歩を踏み出し、挑戦を続ける

今年の 3 月に初めて先生とこのアイデアを共有したことを覚えています。その時、私は少し怖かったです。結局のところ、私は専門外の出身で、ほとんどのコンピュータサイエンス学部でも教えない GPU 計算の研究をしようとしていたからです。

ある日突然、丹琪姉に学院に呼ばれ、環境保護部が COP15 生物多様性会議の展示会を開催するので、作品を作ってみませんか？と聞かれました。

そこで私は再びこのトピックを思い出し、挑戦してみようかと考えました。

私は同じ追求を持つ友人たちを集めました：高校時代の親友で、最初の Python プログラムを動かした陳さん（Github：CPunisher）、アメリカ時間で生活し、毎晩 24 時に作業を引き継ぐ Unity チームメイトの時辰（抖音@時辰不死於背鍋）、そしてクリエイティブ、企画、展示を一緒に行う金希、杜西の先輩たち。

道中で多くの達人に出会い、大量の助けを頂きました。

Github の仲間、分かる人には分かります

3 日 3 晩徹夜して、やっと iOS プログラムの黒画面を点灯させました。この時チームメイトが持ってきた 0.72（階下の串焼き店の名前）に心が躍りました

担任の楊先生、私たちの GPU の父、学科全体の計算力を担当し、クラス全体で R9000P を圧倒

沈浩先生が紹介してくださったニューメディアアーティストの任遠さん、『Processing クリエイティブ・コーディング』の著者。彼が示してくれた「小さな目標」が、私の限界への追求の原動力となりました

ゲーム学科の萌神呼風喚雨、費先生と鄭先輩に空間分割などのアルゴリズムを教えていただきました

群集化学を研究している可愛らしい日本の教授が私のメールに返信してくださり、進化アルゴリズムを組み込んだバージョンが作れるかと尋ねてくださいました

上述のゲーム開発者と私のプログラムを共有しました

学科長：これは雁を追って羽を抜くようなもので、管理費を取らないといけないね

みんな達人ばかりです

講座のポスター、環境保護部に感謝！

WWF の公式による生物多様性の説明を聞く

孫先生、丹琪姉、博哥そして黒弓の皆様、鴎哥、老曹、小鹿姉に特に感謝します。時間を作って直接指導してくださり、私たちを連れて食事に行ってくださいました。また遊びに来てください

（私たちの学年が最も不運だと言われています。コロナのせいで多くの短期留学プログラムがキャンセルされましたが、それでも素晴らしい短期プログラムを持つことができました。中国伝媒大学デジタルメディア学科、投資して損はありません 👍）

リリース・審査提出

ついに審査を通過しました！

Apple の審査は厳しいと聞いていましたが、実際に経験してみると、本当に面倒でしたが、これらの壁を乗り越えた価値は十分にありました。

以前作った多くのものは、プロトタイプや Demo の段階で止まっていて、リリースして多くの人に見てもらうことは考えもしませんでした。今回は完璧主義を脇に置き、機能が 100% 完成する前にまずリリースすることにしました。

そして私を待っていたのは、開発者アカウントの登録、輸出規制、アメリカの納税申告書、外貨口座、年齢制限評価、パッケージのアップロード、これらの全く触れたことのないものでした。

App Store に必須の冗長な文書：プライバシーポリシー（プライバシーデータを一切収集しないプログラムにもわざわざウェブページを開設して説明する必要があることについて言いたいだけです）

初めてのパッケージアップロード成功

パッケージングとテストを続けています

数十枚の異なるサイズのスクリーンショット・プロモーション画像をアップロードし、ついに自分のストアページを見ることができました

Steam 審査通過！

App Store 審査通過！

最後に

つい最近、2021 年のノーベル物理学賞が複雑な物理系に重要な貢献をした 3 人の科学者に授与されました。複雑性思考はますます重要になってきています。天気は決定論的な中で予測不可能に変化し、生命は無秩序な世界で秩序を蓄積します。各個体は独立した目標を持ち、限られたつながりの中で情報を伝達しながら、驚くべき集団知能を生み出すことができます。これが私がこれほどまでに魅了される理由なのでしょう。