2

我正在查看来自Game Physics Engine Development的 BVH 遍历算法的代码，特别是在文件末尾。getPotentialContactsgetPotentialContactsWith

从这个算法的外观来看，它会比较一对初始的兄弟姐妹，但它不会在每个后代中寻找冲突。

我看不出这在像这样的图上是如何工作的，其中虚线表示分支，实线表示叶节点，树的深度由光谱颜色（红色、橙色、黄色、绿色）表示：

BVH问题

我在这里不明白的是什么？我是否需要另一种算法来查找树中的所有联系人？

我还尝试遍历每个叶子，但在许多情况下我最终检测到两次碰撞 - 所以也不是这样。

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 回答