Теория перекрестков Ray-Box

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

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

Как я проверяю, находится ли точка пересечения плоскости на самой поверхности коробки, через функцию

bool PointOnBoxFace(R3Point point, R3Point corner1, R3Point corner2)
{
  double min_x = min(corner1.X(), corner2.X());
  double max_x = max(corner1.X(), corner2.X());
  double min_y = min(corner1.Y(), corner2.Y());
  double max_y = max(corner1.Y(), corner2.Y());
  double min_z = min(corner1.Z(), corner2.Z());
  double max_z = max(corner1.Z(), corner2.Z());
  if(point.X() >= min_x && point.X() <= max_x && 
     point.Y() >= min_y && point.Y() <= max_y &&
     point.Z() >= min_z && point.Z() <= max_z)
     return true;

  return false;
}

где corner1 - это один угол прямоугольника для этой грани окна, а corner2 - противоположный угол. Моя реализация работает большую часть времени, но иногда это дает мне неправильное пересечение. См. Изображение:

На изображении показаны лучи, исходящие из глаза камеры, и попадание на поверхность коробки. Другие лучи являются нормалями к поверхности ящика. Можно видеть, что один луч, в частности (это фактически нормальный вид), выходит из "спины" окна, тогда как нормаль должна подниматься сверху. Это кажется странным, поскольку есть несколько других лучей, которые правильно попадают в верхнюю часть коробки.

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

Спасибо.

Ответ 1

Увеличение epsilon на самом деле не является отличным способом сделать это, так как теперь у вас есть граница размера epsilon на краю вашего ящика, через который могут проходить лучи. Таким образом, вы избавитесь от этого (относительно общего) странного набора ошибок и получите еще один (более редкий) набор странных ошибок.

Я предполагаю, что вы уже предполагаете, что ваш луч движется с некоторой скоростью вдоль своего вектора и находит время пересечения с каждой плоскостью. Так, например, если вы пересекаете плоскость в x=x0, и ваш луч идет в направлении (rx,ry,rz) от (0,0,0), тогда время пересечения t = x0/rx. Если t отрицательный, игнорируйте его - вы идете в другую сторону. Если t равно нулю, вы должны решить, как обращаться с этим специальным случаем - если вы уже в самолете, вы отскакиваете от него или проходите через него? Вы также можете обрабатывать rx==0 как особый случай (чтобы вы могли ударить по краю окна).

В любом случае, теперь у вас есть точно координаты, где вы ударили этот самолет: они (t*rx , t*ry , t*rz). Теперь вы можете просто прочитать, находятся ли t*ry и t*rz в пределах прямоугольника, в котором они должны находиться (т.е. Между min и max для куба вдоль этих осей). Вы не проверяете координату x, потому что уже знаете, что попали в нее. Опять же, вам нужно решить, как и как обрабатывать удары по углам в качестве особого случая. Кроме того, теперь вы можете упорядочить свои столкновения с различными поверхностями по времени и выбрать первый в качестве точки столкновения.

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

Итак, вам просто нужны три функции, такие как та, что у вас уже есть: одна для проверки того, попадаете ли вы в yz, если вы нажмете x, а соответствующие для xz и xy, предположив, что вы нажмите y и z соответственно.

Изменить: добавленный код (verbosely) показывает, как выполнять тесты по-разному для каждой оси:

#define X_FACE 0
#define Y_FACE 1
#define Z_FACE 2
#define MAX_FACE 4

// true if we hit a box face, false otherwise
bool hit_face(double uhit,double vhit,
                 double umin,double umax,double vmin,double vmax)
{
  return (umin <= uhit && uhit <= umax && vmin <= vhit && vhit <= vmax);
}

// 0.0 if we missed, the time of impact otherwise
double hit_box(double rx,double ry, double rz,
                double min_x,double min_y,double min_z,
                double max_x,double max_y,double max_z)
{
  double times[6];
  bool hits[6];
  int faces[6];
  double t;
  if (rx==0) { times[0] = times[1] = 0.0; }
  else {
    t = min_x/rx;
    times[0] = t; faces[0] = X_FACE; 
    hits[0] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z);
    t = max_x/rx;
    times[1] = t; faces[1] = X_FACE + MAX_FACE;
    hits[1] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z);
  }
  if (ry==0) { times[2] = times[3] = 0.0; }
  else {
    t = min_y/ry;
    times[2] = t; faces[2] = Y_FACE;
    hits[2] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z);
    t = max_y/ry;
    times[3] = t; faces[3] = Y_FACE + MAX_FACE;
    hits[3] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z);
  }
  if (rz==0) { times[4] = times[5] = 0.0; }
  else {
    t = min_z/rz;
    times[4] = t; faces[4] = Z_FACE;
    hits[4] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y);
    t = max_z/rz;
    times[5] = t; faces[5] = Z_FACE + MAX_FACE;
    hits[5] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y);
  }
  int first = 6;
  t = 0.0;
  for (int i=0 ; i<6 ; i++) {
    if (times[i] > 0.0 && (times[i]<t || t==0.0)) {
      first = i;
      t = times[i];
    }
  }
  if (first>5) return 0.0;  // Found nothing
  else return times[first];  // Probably want hits[first] and faces[first] also....
}

(я просто набрал это, не скомпилировал его, поэтому остерегайтесь ошибок). (Изменить: только что скорректировано a i → first.)

Во всяком случае, дело в том, что вы обрабатываете три направления отдельно и проверяете, произошло ли воздействие в правом поле в координатах (u, v), где (u, v) либо (x, y), (x, z) или (y, z), в зависимости от того, на какую плоскость вы попали.

Ответ 2

PointOnBoxFace должна быть двумерной проверкой вместо трехмерной. Например, если вы тестируете плоскость z = z_min, вам нужно будет только сравнить x и y с соответствующими границами. Вы уже поняли, что координата z верна. Точность с плавающей запятой, вероятно, отключит вас при повторной проверке третьей координаты.

Например, если z_min равно 1.0, вы сначала проверяете эту плоскость. Вы найдете точку пересечения (x, y, 0.999999999). Теперь, хотя x и y находятся в пределах границ, z не совсем прав.

Ответ 3

Код выглядит нормально. Попробуйте найти этот луч и отладить его.

Ответ 4

РЕДАКТИРОВАТЬ: проигнорировать этот ответ (см. комментарии ниже, где я достаточно убедительно показываю ошибку своих путей).

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

double epsilon = 1e-10; // Depends the scale of things in your code.
double min_x = min(corner1.X(), corner2.X()) - epsilon;
double max_x = max(corner1.X(), corner2.X()) + epsilon;
double min_y = min(corner1.Y(), corner2.Y()) - epsilon;
...

Технически, правильный способ сравнения почти равных чисел состоит в том, чтобы отбросить их представления битов в int и сравнить целые числа для некоторого небольшого смещения, например, в C:

#define EPSILON 10 /* some small int; tune to suit */
int almostequal(double a, double b) {
    return llabs(*(long long*)&a - *(long long*)&b) < EPSILON;
}

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

Ответ 5

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