Могу ли я предложить другой подход?Рассмотрим кадр с началом position и базисными векторами
u = { u.x, u.y, u.z }
v = { v.x, v.y, v.z }
direction = { direction.x, direction.y, direction.z}
Шаг 1: Формируем матрицу
M = {
{u.x, v.x, direction.x},
{u.y, v.y, direction.y},
{u.z, v.z, direction.z}
}
Шаг 2: Вычислите вектор w, который является решением системы уравнений лайнера 3 x 3
M * w = origin - position, то есть
w = inverse(M) * (origin - position);
Убедитесь, что direction не находится в одной плоскости сu, v, в противном случае пересечения нет и inverse(M) не существует.
Шаг 3: , если 0.0 <= w.x && w.x <= 1.0 && 0.0 <= w.y && w.y <= 1.0, то линия пересекает параллелограмм, натянутый на векторы u, v, и точка пересечения равна
w0 = { w.x, w.y , 0 };
intersection = position + M * w0;
, в противном случаелиния не пересекает параллелограмм, натянутый на векторы u, v
Идея этого алгоритма состоит в том, чтобы рассмотреть (неортонормальный) фрейм position, u, v, direction.Тогда матрица M меняет все в координатах этого нового кадра.В этом кадре линия является вертикальной, параллельной оси "z-", точка origin имеет координаты w, а вертикальная линия через w пересекает плоскость в w0.
Редактировать 1: Вот формула шаблона для инверсии матрицы 3x3:
Если исходная матрица M равна
a b c
d e f
g h i
, инверсия равна
(1 / det(M)) * {
{e*i - f*h, c*h - b*i, b*f - c*e},
{f*g - d*i, a*i - c*g, c*d - a*f},
{d*h - e*g, b*g - a*h, a*e - b*d},
}
, где
det(M) = a*(e*i - f*h) + b*(f*g - d*i) + c*(d*h - e*h)
- определитель M.
Таким образом, алгоритм инверсии может быть следующим:
Дан
M = {
{a, b, c},
{d, e, f},
{g, h, i},
}
- Рассчитать
inv_M = {
{e*i - f*h, c*h - b*i, b*f - c*e},
{f*g - d*i, a*i - c*g, c*d - a*f},
{d*h - e*g, b*g - a*h, a*e - b*d},
};
Рассчитать
det_M = a*inv_M[1][1] + b*inv_M[2][1] + c*inv_M[3][1];
Возвращает обратную матрицу M
inv_M = (1/det_M) * inv_M;
Редактировать 2: Давайте попробуем другой подход, чтобы ускорить процесс.
Шаг 1: Для каждой плоскости, определяемой точкой position и двумя векторами u и v, предварительно вычисляются следующие значения:
normal = cross(u, v);
u_dot_u = dot(u, u);
u_dot_v = dot(u, v);
v_dot_v = dot(v, v); // all these need to be computed only once for the u and v vectors
det = u_dot_u * v_dot_v - u_dot_v * u_dot_v; // again only once per u and v
Шаг 2: Теперь для заданной линии с точкой origin и направлением direction, как и раньше, вычислите точку пересечения int_point с плоскостью, натянутой на u и v:
t = dot(normal, position - origin) / dot(normal, direction);
int_point = origin + t * direction;
rhs = int_point - position;
Шаг 3: Calcualte
u_dot_rhs = dot(u, rhs);
v_dot_rhs = dot(v, rhs);
w1 = (v_dot_v * u_dot_rhs - u_dot_v * v_dot_rhs) / det;
w2 = (- u_dot_v * u_dot_rhs + u_dot_u * v_dot_rhs) / det;
Шаг 4:
if (0 < = w1 && w1 <= 1 && 0 < = w2 && w2 <= 1 ){
int_point is in the parallelogram;
}
else{
int_point is not in the parallelogram;
}
Так что яЯ делаю здесь, в основном, нахожу точку пересечения линии origin, direction с плоскостью, заданной position, u, v, и ограничиваю себя плоскостью, которая позволяет мне работать в 2D, а не в 3D.Я представляю
int_point = position + w1 * u + w2 * v;
rhs = int_point - position = w1 * u + w2 * v
и нахожу w1 и w2 путем умножения точки этого векторного выражения на базовые векторы u и v, что приводит к линейной системе 2x2, котораяЯ решаю напрямую.