Этот блог обновляется в режиме реального времени по адресумой гитхаб.
При локальном планировании пути робота необходимо избегать движущихся или статических препятствий в режиме реального времени.Этот процесс связан с проблемой обнаружения столкновений.В этой статье в основном обсуждается эта проблема.
Проблема обнаружения столкновений также является проблемой, часто возникающей при разработке игр.В игровой сцене может быть много объектов, и большинство из них принадлежат удаленным позициям или относительно несвязанным состояниям, поэтому операция столкновения объекта не требует обхода. этих объектов мы можем обсуждать столкновения, используя многоугольник, который заключает в себе один или несколько объектов, что значительно экономит вычисления и время.
В реальных физических системах, как правило, необходимо найти компромисс между скоростью работы и точностью. Хотя очень точный алгоритм обнаружения столкновений может точно представить и решить проблему столкновения, на ранней стадии планирования пути требуется только предварительная оценка столкновения, например, произойдет ли столкновение, и приблизительная степень столкновения, поэтому чтобы не тратить много энергии на проблему обнаружения столкновений, тем самым уменьшая внимание к другим областям. В этой статье в основном используется метод обнаружения столкновений, используемый в игре для решения предварительной оценки обнаружения столкновений, или, когда точность столкновений невысока, неправильные объекты проецируются в относительно правильные объекты для прогнозирования и обнаружения столкновений.

Введение AABB

В настоящее время обнаружение столкновений, обычно используемое в успешных 3D-играх, — это BSP-дерево и метод AABB (Axially Aligned Bounding Box). Дерево BSP — это описание данных, используемое для управления порядком и направлением обнаружения. Подробно здесь это обсуждаться не будет. Метод обнаружения AABB использует куб или сферу для описания, чтобы обернуть весь (или основную часть) 3D-объекта.Мы можем рассчитать, происходит ли столкновение, в зависимости от расстояния и положения коробки. Примечание. Для расчетов и удобства обычно используемые формы упаковочных коробок в AABB — это сфера и прямоугольный параллелепипед, но в других особых случаях в качестве упаковочных коробок также могут использоваться другие формы.
Осевое выравнивание означает не только то, что тело блока параллельно мировой оси координат, но также означает, что каждая грань тела блока перпендикулярна оси координат, такая основная информация может уменьшить количество операций при преобразовании тела блока. . Методы AABB сегодня используются во многих играх, и разработчики часто используют их в качестве моделей обнаружения для моделей.
Ограничивающая рамка AABB в двумерной сцене имеет характеристики (все системы координат на следующем рисунке являются правыми прямоугольными системами координат):

Форма выражения четырехугольник, то есть объект окружен четырехугольником.
Каждая сторона четырехугольника будет перпендикулярна оси системы координат.

Ограничивающая рамка AABB в функциях 3D-сцены:

Форма выражения шестигранная.
Каждая сторона шестигранника параллельна координатной плоскости.

Среди них, чтобы более четко показать характеристики ограничивающей рамки AABB, крайняя справа отображается ограничивающая рамка OBB (Oriented Bounding Box), также известная как направленная ограничивающая рамка. Наиболее прямое различие между ограничивающей рамкой AABB и ограничивающей рамкой OBB заключается в том, что ограничивающую рамку AABB нельзя вращать, в то время как ограничивающую рамку OBB можно вращать, то есть направлять.

Ограничивающая рамка AABB объекта в 3D-сцене представляет собой шестигранник.Хотя есть 8 вершин, для обычного куба AABB нам нужно знать только две вершины (x_min,y_min,z_min) и (х_max,y_max,z_max) для получения центральной точки, длины стороны и других атрибутов AABB, которые подробно описываться не будут.Восемь вершин ограничивающей рамки AABB трехмерного объекта все еще можно идентифицировать по двум вершинам.,Как показано ниже.

Предсказание и обнаружение столкновений сфер

сфера — это простейшая математическая модель для обнаружения столкновений, нам нужно только перейти к центру и радиусу двух сфер для обнаружения. Преимущество сферических столкновений в том, что они очень подходят для игр, требующих быстрого обнаружения, потому что не требуют точных алгоритмов обнаружения столкновений, скорость выполнения относительно высока, и это не будет слишком большой вычислительной нагрузкой для ЦП. Другим недостатком столкновения сфер является то, что оно работает только для приблизительно сферических объектов.Если объект очень узкий или очень широкий, алгоритм обнаружения столкновения не сработает, потому что система обнаружения столкновения отправит сигнал столкновения до того, как объект действительно столкнется.

