隠線除去

3D コンピュータグラフィックスでは、ソリッドオブジェクトは通常、多面体でモデル化されます。多面体の面は、エッジと呼ばれる直線セグメントで囲まれた平面ポリゴンです。曲面は通常、ポリゴンメッシュで近似されます。不透明なオブジェクトの線画を作成するコンピュータプログラムは、どのエッジまたはエッジのどの部分がオブジェクト自体または他のオブジェクトによって隠されているかを判断し、レンダリング中にそれらのエッジをクリップできるようにする必要があります。この問題は、隠線処理と呼ばれます。

隠線問題に対する最初の既知の解法は、1963年にLG Roberts ^[1]によって考案されました。しかし、この解法はモデルに厳しい制限を課し、すべてのオブジェクトが凸型であることを求めます。ベル研究所のRuth A. Weissは、1965年の論文でこの問題に対する1964年の解法を文書化しました。^[2] 1966年にIvan E. Sutherlandは、コンピュータグラフィックスにおける未解決の問題を10個挙げました。^[3] 7番目の問題は「隠線除去」でした。計算の複雑さの点では、この問題は1986年にFrank Devaiによって解決されました。^[4]

たとえばコンピュータ支援設計のモデルには、数千または数百万のエッジが含まれることがあります。したがって、リソース要件 (時間やメモリなど) を問題のサイズの関数として表す計算複雑度のアプローチが重要です。時間要件は、インタラクティブシステムでは特に重要です。

隠線処理の問題の大きさは、モデルのエッジの総数 $n$ とエッジの可視セグメントの総数 $v$ である。可視性はエッジの画像の交差点で変化する可能性がある。エッジの画像の交差点の総数を $kで$ 表すとしよう。最悪の場合、 $k = Θ(n 2)かつ$ $v = Θ(n 2)$ となるが^[4]、通常は $v < k$ である。

アルゴリズム

1984 年以前に公開された隠線処理アルゴリズム^[5]^[6]^[7]^{[8] は}、エッジをその画像の交点で線分に分割し、各線分がモデルの各面に対して可視かどうかをテストします。多面体の集合のモデルを想定し、各境界は位相的に球に等しく、面は位相的に円板に等しくなるようにすると、オイラーの公式によれば、Θ( n ) 面があります。Θ( n ² ) 線分を Θ( n ) 面に対してテストするには、最悪の場合でもΘ( n ^{3 ) 時間がかかります。}^[4] Appel のアルゴリズム^[5]も不安定です。可視性のエラーが後続の線分の端点に伝播してしまうためです。^[9]

OttmannとWidmayer ^[10] およびOttmann、Widmayer、Wood ^[11]は、O (( n + k )log2n ^)時間の 隠れ線アルゴリズムを提案した。その後 、 Nurmiは実行時間をO (( n + k )logn  )に改良した[ 12 ^]。これらのアルゴリズムは、最悪の場合、それぞれΘ(n2log2n)、Θ(n2logn)時間かかるが^、 kが2 乗 より小さい^場合は^、実際にはより高速になる可能性がある。  

あらゆる隠れ線アルゴリズムは、最悪の場合、n辺上のΘ( n )個の隠れ区間の和集合を決定する必要がある。Ω( nlogn ) は n区間の和集合を決定するための下限値であるため、^[13]、達成できる最善の時間はΘ(n2logn)個の最悪ケース時間であることが期待でき、したがって^ヌルミ の アルゴリズムが最適である。

しかし、log  n係数はDevai ^[4]によって排除され、彼は、同じ最適なO ( n ² )上限が隠面除去に対して存在するかどうかという未解決問題を提起した。この問題は1987年にMcKennaによって解決された。^[14]

交差感度アルゴリズム^[10]^[11]^[12]は主に計算幾何学の文献で知られてい ます 。二次の上限はコンピュータグラフィックスの文献でも高く評価されています。Ghaliは^[15]、 DevaiとMcKennaのアルゴリズムは「可視性アルゴリズムのマイルストーンを表している」^{と指摘し、}nエッジのシーンを処理するための理論的な障壁をO(n2logn)から^O( n2 )に打ち破りました。

^{Devai [4]}によって提起されたもう一つの未解決問題は、O ( n  log  n + v ) 時間の隠れ線アルゴリズムが存在するかどうかという問題であり、ここでv は前述のように可視線数であるが、執筆時点ではまだ解決されていない。

並列アルゴリズム

