2

特に、ファイルの最後にあるBVHトラバーサルアルゴリズムのGame PhysicsEngineDevelopmentからのこのコードを見ています。getPotentialContactsgetPotentialContactsWith

このアルゴリズムの外観では、兄弟の最初のペアを比較しますが、各子孫内の衝突は検索しません。

これがこのようなグラフでどのように機能するかわかりません。点線は枝を表し、実線は葉のノードであり、木の深さはスペクトル色（赤、オレンジ、黄色、緑）で表されます。

BVH問題

私がここで理解していないのは何ですか？ツリー内のすべての連絡先を見つけるために別のアルゴリズムが必要ですか？

また、各リーフをトラバースしてみましたが、多くの場合、衝突を2回検出することになります。これも、そうではありません。

4

1 に答える 1

0

I was having the same problem with this function... so I tried a few approaches and I ended up with this:

  private  int getPotentialContactsWith(
         BVHNode other,
        Vector<PotentialContact> contacts,boolean descend) {

      int count=0;
      //System.out.println(id+" comparando com "+other.id+" contacts.size:"+contacts.size());
      checks++;
      // Early out if we don't overlap or if we have no room
      // to report contacts

      if ((descend) && (!isLeaf())) {
         count += children[0].getPotentialContactsWith(
               children[1], contacts,descend);
      }

      if ((descend) && (!other.isLeaf())) {
         count += other.children[0].getPotentialContactsWith(
                other.children[1], contacts,descend);
       }


        if(!overlaps(other)) return 0;




      // If we're both at leaf nodes, then we have a potential contact
      if (isLeaf() && other.isLeaf())
      {
          if (!alreadyInside(body,other.body,contacts)){
              PotentialContact contact=new PotentialContact(body,other.body);
              contacts.add(contact);} else {errors++;}
          return 1;
      }


      // Determine which node to descend into. If either is
      // a leaf, then we descend the other. If both are branches,
      // then we use the one with the largest size.
      if (other.isLeaf() ||
          (!isLeaf() && volume.getSize() >= other.volume.getSize()))
      {
          // Recurse into ourself
          count += children[0].getPotentialContactsWith(
              other, contacts,false
              );

          // Check we have enough slots to do the other side too
              count += children[1].getPotentialContactsWith(
                  other, contacts,false );
      }
      else
      {
          // Recurse into the other node
          count += getPotentialContactsWith(
              other.children[0], contacts,false);

          // Check we have enough slots to do the other side too
              count += getPotentialContactsWith(
                  other.children[1], contacts,false
                  );

      }


      return count;
    }

//// About the code: Well, its in java but I guess its easy to translate or understand what it is doing. I created the function "alreadyInside" to check if I already added the potential contact and I was increasing the variable errors if I did, so far this code is not adding any repeated potential contact (errors=0), so I will problably drop this function to optimize the code. Also, I added the "descend" parameter, which is a flag which tells when to go further down in the structure.

于 2011-12-19T20:31:53.213 に答える