尝试优化直线与圆柱相交 [英] Trying to optimize line vs cylinder intersection

问题描述

我一直在研究一个线段与圆柱体相交的程序，我的大脑一直在融化.

My brain has been melting over a line segment-vs-cylinder intersection routine I've been working on.

 /// 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 坐标不在圆柱的范围内，则应考虑在圆柱范围之外.虽然这在实践中似乎行不通.

I have thought of this way to speed up the discovery of whether the projection of the intersection point lies inside the cylinder's length. However, it doesn't work and I can't really get it because it seems so logical : if the projected point's x, y or z co-ordinates are not within the cylinder's limits, it should be considered outside. It seems though that this doesn't work in practice.

任何帮助将不胜感激！

干杯，

比尔科西亚斯

问题似乎出现在边界情况下，即当圆柱体平行于其中一个轴时.等式中出现舍入错误，优化"停止正常工作.

Edit : It seems that the problems rise with boundary-cases, i.e when the cylinder is parallel to one of the axis. Rounding errors come into the equation and the "optimization" stops working correctly.

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

Maybe, if the logic is correct, the problems will go away by inserting a bit of tolerance like :

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

推荐答案

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

The cylinder is circular, right? You could transform coordinates so that the center line of the cylinder functions as the Z axis. Then you have a 2D problem of intersecting a line with a circle. The intersection points will be in terms of a parameter going from 0 to 1 along the length of the line, so you can calculate their positions in that coordinate system and compare to the top and bottom of the cylinder.

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

You should be able to do it all in closed form. No tolerances. And sure, you will get singularities and imaginary solutions. You seem to have thought of all this, so I guess I'm not sure what the question is.

这篇关于尝试优化直线与圆柱相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！