Определить, находится ли 3D-точка в треугольнике

Question

Учитывая трехмерную точку (x, y & z) и треугольник, состоящий из трех других трехмерных точек, как я могу определить, находится ли точка в треугольнике?

Я много читал о том, как делать это в 2D, наиболее полезным было http://imusthaveit.spaces.live.com/blog/cns!B5212D3C9F7D8093!410.entry,, но я изо всех сил пытаюсь перевести концепцию в 3D - кто-нибудь может помочь с общей концепцией или примером кода? 1005 *

В конечном итоге я хочу получить список точек, которые могут представлять внутреннюю часть треугольника.

Answer 1

Учитывая точку P и треугольник A, B, C, вычислим:

1. the unit normal of triange (A, B, P)  - call it N1
2. the unit normal of triangle (B, C, P) - call it N2

(получите заказ правильно!)

Теперь подумайте о точечном произведении N1 * N2. если P находится в плоскости треугольника и внутри трех сторон, эти нормали должны быть параллельны, поэтому это произведение будет 1,0000 (или 0,999 ...). Если P удерживается в плоскости, но выходит за пределы BC, эти две нормали будут противоположными: N1 * N2 == - 1. Если P не в плоскости, произведение точки будет некоторым промежуточным значением. К сожалению, у нас все еще есть лазейка - если P выходит за пределы CA. Нам нужно вычислить еще один:

3.  the unit normal (C,A,P) called N3

Сделайте эти два теста (в идеальном мире):

N1*N2 == 1.0 ?
N2*N3 == 1.0 ?  

(тестирование N3 * N1 является избыточным) Конечно, тест должен допустить некоторое отклонение от недостатков компьютерной арифметики. Найдите (N1 * N2> 1-эпсилон), где эпсилон - это небольшое значение, зависящее от необходимой точности и типов с плавающей запятой.

Возможно, вам понадобится формула для этих единиц нормалей. Учитывая (A, B, C), вычислите перекрестное произведение N = (B-A) x (C-B). Затем разделите на sqrt (N * N). Определения «точечного произведения» и «перекрестного произведения» легко найти в учебниках, википедии и т. Д. С некоторой алгеброй можно повысить производительность примерно до квадратных корней.

Я не утверждаю, что это самый быстрый алгоритм, но он должен работать (до тех пор, пока

Answer 2

Вы действительно говорите о 3 точках треугольника или 4 точках пирамиды?

Крайне маловероятно, что одна точка будет находиться на плоскости плоского треугольника в трехмерном пространстве.

EDIT:

Как идея для треугольной версии (как вам кажется). Вы можете выполнить 3х2D проверки. Откажитесь от Z, согласованного с вашей контрольной точки и трех треугольных точек, затем посмотрите, находится ли точка в плоскости, используя ваш существующий метод. Затем сделайте то же самое, игнорируя только координату X, а затем снова игнорируя только координату Y. Я уверен, что это не самый эффективный метод, но он будет прост в коде.

Answer 3

private bool PointInTriangle(Vector3[] TriangleVectors, Vector3 P)
    {
        Vector3 A = TriangleVectors[0], B = TriangleVectors[1], C = TriangleVectors[2];
        if (SameSide(P, A, B, C) && SameSide(P, B, A, C) && SameSide(P, C, A, B))
        {
            Vector3 vc1 = Vector3.Cross(Vector3.Subtract(A, B), Vector3.Subtract(A, C));
            if (Math.Abs(Vector3.Dot(Vector3.Subtract(A, P), vc1)) <= .01f)
                return true;
        }

        return false;
    }

    private bool SameSide(Vector3 p1, Vector3 p2, Vector3 A, Vector3 B)
    {
        Vector3 cp1 = Vector3.Cross(Vector3.Subtract(B, A), Vector3.Subtract(p1, A));
        Vector3 cp2 = Vector3.Cross(Vector3.Subtract(B, A), Vector3.Subtract(p2, A));
        if (Vector3.Dot(cp1, cp2) >= 0) return true;
        return false;

    }

Answer 4

Метод, описанный здесь , очень хорош для 2D-случая. Я думаю, что это можно изменить для работы в 3D. Это не дает прямого ответа на ваш вопрос, но если вы понимаете этот метод, вы сможете решить, как изменить его для 3D (если это возможно).

Answer 5

Учитывая трехмерную точку P и три вершины треугольника T1, T2, T3

• Найдите плоскость через три точки T1, T2, T3
• Найдите ближайшую точку на плоскости к P (спроецируйте P на плоскость)

Теперь вы можете преобразовать все точки в двумерную задачу поиска точки в треугольнике. Кроме того, расстояние P до плоскости скажет вам, насколько близко точка находится точно на треугольнике.

Если я правильно понимаю вашу разработку, вы планируете проверить все вокселы в вашей трехмерной сетке, чтобы выяснить, находятся ли они в данном треугольнике? Это было бы очень неэффективно - я думаю, что трехмерная версия линейного алгоритма Брезенхема может работать для того, что вы хотите сделать. Было бы тривиально найти воксел, в котором находится Т1, затем пройти через воксели к Т2, повторив для Т3 и вернуться к Т1.

Answer 6

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

Answer 7

Просто мои наблюдения по улучшению этого (старого) поста. Если вы (предварительно) вычислили векторы U & V для треугольника (U - вектор от A до B, а V - вектор от A до C в стандартном треугольнике ABC, то U и V равны , необязательно на единицу длины), тогда вектор P (от A до точки) можно использовать следующим образом: вычислить произведение точек P с U и P с V. Если оба произведения точек меньше (или равны для точки на ребре) одному но больше (или равно) нулю и их сумма меньше (или равна) единице, тогда точка находится внутри, в противном случае она находится снаружи. Этот подход более эффективен, чем первое сравнение нормалей (перекрестных произведений), а затем и их точечных произведений. Этот подход не требует, чтобы точки уже были в том порядке, в котором они образуют правосторонний треугольник, и, следовательно, более устойчивы. Для этого требуется, чтобы точка находилась в плоскости (или близко к ней), чтобы быть приблизительно точной.