сферическое дерево

Чтобы решить проблему низкой точности удержания шаров, люди выдвинули другуюсферическое деревоМетоды. Как показано на рисунке ниже, дерево сфер на самом деле является иерархической структурой, выражающей трехмерные объекты. Для 3D-объекта сложной формы сначала используйте большую сферу, чтобы охватить весь объект, затем используйте меньшие сферы, чтобы представить основные части объекта, а затем используйте меньшие объемлющие сферы для более мелких деталей.Иерархическая связь между ними образует сферу. дерево.

Например, для персонажа в игре вы можете использовать большую сферу для представления всего человека, затем использовать сферы среднего размера для представления конечностей и туловища, а затем использовать сферы меньшего размера для представления рук и ног. Таким образом, при обнаружении столкновений двух объектов сначала сравниваются две самые большие сферы. Если есть перекрытие, пройдите вниз по древовидной структуре, сравнивая меньшие сферы, пока сферы не перекроются, или пока не будет достигнута самая маленькая сфера, и часть, содержащаяся в этой самой маленькой сфере, является частью, которая столкнулась.

конус скорости

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

В двумерной плоскости предсказание столкновения препятствий происходит следующим образом, гдеDCPA представляет значение ближайшего расстояния, TCPA представляет время в ближайший момент.

Исходный код C# прогнозирования столкновений:

// C# 代码
public static ARPA CPACalculation(double USVGeo_x, double USVGeo_y, double OBSGeo_x, double OBSGeo_y, double USV_Speed, double USV_Azimuth, double OBS_Speed, double OBS_Azimuth)
{
    // 计算距离
    double distance = GeographyBase.GeographyTransfer.CalLength(USVGeo_x,USVGeo_y,OBSGeo_x,OBSGeo_y);
    // 计算方位
    double UAV2OBSAzimuth = GeographyBase.GeographyTransfer.CalAzimuth(USVGeo_x, USVGeo_y, OBSGeo_x, OBSGeo_y);
    double interAngle = USV_Azimuth - OBS_Azimuth; //取值范围在[-180, 180]之间
    if (interAngle > 180)
        interAngle -= 360;
    if (interAngle < -180)
        interAngle += 360;
    // 相对速度
    double RelativSpeed = Math.Sqrt(Math.Pow(USV_Speed, 2) + Math.Pow(OBS_Speed, 2) - 2 * USV_Speed * OBS_Speed * Math.Cos(interAngle / 180.0 * Math.PI));
    // 相对航向
    double angleQ = Math.Acos((Math.Pow(RelativSpeed, 2) + Math.Pow(USV_Speed, 2) - Math.Pow(OBS_Speed, 2)) / (2 * RelativSpeed * USV_Speed)) * 180.0 / Math.PI;
    double RelativeAzimuth = 0;
    if (interAngle > 0)
        RelativeAzimuth = USV_Azimuth + angleQ;
    else
        RelativeAzimuth = USV_Azimuth - angleQ;
    // 相对舷角的计算 
    double bearing = UAV2OBSAzimuth - RelativeAzimuth;
    double DCPA = distance * Math.Sin(bearing * Math.PI / 180.0);
    double TCPA = distance * Math.Cos(bearing * Math.PI / 180.0) / RelativSpeed;
    ARPA arpa = new ARPA();
    arpa.DCPA = DCPA;
    arpa.TCPA = TCPA;
    arpa.SailSpeed = OBS_Speed;
    arpa.SailAngle = OBS_Azimuth;
    arpa.TargetDistance = distance;
    arpa.TargetAzimuth = UAV2OBSAzimuth;
    return arpa;
}скопировать код

Обнаружение столкновений кубов -- AABB

AABB очень чувствителен к ориентации объекта, и AABB может быть разным для разных ориентаций одного и того же объекта (поскольку сфера имеет только одну степень свободы, сфера обнаружения не чувствительна к ориентации объекта).
Когда объект перемещается в сцене, его AABB должен двигаться вместе с ним.Когда объект вращается, есть два варианта: пересчитать AABB с преобразованным объектом или сделать то же преобразование AABB, что и объект. Если объект не искажен, его можно пересчитать с помощью «Преобразованного AABB», так как этот метод намного быстрее, чем с «Преобразованным объектом». Вы можете использовать изменение матрицы, чтобы ускорить расчет нового AABB.Обнаружение столкновений в 3D для начинающих

