床井研究室

■ 2010年01月11日 - ラスタライザ野郎の独り言

余談が長い

実は学生さん向けに GLSL でレイキャスティングのサンプルを作ったのだが、その説明を書いているうちに余談の部分が異様に長くなってしまったので、先にこちらを掲載することにした。これは学生さん向けではなく自分の独り言なので、文体がいつもと異なっている。また、思い出の部分は 26 〜 27 年前の記憶をもとに書いているので、正確ではない。加えて、私はコンピュータのアーキテクチャの知識を持っていないので、おそらく思い込みや間違いを含んでいる。もしかしたらむちゃくちゃ書いているかも知れないので、間違いがあれば指摘して頂けるとありがたい。

Links-1 をこの目で見たのは、六本木の防衛庁 (当時、跡地は東京ミッドタウン) の向かいのビルの地下だったと思う。オープンなラックに積み上げるように組み立ててあって、そこを何台かの扇風機が首を振りながら煽っていた。Links-1 によるレンダリングを見せてもらって驚いた。当時、自分はスキャンライン法のソフトウェアを作っていたのだが、それは画面の上から下に絵を描いていった。レイトレーシングも普通は左上の画素から順に色を付けていっていたから、絵は上から徐々に出てきた。ところが Links-1 は、画面の「左から右」に画素を染めていった。各走査線が徒競走のように先を争って左から右に伸びていった。そして一つの走査線が右端に達するたびに、残りの走査線の伸びがどんどん速くなっていった。鮮烈だった。余談だが、実はこのあいだ、初めて東京ミッドタウンに行った。だが、自分が昔このあたりに来たことがあることに、その時は全然気づかなかった。つくづく、時の流れというものは…

並列コンピュータ

Links-1 は並列コンピュータだ。もともと CG 用に開発されたわけではなかったという印象があるが1、レイトレーシング法はその能力を示すアプリケーションとして最適なものだったのだろう。CPU 間の通信には、最初 RS-232C を使ったと説明された記憶がある。さすがにそれは使い物にならないので、この時点では確かバンク切り替えのような方法でメモリを共有していたように思う。しかし、実際に Links-1 で最高の性能を出そうと思うと、結局すべての CPU のローカルメモリに同じコードとデータを保持しておく必要があった。こうすれば、CPU 間の通信は制御用の CPU から処理すべき画素を受け取ることと、その画素の処理完了を制御用の CPU に通知することだけになる。横断的なメモリの参照は、現在でも並列コンピュータのアーキテクチャ上の課題になっている。ある CPU が他の CPU が管理するメモリを参照することは、他の CPU の足を引っ張り、自分の足をも引っ張ってしまう。また複数の CPU がキャッシュを介して単一のメモリにアクセスする共有メモリ方式の場合は、スヌーピングによりキャッシュの一貫性を維持するトラフィックの増大や、共有メモリへのアクセスにおける競合の発生により、並列度を大幅に上げることができない。メモリを CPU ごとに分散させれば、各 CPU は自分の仕事に専念しやすくなる。分散したメモリに効率的にアクセスするために、過去には Connection Machine や nCUBE のように、CPU 間の接続に特殊なネットワークを用いたものが提案されたこともあった。しかし、このようなアーキテクチャは現在使われていない (と思う)。