1988年にDevaiは、同時読み取り、排他的書き込み（CREW）並列ランダムアクセスマシン（PRAM）計算モデルの下で、n 2プロセッサを使用して隠れ線問題を解くO（log n）時間の並列アルゴリズムを提案^した[16]。プロセッサ数と実行時間の積が問題の逐次複雑度Θ（n 2）よりも漸近的に大きいため、^このアルゴリズムは作業最適 ではない^が、隠れ線問題が複雑度クラスNCにあること、つまり多項式数のプロセッサを使用して多重対数時間で解けることを証明している。

隠面アルゴリズムは隠線除去に使用できますが、その逆はできません。ReifとSen [ ^{17]は、多面体地形の制限されたモデルに対して}O (( n + v )/logn  ) CREW PRAMプロセッサを使用して、隠面問題に対するO (log4n ⁾ 時間アルゴリズムを提案しました。ここでvは出力サイズです。

2011年にDevaiはO(log n)時間の隠れ面アルゴリズムと、より単純なO(log n)時間の隠れ線アルゴリズム[18]を発表しました。n 2  / log n CREW  PRAMプロセッサを使用する隠れ面アルゴリズムは^、作業最適化 されています ^。

隠線アルゴリズムは、n ^{2 個}の排他的読み取り、排他的書き込み (EREW) PRAM プロセッサを使用します。EREW モデルは、実際のマシンに最も近い PRAM バリアントです。隠線アルゴリズムはO ( n ²  log  n ) の作業を行います。これは、実際に使用される最良の順次アルゴリズムの上限です。

Cook、Dwork、Reischukは、同時書き込みのない任意のPRAMのプロセッサ数を無制限に許容するn個の整数の最大値を見つけるためのΩ(log  n )の下限を与えました。 ^[19]n個の整数の最大値を見つけることは、 n個のプロセッサを使用することで、隠れ線問題に定数時間で還元できます。したがって、隠れ線アルゴリズムは時間最適です。^[18]

参照

バックフェースカリング

参考文献

^ LG Roberts. 3次元立体の機械認識。マサチューセッツ工科大学博士論文、1963年。
^ Ruth A. Weiss BE VISION、平面と二次曲面の組み合わせの正投影図を描く IBM 7090 FORTRAN プログラムパッケージ
^ IEサザーランド。コンピュータグラフィックスにおける10の未解決問題。Datamation 、 12(5):22–27、1966年。
^ abcde F. Devai. 隠線消去の二次境界。Proc . 2nd Annual Symp. on Computational Geometry、SCG '86、pp. 269–275、ニューヨーク、NY、米国、1986年。
^ ab A. Appel. 定量的不可視性の概念と立体の機械レンダリング。第22回全国会議論文集、ACM '67、pp. 387–393、ニューヨーク、ニューヨーク、米国、1967年。
^ R. ガリンベルティと U. モンタナリ。隠線処理のアルゴリズムです。共通。 ACM、12(4):206–211、1969 年 4 月。
^ Ch. Hornung. 計算を最小化する隠れ線アルゴリズムへのアプローチ。Computers & Graphics、6(3):121–126、1982年。
^ PP Loutrel. コンピュータ描画多面体の隠線問題の解決法IEEE Trans. Comput ., 19(3):205–213, 1970年3月。
^ JF Blinn. フラクショナルインビジビリティ。IEEE Comput. Graph. Appl ., 8(6):77–84, 1988年11月。
^ ab Th. Ottmann および P. Widmayer。スケルトン構造を使用した可視性問題の解決。Proc . Mathematical Foundations of Computer Science 1984、pp. 459–470、ロンドン、英国、1984 年。Springer-Verlag。
^ ab Th. Ottmann、P. Widmayer、およびD. Wood。最悪ケースの効率的な隠線除去アルゴリズム。Internat。J . Computer Mathematics、18（2）：93–119、1985年。
^ ab O. Nurmi. 隠線除去のための高速ラインスイープアルゴリズム。BIT 、 25:466–472、1985年9月。
^ ML FredmanとB. Weide。U[a _i , b _i ]の測定を計算する複雑さについて。Commun . ACM、21:540–544、1978年7月。
^ M. McKenna. 最悪ケースの最適隠面除去。ACM Trans. Graph.、6:19–28、1987年1月。
^ Sh. Ghali. 実用的なオブジェクト空間可視性アルゴリズムの調査。SIGGRAPHチュートリアルノート、1(2)、2001年。
^ F. Devai. O (log  N ) 並列時間厳守の隠線アルゴリズム。Advances in Computer Graphics Hardware II、pp. 65–73、1988 年。
^ JH Reif および S. Sen. 効率的な出力に敏感な隠れ面除去アルゴリズムとその並列化。Proc . 4th Annual Symp. on Computational Geometry、SCG '88、pp. 193–200、ニューヨーク、NY、米国、1988 年。
^ ab F. Devai。最適な隠面アルゴリズムとその並列化。計算科学とその応用、ICCSA 2011、コンピュータサイエンスの講義ノートの第6784巻、pp 17-29。Springer Berlin/Heidelberg、2011年。
^ S. Cook、C. Dwork、および R. Reischuk。同時書き込みのない並列ランダムアクセスマシンの時間上限と下限。SIAM J. Comput .、15:87–97、1986 年 2 月。

外部リンク

Patrick-Gilles Maillot の論文は、 3D 隠線除去を実行するためのBresenham 線描画アルゴリズムの拡張であり、CAD/CAM およびコンピュータグラフィックスに関する MICAD '87 議事録、591 ページ、 ISBN 2-86601-084-1にも掲載されています。
ベクトル隠線除去、Walter Heger による記事。詳細な説明 (病的なケース) とより多くの引用が含まれています。

[1] LG Roberts. 3次元立体の機械認識。マサチューセッツ工科大学博士論文、1963年。

[2] Ruth A. Weiss BE VISION、平面と二次曲面の組み合わせの正投影図を描く IBM 7090 FORTRAN プログラムパッケージ

[3] IEサザーランド。コンピュータグラフィックスにおける10の未解決問題。Datamation 、 12(5):22–27、1966年。

[Devai86-4] F. Devai. 隠線消去の二次境界。Proc . 2nd Annual Symp. on Computational Geometry、SCG '86、pp. 269–275、ニューヨーク、NY、米国、1986年。

[Appel67-5] A. Appel. 定量的不可視性の概念と立体の機械レンダリング。第22回全国会議論文集、ACM '67、pp. 387–393、ニューヨーク、ニューヨーク、米国、1967年。

[6] R. ガリンベルティと U. モンタナリ。隠線処理のアルゴリズムです。共通。 ACM、12(4):206–211、1969 年 4 月。

[7] Ch. Hornung. 計算を最小化する隠れ線アルゴリズムへのアプローチ。Computers & Graphics、6(3):121–126、1982年。

[8] PP Loutrel. コンピュータ描画多面体の隠線問題の解決法IEEE Trans. Comput ., 19(3):205–213, 1970年3月。

[9] JF Blinn. フラクショナルインビジビリティ。IEEE Comput. Graph. Appl ., 8(6):77–84, 1988年11月。

[Ottmann1-10] Th. Ottmann および P. Widmayer。スケルトン構造を使用した可視性問題の解決。Proc . Mathematical Foundations of Computer Science 1984、pp. 459–470、ロンドン、英国、1984 年。Springer-Verlag。

[Ottmann2-11] Th. Ottmann、P. Widmayer、およびD. Wood。最悪ケースの効率的な隠線除去アルゴリズム。Internat。J . Computer Mathematics、18（2）：93–119、1985年。

[Nurmi-12] O. Nurmi. 隠線除去のための高速ラインスイープアルゴリズム。BIT 、 25:466–472、1985年9月。

[13] ^ ML FredmanとB. Weide。U[a _i , b _i ]の測定を計算する複雑さについて。Commun . ACM、21:540–544、1978年7月。

[14] M. McKenna. 最悪ケースの最適隠面除去。ACM Trans. Graph.、6:19–28、1987年1月。

[15] Sh. Ghali. 実用的なオブジェクト空間可視性アルゴリズムの調査。SIGGRAPHチュートリアルノート、1(2)、2001年。

[16] F. Devai. O (log  N ) 並列時間厳守の隠線アルゴリズム。Advances in Computer Graphics Hardware II、pp. 65–73、1988 年。

[17] JH Reif および S. Sen. 効率的な出力に敏感な隠れ面除去アルゴリズムとその並列化。Proc . 4th Annual Symp. on Computational Geometry、SCG '88、pp. 193–200、ニューヨーク、NY、米国、1988 年。

[Devai11-18] F. Devai。最適な隠面アルゴリズムとその並列化。計算科学とその応用、ICCSA 2011、コンピュータサイエンスの講義ノートの第6784巻、pp 17-29。Springer Berlin/Heidelberg、2011年。

[19] S. Cook、C. Dwork、および R. Reischuk。同時書き込みのない並列ランダムアクセスマシンの時間上限と下限。SIAM J. Comput .、15:87–97、1986 年 2 月。