HTML5 は 3D および 2D 視覚化を実装します。QuadTree クアッドツリー衝突検出_PHP チュートリアル

HTML5 は 3D および 2D 視覚化 QuadTree クアッドツリー衝突検出を実装します

QuadTree は、その名前が示すように、ツリー状のデータ構造であり、各ノードには 4 つの子ノードがあり、2 次元平面をサブ領域に再帰的に分割できます。 QuadTree は、空間データベースのインデックス作成、3D 脊椎可視領域のトリミング、さらには画像の分析と処理にもよく使用されます。これは、ゲーム分野で最もよく使用される QuadTree の衝突検出です。 QuadTree アルゴリズムを使用すると、テストする必要がある衝突の数が大幅に減少するため、ゲームの更新パフォーマンスが向上します。この記事の例は、HT for Web の Canvas トポロジ マップと WebGL の 3D エンジン コンポーネントに基づいており、 GraphView と Graph3dView を介して同じデータ モデル DataModel を使用し、同時に 2D および 3D コリジョン ビュー効果を表示します: http://v.youku.com/v_show/id_XODQyNTA1NjY0.html

http://www.hightopo.com/ demo/QuadTree/ht-quadtree.html

QuadTree 実装の成熟したバージョンは多数ありますが、私が選択したのは https://github.com/timohausmann/quadtree-js/ です。quadtree アルゴリズムは非常に単純です。したがって、このオープン ソース ライブラリにはコードが約 200 行しかありません。使い方も非常に簡単で、最初のパラメータはゲーム空間の範囲を設定するためにrect情報に渡され、まず古いデータがquadtree.clear()によってクリアされます。 quadtree.insert(rect) 新しいノードの長方形領域。これにより、quadtree が初期化されます。残っているのは、必要に応じて、指定された長方形領域と交差する可能性のある長方形オブジェクトの配列を取得することだけです。検出されること。

私は HT (http://www.hightopo.com/) GraphView と Graph3dView の 2 つのコンポーネントを構築し、ht.widget.SplitView を通じて左右に分割しました。両方のビューが同じ DataModel を共有しているため、残りの懸念事項は解決されます。は、DataModel に対するデータ操作のみです。200 個の ht.Node オブジェクトが構築され、同時に、各オブジェクトの attr 属性に保存されます。これは、quadtree に繰り返し挿入されます。更新中にオブジェクトが繰り返し作成され、quadtree.retrieve(rect) で検出する必要がある長方形オブジェクトを取得するときに、その長方形オブジェクトも ht.Node オブジェクトを参照するように保存されます。関連付けられた ht.Node オブジェクト。最終的に衝突として検出されたプリミティブに赤色の効果を設定する必要があるためです。つまり、ht.Node は通常、デフォルトの青色を表示し、相互に衝突すると赤色に変わります。

quadtree.retrieve(rect) から取得される、検出する必要がある長方形オブジェクトの配列には、それ自身のプリミティブが含まれることになりますが、同時に、これらは衝突する可能性があるという意味ではありません。この例はすでに衝突しているため、ht.Default.intersectsRect(r1, r2) を使用して、それらが交差するかどうかを最終的に判断します。例が円の場合、2 つの円の中心間の距離を計算できます。交差するかどうかを判断する半径が 2 つ未満であるため、最終的な判断基準はゲームの種類によって異なります。

QuadTree を使用すると、コンピューティングのパフォーマンスが大幅に向上しました。そうでない場合、100 個のグラフィック要素には 100*100 回の監視が必要になります。この量は、通常、100*(10~30) になります。 youku.com/v_show/id_XODQyNTA1NjY0.html

http://www.hightopo.com/demo/QuadTree/ht-quadtree.html

衝突検出に加えて、QuadTree アルゴリズムには多くの興味深い応用分野があります。興味がある場合は、https://github.com/fogleman/Quads で試してみることができます

すべてのコードは次のとおりです。

りー

http://www.bkjia.com/PHPjc/1080259.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/1080259.html技術記事 HTML5 は 3D および 2D の視覚化を実装しています QuadTree クアッドツリー衝突検出 QuadTree クアッドツリーは、名前が示すように、各ノードに 4 つの子ノードがあり、2 次元平面を再帰的に分割できます。