c++ - 尝试优化线与圆柱相交

Question

我的大脑一直在思考我一直在研究的线段与圆柱相交例程。

 /// Line segment VS <cylinder>
 // - cylinder (A, B, r) (start point, end point, radius)
 // - line has starting point (x0, y0, z0) and ending point (x0+ux, y0+uy, z0+uz) ((ux, uy, uz) is "direction")
 // => start = (x0, y0, z0)
 //   dir = (ux, uy, uz)
 //   A
 //   B
 //   r
 //   optimize? (= don't care for t > 1)
 // <= t  = "time" of intersection
 //   norm = surface normal of intersection point
 void CollisionExecuter::cylinderVSline(const Ogre::Vector3& start, const Ogre::Vector3& dir, const Ogre::Vector3& A, const Ogre::Vector3& B, const double r,
             const bool optimize, double& t, Ogre::Vector3& normal) {
  t = NaN;

  // Solution : http://www.gamedev.net/community/forums/topic.asp?topic_id=467789
  double cxmin, cymin, czmin, cxmax, cymax, czmax;
  if (A.z < B.z) { czmin = A.z - r; czmax = B.z + r; } else { czmin = B.z - r; czmax = A.z + r; }
  if (A.y < B.y) { cymin = A.y - r; cymax = B.y + r; } else { cymin = B.y - r; cymax = A.y + r; }
  if (A.x < B.x) { cxmin = A.x - r; cxmax = B.x + r; } else { cxmin = B.x - r; cxmax = A.x + r; }
  if (optimize) {
   if (start.z >= czmax && (start.z + dir.z) > czmax) return;
   if (start.z <= czmin && (start.z + dir.z) < czmin) return;
   if (start.y >= cymax && (start.y + dir.y) > cymax) return;
   if (start.y <= cymin && (start.y + dir.y) < cymin) return;
   if (start.x >= cxmax && (start.x + dir.x) > cxmax) return;
   if (start.x <= cxmin && (start.x + dir.x) < cxmin) return;
  }

  Ogre::Vector3 AB = B - A;
  Ogre::Vector3 AO = start - A;
  Ogre::Vector3 AOxAB = AO.crossProduct(AB);
  Ogre::Vector3 VxAB  = dir.crossProduct(AB);
  double ab2 = AB.dotProduct(AB);
  double a = VxAB.dotProduct(VxAB);
  double b = 2 * VxAB.dotProduct(AOxAB);
  double c = AOxAB.dotProduct(AOxAB) - (r*r * ab2);
  double d = b * b - 4 * a * c;
  if (d < 0) return;
  double time = (-b - sqrt(d)) / (2 * a);
  if (time < 0) return;

  Ogre::Vector3 intersection = start + dir * time;        /// intersection point
  Ogre::Vector3 projection = A + (AB.dotProduct(intersection - A) / ab2) * AB; /// intersection projected onto cylinder axis
  if ((projection - A).length() + (B - projection).length() > AB.length()) return; /// THIS IS THE SLOW SAFE WAY
  //if (projection.z > czmax - r || projection.z < czmin + r ||
  // projection.y > cymax - r || projection.y < cymin + r ||
  // projection.x > cxmax - r || projection.x < cxmin + r ) return; /// THIS IS THE FASTER BUGGY WAY

  normal = (intersection - projection);
  normal.normalise();
  t = time; /// at last
 }

我想到了这种方法来加快发现交点的投影是否在圆柱体的长度之内。但是，它不起作用，我无法真正理解它，因为它看起来很合乎逻辑: 如果投影点的 x、y 或 z 坐标不在圆柱体的范围内，则应将其视为在圆柱体范围之外。但这似乎在实践中行不通。

如有任何帮助，我们将不胜感激!

干杯，

比尔·科西亚斯

编辑: 问题似乎随着边界情况而增加，即当圆柱体平行于其中一个轴时。舍入误差进入等式，“优化”停止正常工作。

也许，如果逻辑是是正确的，那么通过插入一点容忍度问题就会消失，例如:

  if (projection.z > czmax - r + 0.001 || projection.z < czmin + r - 0.001 || ... etc...

Answer 1

圆柱体是圆形的吧？您可以变换坐标，使圆柱体的中心线作为 Z 轴。然后你有一个与圆相交的线的二维问题。交点将根据沿直线长度从 0 到 1 的参数，因此您可以计算它们在该坐标系中的位置，并与圆柱体的顶部和底部进行比较。

您应该能够以封闭形式完成所有操作。没有公差。当然，你会得到奇点和假想的解决方案。您似乎已经想到了所有这些，所以我想我不确定问题是什么。