3

3Dで地形樹を作ることについての質問です。ちょっとしたコンテキスト: 物理エンジンがあり、ボディと衝突ポイント、およびいくつかの制約があります。これは宿題ではなく、マルチスレッドでの実験です。

このドキュメントのように、レイヤーに属するオブジェクトのグループを使用して、ボディを下から上に並べ替える必要があります。「衝撃伝播」のセクションを参照して ください http://www2.imm.dtu.dk/visiondag/VD05/グラフィカル/スライド/kenny.pdf

選別木

ツリーを反復処理する方法を説明するために彼が使用する疑似コードは、完全に理にかなっています。

shock-propagation(algorithm A)
compute contact graph
for each stack layer in bottom up order
     fixate bottom-most objects of layer
     apply algorithm A to layer
     un-fixate bottom-most objects of layer
next layer

私はすでにアルゴリズム A を把握しています (私のインパルス コード)。3D ポイントのリストを使用したツリー/レイヤーの並べ替え (トポの並べ替え) の疑似コードはどのようになりますか?

IE、次の「ラング」または「ブランチ」を停止/開始する場所がわかりません。私はそれをy位置でチャンクアップすることができたと思いますが、それは扱いにくく、エラーが発生しやすいようです. 地形選別を調べますか? 3Dでこれを行う方法がよくわかりません。どうすれば topo ソートの「エッジ」を取得できますか?

私はこれを考えすぎて、ポイント p1 を見つけてから、最も遠い次のポイント p2.y > p1.y を見つけて「点をつなぐ」だけですか? ここで、純粋な距離を使用すると、p0 からの p1 の距離が p2 よりも大きくなる可能性があるという問題が見られます。これは、不適切な並べ替えにつながります。

4

1 に答える 1

1

私は自分でこれに取り組みました。

このペーパーにリンクされているダウンロード可能なソース コードで、これを実現する方法の例を見つけました。

http://www-cs-students.stanford.edu/~eparker/files/PhysicsEngine/

具体的には、221 行目から始まる WorldState.cs ファイルです。

しかし、すべての静的オブジェクトに -1 のレベルを割り当て、他の各オブジェクトに異なるデフォルト レベルの -2 を割り当てるという考え方です。次に、レベル -1 のボディとの衝突ごとに、衝突したボディをリストに追加し、そのレベルを 0 に設定します。

その後、while ループ while(list.Count > 0) を使用して、衝突するボディをチェックし、レベルを body.level + 1 に設定します。

その後、まだデフォルト レベル (前に -2 と言いました) を持つシミュレーション内の各ボディに対して、そのレベルを最高レベルに設定します。

さらに細かい点がいくつかありますが、例のコードを見ると、これまで以上にうまく説明できます。

それが役に立てば幸い！

Evan Parker のコードからの関連コード。【スタンフォード】

{{{

// topological sort (bfs)
            // TODO check this
            int max_level = -1;
            while (queue.Count > 0)
            {
                RigidBody a = queue.Dequeue() as RigidBody;
                //Console.Out.WriteLine("considering collisions with '{0}'", a.Name);
                if (a.level > max_level) max_level = a.level;
                foreach (CollisionPair cp in a.collisions)
                {
                    RigidBody b = (cp.body[0] == a ? cp.body[1] : cp.body[0]);
                    //Console.Out.WriteLine("considering collision between '{0}' and '{1}'", a.Name, b.Name);
                    if (!b.levelSet)
                    {
                        b.level = a.level + 1;
                        b.levelSet = true;
                        queue.Enqueue(b);
                        //Console.Out.WriteLine("found body '{0}' in level {1}", b.Name, b.level);
                    }
                }
            }

            int num_levels = max_level + 1;

            //Console.WriteLine("num_levels = {0}", num_levels);

            ArrayList[] bodiesAtLevel = new ArrayList[num_levels];
            ArrayList[] collisionsAtLevel = new ArrayList[num_levels];
            for (int i = 0; i < num_levels; i++)
            {
                bodiesAtLevel[i] = new ArrayList();
                collisionsAtLevel[i] = new ArrayList();
            }

            for (int i = 0; i < bodies.GetNumBodies(); i++)
            {
                RigidBody a = bodies.GetBody(i);
                if (!a.levelSet || a.level < 0) continue; // either a static body or no contacts

                // add a to a's level
                bodiesAtLevel[a.level].Add(a);

                // add collisions involving a to a's level
                foreach (CollisionPair cp in a.collisions)
                {
                    RigidBody b = (cp.body[0] == a ? cp.body[1] : cp.body[0]);
                    if (b.level <= a.level) // contact with object at or below the same level as a
                    {
                        // make sure not to add duplicate collisions
                        bool found = false;
                        foreach (CollisionPair cp2 in collisionsAtLevel[a.level])
                            if (cp == cp2) found = true;

                        if (!found) collisionsAtLevel[a.level].Add(cp);
                    }
                }
            }

            for (int step = 0; step < num_contact_steps; step++)
            {
                for (int level = 0; level < num_levels; level++)
                {
                    // process all contacts
                    foreach (CollisionPair cp in collisionsAtLevel[level])
                    {
                        cp.ResolveContact(dt, (num_contact_steps - step - 1) * -1.0f/num_contact_steps);
                    }
                }
            }

}}}
于 2013-01-17T11:19:42.077 に答える