Попытка оптимизировать линию и пересечение цилиндра

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

Это то, что я использую, может помочь:

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;
}

Answer 2

цилиндр круглый, верно? Вы можете преобразовать координаты так, чтобы центральная линия цилиндра функционировала как ось Z. Тогда у вас есть двумерная задача о пересечении линии с окружностью. Точки пересечения будут обозначать параметр, проходящий от 0 до 1 по длине линии, поэтому вы можете рассчитать их положение в этой системе координат и сравнить их с верхом и низом цилиндра.

Вы должны быть в состоянии сделать все это в закрытом виде. Нет допусков. И, конечно же, вы получите особенности и мнимые решения. Вы, кажется, думали обо всем этом, так что, думаю, я не уверен, в чем вопрос.

Answer 3

Хороший ответ Майка. Для любой сложной фигуры лучше всего найти матрицу преобразования T, которая отображает ее в хорошую вертикальную версию, в данном случае прямой цилиндр с радиусом 1. высота 1, хорошо бы справился с этой задачей. Разберитесь с новой строкой в ​​этом новом пространстве, выполните расчет, конвертируйте обратно.

Однако, если вы хотите оптимизировать (и это звучит так, как вы), вероятно, есть нагрузки, которые вы можете сделать.

Например, вы можете рассчитать кратчайшее расстояние между двумя линиями - возможно, используя правило точечного произведения - представьте, что вы объединяете две строки в один поток. Тогда, если этот поток является самым коротким из всех возможных потоков, то он будет перпендикулярен обеим линиям, поэтому Thread.LineA = Thread.LineB = 0

Если кратчайшее расстояние больше радиуса цилиндра, то это промах.

Вы можете определить местоположение цилиндра, используя x, y, z, и вычеркнуть все это как какое-то ужасное квадратное уравнение, и оптимизировать, вычислив сначала дискриминант и вернув нулевой удар, если он отрицательный.

Чтобы определить местоположение, возьмите любую точку P = (x, y, z). опустите его как перпендикуляр к центральной линии вашего цилиндра и посмотрите на его величину в квадрате. если это равно R ^ 2, то точка находится в.

Затем вы добавляете свою строку {s = U + lamda * V} в этот беспорядок, и у вас получится какой-то неприятный квадратик в lamda. но это, вероятно, будет быстрее, чем возиться с матрицей, если только вы не можете заставить аппаратное обеспечение сделать это (я предполагаю, что OpenGL имеет некоторую функцию, чтобы заставить аппаратное обеспечение делать это сверхбыстрым).

Все зависит от того, сколько оптимизации вы хотите; лично я согласился бы с ответом Майка, если бы не было действительно веской причины не делать этого.

PS. Вы можете получить больше помощи, если объясните, какую методику вы используете, а не просто выводите код, оставив читателю возможность выяснить, что вы делаете.

Answer 4

Задумывались ли вы об этом таким образом?

Цилиндр - это, по сути, "жирный" отрезок, поэтому для этого можно найти ближайшую точку на отрезке (центральная линия цилиндра), чтобыотрезок (отрезок, который вы проверяете на пересечение).

Оттуда вы проверяете расстояние между этой ближайшей точкой и другим отрезком и сравниваете его с радиусом.

ВВ этот момент у вас есть тест «Pill vs Line Segment», но вы, вероятно, могли бы провести несколько тестов на плоскости, чтобы «отрубить» колпачки на пилюле, чтобы сделать цилиндр.надеюсь, это поможет (: