■

・Building a Million Particle System
pdf1枚目読み終わった。内容はGPU上でのパーティクルシステムの実装について。毎フレーム各パーティクルの現在地、速度なんかを計算、テクスチャに描きこんどいて、それを使ってパーティクルを描写する話。
条件として、浮動小数点テクスチャフォーマットと頂点シェーダからテクスチャにアクセスできることが必要。後者は頂点シェーダ3.0からなので現在のPCのGPUでは無理っぽ。

パーティクルは半透明なので基本的に描写処理の最後に、視点からの距離でソートしてから描き始める必要がある。この論文?ではGPU上でこのソートを行うのにOdd-even Mergesortなるものを使用している。
特徴としては

• 定数時間(処理回数)で処理が完了する
• それぞれのiterationで整列が崩れることはない。
  (訳がいまいち…原文はwith each iteration sortedness never decrease)

GPU上で並列にソートするのに都合がいいらしい。基本的にパーティクルのZ座標は１フレームではそう大きく変わらないので各パーティクルの位置は、前フレームの位置との間に相関性(coherence)がある。よって何千、何万ものパーティクルを全部、毎回ソートせずに、多少不正確でも、処理を何10フレームかに分けた上で高速に部分ソート、描写処理を行うことも可能とのこと。

これ見てて浮動小数点対応の基数ソートの話思い出した。
http://codercorner.com/RadixSortRevisited.htm
IEEE754の浮動小数点形式の特徴を利用して浮動小数点を基数ソートする話。
Radium Software Developmentに詳しい説明が。
http://www.radiumsoftware.com/0310.html#031028
定数時間で処理が終わる所が同じ。coherenceが利用できないのが問題か。何かに使えそうかもと思ってたけど、大抵の用途にはクイックソートのが速そう。

眠いので続きはまた今度。以下何描こうと思ってたか忘れないようにメモ。
IEEE754、パーティクルによる塗りつぶし、フィルレート、縮小バッファ