6

Есть 2 треугольника заданные тремя пространственными координатами (x,y,z) Допустим у нас есть подозрение по их пересечению треугольников (образующие кубы пересекаются).

Вопрос: как определить факт пересечения этих треугольников. Поясню. Мне не нужно знать в каком отрезке они пересекаются, и даже не нужно знать одну из точек пересечения. Меня интересует "быстрый" алгоритм поиска факта пересечения, т.е. true или false.

З.Ы.: Искал в интернете, есть алгоритмы нахождения пересечения, а факта нет. И существуют ли вообще упращенные алгоритмы?

З.Ы.: Кое что нашёл. Есть сайт RealTimeRendering, Там есть метод Fast Triangle-Triangle Intersection test by Tomas Möller. Пока изучаю его. Подозреваю, что есть более быстрые алгоритмы.

3 ответа 3

-1

Записываем точки в виде (1, ax, ay, az)

Считаем плоскость как вектор-определитель (D, A, B, C)

i  j  k  e
1 ax ay az
1 bx by bz
1 cx cy cz

Аналогично пересекаем две получившиеся плоскости.

3
  • 1
    А точно столбец из единиц не справа?
    – VladD
    16 мар 2016 в 15:00
  • @VladD, однородные координаты. Вроде слева, как первая координата. А вообще, я сейчас подумал, что пересечение плоскостей не будет означать пересечение треугольников.
    – Qwertiy
    16 мар 2016 в 15:05
  • 1
    Ну это да, не означает. Но всё же, непонятно, почему первая координата выделена. Давайте проверим на точках (1, 0, 0), (0, 1, 0), (0, 0, 1), которые должны давать плоскость x + y + z = 1.
    – VladD
    16 мар 2016 в 16:53
-1

Два выпуклых объекта не пересекаются тогда и только тогда, когда существует плоскость (для двумерного случая - прямая), такая, что проекции геометрий на эту плоскость (прямую) не пересекаются. http://home.arcor.de/philippe.guigue/triangle_triangle_intersection.htm

3
  • 4
    Окей. И как использовать этот факт? По ссылке написано что-то по теме, но если вы предоставите выжимку или лучше алгоритм, ваш ответ будет гораздо ценнее.
    – VladD
    16 мар 2016 в 14:40
  • есть алгоритм на с++(он в конце статьи)
    – afront
    16 мар 2016 в 16:00
-1

После поисков по просторам итернетов я нашел оптимальный способ описанный Томасом Моллером. Написал код под C# для данного алгоритма.

public bool PointInTriangle2D(float[][] t, float[] p)
{
  bool inside = false;
  int j = 2; // = 3 - 1
  for (int i = 0; i < 3; i++)
  {
    if ((t[i][1] < p[1] && t[j][1] >= p[1] || t[j][1] < p[1] && t[i][1] >= p[1]) &&
        (t[i][0] + (p[1] - t[i][1]) / (t[j][1] - t[i][1]) * (t[j][0] - t[i][0]) < p[0]))
      inside = !inside;
    j = i;
  }
  return inside;
}

public bool Moller1997b(Vertex[] V0, Vertex[] V1)
{
  return Moller1997b(new Vertex[2][] { V0, V1 });
}