現在の主流は汎用的な CPU を使ったクラスター型のシステムやグリッド型のシステムである。だが、いかなるインターコネクトも CPU の速度に比べれば遥かに遅い。このため、これらもあらかじめコードやデータのコピーをばらまき、書き込みに制限を加えるなどしてコピー間の矛盾の発生を抑制しながら、それぞれの CPU が他の CPU に煩わされること無く自分の仕事に専念できるようプログラムする必要がある。この点は Links-1 の時代からあまり進歩が無いように思える。PlayStation 3 の CPU である Cell も、個々の SPE がローカルストアと呼ばれるメモリを保持している。ここにメインメモリからコードやデータを明示的にコピーすることにより、キャッシュの一貫性を維持するコストを省き、SPE は自分の仕事に専念することができる。しかし、このとき他の SPE のローカルストアにアクセスすることはできない。同様に GPU も、シェーダプログラムは実行中に他のシェーダプログラムの処理内容について一切関知することは無い。このような特性により、並列コンピュータにおけるプログラミングでは、単一 CPU のプログラミングとは異なる配慮が必要になる。例えば、従来当たり前のようにプログラムの各所に現れていた「合計を求める処理」ですら、並列コンピュータの性能を殺さずに実装するために、アーキテクチャに依存した独特なテクニックが必要になることが多い。例えばデータを共有メモリ上に置いた場合、共有メモリを半分ずつに区切って重ね合わせる処理を再帰的に繰り返すことにより、理論上は $O(\log N)$ の計算量で合計を求めることができる。しかし、共有メモリへのアクセス自体のコストが高い上に、複数の CPU が共有メモリに同時にアクセスした場合、競合によって多くの CPU がブロックされてしまうことも予想される。このように CPU とメモリとの間に横たわる問題は、これまでも、そしてこれからも、呪いのように人々の頭を悩ましている。HPC, すなわちスーパーコンピュータにおいてさらに先を目指すには、やはりこの部分に何らかのブレークスルーが必要なのではないかと考えている。そして、少なくともそれは、汎用の CPU を並べることによって見つかるものではない気がしている。

リアルタイムレイトレーシング

CPU 自体の高速化や SIMD 命令の実装、マルチコア化、およびプログラム可能な GPU の登場によって、従来オフラインレンダリングでしか用いられてこなかったレイトレーシング法を、リアルタイムレンダリングに応用しようとする流れが発生した。既にいくつかのプロジェクトが有意義な成果を得ているほか、NVIDIA の OptiX のように API として整備されたものも存在する。この流れにより、リアルタイムレンダリングのアルゴリズムが OpenGL や Direct3D が採用しているデプスバッファ法からレイトレーシング法に移行するという予測もある。ここで少し、これについて考えてみたい。ただし、レイトレーシング法は反射や屈折を含む大域照明に対応するアルゴリズムなので、デプスバッファ法などと比較するために、ここでは視点から直接放出された第一世代の視線のみを扱うレイキャスティング法を対象にする。レイトレーシング法 (レイキャスティング法) がリアルタイムレンダリングに応用可能であるとした根拠は、レイトレーシング法の計算量が空間分割などの効率化手法により、データ量に対して $O(1)$ とすることができる点にある。このことは、国内ではインテグラを設立された 藤本 彰 氏によって、1983 年頃に示されていた (と思う)。

これに対して、デプスバッファ法などのラスタライズベースのアルゴリズムの計算量は、一般にデータ量に対して $O(N)$ となる。CPU や GPU の性能向上や、シーンの品質を向上するためにデータ量が爆発的に増大している現状を考えると、現実はこの二つのグラフが逆転する点を既に超えている可能性がある。ただし、これはあくまで理想的な場合である。実際にこの性能を得るには、レンダリングの前にシーンを空間分割する必要がある。そのコストはシーンのデータ量に対して $O(N)$ である。実は空間分割は、シーンの空間的なラスタライズと同等な (干渉) 問題である。等分分割すなわちボクセライズはラスタライズそのものだし、八分木の作成も画面を再帰的に四分割する Warnock のアルゴリズムと同等である。BSP 木も k-d 木も本質はこれと変わらない。シーンに変化が無ければ続くフレームのレンダリングの際に以前の空間分割の結果を再利用できるが、シーンが動的に変化した場合は空間分割をやり直さなければならない。シーンの動的な変化への対応はリアルタイムレンダリングに当然要求される事項である。さらにデータ量が非常に増えた場合、同一の部分空間に複数のオブジェクトが存在する状況が増えるため、交差判定の回数がデータ量に依存するようになる。以上によりレイキャスティング法のグラフは、実際には少し右上がりになっている。この傾きがラスタライズベースのアルゴリズムに対して緩やかであることの実証を、今のところ私は知らない (単に知らないだけで、あるのかも知れない)。私にはラスタライズベースのアルゴリズムの計算量が、空間分割のアルゴリズムに対して無視できないほど大きいという実感はない。このように考えた場合、二つのグラフが逆転する点は、もう少し先にあるような気がする。

