Алгоритм обхода столкновений BVH, не смотрящий на каждого потомка

Question

Я смотрю на этот код из Game Physics Engine Development для алгоритма обхода BVH, в частности getPotentialContacts а также getPotentialContactsWith в конце файла.

По внешнему виду этого алгоритма он будет сравнивать исходную пару братьев и сестер, но не будет искать коллизии внутри каждого потомка.

Я не вижу, как это будет работать на графике, подобном этому, где пунктирные линии представляют ветви, твердые тела - это листовые узлы, а глубины дерева представлены цветами спектра (красный, оранжевый, желтый, зеленый):

Что я здесь не понимаю? Нужен ли другой алгоритм, чтобы найти все контакты в дереве?

Я также пытался пройтись по каждому из листьев, но затем я во многих случаях обнаружил столкновения дважды - так что это тоже не так.

Answer 1

У меня была та же проблема с этой функцией... поэтому я попробовал несколько подходов, и я закончил с этим:

  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;
    }

//// О коде: Ну, это в Java, но я думаю, его легко перевести или понять, что он делает. Я создал функцию "readyInside", чтобы проверить, добавил ли я уже потенциальный контакт, и увеличивал ли он ошибки переменных, пока этот код не добавляет повторяющийся потенциальный контакт (errors=0), поэтому я, вероятно, отброшу это функция для оптимизации кода. Кроме того, я добавил параметр "нисходящий", который является флагом, указывающим, когда идти дальше в структуре.