Mac用プロットライブラリ-23「隠面消去特有の問題と非循環有向グラフ」 [考え中 - プロットライブラリ]
3次元プロットのための隠面消去をいかに実装するか、と言う問題をしばらく考えている。前後関係をハッセ図に描ければ、Z-Sort法(奥にあるオブジェクトから描いて手前のオブジェクトを上描きしていく)で隠面消去が可能になるのでその方針で考えている。
わざわざ半順序集合だのハッセ図だの持ち出して、無理矢理難しい話にするつもりなわけではない。しかし、数学に現れる概念と同じに見なせるものがあれば、その周辺のいろいろな定理や特徴をそのまま流用することができる。非常に便利なのでちょっと行き詰まると数学の、特に代数と数論まわりで似たものがないか探すのが癖になっている。似ているだけで役に立たないこともあるけど、単に名前を流用するだけでも(名前をつけるのは大切なのに、なんとつけるかはいつも困るので)有益と言える。
ところがそこのちょっとした問題が...さて困った。
さて問題とは、オブジェクトの前後関係を表すハッセ図の特徴として
- 独立した複数のハッセ図になる場合がある
- 最大元、最小元、あるいはその両方が存在しない場合がある
一つ目は例えば図-13のようなオブジェクトの場合、
対応するハッセ図は図-14のようになる。
つまりハッセ図が一つに繋がらないで分かれてしまう。
また、最大元最小元は、例えば図-15のようなハッセ図の場合、
最大元と最小元のどちらもない。もし再帰(リカーシブコール)を使うなら、最大元がないことは問題にならないが、最小元がないのは問題で、つまりどのオブジェクトから描き始めればいいのか決められない、ということになる。
それを解決するためには、例えば
- 「誰にも踏まれていないオブジェクト」を一度走査して探す
- 「カメラそのもの」をオブジェクトに含める
一番目の方法は「踏まれ回数」みたいな変数を持っていて、線が引かれるたびにその変数をインクリメントする。線を引き終わった後、その変数が「0」のものから描き始める、というものである。
この方法は余分な変数が必要なのと、余分な走査が必要な点がデメリットとなるが、実装は簡単である。
また2番目の方法は、カメラそのものよりカメラに近いオブジェクトは無いので常に最小元となることが保証されて、しかもそこからすべてのオブジェクトをたどることができる(たどれないオブジェクトは表示されない)はずである。
しかしそうすると、さっき軽く流してしまった「線を引くときの微妙な問題」がクローズアップされることになる。
先に示したアルゴリズムでは図-16のような二つの配置
は図-17のように区別されてしまう。
微妙な問題と言うのは、推移則、つまり
から
となるが推移則に対応する線は引かない、ということになってる。
実装上は引かれた線すべてについて自分が踏んづけているオブジェクトが描かれるまで自分自身を描くのを保留することになるので、推移則に対応する線があってもなくても結果は変わらない。しかし保留すると言うことは保留が解けるまでスタックに居続けることになるので線が多いとスタックを消費してしまう。
もしオブジェクトにカメラそのものを含めると、まず最初にカメラからすべてのオブジェクトに線が引かれることになる。
この方法も、推移則に対応する線を消去する簡単なアルゴリズムを思いつかないかぎり、オブジェクトを走査するのよりもかえって時間がかかる可能性がある。
「カメラそのもの」の発想は面白いので何か考えたいと思うけど、いいアイデアが浮かばないのでとりあえずオブジェクトを走査する方法を実装では採用することにする。
コメント 0