22

我希望确定光线和盒子之间的交点。盒子由它的最小 3D 坐标和最大 3D 坐标定义，射线由它的原点和它指向的方向定义。

目前，我正在为盒子的每个面形成一个平面，并将射线与平面相交。如果光线与平面相交，那么我检查相交点是否实际上在盒子的表面上。如果是这样，我检查它是否是这条射线最近的交点并返回最近的交点。

我检查平面交点是否在盒子表面本身的方法是通过一个函数

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是对角。我的实现大部分时间都有效，但有时它给了我错误的交集。请看图片：

替代文字

该图像显示了来自相机眼睛并撞击盒子表面的光线。其他光线是盒子表面的法线。可以看出，特别是一条光线（实际上是看到的法线）从盒子的“背面”出来，而法线应该从盒子的顶部出来。这似乎很奇怪，因为有多个其他光线正确地击中了盒子的顶部。

我想知道我检查交点是否在盒子上的方式是否正确，或者我是否应该使用其他算法。

谢谢。

4

5 回答 5

17

通过 epsilon 增加事物实际上并不是一个很好的方法，因为您现在在盒子的边缘有一个大小为 epsilon 的边框，光线可以通过它。所以你会摆脱这组（相对常见的）奇怪的错误，并最终得到另一组（罕见的）奇怪的错误。

我假设您已经在设想您的光线沿着其矢量以某种速度行进，并找到与每个平面相交的时间。因此，例如，如果您在 处与平面相交，并且您的光线从x=x0方向射入，则相交时间为。如果是负面的，忽略它——你会走另一条路。如果为零，您必须决定如何处理这种特殊情况——如果您已经在飞机上，您是弹开它，还是穿过它？您可能还想作为一种特殊情况处理（这样您就可以碰到盒子的边缘）。(rx,ry,rz)(0,0,0)t = x0/rxttrx==0

无论如何，现在你有了你撞击那架飞机的确切坐标：它们是(t*rx , t*ry , t*rz)。现在你可以读出它们是否t*ry和t*rz它们需要在矩形内（即沿着这些轴的立方体的最小值和最大值之间）。 您不测试 x 坐标，因为您已经知道您击中了它 再次，您必须决定是否/如何处理击中角落作为特殊情况。此外，现在您可以按时间排序与各种表面的碰撞，并选择第一个作为碰撞点。

这允许您在不使用任意 epsilon 因子的情况下计算您的光线是否以及在何处与您的立方体相交，以达到浮点运算可能的精度。

因此，您只需要三个函数，就像您已经拥有的函数一样：一个用于测试您是否在yz假设您 hit的情况下击中x，以及相应的xz假设xy您击中yand的函数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) 取决于您击中的飞机。

于 2010-04-01T23:24:17.963 回答
2

PointOnBoxFace应该是二维检查而不是三维检查。例如，如果您正在对z = z_min平面进行测试，那么您应该只需要比较x它们y各自的边界。您已经发现z坐标是正确的。当您“重新检查”第三个坐标时，浮点精度可能会让您绊倒。

例如，如果z_min是 1.0，您首先针对该平面进行测试。x您会找到 ( , y, 0.999999999)的交点。现在，即使x和y都在界限内，z也不太正确。

于 2010-04-01T23:57:35.883 回答
0

代码看起来不错。尝试找到这个特定的射线并对其进行调试。

于 2010-04-01T21:47:30.160 回答
0

编辑：忽略这个答案（请参阅下面的评论，我非常有说服力地展示了我的方式的错误）。

您正在测试该点是否在体积内，但该点位于该体积的外围，因此您可能会发现它是体积外的“无穷小”距离。尝试通过一些小的 epsilon 来增加盒子，例如：

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 的评论，这让我找到了一个很好的页面，详细解释了这项技术。）

于 2010-04-01T21:49:41.543 回答
0

会不会是那条光线最终正好穿过盒子的边缘？浮点舍入错误可能会导致右侧和背面都错过它。

于 2010-04-01T21:50:47.307 回答