デプスバッファ法の速度

もう一つ考えておきたいことがある。そもそも、この予測でレイキャスティング法の比較対象としているデプスバッファ法は、そんなに速いアルゴリズムなのだろうか。ハードウェアで実装されるようになってからつい忘れてしまいがちになるが、ラスタライザをソフトウェアで実装していた時代の人は、デプスバッファ法がとても遅いアルゴリズムだということを知っていたはずではないだろうか。今度は画面の解像度 (画素数) に対する、可視面判定の計算量について考えてみる。最もシンプルな可視面判定アルゴリズムであるデプスソート法 (ペインタアルゴリズム) は、いくつかの問題点や制限があるにせよ、可視面判定に限れば計算量は解像度に依存しない。すなわち、計算量は $O(1)$ である。可視面判定は本来そういう性質を持つものだと考える。ところが、デプスソート法の問題を回避するために画面を分割して処理する手段が導入されてから、可視面判定の計算量が画面の解像度に依存するようになった。それでも画面を再帰的に四分割する Warnock のアルゴリズムで $O(\log N)$ であり、北海道大学の 山本 強 先生が開発された四分木 dZ バッファ法も同じく $O(\log N)$ だと予想される。また、画面を走査線単位に分割して処理する (スパニング) スキャンライン法の計算量は、画面の走査線数に比例し走査線上の画素数には依存しないので、画面の解像度に対しては $O(\sqrt{n})$ になる。さらにスキャンライン法は、シーンがポリゴンの交差を含まないなら、走査線間の一貫性 (コヒーレンシ) を利用することにより、これを $O(1)$ に近づけることができる。これらに対してデプスバッファ法やレイキャスティング法の計算量は、画面の解像度に対して $O(N)$ である。レイキャスティング法 (レイトレーシング法) では、サンプリング間隔を適応的に間引くことで高解像度化による速度低下を低減させることができるが、処理時間が画面の解像度に比例することに変わりはない。

デプスバッファ法の遅さの原因の一つは、並列コンピュータの問題と同じところにあるように思う。デプスバッファによる可視面判定を高速化するためにデプスバッファの更新処理を並列化しようとしても、デプスバッファの内容が他の更新処理の結果に依存するためにスループットが上がらないということが起こりえる。デプスバッファの更新処理を担当する ROP (Rendering Output Pipeline) ユニット (あるいはレンダーバックエンド) は、実際には担当する画素を占有するため、個々の画素の更新処理は逐次的に行なわれる。デプスバッファ法の処理速度は、デプスバッファという共有メモリによって律速されてしまうのである。これを避けるために、ROP ユニット群とデプスバッファの間は通常非常に広帯域のバスで結ばれている。実際、GPU の内部バス幅は上位の高性能なものほど広くなっている (テクスチャフェッチを高速化する目的もある)。しかし、これは GPU のロジックを複雑化しシリコンの面積と消費電力を増大させる要因でもある。PowerVR は画面の分割 (タイリング) により処理対象の領域 (チャンク) をローカルメモリのように扱うことで、消費電力の低減と実効性能の向上を果たしていると思われる (実は良く知らないので推測)。この他の GPU でも、デプス圧縮や階層化デプスバッファなどの手法により、デプスバッファへのデータ転送量を削減して高速化を実現している。デプスバッファ法にはもう一つ問題がある。デプスバッファ法は既にフレームバッファ (デプスバッファ、カラーバッファ、他の集合体) に書き込んだ内容に後から上書きすることで、最終的な可視面を残すという手法である。したがって、品質を上げるために高いコストをかけてカラーバッファに書き込んだ内容であっても、表示されないと判定されれば、単に破棄されてしまう。この無駄を回避するため、すべての可視面を判定した後に陰影を求めてカラーバッファに書き込む遅延レンダリングという手法が提案されている。

