试图优化线路VS缸路口 [英] Trying to optimize line vs cylinder intersection

问题描述

我的大脑已经被融化了线路段VS缸路口例行我一直在努力。

  ///线段VS＆LT;气缸GT;
 //  - 气缸（A，B，R）（起点，终点，半径）
 //  - 线已开始点（X0，Y0，Z0）和结束点（X0 +​​ UX，Y0 +乌伊，Z0 + UZ）（（UX，UY，UZ）为方向）
 // =＆GT;开始=（X0，Y0，Z0）
 // DIR =（UX，UY，UZ）
 //   一个
 // B
 //ř
 //优化？ （=不在乎T＆GT; 1）
 //＆LT;路口= T =时间
 //规范=表面法线交点
 无效CollisionExecuter :: cylinderVSline（常量食人魔:: Vector3类型和放大器;启动，常量食人魔:: Vector3类型和放大器;目录，常量食人魔:: Vector3类型和放大器; A，常量食人魔:: Vector3类型和B，const的双R，
             常量布尔优化，双和放大器; T，食人魔:: Vector3类型和放大器;正常） {
  T = NaN的;

  //解决方案：http://www.gamedev.net/community/forums/topic.asp?topic_id=467789
  双cxmin，cymin，czmin，cxmax，cymax，czmax;
  如果（A.z＆LT; B.z）{czmin = A.z  -  R的; czmax = B.z + R; }其他{czmin = B.z  -  R的; czmax = A.z + R; }
  如果（A.y＆LT; B.y）{cymin = A.y  -  R的; cymax = B.y + R; }其他{cymin = B.y  -  R的; cymax = A.y + R; }
  如果（A.x＆LT; B.x）{cxmin = A.x  -  R的; cxmax = B.x + R; }其他{cxmin = B.x  -  R的; cxmax = A.x + R; }
  如果（优化）{
   如果（start.z＆GT; = czmax和放大器;及（start.z + dir.z）＆GT; czmax）回报;
   如果（start.z＆LT; = czmin和放大器;及（start.z + dir.z）＆LT; czmin）回报;
   如果（start.y＆GT; = cymax和放大器;及（start.y + dir.y）＆GT; cymax）回报;
   如果（start.y＆LT; = cymin和放大器;及（start.y + dir.y）＆LT; cymin）回报;
   如果（start.x＆GT; = cxmax和放大器;及（start.x + dir.x）＆GT; cxmax）回报;
   如果（start.x＆LT; = cxmin和放大器;及（start.x + dir.x）＆LT; cxmin）回报;
  }

  食人魔:: Vector3类型AB = B  -  A;
  食人魔:: Vector3类型AO =启动 -  A;
  食人魔:: Vector3类型AOxAB = AO.crossProduct（AB）;
  食人魔:: Vector3类型VxAB = dir.crossProduct（AB）;
  双AB2 = AB.dotProduct（AB）;
  双A = VxAB.dotProduct（VxAB）;
  双B = 2 * VxAB.dotProduct（AOxAB）;
  双C = AOxAB.dotProduct（AOxAB） - （R * R * AB2）;
  双D = B * B  -  4 * A * C;
  如果（D＆LT; 0）回报;
  双时间=（-b  - 的sqrt（D））/（2 * A）;
  如果（时间小于0）返回;

  食人魔:: Vector3类型交叉口=开始+ DIR *的时间; ///交点
  食人魔:: Vector3类型投影= A +（AB.dotProduct（路口 -  A）/ AB2）* AB; ///交集投影到圆柱轴
  如果（（投影 -  A）.length（）+（B  - 投影）.length（）＆GT; AB.length（））回报; ///这是SLOW安全的方式
  //如果（projection.z＆GT; czmax  -  R的|| projection.z＆LT; czmin + R ||
  // projection.y＆GT; cymax  -  R的|| projection.y＆LT; cymin + R ||
  // projection.x＆GT; cxmax  -  R的|| projection.x＆LT; cxmin + R）返回; ///这是更快BUGGY WAY

  正常=（路口 - 投影）;
  normal.normalise（）;
  t =时间; /// 最后
 }
 

我已经想到了这种方式加快交点的投影是否在圆柱体的长度内发现。但是，它不工作，我真的不能得到它，因为它似乎很符合逻辑的： 如果投影点的x，y或z轴坐标是不内圆柱体的限制，但是应该考虑外面。看来虽然这不会在实践中

任何帮助将是很大的AP preciated！

干杯，

比尔Kotsias

编辑：看来，问题上升与边界的情况下，即当气缸平行于轴线之一。舍入误差来代入公式和优化停止正常工作。

也许，如果逻辑的是的正确，这些问题将通过插入位公差像消失：

 如果（projection.z＆GT; czmax  -  R + 0.001 || projection.z＆LT; czmin + R  -  0.001 || ...等...
 

解决方案

气缸是圆形的，对不对？可以坐标转换，以使气缸作为Z轴的中心线。然后，你必须相交用圆圈的线的2D问题。交点将在一个参数从0沿线的长度要1而言，这样就可以计算出它们的位置在该坐标系中，并比较圆柱体的顶部和底部。

您应该能够做到这一切在封闭的形式。无公差。而且，当然，你会得到奇点和虚的解决方案。你似乎已经想到了这一切，所以我想我不知道问题是什么。

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
 }

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.

Any help would be greatly appreciated!

Cheers,

Bill Kotsias

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

解决方案

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.

这篇关于试图优化线路VS缸路口的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！