Определение столкновений между простейшими геометрическими объектами.

Введение.

Геометрический объект - некоторое множество точек. (Т.к. других объектов у нас не будет, слово геометрический для краткости будет опускаться.)

Два геометричеких объекта пересекаются или столкиваются если они имеют общие точки.

В статье будут рассмотрены только алгоритмы для определения того пересекаются ли некоторые два объекта или нет. В качестве базы мы будем использовать модуль для работы с векторами (который в архиве называется DMath.pas). Скачать примеры к статье можно тут.

2д

Начнем с простого - с определения столкновений между двумерными объектами.

Круг - круг

Все просто - нужно вычислить расстояние между центрами кругов, если оно меньше суммы радиусов, то круги пересекаются, в противном случае нет.

Type
TCircle = packed record
  Pos: TVec2D;
  Rad: Single;
end;

Function ColCircleVsCircle(A, B: TCircle): Boolean;    
begin
  Result := Dist2D(A.Pos, B.Pos) < A.Rad + B.Rad;
end;

AARect - AARect

AARect - сокращение от axis-aligned rectangle, то есть прямоугольник, стороны которого параллельны осям координат.

Два AARect'а пересекаются тогда и только тогда, когда они пересекаются в обеих проекциях - на ось OX и ось OY.

Если, скажем, прямоугольники не пересекаются в проекции на ось X, то существует вертикальная прямая, проходящая между прямоугольниками, поэтому пересекаться они не могут.

Если же прямоугольники пересекаются в обеих проекциях, то проделаем следующее. Возьмем общую точку в проекции на ось X и проведем через нее вертикальную прямую. Аналогично для оси Y:

Очевидно, что точка пересечения этих двух прямых - точка пересечения AARect'ов.

Type
TAARect = packed record
  Min, Max: TVec2D;
end;

// A < X < B ?
// (Определение столкновения между точкой X и интервалом (A, B))
Function IsMiddle(X, A, B: Single): Boolean;
begin
  Result := (A < X) And (X < B);
end;

// Определение столкновения между двумя одномерными отрезками
Function ColLine1DVsLine1D(A, B, C, D: Single): Boolean;
begin
  Result := IsMiddle(A, C, D) Or IsMiddle(B, C, D) Or
            IsMiddle(C, A, B) Or IsMiddle(D, A, B);
end;

Function ColAARectVsAARect(A, B: TAARect): Boolean;
begin
  Result := ColLine1DVsLine1D(A.Min.X, A.Max.X, B.Min.X, B.Max.X) And
            ColLine1DVsLine1D(A.Min.Y, A.Max.Y, B.Min.Y, B.Max.Y);
end;

ORect - ORect

ORect - сокращение от oriented rectangle, что в переводе значит ориентированный прямоугольник. Т.е. ORect - это любой прямоуголник на плоскости.

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

Въедливый читатель мог заметить, что выше при определениях столкновений (Circle Vs Circle, AARect Vs AARect) мы почему-то не учитывали границы объектов. Исправить это, конечно, просто - нужно заменить все строгие неравенства на нестрогие. Но сделано это специально для поддержания однородности статьи - сейчас (ORect vs ORect) мы не будем учитывать границу из-за удобства написания алгоритма.

Для начала введем определение. Разделяющей прямой прямоугольников A и B будем называть такую прямую, что эти прямоугольники относительно этой прямой расположены строго по разные стороны. Замечу, что так как мы не учитываем границы, разделяющей прямой может быть одна из сторон прямоугольника.

Оказывается, что верно следующее утверждение:

Если одна из сторон одного из двух прямоугольников является разделяющей прямой, то прямоугольники пересекаются, в противном случае нет.

В одну сторону доказать это утверждение просто - если разделяющая прямая существует вообще (не важно какая), то прямоугольники не могут иметь общих точек.

Теперь пусть ни одна из сторон не является разделяющей прямой. Предположим, что прямоугольники не пересекаются. В таком случае один из прямоугольников должен пересекать продолжения всех сторон второго, т.е располагаться как-то так:

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

Приступим к написанию кода. Хранить ORect мы будем в виде четырех его вершин - это будет удобно для алгоритма.

Type
TORect = Array[0..3] Of TVec2D;

//
// Au?eneaiey eiyooeoeaioia A, B e C i?yiie A*X + B*Y + C = 0 ii aaoi oi?eai V1, V2
//
Procedure CalcABC(V1, V2: TVec2D; Var A, B, C: Single);
  Var
    N: TVec2D;
