Mac用プロットライブラリ-21「隠面消去の問題」

こないだから突入した3次元プロットの問題点整理。前回は隠面消去がナイーブな方法では解決できないことに気がついた。ではどうするか、というところで寝てしまったので今日はその続き。

で、どうするか

この問題を解決するにはどうすればいいかいろいろ考えた。
やはり射影変換の結果のオブジェクトの座標をもつすべての点に奥行き方向の値（射影変換直前のz座標の値）を持つことにしよう。2次元に変換されたオブジェクトの頂点すべてに奥行きの値がついたことになる。その値を使って次のようなことをする。

1. 一つのオブジェクトを取り出す
2. 他のオブジェクトのうち重なって見えているものを探す
3. それらに関して奥行きの値で描画する順番を入れ替える
4. さらに次のオブジェクトを取り出して繰り返す

ということをやることにしよう。つまり、前回のZ-sort法というのをそのままやることにする。オブジェクトの数がN個あれば、これをN!回繰り返さなければならない。これはかなり重い処理になる。

この中の肝心の、奥行きの値で順番を入れ替えるということはつまり

1. あるオブジェクトが持つ頂点それぞれに関して
1. 図-8のようにその他のオブジェクトに2次元的に内包されているかどうかをしらべる
2. 内包されていた場合、そのオブジェクトの、内包している頂点位置での奥行きの値を計算する
2. 頂点すべてについて以上を行う
3. オブジェクトの役割を入れかてこんどは内包チェックをした方の頂点に対してもとのオブジェクトに内包されているかどうかをチェックする
4. 内包関係にある頂点が2点以上あった場合、同じ前後関係になっているか確認する
5. 得られた前後関係によって順番を入れ替える

としよう。あー、大変。えらいこっちゃ。

ここで、一組のオブジェクトに対して２点以上内包関係があって、それぞれの前後関係が違っているときは、すなわちオブジェクトが交差しているということになる。交差の問題は、また後で考えることにする。

前後関係を表現するための順序付け

以上の前後関係の表現はただでさえ重い処理になるが、射影変換されたすべてのオブジェクトを順序付けする必要はない。図-9の二つの射影変換されたオブジェクトは、例えばAの方が非常に遠い場合でも、表示には影響がない。

ところが図-10の場合のようにオブジェクトが重なって見えるとき、A→B→Cの順序付けをする必要が出てくる。

最初にあった二つのオブジェクトに三つ目が出現することで順序付けする必要が発生する場合もある。

オブジェクトの数が増えるとこのチェックの手間が爆発的に増大する。ところが、一般のプロットでは多くのオブジェクトが図-9のAとBのような関係になっているはずである。でなければ、例えば一列に並んだオブジェクトを先頭から眺めるような場合であるが、その場合にはあまりプロットする意味がない（先頭のオブジェクトに他が隠れてしまって見えない）はず。

半順序集合に対するソート

ということは、前後関係を決めたいオブジェクトの集合は「半順序集合」であると見なす必要がある、ということになる。 面倒な話になったみたいだけど、これは実装上はすごく重要なこと。

そもそも一般の並べ替え（ソートという）アルゴリズムは「全順序」を前提にしている。全順序とはようするに任意のふたつのオブジェクトの間に順番がつけられるということで、例えば実数の集合は2項関係「≦」に関して全順序であるが、複素数全体の集合は全順序ではない（半順序でさえないけど）。

じゃあ、半順序集合ってどんなのか、というと任意のふたつがいつも順序づけられるとは限らない集合のことで、今回の順序付けをする場合、図-10AとC、CとBには順序付けされるけど、AとBは直接順序はつけられない。wikipediaには半順序の例としてベキ集合（ある集合の部分集合全体の集合）を挙げている。ベキ集合の要素の組に対して、包含関係が成り立つ組と成り立たない組が現れる。その集合の包含関係「⊆」で順序を表す（A⊆BをA≦Bとみなす）と半順序になる。

ソートアルゴリズムではある二つの要素を取り出して順序を調べる、ということをやって全体をその順序で並べ直している。これは任意の二つの要素の間で必ず順序づけされていなければならない、つまり全順序でなければならないと言うことになる。Wikipediaにも「全順序関係を定義して一列に並べる」ことがソートである、となっている。

しかし必ずしもアルゴリズム上全順序が必須と言うわけではなく、半順序に対しても使えるアルゴリズムはあるが実装は全順序を前提にしている（たぶん。実装を全部チェックなんかできんわ）。もちろん順序が定義されていない要素が含まれている場合に最終的にどういう形で並べておくか（何らかの形で順番にならなければ線形なメモリの上に展開できない）という問題は残る。従ってどのみち半順序専用のソートルーチンを用意する必要がある。

今回のライブラリでは順序付けされるかどうかのチェックはなるべく簡単に済ませたい。つまり図-9のような場合はチェックのために面倒な計算がないようにしたい。また、ひとつひとつのチェックのたびにオブジェクトの順番入れ替えが発生するのも避けたい。

またAとBの順序はつけられないが、A→CとC→Bの順序付けがされた結果としてA→Bに自動的になるようにしたい。

さて、また、どうするか。半順序集合に対するソート（厳密にはソートとは呼ばないな。言葉尻を捕まえれば）を具体的にどうするか、その結果として普通のソートとどんな風に違うか、を考えていこう。これはこれで結構面白い話になってきたがな。めんどくさいけど楽しい。