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

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

2 голосов
/ 24 ноября 2011

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

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

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

BVH problem

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

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

1 Ответ

0 голосов
/ 20 декабря 2011

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

  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), поэтому я, вероятно, отброшу этофункция для оптимизации кода.Кроме того, я добавил параметр «нисходящий», который является флагом, указывающим, когда идти дальше в структуре.

...