Теория пересечения лучей-бокса

Question

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

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

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

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 это противоположный угол.Моя реализация работает большую часть времени, но иногда дает неправильное пересечение.Пожалуйста, смотрите изображение:

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

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

Спасибо.

Answer 1

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

Я предполагаю, что вы уже представляете, что ваш луч движется с некоторой скоростью вдоль своего вектора, и находите время пересечения с каждой плоскостью.Так, например, если вы пересекаете плоскость в точке 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 находятся внутри прямоугольника, в котором они должны находиться (т.между минимумом и максимумом куба по этим осям). Вы не проверяете координату x, потому что уже знаете, что попали в нее. Опять же, вам нужно решить, следует ли и как обрабатывать попадания в углы в особом случае.Кроме того, теперь вы можете упорядочить столкновения с различными поверхностями по времени и выбрать первую из них в качестве точки столкновения.

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

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

---

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

#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....
}

(Я только что напечатал это, не скомпилировал, так что остерегайтесь ошибок.) (Редактировать:только что исправил i -> first.)

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

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;
...

Технически правильный способ сравнения почти равных чисел — это привести их битовые представления к целым числам и сравнить целые числа с некоторым небольшим смещением, например, в 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;
}

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