Пересечение луч-квадрат

В 2D у меня есть начальная точка (x_1, y_1), конечная точка (x_2, y_2) и три точки, которые представляют три вершины квадрата (верхняя левая, верхняя правая и нижняя правая вершины).

Моя цель — вернуть true, если луч, исходящий из (x_1, y_1) и проходящий через (x_2, y_2), пересекается с плоскостью (или квадратом), заданной тремя вершинами. В конце концов, я хотел бы расширить это до 3D-пересечения с кубом, поэтому сейчас я использую 3D-векторы.

После рассмотрения многих других вопросов SO я придумал следующий код на Java:

// Determines if a given ray intersects a given square
// R1, R2 are two points on the ray
// S1 (upper left vertex), S2 (upper right vertex), and S3 (lower left vertex)
public static boolean intersectRayWithSquare(Vector3 R1, Vector3 R2, Vector3 S1, Vector3 S2, Vector3 S3) {

    Vector3 dS21 = S2.sub(S1); // Subtract S1 from S2
    Vector3 dS31 = S3.sub(S1);
    Vector3 n = dS21.cross(dS31); // Take the cross product of two vectors
    Vector3 dR = R1.sub(R2);

    double ndotdR = n.dot(dR);

    if (Math.abs(ndotdR) < 1e-25f) {
        return false;
    }

    double t = -n.dot(R1.sub(S1)) / ndotdR;

    Vector3 M = R1.add(dR.scale(t));
    Vector3 dMS1 = M.sub(S1);

    double u = dMS1.dot(dS21);
    double v = dMS1.dot(dS31);

    return (u >= 0.0 && u <= dS21.dot(dS21)
    && v >= 0.0 && v <= dS31.dot(dS31));
}

Это очень хорошо работает, чтобы определить, пересекается ли LINE, проходящая через R1 и R2, с квадратом. Однако рассмотрим следующий случай:

ОБНОВЛЕНО: более точное изображение для лучшей демонстрации проблемы

Прямая ссылка на imgur, так как у меня недостаточно представителей для публикации изображений D:

Если мы вызовем эту функцию дважды, по одному разу для каждого квадрата, они обе вернут true. Мне нужно, чтобы вызов (R1, R2, S1) возвращал true, а вызов (R1, R2, S2) возвращал false.

PS: Это мой первый пост (но ДОЛГО скрывающийся), поэтому, если вам нужна дополнительная информация или у вас есть какие-либо комментарии, которые помогут мне улучшить мой вопрос, пожалуйста, дайте мне знать.


java raycasting geometry 2d
person Nyecarr    schedule 06.06.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Таким образом, эту проблему можно решить, добавив дополнительное требование к логическому оператору.

return (u >= 0.0 && u <= dS21.dot(dS21) && v >= 0.0 && v <= dS31.dot(dS31) && t < 0);
// t < 0 to eliminate squares behind the ray
person Nyecarr    schedule 10.06.2014

arrow_upward
0
arrow_downward

По сути, у вашего луча есть начальная точка и направление, но нет конечной точки.

Все, что вам нужно сделать, это после вашей проверки, чтобы увидеть, удовлетворяет ли какая-либо точка в квадрате формуле линии, проверьте правильность направления.

то есть просто глядя на размер x для простоты:

if (x1<x2) {
  points_in_square.x must be >= x1
} else if (x1>x2) {
  points_in_square.x must be <= x1 
} else {
  // line is vertical, handle this case
}

Вы можете посмотреть на уже существующие реализации подобных вещей. Например, jMonkeyEngine — это 3D-движок Java с открытым исходным кодом, который содержит пересечения для лучей с ограничивающими рамками, выровненными по осям, — что, по сути, именно то, что вы ищете. У меня нет удобной ссылки, но попробуйте поискать по ключевым словам, которые я только что дал.

person Tim B    schedule 06.06.2014
comment
Я думаю, что, возможно, моя первая картина была немного обманчивой. Я обновил пост с более точной картиной проблемы. - person Nyecarr; 06.06.2014