begin
  // 1. Au?eneyai aaeoi?, ia?iaiaeeoey?iue i?yiie
  N := Vec2D(V1.Y - V2.Y, V2.X - V1.X);
  // 2. Ii?iaeecoai aai
  N := Norm2D(N);
  // 3. Caienuaaai ?acoeuoao e au?eneyai C ii oi?ioea C = - A*X - B*Y
  A := N.X;
  B := N.Y;
  C := - V1.X*A - V1.Y*B;
end;

//
//
//
Function GetDistToLine(X: TVec2D; S, F: TVec2D): Single;
  Var
    A, B, C: Single;
begin
  CalcABC(S, F, A, B, C);
  Result := A*X.X + B*X.Y + C;
end;

Function ClassifyORect(S, F: TVec2D; ORect: TORect): Integer;
  Var
    I: Integer;
    InFront: Boolean;
    InBack: Boolean;
    D: Single;
begin
  InFront := False;
  InBack := False;
    For I := 0 to 3 do begin
      D := GetDistToLine(ORect[I], S, F);
        If D > EPS then
          InFront := True;
        If D < -EPS then
          InBack := True;
    end;
    If InFront And InBack then
      Result := 0
    else
    If InFront then
      Result := 1
    else
      Result := -1;
end;

//
//
//
Function ColORectVsORect(A, B: TORect): Boolean;
  Var
    I: Integer;
begin
  Result := True;
    For I := 0 to 3 do
      If ClassifyORect(A[I], A[(I + 1) mod 4], A)*
         ClassifyORect(A[I], A[(I + 1) mod 4], B) < 0 then
        Result := False;
    For I := 0 to 3 do
      If ClassifyORect(B[I], B[(I + 1) mod 4], A)*
         ClassifyORect(B[I], B[(I + 1) mod 4], B) < 0 then
        Result := False;
end;

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

Но сначала научимся поворчивать точку X, Y на угол A относительно точки (0, 0). Как это сделать? Нет, для этого не нужно искать умные формулы, не нужна даже бумага с карандашом - формулу можно вывести в уме. Смотрите.

Пусть i такое хитрое число, что i^2 = -1. (Жаргонно его называют мнимой единицей.) Запишем наш вектор в виде (X + Y*i) и угол в виде (CosA + SinA*i), а потом перемножим эти два числа:

(X + Y*i)(CosA + SinA*i) = (X*CosA + Y*SinA*(i^2) + (X*SinA + Y*CosA)*i) = (X*CosA - Y*SinA + (X+SinA + Y+CosA)*i)

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

Теперь мы без проблем можем написать код:

Function CreateORect(Pos: TVec2D; Angle, Width, Height: Single): TORect;
  Var
    I: Integer;
begin
  Result[0] := Vec2D( Width/2,  Height/2);
  Result[1] := Vec2D(-Width/2,  Height/2);
  Result[2] := Vec2D(-Width/2, -Height/2);
  Result[3] := Vec2D( Width/2, -Height/2);
    For I := 0 to 3 do begin
      Result[I] := Vec2D(Result[I].X*Cos(Angle) - Result[I].Y*Sin(Angle),
                         Result[I].X*Sin(Angle) + Result[I].Y*Cos(Angle));
      Result[I] := Add2D(Result[I], Pos);
    end;
end;

Лучи и отрезки

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

3д

Алгоритмы в разделе 2д подобраны таким образом, чтобы они легко обобщались на трехмерный случай.

Шар - шар

Идея абсолютно аналогична алгоритму Circle Vs Circle - нужно вычислить расстояние между центрами сфер и сравнить его с суммой радиусов.

Function SphereVsSphere(A, B: TSphere): Boolean;
begin
  Result := Dist3D(A.Pos, B.Pos) < A.Rad + B.Rad;
end;

AABox - AABox

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

Function ColAABoxVsAABox(A, B: TAABox): Boolean;
begin
  Result := ColLine1DVsLine1D(A.Min.X, A.Max.X, B.Min.X, B.Max.X) And
            ColLine1DVsLine1D(A.Min.Y, A.Max.Y, B.Min.Y, B.Max.Y) And
            ColLine1DVsLine1D(A.Min.Z, A.Max.Z, B.Min.Z, B.Max.Z);
end;

OBox - OBox

Идея аналогична алгоритму ORect vs ORect - только теперь мы будем искать не разделяющую ось, а разделяющую плоскость.

Type
TOBox = packed record
  // вершины ящика
  V: Array[0..7] Of TVec3D;
  // плоскости, которые содержат стороны ящика
  P: Array[0..5] Of TPlane;
end;

Function ClassifyOBox(P: TPlane; O: TOBox): Integer;
  Var
    I: Integer;
    InFront: Boolean;
    InBack: Boolean;
    D: Single;
