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

    Для проверки столкновений и ray tracing'a необходимо определить, пересекается ли луч с каким-либо полигоном сцены. Существует много разных способов решения этой задачи. Я расскажу вам о двух алгоритмах, по моему мнению, наиболее простых и эффективных.

Определение точки пересечения прямой с плоскостью.

    Допустим у вас есть отрезок, начинающийся в точке StartPoint и кончающийся в точке EndPoint. Также у вас есть плоскость Ax + By + Cz + D = 0, где N={A;B;C}, как вы помните, вектор нормали, а D - расстояние от начала координат до плоскости. Так как же определить точку пересечения плоскости с прямой? Это оказывается довольно просто, если немного вспомнить математику.

    Параметрическое уравнение прямой, проходящей через StartPoint и EndPoint, имеет вид:  

    PointOnRay = StartPoint + t*RayDir

RayDir - вектор, совпадающий с направлением прямой и равный EndPoint - StartPoint. При каком-то значении t прямая пересечет плоскость, если, конечно, она ей не параллельна. Найдем t.

    Пусть прямая пересекает плоскость в точке I (intersection point), тогда 

    I = StartPoint + t*RayDir    (1)

С другой стороны уравнение плоскости можно записать в следующем виде: N dot I = -D (dot - скалярное произведение векторов). Подставим (1) в это уравнение. 

    N dot (StartPoint + t*RayDir) = -D  <=> N dot StartPoint + t* (N dot RayDir) = -D 

Отсюда получаем: 

    t = -(D + N dot StartPoint)/(N dot RayDir)    (2)

Теперь, подставив (2) в уравнение (1), получим точку пересечения луча с плоскостью. Теперь немного проанализируем то, что мы получили.

• Если N dot RayDir равно 0, то это значит, что прямая параллельна плоскости и никогда ее не пересечет.

• Если t < 0 или t > 1, то это значит, что точка пересечения лежит до StartPoint или за EndPoint соответственно.

А вот и исходник прямо из моего 3d engine'а:

#define EPSILON 0.000001

 

int R_TraceRay(CVector start, CVector end)
{
    CVector dir, intersection;
    double cosang, dist, lamda;

    dir = end - start;

    for (int i=0; i<Level.numsurfaces; i++)
    {
        CSurface *s = &Level.surfaces[i];

        cosang = DotProduct(dir, s->normal);
        if (cosang > -EPSILON && cosang < EPSILON)
            continue; // Determine if ray paralle to a plane.

        dist = DotProduct(start, s->normal);

        lamda = (-s->dist-dist)/cosang;
        if (lamda < 0 || lamda > 1)
            continue;

        intersection = start + dir*lamda;

 

        // ...

        // Проверка, лежит ли точка внутри треугольника или нет.

        // ...

    }

 

    return 1; // no collision

}

Сложно? Вроде нет, но это только начало ;-)

Определение, лежит ли точка внутри треугольник или нет.

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

"Barycentric intersection" алгоритм.

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

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

    Параметрическое уравнение плоскости имеет вид:

    P = (1-u-v)*A + u*B + v*C    (3)

A, B и C - три точки, задающие плоскость. (Не путать с координатами вектора нормали!). Если мы будем изменять u и v от –Ґ до +Ґ, то будем всегда получать точки P, лежащие в плоскости ABC.

Если все коэффициенты і 0, то точка лежит внутри треугольника ABC, т.е. 1-u-v і 0, u і 0 и v і 0. Таким образом, надо выразить из (3) u и v, подставить вместо P точку пересечения прямой с треугольником и проверить следующие условия: 0 Ј u Ј 1 и 0 Ј v Ј (1–u). Если это выполняется, то точка пересечения лежит внутри треугольника ABC.

Алгоритм N2.

    Этот алгоритм тоже довольно хороший и его можно применять для полигонов. Я думаю, он даже более быстрый, чем barycentric алгоритм (при соответствующей оптимизации), особенно если его применять для многоугольников.

    Пусть у нас есть на плоскости (!) треугольник ABC. Как определить, лежит ли точка M(x,y) внутри треугольника или вне его? Будем считать, что треугольник задан векторами AB, BC и CA. Если точка M лежит правее вектора AB, правее BC и CA, то она находится внутри треугольника. Для определения, где лежит точка M относительно вектора AB, воспользуемся следующей формулой:

    j = (y - y₀) (x₁ - x₀) - (x - x₀) (y₁ - y₀)

(x₀,y₀), (x₁,y₁) - координаты точек А и B соответственно. Если j больше 0, то точка М лежит слева от вектора AB, если меньше 0, то справа от AB, а если j равно 0, то на AB. Таким образом если для всех сторон треугольника (полигона) выполняется неравенство j  Ј 0, то точка M лежит внутри треугольника (полигона). Этот метод работает довольно быстро, т.к. часто условие не выполняется уже при проверки первой стороны, и дальнейшие вычисления можно не выполнять.

    Вы скажите, причем тут треугольник на плоскости, если мы работаем в 3D? Все очень просто. Если мы спроецируем треугольник вместе с точкой его пересечения с лучом на плоскость Oxy, Oxz или Ozy, то ничего не изменится! Если точка лежала внутри треугольника (полигона), то она так и будет там лежать. Проецирование выполняется элементарно: просто отбрасывается одна из координат x, y или z. Остается только выбрать плоскость проецирования. Если проецировать все треугольники на одну плоскость, то часть из них вырождается в линии.

    Для выбора плоскости проецирования надо определить абсолютное значение какой координаты (x, y или z) вектора нормали является максимальным. Сделать это можно так:

 

if (  fabs(normal.x) >= fabs(normal.y)
    && fabs(normal.x) >= fabs(normal.z) )
{
    projection_plane = YZ;

}

Аналогично сравниваем координаты нормали y и z.

    Важно учесть, что в зависимости от знака normal.x (здесь я предполагаю, что fabs(normal.x) максимально, и проецируем на Oyz), условие на j будет меняться. Т.е. если normal.x < 0, то точка будет лежать внутри треугольника при условии, что j для всех сторон больше или равно нулю. Другими словами, при проецировании может меняться порядок вершин. Если normal.x < 0, и вершины расположены "по часовой стрелке", то при проецировании они будут расположены "против часовой стрелки".

    Вот и все! Эти алгоритмы проверены и отлично работают, и если у вас что-то будет не получаться, то либо я где-то ошибся, либо вы что-то не поняли :-) Если у вас есть какие-нибудь дополнения и/или исправления, то пишите мне.

This page and its contents are Copyright 2000 by Sergey A. Makovkin
Unless otherwise noted, you may use any and all code examples provided herein in any way you want.
All other content, including but not limited to text and images, may not be reproduced without consent.
This file was last edited on Monday, 18-Dec-2000.