問題タブ [bsp-tree]

BSP ツリーを作成したい三角形のポリゴン スープがあります。私の現在のプログラムは、すべての三角形が消費されるまで、モデルからランダムな三角形を一度に 1 つずつ挿入して BSP ツリーを構築するだけです。その後、ツリーの深さと幅をチェックし、達成した最高のスコア (最小の深さ、最小の幅) を記憶します。 ）。

定義により、最適な深さは log2(n) (同一平面上の三角形がグループ化されている場合はそれ以下?) になります。ここで、n はモデル内の三角形の数であり、最適な幅は n (分割が発生していないことを意味します) です。しかし、この頂点に達することのない特定の三角形の配置があります。

BSP ツリーの品質をチェックするための効率的なテストはありますか? 具体的には、プログラムがより最適な構造を探すのをやめる必要があることをプログラムが知る方法を見つけようとしています。

インターネットは、2次元のBSPツリーに関する情報で満たされています（つまり、レイキャスティング、すべての壁は平行です）。誰かがリンクを持っているか、3次元でBSPツリーについて説明している本を知っていますか？

私は二分木を構築しています。バイナリ ツリーはファイルにあらかじめ組み込まれているので、それを構築する必要があります。構造化されているため、ツリーを配列に読み込みます。各ツリー ノードは次のようになります。

ツリーを構築するコードを作成する方法をいくつか試しました。私がやろうとしていることを理解できるように、疑似コードをいくつか示しましょう。

• ヘッド ノードを読み取ります。ノードは配列の 1 番です。
• ノードに左右の配列インデックスがある場合は、新しいノードを作成し、配列インデックスからの情報をそのツリー ノードに挿入します。
• ノードに左右のインデックスがない場合、それはリーフ ノードです。

これが私の建物機能です：

私のデバッグは、関数がプログラムがクラッシュするまでノード 2 を挿入しようとすることを示しています。

誰かがこれで私を助けることができますか?

Quake などの古い 3D レベルでビルド済みの BSP ツリーを利用する方法を知っており、レベル レンダラーも作成しました。今、私は実際にその BSP ツリーを自分で構築する次のステップに進んでいます。その背後にあるプロセスは知っていますが、誰かアドバイスやチュートリアルへのリンクがあるかどうか疑問に思っていました.

こんにちは、Quake レベルのレンダラーを書いています。透明性を考慮に入れる必要があるところまで来ています。バイナリ スペース パーティショナー (BSP) ツリーは、データが距離で並べ替えられるようにフォーマットされていることを知っています。または、少なくともそれは私が聞いたことですが、これを達成する方法がわかりません。BSP ツリーを構築し、PVS をデコードしました。

やるべきこと: 1. 自分がどのリーフにいるのかを把握します。たとえば、6 です。2. 最大から葉 6 までレンダリングします。ただし、これらの葉は私の錐台と PVS にあります。3. 再び PVS と錐台を考慮して、最小からリーフ 6 までレンダリングします。

これが BSP ツリーのしくみではないでしょうか。

これが質問 1 です。質問 2 は PVS を扱います。スペースが問題だった昔、PVS は圧縮されていたので優れていました。私が今持っている方法では、フレームをレンダリングするたびに PVS を解凍するのではなく、一度それを行い、レンダリング中にトラバースするベクトルに葉の可視性を保存します。これは理にかなっていますか、それとも逆効果ですか?

要約すると、BSP ツリーが構造化されており、リーフが既に距離によってソートされており、リーフ 6 (合計 9 リーフのうち) で、9、8、7、6、1、2、3 をレンダリングする必要があると仮定できますか? 4、5 (リーフ 6 の PVS に 9 つすべてが表示されていると仮定) は、同様に PVS と錐台を考慮します。

ありがとうございました。

BSPツリーをメモリにロードしています。最初に自分がどのリーフにいるかを調べます。次に、PVSをデコードします。次に、そのPVSの各領域を調べて、錐台内にあるかどうかを確認します。

これはレンダリングの間違った方法であり、実際にはBSPツリーをトラバースしてバックツーフロントレンダリングを実行する必要があると言われています。これをどのように正確に行うのですか？私はこれを行うための多くの異なる方法を見てきました、それが私が尋ねる理由です。

たとえば、Quake 3 BSPレンダリングは次のように述べています。BSPをトラバースして、カメラがどのリーフに配置されているかを判別します。このリーフのPVSを取得して解凍し、PVSを反復処理して、BSPでリーフにマークを付けます。BSPを近くから遠くまでトラバースするノードがマークされていない場合は、スキップします。カメラ錐台に対してノード境界ボックスをテストします。現在の葉をレンディションリストに追加します

これは今でも標準的な方法ですか、それとも少なくとも単純なゲームの場合はそうです。

BSPツリーアプローチを使用して多角形から三角形を生成するコード例を使用して、誰でもリソースを指すことができますか？ありがとう。

これは、コーディングの質問というよりも概念的な質問です。BSPツリーの基本的な概念を理解しましたが、ポジショニングに頭を巻くのに問題があります。BSPツリーで現在の場所を見つけるために、分割平面の前にいる場合は右に移動し、後ろにある場合は左に移動して、ツリーを再帰的に繰り返し処理することがわかりました。私が最終的に葉のノードにぶつかったとき、それは私が世界にいる場所です。

さて、レンダリングに関して、前から後ろにレンダリングする必要がある場合、ツリーの右側から始めて、左側の最後のノードに到達するまで再帰的にレンダリングしますか？後ろから前へはどうですか？それは反対でしょうか？

ありがとう！

私は、3次元のBSPツリーを実装して、透明な単一のオブジェクト（立方体、円柱が入ったボックスなど）をレンダリングしようとしています。私の知る限り、これはうまくいくはずですが、そうではなく、その理由がわかりません。私が読んだものはすべて、BSPツリーが2次元または複数のオブジェクトで使用されていることを示しているため、コードにエラーがあるのではなく、BSPツリーを適用できるものを一般的に誤解しているのではないかと思いました。私はオンラインで多くのことを調べましたが、私のコードはBretton Wade（ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html）と同じように見えるので、誰かがサンプルを持っている場合特に単一オブジェクト/透明性のためのBSPコードの、それは素晴らしいでしょう。

ありがとうございました。