begin
  InFront := False;
  InBack := False;
    For I := 0 to 7 do begin
      D := GetDistToPlane(O.V[I], P);
        If D > EPS then
          InFront := True;
        If D < -EPS then
          InBack := True;
    end;
    If InFront And InBack then
      Result := 0
    else
    If InFront then
      Result := 1
    else
      Result := -1;
end;

Function ColOBoxVsOBox(A, B: TOBox): Boolean;
  Var
    I: Integer;
begin
  Result := True;
    For I := 0 to 5 do
      If ClassifyOBox(A.P[I], A)*
         ClassifyOBox(A.P[I], B) < 0 then
        Result := False;
    For I := 0 to 5 do
      If ClassifyOBox(B.P[I], A)*
         ClassifyOBox(B.P[I], B) < 0 then
        Result := False;
end;

Ну, и, конечно же, функция для перевода OBox'а из удобных для понимания в удобные для обработки столкновения данные. Я не стал мудрить и приумывать алгоритмы с циклами, чтобы не расписывать случаи, а просто свел каждый случай к одной строке. Входные данные - центр ящика, направление вправо и вверх и размеры ящика по всем трем измерениям (W = width = размер вправо, H = Height = размер вверх, D = Depth = размер вперед).

//
//  Создает плоскость по точке, лежащей на ней, и нормали
//
Function Plane(O, N: TVec3D): TPlane;
begin
  Result.N := N;
  Result.D := - Dot3D(O, N);
end;

Function CreateOBox(Pos, Right, Up: TVec3D; W, H, D: Single): TOBox;
  Var
    I: Integer;
    // Forward
    Frd: TVec3D;
begin
  // На всякий случай
  Right := Norm3D(Right);
  Up := Norm3D(Up);
  // Вычисляем вектор вперед
  Frd := Cross3D(Right, Up);
  // Строим плоскости
  Result.P[0] := Plane(Add3D(Pos, Mul3D(Right,  W/2)),       Right);
  Result.P[1] := Plane(Add3D(Pos, Mul3D(Right, -W/2)), Mul3D(Right, -1));
  Result.P[2] := Plane(Add3D(Pos, Mul3D(Up,  H/2)),       Up);
  Result.P[3] := Plane(Add3D(Pos, Mul3D(Up, -H/2)), Mul3D(Up, -1));
  Result.P[4] := Plane(Add3D(Pos, Mul3D(Frd,  D/2)),       Frd);
  Result.P[5] := Plane(Add3D(Pos, Mul3D(Frd, -D/2)), Mul3D(Frd, -1));
  // Строим вершины
  Result.V[0] := Add3D(Add3D(Pos, Mul3D(Right,  W/2)), Add3D(Mul3D(Up,  H/2), Mul3D(Frd,  D/2)));
  Result.V[1] := Add3D(Add3D(Pos, Mul3D(Right, -W/2)), Add3D(Mul3D(Up,  H/2), Mul3D(Frd,  D/2)));
  Result.V[2] := Add3D(Add3D(Pos, Mul3D(Right,  W/2)), Add3D(Mul3D(Up, -H/2), Mul3D(Frd,  D/2)));
  Result.V[3] := Add3D(Add3D(Pos, Mul3D(Right, -W/2)), Add3D(Mul3D(Up, -H/2), Mul3D(Frd,  D/2)));
  Result.V[4] := Add3D(Add3D(Pos, Mul3D(Right,  W/2)), Add3D(Mul3D(Up,  H/2), Mul3D(Frd, -D/2)));
  Result.V[5] := Add3D(Add3D(Pos, Mul3D(Right, -W/2)), Add3D(Mul3D(Up,  H/2), Mul3D(Frd, -D/2)));
  Result.V[6] := Add3D(Add3D(Pos, Mul3D(Right,  W/2)), Add3D(Mul3D(Up, -H/2), Mul3D(Frd, -D/2)));
  Result.V[7] := Add3D(Add3D(Pos, Mul3D(Right, -W/2)), Add3D(Mul3D(Up, -H/2), Mul3D(Frd, -D/2)));
end;

Лучи и отрезки

Совершенно анлогично двумерному случаю - лучи и отрезки в пространстве являются вырожденными случаями OBox'ов.

Заключение

ФИКС МИ!!!

Пояснение для алгоритма с поворотом ORect'а. Если вектор (x, y) имеет длину L и образует угол B с осью OX, то X = L*CosB, Y = L*SinB. Повернутый вектор должен иметь координаты X' = L*Cos(A+B) = L*(CosA*CosB - SinA*SinB) = (L*CosA)*CosB - (L*SinA)*SinB = X*CosB - Y*SinB, что мы и получили в формуле с комплексной единицей. Аналогично с Y-овой координатой.