（本文）ポリゴンによって表現された3次元モデルを高速に画面に表示する技術はコンピュータグラフィックスにおいて基幹をなすものであり，長年にわたって研究されてきたテーマの一つである．

中でも，複雑な構造を持つ機械モデルや建築モデルの内部を透視したり，着目する部品を強調するために他の部分を透過性にしたりする場合に，それら透過部分のポリゴンを半透明にして表示する技術が必要となる．そして，雲や霧，水，ガラス製品，光の効果などコンピュータグラフィックスで扱われる多くのオブジェクトの表示に半透明ポリゴンが用いられることが多い．

これら半透明なポリゴンを多数含むシーンにおいて視点をリアルタイムに移動させながら画面へのモデル表示を行うには，毎フレームごとに視点から見たポリゴンどうしの前後関係を高速に求める必要がある．

従来，前処理としてポリゴンを2分木状に構造化しておくことで，正確な前後関係を求める方法が広く利用されてきた．しかし，視点位置が変わるたびに，木のすべてのノードを探索する必要があるこれらの従来手法においては，面数に比例して探索時間が増大するため，大規模なモデルではリアルタイムな処理が困難となる．そこで，様々な高速化手法も試みられてきたが，一般に探索時間と木のサイズとはトレードオフの関係にあり，メモリコストを現実的な値に抑えながら高速化を実現することがこれまでの課題であった．

本研究では，ポリゴンどうしの遮蔽状態と視点位置との関係を厳密に評価することで，処理時間とメモリコストの両方を大きく低減する新しい手法を提案する．

大きく分けて4つの手法が提案されるが，それぞれに対象とするモデル形状や面数，利用場面等に応じた特性を有する．いずれの手法においても，今日一般に用いられるポリゴンモデルに適用したとき，従来手法よりも高速かつ少ないメモリで実現可能であることを実験と理論により示す．

福重真一（ふくしげしんいち）提出の本論文は「優先順位アルゴリズムによる可視面決定に関する研究」と題し、全9章よりなり、モデルを構成するポリゴンを視点に対して前にあるものから順に並び替える、という優先順位アルゴリズムに関する問題を扱っている。

第1章では、本研究の解決すべき課題、特に半透明ポリゴンを多数含むようなポリゴンモデルのリアルタイムレンダリングに関わる問題について説明し、本研究の目的と提案する4つの手法の概要および本研究の構成について述べた。

第2章では、優先順位アルゴリズムを中心とした可視面決定に関する先行研究について解説し、特に今日最も広く用いられている優先順位アルゴリズムであるBSP法とその問題点について述べた。また、本研究が目的の一つとしている半透明ポリゴンの描画についてその原理の説明を行った。

第3章では、視点が与えられたときにポリゴン間に生じる遮蔽関係、およびこの遮蔽状態と視点位置との関係について考察し、遮蔽関係が生じる視点領域の求め方を示した。また、ポリゴンの裏面消去が有効な場合に成り立つ“視点に依存しないポリゴン間の優先順位関係” について考察し、任意のポリゴンの組み合わせに対してこの優先順位関係を効率的に判定する方法を提案した。更に、これら2つの関係を用いた遮蔽関係リストおよび優先順位リストの概念を提案し、優先順位アルゴリズムが与えられた視点に対する遮蔽関係リストを求める問題に帰着されることを示した。

第4章では、3次元ボロノイ図によって、ポリゴンの集合をクラスタリングすることによって、デプスソートをクラスタ単位で高速に行うアルゴリズムを提案した。また、視点とボロノイ母点との距離によって各ボロノイ領域間の遮蔽関係を表現できることを証明した。この性質を用いることで、従来のデプスソート法では遮蔽関係に破綻が生じることがあったのに対し、正しい遮蔽関係を与える空間分割の方法を示し、この問題を解決することが出来た。

第5章では、与えられたポリゴンの集合から単一のリスト構造を構成し、視点位置に応じてリストの一部を並び替えることで視点に対するポリゴンの前後関係を効率的に求めるアルゴリズムを提案した。BSP法が毎フレームごとに木の全てのノードを再帰的に探索する必要があるのに対し、提案手法では表裏判定に必要なポリゴンのみによる判定を行い、更新の必要があるリストの一部のみを逐次的に入れ替えていくことで、1フレームあたりのソーティング処理を高速化した。同時にBSP法においては多数発生するポリゴンの切断回数を提案手法によって大きく低減し、出力ポリゴン数の増加およびそれに伴う処理時間の増大を抑えることを示した。

第6章では、ポリゴン間の遮蔽状態と視点位置との関係を厳密に評価することで、BSP木の持つ冗長性を排した新しい2分木構造を提案し、この2分木を用いることで、木のルートからリーフまでを1回たどるのみで全てのポリゴン間の遮蔽関係を求めることを可能とするアルゴリズムを提案した。

第7章では、与えられたポリゴンの集合から遮蔽関係に基づいて円環状に連なったデータ構造を構成し、任意視点から見たポリゴンの前後関係を円環列を一巡するだけの一回のパスで求めるアルゴリズムを提案した。あらかじめポリゴンモデルの周囲に有限個のview cellを配し、各cellの中心から見たポリゴンの優先順位を単一の円環構造として保持しておくことにより、視点位置が変化するたびに必要であった並び替え操作そのものをなくし、近似的にではあるが視点に対する遮蔽関係リストを高速に得ることが可能となることを示した。

第8章では，本研究において提案した4つの手法を互いに比較し、特に速度面とメモリコスト面およびアルゴリズムの安定性に着目した総合的な評価を行った。その結果、いずれの手法においても、今日一般に用いられているポリゴンモデルに適用したとき、従来手法よりも高速かつ少ないメモリで実現可能であることが分かった。また、提案手法それぞれについて、理論面からの考察も行い、その特長を明らかにした。

第9章では、本研究の結論と今後の展望について述べた。

以上を総括すると、本研究では、ポリゴンどうしの遮蔽状態と視点位置との関係、また視点位置には依存しないポリゴン間の優先順位関係の概念を導入し、これらの関係を用いて処理時間とメモリコストを共に既存手法よりも低減させる新しい優先順位アルゴリズムの提案を行った。特に、数十万面以上のポリゴンからなる半透明モデルを高速に表示することを可能とし、コンピュータグラフィックスにおけるモデル表示の分野において大きな貢献を行った。

よって本論文は博士（工学）学位請求論文として合格と認められる。