量子レンダリング 2

by syoyo

さて、SIGGRAPH のコースで解説される量子レンダリングは、
以下の SPIE に採択された論文が元ネタのようです。

M. Lanzagorta and J. K. Uhlmann,
Multidimensional quantum data structures,
Proc. SPIE 5436, 45, April 2004.
http://vlsicad.eecs.umich.edu/Quantum/papers/

(pdf のタイトルでは quantum rendering となっているけど、いいのかな?)

本論文では、量子アルゴリズムのひとつである、
Grover の量子探索アルゴリズム


http://internet.watch.impress.co.jp/www/article/2000/0524/grover.htm

http://www.jsme.or.jp/publish/kaisi/010102t.pdf

をレンダリングアルゴリズムに用いることで、通常 O(N) のクエリ処理が
O(sqrt(N)) で行えることを示しています。

本論文では、Z-バッファ、レイトレ、ラジオシティ、LOD の
4 つの CG アルゴリズムに Grover の量子探索アルゴリズムが適用できる
ことを取り上げています。

たとえば、Z-バッファによるポリゴンレンダリングでは、
通常 N 個のポリゴンを描画する場合、ポリゴンが覆うピクセルが平均 p 個で
あるとすると、O(pN) の時間が古典的なコンピュータではかかりますが、
これが量子コンピュータと Grover のアルゴリズムを用いることで、
O(p sqrt(N)) の時間で処理できることになります。

レイトレの場合では、N 個の物体との交差判定が、
O(N) から O(sqrt(N)) で可能となるそうです。

とはいえ、実際のアプリでは、このような総当り的な処理は行われずに、
Z-バッファやレイトレでは BSP などの空間データ構造を使って、
理想的には O(logN) に比例する
時間で処理するようにしているのがほとんどですので、
量子アルゴリズムによる O(sqrt(N)) というのは、
オーダーの観点から見るとそれほどアドバンテージ
がない気がするかもしれません。

とはいえ、そもそも量子コンピュータは実現すれば
現在の古典的コンピュータの 1000 倍以上の性能にもなるそうですし、
BSP などのちまちましたテクニックを使わずとも、N 個の
クエリ処理が純粋に O(sqrt(N)) の
オーダーになることを考えると、やっぱり量子アルゴリズムはすごそうです。

そういえば、Shor の因数分解アルゴリズムなど、
いまあるもの以外に量子アルゴリズムを新たに発見すると、
ノーベル賞ものだとか…

Advertisements