ScratchでDOOMのような3Dゲームを作りたいと考えています。BSP木を使った仕組みが近いことは知っていますが、仕組み自体はまったく理解できていません。教えていただけますか?

1件の回答

回答を書く

1017894

2026-04-08 07:00

+ フォロー

この回答ですぐに Scratch で BSP 木のプログラミングを始められるわけではありませんが、おおまかにでも理解の手助けになればと思います。





3D のモデルの最小単位である「ポリゴン」って空間内にたくさんありますよね。

それらポリゴンを前後関係を考えずに単純に描いてしまうと、奥にあるはずのポリゴンが手前のポリゴンよりも手前側に描かれてしまうことがあり、おかしな景観が描かれてしまいます。





それを改善するのが「画家のアルゴリズム」です。

「画家のアルゴリズム」ではすべてのポリゴンの奥行き座標(Z座標)に着目してソートを行い、奥から手前へ向かって順にポリゴンを描きます。

前後関係が正しく描かれるので自然な景観が得られます。





この画家のアルゴリズムをさらに速度的に改善するのが BSP 木です。



BSP 木では、

まず、ポリゴン一つを選び親とします。

他のポリゴンがその親ポリゴンの表側にあるのか、裏側にあるのかを判別して裏組と表組の 2 つのグループに分けます。



さらにその各グループ内でポリゴン一つを選び親として、そのグループ内の他のポリゴンが親ポリゴンの表側にあるのか、裏側にあるのか判別して裏組と表組の 2 つのグループに分けます。

さらに…



と繰り返して BSP 木が完成します。





BSP 木をプログラムで利用するときは、

たとえば、



ポリゴン A とポリゴン B があり、

ポリゴン A を親として、



条件①

ポリゴン B が親の裏側に位置している

(ツリー作成時にグループ分けという形で判別済み)



条件②

親であるポリゴン A が視点に対して表側を見せている



①②の条件が満たされているとき、視点がどこにあったとしても、ポリゴン B は必ずポリゴン A の奥にあると言えます。

だからこのときポリゴン B をまず先に描き、後からポリゴン A を描けば良い、ということになります。



このパターンは 4 つあります。



親が表側を見せBが裏グループならBは奥

親が表側を見せBが表グループならBは前



親が裏側を見せBが表グループならBは奥

親が裏側を見せBが裏グループならBは前





BSP 木を利用して描画するプログラムはだいたい下記のようなプログラムになります。



ポリゴン描画手続き(引数:親ポリゴン)



   if 引数の親ポリゴンは視点に対して表側を見せている then



      ポリゴン描画手続き( 引数の親ポリゴンの裏側のポリゴン )



      引数の親ポリゴンを画面に描く



      ポリゴン描画手続き( 引数の親ポリゴンの表側のポリゴン )



   else



      ポリゴン描画手続き( 引数の親ポリゴンの表側のポリゴン )



      引数の親ポリゴンを画面に描く

      ※ ただし、後面除去の場合は,不可視なので描かない



      ポリゴン描画手続き( 引数の親ポリゴンの裏側のポリゴン )



   end if



手続き終了





以下は URL をまじえての勉強手順です。

それなりに難度はあると思いますが、BSP 木を理解するために必要なサイトばかりです。





[1] まずはプログラムで 3DCG が描けること。

このサイトでは 3DCG の基礎的な計算式「s=50、h=x*s/z、v=y*s/z」について読めます。

https://ja.wikipedia.org/wiki/3次元コンピュータグラフィックス#透視投影



[2] そしてこのサイトでは「s=50、h=x*s/z、v=y*s/z」を使用した 3DCG プログラミングについて説明しています。(私のサイトです)

https://web6047.sakura.ne.jp/cgi-bin/prj/20180203-3DCG/index.html?menu=off





[3] 簡易的にでも 3DCG が描けたら、「画家のアルゴリズム」を導入します。

https://www.myu.ac.jp/~makanae/CG/cg1_14.htm

ここで語られる「4.塗り重ね法」とは「画家のアルゴリズム」のことです。





[4]「画家のアルゴリズム」を導入できたら、「BSP 木」を導入します。



BSP 木の実践的な説明(詳しい)

https://www.kushiro-ct.ac.jp/yanagawa/cg-2018/10-1207/





[5] BSP-tree を使用した 3DCG プログラム 作例(JavaScript



https://web6047.sakura.ne.jp/cgi-bin/prj/20180203-3DCG/20251109-戦車が移動する例/bsp_sample.html

(私のサイトです)

うったえる有益だ(0シェアするブックマークする

関連質問

Copyright © 2026 AQ188.com All Rights Reserved.

博識 著作権所有