クォータービューの描画順の問題(1)

世間様がGoogle Code Jam 2004で盛り上がっていたころ、うちの掲示板でクォータービューの描画順問題が話題になっていた。正直言ってGoogle Code Jamの問題よか、よっぽど難しい。難問である。しかも、これが難問であることに当初、気づきもしなかった。ちょっとその問題と解答に至るまでの手順をここに書きとどめておきたい。

まず問題の内容を説明しよう。この問題は、2D描画のみを使って擬似的にクォータービューを実現しようとするときに生じる、描画順序の問題である。2D描画では、遠くにあるものから優先して描画していく。そうすることにより、手前にあるものは最後に描画され、前後関係が正しく描画されるからである。この視点からの遠さのことを、(3Dに見立てて)Z-orderと呼ぶことがある。ここでは、この用語を採用する。

いま行ないたいのは、図に示すような、キューブ(直方体)の描画である。ただしキューブ同士はめり込む(3D的に交差する)ような位置関係には存在していないものとする。このキューブの座標が与えられたときにこの描画順序を決定するアルゴリズムを教えてくれ、というものだった。

あらかじめお断りしておくが、3Dを使えばいいヤンという意見ももちろんあるのだが、ゲームボーイのようなショボイハードでもこういうことをやりたいことが現実的に在って、やはりそのときに3Dを使わないとこの問題ができないようなゲームプログラマはゲームプログラマ失格だろう。また、あらゆるビデオカードが3D機能をハード的にアクセラレート出来るわけでもないので、3Dでやれば済むというような問題でもないのである。

またもうひとつ。内部的には3D計算を行なって、面を描画していこうという考えかた。これはこれで正しいが、あるキューブとあるキューブは交差しないことが条件として与えられているから、あるキューブとあるキューブとの前後関係は必ず決定できるわけである。それなのに面単位で描画するのではその分のオーバーヘッドの分だけ損をする。だもんで、キューブをひとつの塊と考えて、その描画順序を決定するアルゴリズムが欲しいのである。(つづく)