Статическое обнаружение AABB

Статическое обнаружение AABB относительно просто.Он определяет, пересекаются ли два статических прямоугольника.Это логический тест, и результат теста является только пересечением или непересечением. Здесь мы также предоставляем методы для получения информации о диапазоне пересечения, обычно целью этого теста является возврат логического значения. В одномерной координатной оси условия пересечения двух отрезков A и B таковы:

Максимальное значение A отрезка A на оси координат_maxНе менее минимального значения B отрезка B на оси координат_min;
Максимальное значение B на оси отрезка B_maxНе менее минимального значения А отрезка А на оси координат_min;
Это_max-B_min)*(B_max-A_min)>0

Исходя из вышеизложенного,Принцип обнаружения столкновений AABB в 2D-сцене:

На приведенном выше рисунке сделаны проекции объекта A и объекта B соответственно в направлениях осей X и Y. Координаты точки максимума в направлении оси Y объекта A: Y1, координата точки минимума Y2, точка минимума координата X1 в направлении оси X, и координата максимальной точки X2., и то же самое верно для объекта B. Красная область на рисунке — это перекрывающаяся часть проекции объекта А и объекта В.
Обнаружение столкновений AABB в двумерной сцене имеет следующие правила: объект A и объект B проецируются по двум осям координат, и только когда обе оси координат перекрываются, два объекта означают, что произошло столкновение.
То есть, если (Y1-Y4)*(Y3-Y2)>0 в направлении оси Y и (X4-X1)*(X2-X3)>0 в направлении оси X, то это доказывает, что объект A и объект B пересекаются, иначе Докажите, что объекты A и B не совпадают.
Принцип обнаружения столкновений AABB в 3D-сцене:
Ограничивающая рамка AABB объекта в 3D-сцене представляет собой шестигранник, а его система координат является лишь еще одной осью Z для 2D-системы координат, поэтому фактически обнаружение столкновения AABB объекта в 3D-сцене все еще может быть определено. с помощью четырехточечной информации.Для достижения, то есть из восьми вершин объекта A и восьми вершин объекта B, соответственно выберите две самые большие и самые маленькие вершины для сравнения. Схематическая диаграмма столкновения выглядит следующим образом:

Обнаружение столкновений AABB в 3D-сцене имеет следующие правила: объект A и объект B проецируются по трем осям координат, и только когда три оси координат перекрываются, два объекта означают, что произошло столкновение.
Код реализации выглядит следующим образом, где массивы min и max являются минимальной и максимальной точками другого AABB и, наконец, возвращают результат обнаружения столкновения и AABB части столкновения.

движущийся многогранник

При использовании одноэтапного обнаружения столкновений возникает проблема, заключающаяся в том, что при большом временном шаге два объекта проникают полностью, но алгоритм не обнаруживает этого, как показано на следующем рисунке. Обычное решение состоит в том, чтобы сгенерировать 4D-пространство с шагом в единицу времени между начальным и конечным временем движения объекта.4D гипермногогранник, также известный как движущийся многогранник, используется для тестирования на проникновение.

После создания сетки 3D-объекта необходимо выполнить мониторинг столкновений на подсетках в 3D-объекте, а подсетки представляют собой обычные кубы. В единицу времени максимальная огибающая объектов, соединяющая начальное и конечное время, представляет собой многогранник движения. Среди них ширина оболочки может быть получена путем вычисления ширины в направлении движения вертикального объекта, а также может быть применен метод вращения.
Хотя алгоритм обнаружения столкновений AABB отличается простотой метода расчета и высокой скоростью, он подходит только для случаев с низкими требованиями к точности. По сравнению с обнаружением столкновений AABB, существует алгоритм, который ближе к объекту и более точному обнаружению столкновений OBB.

OBB

Продолжение следует

Ссылки и ресурсы (в произвольном порядке)

[1] Gottschalk, Stefan, Ming C. Lin, and Dinesh Manocha. "OBBTree: A hierarchical structure for rapid interference detection." Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. ACM, 1996.
Алгоритм обнаружения столкновений AABB для 3D-объектов
Обнаружение столкновений в 3D для начинающих
Сравнение методов расчета риска столкновения судов (не анонимно)