1

円形のオブジェクトがあるとしましょう。各オブジェクトの直径は64ピクセルです。

私の四分木のセルは、たとえば96x96ピクセルです。

円が存在するセルとそのすべての隣接セルからの衝突を確認すると、すべてが正常に機能します。

しかし、直径が512ピクセルの円が1つある場合はどうなりますか？これは多くのセルをカバーするため、隣接セルのみをチェックする場合に問題になります。しかし、はるかに大きなオブジェクトがツリーに挿入されるたびに、クワッドツリーグリッドのサイズを変更することはできません...

4

3 に答える 3

3

代わりに、オブジェクトを単一のセルに配置すると、オブジェクトが衝突するすべてのセルにオブジェクトが配置されます。そうすれば、各セルを個別にテストできます。オブジェクトへのポインタを使用して、コピーを作成しないようにします。また、これはleavenodesでのみ行う必要があるため、上位ノードに含まれるデータと下位ノードを組み合わせる必要はありません。

于 2011-12-11T10:19:41.143 に答える
1

これは興味深い問題です。たぶん、木の高さの情報でノードまたはセルを拡張できますか？オブジェクトが大きい場合は、最小のセルがツリーの高さでネストします。これは、グーグルやビングマップのようなマップのアプリケーションが行うことです。

同様のソリューションへのリンクは次のとおりです：http：//www.gamedev.net/topic/588426-2d-quadtree-collision---variety-in-size。画面を四分木と混同していました。簡単な再帰で衝突を確認できます。

于 2011-08-07T17:58:09.163 に答える
0

オーバーサーチ

検索中、最初に最大のオブジェクトから始めます...

QuadTreeNode.Centre.Xに対してObject.Position.Xをテストし、また

QuadTreeNode.Centre.Yに対してObject.Position.Yをテストします。

...次に、差の絶対値を取得することにより、絶対値がオブジェクトの半径を超えない場合は常に、オブジェクトを特定の子ノード内にあるものとして扱います。

...つまり、オブジェクトの一部がそのクワッドに侵入したとき:)

AABB（Axis Aligned Bounding Boxes）でも同じことができます。

ここでの唯一の本当の注意点は、画面の大部分を覆う非常に大きなオブジェクトがツリー全体の検索を強制することです。このような場合、別のアプローチが必要になる場合があります。

もちろん、これは他のすべてがテストされているオブジェクトのみを処理します。世界の他のすべての大きなオブジェクトが正しく識別されるようにするには、クワッドツリーを少し変更する必要があります...

複数の外観を使用する

QuadTreeのこのバリエーションでは、オブジェクトをQuadTreeのリーフノードにポインターとしてのみ配置します。より大きなオブジェクトは、複数のリーフノードに表示される場合があります。

一部のオブジェクトはツリー内で複数の外観を持っているため、テスト済みのオブジェクトを回避する方法が必要です。

それで...

単純なブールWasHitフラグを使用すると、ヒットテストパスで同じオブジェクトを複数回テストすることを回避できます。また、すべての「ヒット」オブジェクトに対して「クリーンアップ」を実行して、次のテストの準備を整えることができます。

これは理にかなっていますが、all-vs-allヒットテストを実行するのは無駄です。

ですから...少し賢くなりますが、シーン内の各オブジェクト内でポインタ'ptrLastObjectTestedAgainst'を使用することで、クリーンアップをまったく回避できます。これにより、この実行で同じオブジェクトを再テストする必要がなくなります（ポインターは最初の遭遇後に設定されます）

シーンに対して新しいオブジェクトをテストするときにリセットする必要はありません（新しいオブジェクトのポインタ値は最後のオブジェクトとは異なります）。これにより、単純なBoolフラグの場合のようにポインターをリセットする必要がなくなります。

オブジェクトサイズが大きく異なるシーンで後者のアプローチを使用しましたが、うまく機能しました。

弾性四分木

「弾力性のある」QuadTreeも使用しました。基本的に、各QuadTreeNodeに理想的に収まるアイテムの数に制限を設定します-ただし、標準のQuadTreeとは異なり、特定の場合にコードがこの制限をオーバーライドできるようにします。

ここでの最も重要なルールは、オブジェクトを完全に保持できないノードにオブジェクトを配置することはできないということです...最上位のノードが画面よりも大きいオブジェクトをキャッチします。

したがって、小さなオブジェクトは引き続き「フォールスルー」して通常のQuadTreeを形成しますが、大きなオブジェクトは常にリーフノードまでフォールスルーするわけではなく、代わりに最後にフィットしたノードを拡張します。

非リーフノードは、オブジェクトがツリーから落下するときにオブジェクトを「ふるいにかける」と考えてください。

これは、多くのシナリオで非常に効率的な選択であることがわかります:)

結論

これらの標準アルゴリズムは便利な一般的なツールですが、特定の問題について考える代わりにはならないことを忘れないでください。特定のアルゴリズムやライブラリを使用するという罠にはまらないでください。「よく知られているからといって」...アプリケーションは独自のものであり、わずかに異なるアプローチの恩恵を受ける可能性があります。

したがって、アルゴリズムの適用を学ぶだけでなく、それらのアルゴリズムから学び、原理自体を斬新で適切な方法で適用してください。これらは唯一のツールではなく、必ずしもアプリケーションに最適なツールでもありません。

それらのアイデアのいくつかがお役に立てば幸いです。

于 2021-06-27T16:27:00.193 に答える