CGプログラミングで前のポリゴンに隠れているポリゴンをレンダリングしない方法はありますか？

質問

CGのレンダリングの質問です。

カメラが座標（-10,0,0）から(0,0,0)を見ています。
そのときに3角形AとBがあり、それぞれの頂点が：
A(0,0,0)(0,0,10)(0,10,0)
B(2,0,0)(2,0,3)(2,3,0)
となってBがAに隠れています。

簡単なOPENGLのプログラムでは：
glBegin(GL_TRIANGLES); // draws triangle
glVertex3f(0.0f, 0.0f, 0.0f);
glVertex3f(0.0f, 0.0f, 10.0f);
glVertex3f(0.0f, 10.0f, 0.0f);
glEnd();
glBegin(GL_TRIANGLES); // draws triangle
glVertex3f(1.0f, 0.0f, 0.0f);
glVertex3f(1.0f, 0.0f, 5.0f);
glVertex3f(1.0f, 5.0f, 0.0f);
glEnd();

gluLookAt(-10.0,0.0,0.0, //Where should the camera locate
0.0,0.0,0.0,//Where to look at
0.0,0.0,1.0); //Which is up in CG
...
となるのですが。

今回のようにポリゴンが2つで済む時にはすべてをレンダリングしてもなんともないのですが、私のプログラムでは複雑に配置されたポリゴンがたくさんある３D地図なので、どうしても後ろのポリゴンを書かなくてもよいように判定をしたいのです。

どなたかどのポリゴンが視覚に入るか判定できるアルゴリズムのようなものをご存知でしたらご教授いただけるでしょうか？

回答No.4

titokani · ベストアンサー

もうすこし考えてみました。

・すべてのポリゴンについて、2Dに変換して、ついでにZとバウンディングボックスも計算する
・ポリゴンをZでソート
・手前のポリゴンから2Dの当り判定。このとき、完全に隠れるポリゴンはリストから削除
・残ったポリゴンをZバッファを使って描画

という感じでどうでしょうか？

回答No.3

titokani

OpenGLもDirectXもつかわずに3Dプログラミングをしているのでしょうか？
しかし、ポリゴンとポリゴンが交差(突き刺さっている感じ)する立体を
描きたいと思ったら、結局Zバッファの類は実装しないといけないような。

だったら、最初からZバッファ+Zソートあたりで作ってしまったほうが
早いかなと思います。

ポリゴンの重なり判定の高速化という話なら、バウンディングボックスとかを
使うことによって計算量は減らせるでしょうが、う～ん、どうでしょうね。

回答No.2

BearCave

OpenGLを使っているのなら、その処理はOpenGLがやってくれるはずですが。三角形Ａは、Ｂに完全に隠れていればレンダリングされず、描画スピードにも影響されないと思いますよ。実際に大きな３Ｄ地図で実験してみれば一目瞭然だと思います。カメラの前にポリゴンを置いて、その奥にある巨大な３Ｄモデルを遮れば、フレームレートは飛躍的に上がります。

お礼

OpenGLを使っているわけでないのです。ロボットの目が３D地図の中を移動するようなことをやっているので、ロボットの目の視界に３D地図中のどのポリゴンが見えるかな、といった判定ができるアルゴリズムを探しています。

そのOpenGLのコードのくだりはそういう風に説明した方が分かりやすいかな、と思っただけでした。（たぶん回答してくれるのはCGをやっている人かなと予想したのですが…）

説明が悪くてすみませんでした。とにかくご回答ありがとうございました！

回答No.1

titokani

全てのポリゴンを総当りでチェックすると、結構な計算量ですよ。
素直にＺバッファでやったほうが効率がいいかも。ＧＰＵのアクセラレーションも期待できそうだし。

真面目にやるなら

・２Ｄに投影して重なり判定。
・重なっていた場合、３Ｄでの交差判定

という感じでしょうか。

補足

2Dに投影して重なり判定をしているのですが、ご指摘の通り相当の計算量になるのです。そこで投影する前になにかポリゴンの集合にフィルターをかけることができないかな、という質問なのです…ポリゴンの法線ベクトルとカメラ視界との角度を利用したりしてみているのですが、なかなかすっぱりとは減ってくれません。

なにか心当たりがあればよろしくお願いします。