logo标签列表

尝试优化直线与圆柱体的相交问题。

c++optimizationmath3dintersection
6

我一直在研究线段与圆柱体相交的算法，这让我的大脑感到非常困惑。

 /// 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坐标不在圆柱体的限制范围内，则应将其视为在外部。然而，在实践中似乎并不起作用。
非常感谢任何帮助！
问候，
Bill Kotsias
编辑：问题似乎出现在边界情况下，即当圆柱体与其中一个轴平行时。舍入误差会影响计算，并且“优化”无法正确工作。
也许，如果逻辑是正确的，通过插入一些公差，问题就会消失，例如：
  if (projection.z > czmax - r + 0.001 || projection.z < czmin + r - 0.001 || ... etc...
4个回答
6
圆柱体是圆形的，对吧？您可以转换坐标系，使得圆柱体的中心线作为Z轴。然后，您就有了一个二维问题，即如何将一条直线与一个圆相交。交点将以参数的形式从0到1沿着线的长度进行计算，因此您可以在该坐标系中计算它们的位置，并将其与圆柱体的顶部和底部进行比较。
您应该能够全部以闭合形式完成。没有公差。当然，您会得到奇点和虚数解。您似乎已经考虑到了所有这些，所以我不确定问题是什么。
4

这是我使用的内容，它可能有助于你：

bool d3RayCylinderIntersection(const DCylinder &cylinder,const DVector3 &org,const DVector3 &dir,float &lambda,DVector3 &normal,DVector3 &newPosition)
// Ray and cylinder intersection
// If hit, returns true and the intersection point in 'newPosition' with a normal and distance along
// the ray ('lambda')
{
  DVector3 RC;
  float d;
  float t,s;
  DVector3 n,D,O;
  float ln;
  float in,out;

  RC=org; RC.Subtract(&cylinder.position);
  n.Cross(&dir,&cylinder.axis);

  ln=n.Length();

  // Parallel? (?)
  if((ln<D3_EPSILON)&&(ln>-D3_EPSILON))
    return false;

  n.Normalize();

  d=fabs(RC.Dot(n));

  if (d<=cylinder.radius)
  {
    O.Cross(&RC,&cylinder.axis);
    //TVector::cross(RC,cylinder._Axis,O);
    t=-O.Dot(n)/ln;
    //TVector::cross(n,cylinder._Axis,O);
    O.Cross(&n,&cylinder.axis);
    O.Normalize();
    s=fabs( sqrtf(cylinder.radius*cylinder.radius-d*d) / dir.Dot(O) );

    in=t-s;
    out=t+s;

    if (in<-D3_EPSILON)
    {
      if(out<-D3_EPSILON)
        return false;
      else lambda=out;
    } else if(out<-D3_EPSILON)
    {
      lambda=in;
    } else if(in<out)
    {
      lambda=in;
    } else
    {
      lambda=out;
    }

    // Calculate intersection point
    newPosition=org;
    newPosition.x+=dir.x*lambda;
    newPosition.y+=dir.y*lambda;
    newPosition.z+=dir.z*lambda;
    DVector3 HB;
    HB=newPosition;
    HB.Subtract(&cylinder.position);

    float scale=HB.Dot(&cylinder.axis);
    normal.x=HB.x-cylinder.axis.x*scale;
    normal.y=HB.y-cylinder.axis.y*scale;
    normal.z=HB.z-cylinder.axis.z*scale;
    normal.Normalize();
    return true;
  }

  return false;
}
2
你能解释一下你在给函数输入的变量是什么吗？ - JokerMartini
3
你有没有想过这种方法呢？
一个圆柱实质上是一个“粗壮”的线段，因此一种实现方式是找到线段（圆柱的中心线）上最靠近另一个线段（你正在测试相交的线段）的点。
然后，你检查这个最接近点与另一个线段之间的距离，并将其与半径进行比较。
此时，你就有了“药丸对线段”测试，但你可能可以进行一些平面测试，以“割掉”药丸上的盖子来制造圆柱体。
希望这些内容能对你有所帮助（：）
2

迈克的回答很好。对于任何棘手的形状，最好找到转换矩阵T，将其映射到一个漂亮的竖直版本中，在这种情况下，半径为1、高度为1的圆柱体可以完美地完成工作。在这个新空间中找出你的新线，进行计算，然后转换回去。

然而，如果你想要优化（听起来你是这样做的），那么可能有很多事情可以做。

例如，你可以计算两条线之间的最短距离——可能使用点积规则——想象一下用线连接两条线。然后，如果这根线是所有可能线中最短的，那么它将垂直于两条线，因此Thread.LineA = Thread.LineB = 0

如果最短距离大于圆柱的半径，则会错过。

你可以使用x、y、z定义圆柱的轨迹，并将整个过程处理为一些可怕的二次方程，通过先计算判别式来进行优化，并在判别式为负时返回无撞击。

要定义轨迹，请取任意点P=(x,y,z)。将其作为垂线投影到圆柱体的中心线上，并查看其平方大小。如果等于R^2，则该点在内。

然后将你的线{s=U+lamda*V}扔进去，你会得到一些丑陋的二次方程。但是，除非你可以让硬件来做这个工作（我猜OpenGL有一些函数可以让硬件以超快的速度完成这项工作），否则这可能比摆弄矩阵更快。

这一切都取决于你想要多少优化；个人认为，除非有真正的好理由不这样做，否则我会选择迈克的答案。

另外，如果你解释一下你使用的技术，而不仅仅是倾倒代码，那么你可能会得到更多的帮助，让读者能够理解你在做什么。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接