Как выбрать одно из двух правильных пересечений между плоскостью и треугольными ребрами в 3D? - PullRequest
Новая
       42

Как выбрать одно из двух правильных пересечений между плоскостью и треугольными ребрами в 3D?

1 голос
/ 10 мая 2019

У меня есть линия (A, B) и треугольник (P0, P1, P2) где-то в трехмерном пространстве. Другими словами, у меня есть 3 точки ([x, y, z] каждая) для треугольника и две точки (также [x, y, z]) для линии. Одна точка линии лежит внутри треугольника (A или B). Основная цель - найти пересечение по краю треугольника, который является частью линии (A, B) на экране.

Что я делаю:

1. Рассчитать плоскость Normal от начала линии (A), конца линии (B) и положения камеры: 

    Vector3 Normal = Vector3.Cross(A - cameraPos, B - cameraPos);

2. Найдите два пересечения, проверив каждый край треугольника: 

    bool IsPlaneIntersectLine(Vector3 Normal, Vector3 A, Vector3 B, Vector3 EdgePoint1, Vector3 EdgePoint2, out Vector3 Intersection)
    {
        float dotProduct = Vector3.Dot(Normal, (EdgePoint1 - EdgePoint2));
        if (dotProduct == 0f)
            return false;
        float dot1 = Vector3.Dot(Normal, (A - EdgePoint2));
        float distance = dot1 / dotProduct;
        if (distance > 1f || distance < 0f)
            return false;
        Intersection = EdgePoint2 + distance * (EdgePoint1 - EdgePoint2);
        return true;
    }

    Vector3 intersection1, intersection2, intersection3;
    bool isEdge1Intersected = IsPlaneIntersectLine(Normal, A, B, triangle.P0, triangle.P1, out intersection1);
    bool isEdge2Intersected = IsPlaneIntersectLine(Normal, A, B, triangle.P1, triangle.P2, out intersection2);
    bool isEdge3Intersected = IsPlaneIntersectLine(Normal, A, B, triangle.P2, triangle.P0, out intersection3);

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

Также я попытался проверить произведение точки между вектором линии и вектором пересечения: 

    float dot = Vector3.Dot((Intersection - A), (B - A));
    if (dot < 0f)
    {
        return false;
    }

Но есть некоторые треугольники / ребра, которые не подходят для этого условия.

Как найти одно пересечение на ребре треугольника, которое является частью линии (A, B) на экране?

Ответы [ 3 ]

1 голос
/ 11 мая 2019

Как я уже описал один подход в моем предыдущем ответе , касающемся более общего алгоритма, один прямой способ проверить эту конкретную ситуацию состоит в том, чтобы сформировать два вектора перекрестных произведений

V1 = Vector3.Cross((A - cameraPos), (Intersection - cameraPos))

V2 = Vector3.Cross((Intersection - cameraPos), (B - cameraPos))

Эти два вектора перпендикулярны плоскости (cameraPos, A, B) и поэтому лежат на общей линии. Если оба они указывают в одном направлении, то, поворачивая взгляд вокруг cameraPos, начиная с точки A в направлении точки B, вы увидите первую точку A, затем точку Intersection, а затем точку B. Однако, если векторы V1 и V2 указывают в противоположных направлениях, вы не увидите пересечения точек между точками A и B. Поэтому, чтобы решить вашу проблему, я ожидаю, что следующий алгоритм сделает работа: 

V1 =  Vector3.Cross((A - cameraPos), (Intersection - cameraPos));
V2 =  Vector3.Cross((Intersection - cameraPos), (B - cameraPos));
dot = Vector3.Dot(V1, V2);

if dot < 0f
{
   return false
}

Одно замечание: все эти алгоритмы применяются в основном к видимым треугольникам, поэтому для невидимых треугольников нужно быть осторожным. Кроме того, если A и B находятся в одном и том же треугольнике, эти алгоритмы встречают исключение. И если A уже на одном ребре треугольника, то это исправление не требуется, и я думаю, что вы можете напрямую перейти к шагу 3 из общего алгоритма .

0 голосов
/ 10 мая 2019

Если вы хотите 2D пересечение , линии и не более двух ребер, как видно на экране, то сначала вам нужно рассчитать проецируемые координаты.
Для получения подробной информации, найдите любой хороший учебник, где вы узнаете о преобразованиях (используя матрицы 4x4). Обязательно поймите три преобразования: Модель, Вид и Проекция. Если у вас есть двухмерные данные (отклоните координату глубины после проецирования), ваша задача сводится к тестированию трех пересечений двухмерных линий.

Если вы хотите 3D-пересечение (необработанные данные, без преобразований), тогда найдите пересечение плоской линии (плоскость треугольника). Как только вы получите точку пересечения, если есть, рассчитайте расстояния от этой точки до каждого ребра.

0 голосов
/ 10 мая 2019

Здесь идет ответ от разработчика игры, а не от специалиста по геометрии, так что это заставит большинство математиков съежиться, но в целом это должно сработать.

Поскольку треугольники плоские, и вы уже рассчиталиНормальная плоскость, вы можете создать матрицу преобразования, которая будет вращать треугольник так, чтобы он был нормальным, был прямым и перевести его центр в [0,0,0].(Я не могу объяснить математику для создания этой матрицы на моей голове, но есть много библиотек с открытым исходным кодом с этой встроенной логикой, в основном обратная матрица «взгляда»).По сути, это матрица из мира в локальное пространство.

Получив эту матрицу, вы можете применить ее к двум точкам на линии, чтобы переместить ее в локальное пространство, и тогда вы получите очень простуюзадача определения, где линия пересекает плоскость осей XZ (то есть решить, где Y равен нулю).В то время как у вас есть все во временном 2D, вы можете использовать барицентрические координаты, чтобы проверить, находится ли точка пересечения в треугольнике, на границе или снаружи очень легко.

Как только у вас есть точка ответа в локальномпространство, преобразуйте его с помощью обратной матрицы, чтобы переместить его обратно в мировое пространство, и все готово.

...