public bool Moller1997b(Vertex[][] V)
{
  float[][] dv = new float[2][];
  int[][] sign = new int[2][];
  float[][] pv = new float[2][];
  float[][] t = new float[2][];
  float[][] triange2D = new float[3][];
  float[] point2D = new float[2];
  for (int j = 0; j < 3; ++j)
    triange2D[j] = new float[2];
  for (int j = 0; j < 2; ++j)
  {
    dv[j] = new float[3];
    sign[j] = new int[3];
    pv[j] = new float[3];
    t[j] = new float[2];
  }

  //Находим вектор-нормаль ко второму треугольнику 
  Vertex N1 = (V[1][1] - V[1][0]).VectorProduct(V[1][2] - V[1][0]);
  //и коэфициент плоскости второго треугольника
  float d1 = -N1.ScalarProduct(V[1][0]);
  //Уровнение плоскости второго треугольника будет выглядеть 
  //π2 : N2*X+d2=0, где X-любая точка плоскости (одна из точек v2)
  //Но нам это в данной задаче не важно
  //Проверяем с какой стороны плоскости лежат точки первого треугольника
  for (int i = 0; i < 3; ++i)
  {
    dv[0][i] = N1.ScalarProduct(V[0][i]) + d1;
    sign[0][i] = Math.Abs(dv[0][i]) > epsilant ? Math.Sign(dv[0][i]) : 0;
  }
  //Треугольник 0 не пересекается с плоскостью другого треугольника
  if (sign[0][0].Equals(sign[0][1]) && sign[0][1].Equals(sign[0][2]) && !sign[0][0].Equals(0))
    return false;
  //Треугольники в одной плоскости
  //Как показала практика такие случаи оооочень большая редкость
  if (sign[0][0].Equals(sign[0][1]) && sign[0][1].Equals(sign[0][2]) && sign[0][0].Equals(0))
  {
    //Теперь выберем на какую плоскость (xy, yz, xz) спроецируем треугольники
    float aNX = Math.Abs(N1.X);
    float aNY = Math.Abs(N1.Y);
    float aNZ = Math.Abs(N1.Z);
    float maxN = Math.Max(aNX, Math.Max(aNY, aNZ));
    //Какую компоненту будем игнорить
    int ignoreIndex = (aNX.Equals(maxN)) ? 0 : (aNY.Equals(maxN)) ? 1 : 2;
    //Какие компоненты будем использовать для 2D координат
    int iX = ignoreIndex == 0 ? 2 : 0;
    int iY = ignoreIndex == 1 ? 2 : 1;
    //Проверка принадлежности хотябы одной точки треугольника 0 треугольнику 1
    //http://ru.stackoverflow.com/questions/464787/Точка-внутри-многоугольника
    for (int p = 0; p < 3; ++p)
    {
      for (int i = 0; i < 3; ++i)
      {
        triange2D[i][0] = V[1][i][iX];
        triange2D[i][1] = V[1][i][iY];
      }
      point2D[0] = V[0][p][iX];
      point2D[1] = V[0][p][iY];
      if (PointInTriangle2D(triange2D, point2D))
        return true;
    }
    //или центр масс второго треугольника 1 попадает в треугольник 0. Заодно включает 
    //вопрос совподения (или очень близкого к совпадению) трех точек одного треугольника и трех точек другого треугольника
    for (int i = 0; i < 3; ++i)
    {
      triange2D[i][0] = V[0][i][iX];
      triange2D[i][1] = V[0][i][iY];
    }
    point2D[0] = (V[1][0][iX] + V[1][1][iX] + V[1][2][iX]) / 3f;
    point2D[1] = (V[1][0][iY] + V[1][1][iY] + V[1][2][iY]) / 3f;
    if (PointInTriangle2D(triange2D, point2D))
      return true;
    return false;
  }
  Vertex N0 = (V[0][1] - V[0][0]).VectorProduct(V[0][2] - V[0][0]);
  float d0 = -N0.ScalarProduct(V[0][0]);
  for (int i = 0; i < 3; ++i)
  {
    dv[1][i] = N0.ScalarProduct(V[1][i]) + d0;
    sign[1][i] = Math.Abs(dv[1][i]) > epsilant ? Math.Sign(dv[1][i]) : 0;
  }
  //Треугольник 1 не пересекается с плоскостью другого треугольника
  if (sign[1][0].Equals(sign[1][1]) && sign[1][1].Equals(sign[1][2]) && !sign[1][0].Equals(0))
    return false;
  //Треугольники на разных плоскостях
  Vertex D = N0.VectorProduct(N1);
  float aDX = Math.Abs(D.X);
  float aDY = Math.Abs(D.Y);
  float aDZ = Math.Abs(D.Z);
  float maxD = Math.Max(aDX, Math.Max(aDY, aDZ));
  int Tindex = (aDX.Equals(maxD)) ? 0 : (aDY.Equals(maxD)) ? 1 : 2;
  for (int j = 0; j < 2; ++j)
  {
    //l и r это индексы точек находящихся по одну из сторон плоскости j
    int c = 1, l = 0, r = 2;
    if (sign[j][0].Equals(sign[j][1])) { c = 2; r = 0; l = 1; }
    else if (sign[j][1].Equals(sign[j][2])) { c = 0; r = 2; l = 1; } //Иначе оставляем без изменений
    for (int i = 0; i < 3; ++i)
      pv[j][i] = pv[j][i] = V[j][i][Tindex];//D.ScalarProduct(V[j][i]); //pv[j][i] = V[j][i][Tindex];
    t[j][0] = pv[j][l] + (pv[j][c] - pv[j][l]) * dv[j][l] / (dv[j][l] - dv[j][c]);
    t[j][1] = pv[j][r] + (pv[j][c] - pv[j][r]) * dv[j][r] / (dv[j][r] - dv[j][c]);
    if (t[j][0] > t[j][1])
    {
      float _t = t[j][0];
      t[j][0] = t[j][1];
      t[j][1] = _t;
    }
  }
  return (t[0][0] < t[1][1]) && (t[0][1] > t[1][0]);
}

где ScalarProduct и VectorProduct это векторные и скалярные произведения соответственно

public float ScalarProduct(Vertex rhs)
{
  return X * rhs.X + Y * rhs.Y + Z * rhs.Z;
}

public Vertex VectorProduct(Vertex rhs)
{
  return new Vertex((Y * rhs.Z) - (Z * rhs.Y), (Z * rhs.X) - (X * rhs.Z),
      (X * rhs.Y) - (Y * rhs.X));
}
3
  • 1
    Если это не является ответом, то зачем это размещать как ответ? Тем более, что это ответ-ссылка, что так же не приветствуется правилами сайта.
    – Kromster
    17 мар 2016 в 5:45
  • Вы вообще читаете что написано? "Пока ответом считать не буду, т.к. подозреваю есть более быстрые способы." слово "Пока" вам ничего не говорит? И также "Пока изучаю его. Код выложу позже." тоже ни о чем не говорит? Мой предответ, возможно, будет помощью для тех, кто ищет решение аналогичной задачи. 17 мар 2016 в 5:47
  • Уважаемый Дмитрий, SO это база прикладных вопросов и решений. В текущем виде, такой анонс ответа не является решением. Возможно стоит включить эту ссылку в вопрос.
    – Kromster
    17 мар 2016 в 7:20

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.