ソフトウェアラスタライザ

一方、このようなデプスバッファ法の問題を避けるために、デプスバッファを使わないという選択肢も存在する。例えばスキャンライン法ではデプスバッファは不要だし、映像信号のタイミングに合わせて画像を生成するようにすればカラーバッファすら不要になる。画面のリフレッシュレートは 60Hz あれば充分なので (ゲームのレスポンスを上げるために V-Sync を無視して fps を必要以上に上げる場合があるが、これは表示されない映像を生成するだけで無意味な手法である)、これに追従できる速度で逐次処理を進めていけばよい。これに広帯域の内部バスは不要であり、「ピクセルフィルレート」などの指標は意味を持たない。有限のフレームバッファに際限なくデータを書き込むデプスバッファ法のアプローチには無駄が多すぎる。既にバーテックスシェーダやフラグメント (ピクセル) シェーダはプログラム可能となった。最近ではジオメトリシェーダに始まりハルシェーダやドメインシェーダ、果てはコンピュートシェーダなど様々なシェーダステージが追加され、GPU がいったい何をするものなのか訳が分からない状態になってきている。しかし、ここに来てもなおラスタライザ (とクリッパ) は固定ハードウェアのままである。GPU に残されたプログラム可能化の余地は、おそらくこの部分しか無い。インテルが Larrabee においてソフトウェアラスタライザを採用すると発表したのを聞いて、ついにこの部分までプログラム可能となるかと期待したのだが、現実には環境がそこまでに詰まっていなかったのか、先送りにされてしまった。現在使われているシェーダのプログラミングモデルはデプスバッファ法を想定したものであり、スキャンライン法などその他のアルゴリズムにうまく馴染まない。ソフトウェアでラスタライザを実装するとき、その仕様が (デプスバッファ法を前提としてきた) シェーダのプログラミングモデルに制限されることを恐れたのかも知れない。あるいは単にデプスバッファ法では期待したパフォーマンスが出なかったのかも知れない。これは勝手な想像である。

このようにデプスバッファ法は遅いアルゴリズムである。それが GPU における可視面判定の手法として使われ続けている理由は、ひとえにそれが簡単だからである。簡単だからこそ、初期のグラフィックスハードウェアにおいて可視面判定 (隠面消去処理) の手段として採用されたのである。単にそれが今も引き継がれており、その上にいろんなものを乗せてしまったために、今更変更が利かないというだけだと思っている。同様にレイトレーシング法が高品質な画像を生成するための手段として利用されるのも、簡単だからである。簡単だからこそ、複雑な光学現象の再現や、曲面や雲など多様な形状のレンダリングが可能になる。しかし、高品質な画像を生成することが、即座にレイトレーシング法に結びつくとは思わない。例えば、古くからあるが今も高品質な映像制作に使用されている PhotoRealistic Renderman (あるいは Reyes) は、レイトレーシング法が基本ではない。また、これも古いソフトだが、ElectricImage 3D というレンダラもスキャンライン法がベースだった。確かに、現在使われている商用の高品質レンダラは Mental Ray をはじめレイトレーシングベースのものがほとんどだが、LightWave 3D のレンダラのようにハイブリッドなものも存在する (あれはあれで無駄が多いのだけど)。

高品質なリアルタイムレンダリングを目指すとき、効率的になったレイトレーシング法はその手法として有力な候補のひとつだと思うが、選択肢はそれだけではない。要は、要求される品質と性能を満たす最適な手法を選ぶことにある。そして、そのときに OpenGL や Direct3D などは、映像生成のための API としての意味をほとんど持たなくなるだろう。プログラム可能なシェーダを選んだ時点で、我々はお仕着せの API を使うのをやめて、自分で作ることに決めたのだ。GPU を汎用のプロセッサとして扱い、そこにソフトウェアでレンダリングアルゴリズムを実装することになれば、そこで何をするのかは我々の手にゆだねられている。

  1. CG 用でした。(2026 年 8 月 29 日 追記) ↩