Слишком медленное обнаружение столкновения двух объектов слишком медленно
У меня есть проект, чтобы увидеть, сталкиваются ли два объекта (из примерно 10000 треугольников в каждом), используя алгоритм столкновения грубой силы, визуализированный в OpenGL. Два объекта не движутся. Я должен буду перевести их на некоторые позиции и найти, например, 100 треугольных столкновений и т. Д.
До сих пор я написал код, который фактически проверяет пересечение между двумя этими моделями. Если я все понял правильно, мне нужно проверить каждое ребро каждого треугольника первой модели с каждой плоскостью каждого треугольника другой модели. На самом деле это означает 3 цикла for, которые заканчиваются часами. Я полагаю, что у меня что-то не так, или я неправильно понял всю концепцию.
for (int i=0; i<model1_faces.num; i++) {
for (int j=0; j<3; j++) {
x1[j] = model1_vertices[model1_faces[i].v[j]-1].x;
y1[j] = model1_vertices[model1_faces[i].v[j]-1].y;
z1[j] = model1_vertices[model1_faces[i].v[j]-1].z;
}
A.x = x1[0];
A.y = y1[0];
A.z = z1[0];
B.x = x1[1];
B.y = y1[1];
B.z = z1[1];
C.x = x1[2];
C.y = y1[2];
C.z = z1[2];
TriangleNormal = findNormalVector((B-A)*(C-A));
RayDirection = B-A;
for (int j=0; j<model2_faces.num; j++) {
PointOnPlane = model2_vertices[model2_faces[j].v[0]-1]; // Any point of the triangle
system("PAUSE");
float D1 = (A-PointOnPlane)^(TriangleNormal); // Distance from A to the plane of j triangle
float D2 = (B-PointOnPlane)^(TriangleNormal);
if ((D1*D2) >= 0) continue; // Line AB doesn't cross the triangle
if (D1==D2) continue; // Line parallel to the plane
CollisionVect = A + (RayDirection) * (-D1/(D2-D1));
Vector temp;
temp = TriangleNormal*(RayDirection);
if (temp^(CollisionVect-A) < 0) continue;
temp = TriangleNormal*(C-B);
if (temp^(CollisionVect-B) < 0) continue;
temp = TriangleNormal*(A-C);
if (temp^(CollisionVect-A) < 0) continue;
// If I reach this point I had a collision //
cout << "Had collision!!" << endl;
Также я не знаю точно, где именно эта функция должна быть вызвана выше. В моей функции рендеринга, чтобы она работала непрерывно во время рендеринга или только один раз, учитывая тот факт, что мне нужно только проверять столкновение неподвижных объектов?
Буду признателен за некоторые объяснения, и если вы слишком заняты или скучаете, чтобы увидеть мой код, просто помогите мне немного лучше понять всю эту концепцию.
Решение
Как уже предлагалось, вы можете использовать ограничивающие объемы. Чтобы наилучшим образом использовать их, вы можете расположить свои ограничивающие тома в Octree, и в этом случае тома представляют собой ящики.
На самом внешнем уровне каждый ограничивающий объем содержит весь объект. Таким образом, вы можете проверить, являются ли два объекта может быть пересекаются, сравнивая их ограничивающие объемы нулевого уровня. Проверка на пересечение двух блоков, где все грани выровнены по оси, тривиальна.
Октри будет индексировать, который лица к которому принадлежат подразделения ограничивающего объема. Поэтому некоторые лица, конечно, будут принадлежать более чем одному объему и могут быть проверены несколько раз.
Преимущество состоит в том, что вы можете отменить многие из тестов грубой силы, которые гарантированно не пройдут из-за того, что только небольшая часть ваших подчиненных частей будет фактически пересекаться. Фактическое тестирование пересечения по-прежнему грубой силы, но на небольшом подмножестве граней.
Другие решения
Как вы заметили, обнаружение столкновений методом грубой силы часто не масштабируется. 🙂 Обычный подход заключается в определении ограничивающий объем который содержит ваши модели / формы и упрощает расчеты пересечения. Ограничивающие объемы бывают разных форм и размеров в зависимости от ваших моделей. Это могут быть шары, коробки и т. Д.
В дополнение к определению ограничивающих объемов, вы захотите обнаружить столкновение в вашем update раздел кода, где вы, скорее всего, переходите в какой-то delta время. Тот delta часто требуется время, чтобы определить, как далеко должны двигаться объекты и произошло ли столкновение в этот период времени.