Как обеспечить эффективное обнаружение столкновений и реагирование на сферические объекты и треугольную местность? - PullRequest
Новая
       33

Как обеспечить эффективное обнаружение столкновений и реагирование на сферические объекты и треугольную местность?

0 голосов
/ 07 ноября 2019

Я пытался эффективно обнаруживать столкновения между объектами и местностью. Объекты представлены подвижными сферами, а местность состоит из статических треугольников.
До сих пор мне удалось реализовать алгоритм столкновения, но у него есть несколько серьезных проблем:
1. Это оченьресурсоемкий.
2. Столкновение работает только с одной стороны треугольников.
3. Несколько одновременных столкновений дают плохие результаты.
Ниже я изложил алгоритм, который у меня есть. Он основан на статье realtimecollisiondetection.net и использует математическую библиотеку GLM. Я упростил циклы, имена переменных, ненужный код и члены класса: 

//Class definitions:  
class Sphere
{
     public:
     float x;
     float y;
     float z;
     float radius;
     float sqradius;
     float xmov;
     float ymov;
     float zmov;
};
class TriangularWall
{
     public:
     float x[3];
     float y[3];
     float z[3];
     glm::vec3 Normal;
};

using namespace glm; 
Sphere Obj;
TriangularWall Wall;
//Assume that the 2 objects above are constructed. I didn't include their constructors because they looked ugly. 
float rr=Obj.sqradius;  
vec3 A=vec3(Wall.x[0], Wall.y[0], Wall.z[0])-vec3(Obj.x, Obj.y, Obj.z);  
vec3 B=vec3(Wall.x[1], Wall.y[1], Wall.z[1])-vec3(Obj.x, Obj.y, Obj.z);
vec3 C=vec3(Wall.x[2], Wall.y[2], Wall.z[2])-vec3(Obj.x, Obj.y, Obj.z);  
vec3 V=cross(B-A, C-A);  
float d=dot(A, V);  
float e=dot(V, V);  
float di=d;  
float ei=e;
vec3 Ai;
vec3 Bi;
vec3 Ci;
vec3 Vi;
if(!(di*di>rr*ei))
{
      float aa=dot(A, A);
      float ab=dot(A, B);
      float ac=dot(A, C);
      float bb=dot(B, B);
      float bc=dot(B, C);
      float cc=dot(C, C);
      if(!(aa>rr && ab>aa && ac>aa))
      if(!(bb>rr && ab>bb && bc>bb))
      if(!(cc>rr && ac>cc && bc>cc))
      {
            vec3 AB=B-A;
            vec3 BC=C-B;
            vec3 CA=A-C;
            float d1=ab-aa;
            float d2=bc-bb;
            float d3=ac-cc;
            float e1=dot(AB, AB);
            float e2=dot(BC, BC);
            float e3=dot(CA, CA);
            vec3 Q1=A*e1-d1*AB;
            vec3 Q2=B*e2-d2*BC;
            vec3 Q3=C*e3-d3*CA;
            vec3 QC=C*e1-Q1;
            vec3 QA=A*e2-Q2;
            vec3 QB=B*e3-Q3;
            if(!(dot(Q1, Q1)>rr*e1*e1 && dot(Q1, QC)>0)
            if(!(dot(Q2, Q2)>rr*e2*e2 && dot(Q2, QA)>0)
            if(!(dot(Q3, Q3)>rr*e3*e3 && dot(Q3, QB)>0)
            {
                  vec3 ObjectMov=vec3(Obj.xmov, Obj.ymov, Obj.zmov);
                  if(dot(ObjectMov, Wall.Normal)<0)
                  ObjectMov-=dot(ObjectMov, Wall.Normal);
                  Obj.xmov=ObjectMov [0];
                  Obj.ymov=ObjectMov [1];
                  Obj.zmov=ObjectMov [2];
            }
      }
}

Для третьего вопроса я заново создал приведенный выше алгоритм (просто остановив объект на соответствующемось, если столкновение все еще имеет место). Тем не менее, это значительно загружает программу и не дает таких приятных эффектов.
Я также знаю, что мог бы включить несколько настроек производительности в алгоритм выше, но я не вижу ничего, что могло бы улучшить производительностьс большим отрывом.
Я знаю, что я мог бы также использовать октреи, однако они показались мне довольно сложными, и я также беспокоюсь, что в некоторых ситуациях они могут создать большую задержку.
Следовательно, есть ли способ улучшить алгоритм, который я использовал, чтобы исправить его основные проблемы? Или я должен просто попытаться использовать другой?

1 Ответ

1 голос
/ 08 ноября 2019

Если предположить, что то, что вы называете "ресурсоемким", слишком большое время выполнения, количество треугольников должно быть значительным. Поэтому первое, что нужно сделать, - это уменьшить количество треугольников, с которыми нужно проверять.

Вы упомянули окт-деревья. В более общем смысле, иерархия ограничивающих объемов - это путь. (https://en.wikipedia.org/wiki/Bounding_volume_hierarchy.) Ускорения будут огромными для миллионов треугольников. В вашем конкретном случае, я бы, вероятно, выбрал бинарное дерево ограничивающих сфер.

Обратите внимание, что до его реализации вы ужеполучить ускорение, предварительно рассчитав ограничивающую сферу каждого треугольника (центр сферы является центром описанной окружности, т. е. пересечения плоскостей-посредников и плоскости треугольника). Затем непересекающиеся треугольники обнаруживаются путем сравнениярасстояние между центрами к сумме радиусов.

Что касается точного теста пересечения между сферой и треугольником, я боюсь, что нет бесплатного обеда. Используя метод «надувания / спуска»,центр сферы может находиться внутри правой призмы над треугольником, одного из трех усеченных цилиндров по краям или одной из трех сфер вокруг вершин.

При любом подходе вам придется иметь дело счто сложность дела анализs.

...