Как сделать пересечение луча и треугольника?

Я столкнулся с проблемой пересечения луча с краями треугольника. На самом деле, я пытаюсь выбрать / пересечь треугольник, вершину, край меша с помощью мыши. Итак, я сделал луч из текущего положения мыши, а затем пересекаю его с элементами сетки, такими как треугольник / многоугольник, вершина, край и т. Д., Чтобы работать с ним. В основном, про 3D моделирование. Пересечение с треугольником было легко и весело. А вершинная часть была сложной.

Но теперь я не знаю, как пересекать / выбирать ребра треугольника. Я имею в виду, как я отношусь к ним при пересечении с Мышиным Лучом? Сначала я подумал, что их можно рассматривать как трехмерную линию. Но в итоге не удалось сделать пересечение Луча и Линии. Искал в Интернете, но не нашел никакой полезной информации. Хотя я обнаружил, что некоторые проекты с открытым исходным кодом используют встроенные функции выбора OpenGL для выбора / пересечения с Edge. Но в моем случае я не могу это использовать. :(

Моя текущая структура кода выбора края выглядит следующим образом:

void pickEdge(Ray ray, Scene scene)
{
    for each object in scene
    {
        mesh = getMesh(object)
        for each triangle in mesh
        {
            for each edge in triangle
            {
                v1 = getV1(edge)
                v2 = getV2(edge)

                // Do intersect with 'ray' and 'v1', 'v2'. But how?
            }
        }
    }
}

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


person Farhad Reza    schedule 05.08.2016    source источник
comment
Определите, находится ли ваша точка выбора в пределах допустимого «радиуса» края, используя формулу расстояния до линии. Затем выполняется ортогональная проекция на кромку, чтобы получить «точку» на кромке, если это необходимо.   -  person Brett Hale    schedule 05.08.2016
comment
@Brett Hale Вы говорите «используя формулу расстояния до линии». На самом деле я застрял на этом этапе. Фактически я еще не могу реализовать пересечение Ray-Line. Было бы намного полезнее, если бы вы отправили его в качестве ответа с более подробной информацией. Спасибо за ценный комментарий :)   -  person Farhad Reza    schedule 05.08.2016
comment
А ... вообще-то я все еще застрял :( Нужна помощь ... Пожалуйста.   -  person Farhad Reza    schedule 25.08.2016


Ответы (4)


В вашем случае проблема поиска пересечения между треугольником и лучом в трехмерном пространстве может быть сведена к нахождению местоположения точки (ВНУТРИ, СНАРУЖИ, НА ГРАНИЦЕ) в треугольнике в двухмерном пространстве (плоскости). Все, что вам нужно сделать, это спроецировать треугольник на плоскость экрана, найти пересечение на краю и выполнить обратное проецирование на краю. Положение точки - это положение мыши. Единственная проблема состоит в том, чтобы рассматривать вырожденные случаи, такие как отображение треугольника в линейный сегмент. Но я думаю, это не будет проблемой, потому что с такими случаями легко справиться.

person LmTinyToon    schedule 15.08.2016

Пожалуйста, обратите внимание на алгоритмы в конце этой страницы и на все те, которые предлагает этот веб-сайт в целом: http://geomalgorithms.com/a05-_intersect-1.html

person abenci    schedule 08.08.2016
comment
Вау! Эти алгоритмы действительно очень полезны. Я должен посмотреть, смогу ли я использовать их с умом для решения моей проблемы ... Спасибо. - person Farhad Reza; 09.08.2016

Первый подход - ортогонально спроецировать край (и луч) на плоскость, перпендикулярную лучу, а затем вычислить расстояние от проецируемого луча до проецируемого края.

Т.е. сначала вы определяете два ортогональных вектора rdir1, rdir2, ортогональных вашему лучу.

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

Затем вы проецируете край на эту плоскость, просто применяя точечные произведения: pv1 = new Vector2(DotProduct(v1, rdir1), DotProduct(v1, rdir2)) pv2 = new Vector2(DotProduct(v2, rdir1), DotProduct(v2, rdir2))

Теперь вы можете вычислить расстояние от этой 2-й линии pv1, pv2 до точки rp.

При условии, что направление края берется из «прямого» направления матрицы обзора, тогда два вектора, ортогональные этому, будут левым и правым векторами матрицы обзора.

Выполнение приведенного выше рецепта даст нечто похожее на проецирование края на экран. Следовательно, в качестве альтернативы вы можете проецировать край на экран и работать с этими координатами.

person VlltStiller    schedule 02.09.2016
comment
Хм ... Я думал, что моя проблема может быть решена с помощью простой математики 3D (xyz). Но сейчас, похоже, все будет не так просто. На самом деле я редко понимаю ортогональную проекцию, проецируя что-то на ... плоскость ... вещи ... и т. Д. Это правда, что хорошее знание математики является самым важным в этих случаях. И я, я, я сам; всегда застревал в этой точке: (... Вы меня понимаете? В любом случае, спасибо за этот лучший ответ. Дайте мне посмотреть, смогу ли я решить свою проблему. О ... У меня сейчас мало времени. Но спасибо! - person Farhad Reza; 03.09.2016
comment
Привет, Мохаммад, не пугайся длинного ответа. Это действительно очень просто. Действительно, есть другой способ (с использованием перекрестных произведений), но ответ был уже слишком длинным. Если вам интересно, я добавлю этот другой маршрут. - person VlltStiller; 03.09.2016
comment
Конечно. На самом деле, я был бы очень рад получить от вас больше информации. С Уважением. - person Farhad Reza; 05.09.2016

Прежде всего, каково расстояние между двумя геометрическими объектами A и B? Это минимальное расстояние между любыми двумя точками на A и B, т.е. dist(A,B) = min { EuclideanLength(x - y) | x in A, y in B}. (Если он существует и уникален, как в вашем случае.)

Здесь EuclideanLength((x,y,z)) = sqrt(x^2 + y^2 + z^2), как вы уже знаете. Поскольку sqrt строго увеличивается, достаточно минимизировать SquareEuclideanLength((x,y,z)) = x^2 + y^2 + z^2, что значительно упрощает проблему.

В вашем вопросе объекты - это отрезок линии A := {v1 + t*(v2-v1) | 0 <= t <= 1} и линия B := {p + s*d | s is any real number}. (Не беспокойтесь, что вы спросили о луче, линия - это действительно то, что вам нужно.)

Теперь вычисление расстояния сводится к нахождению подходящих t и s, таких, что SquareEuclideanLength(v1 + t*(v2-v1) - p - s*d) минимально, и последующему вычислению EuclideanLength(v1 + t*(v2-v1) - p - s*d) для получения реального расстояния.

Чтобы решить эту проблему, нам понадобится аналитическая геометрия. Поскольку d не равно нулю, мы можем записать каждый вектор v как сумму части, ортогональной d, и части, кратной d: v = Ov + Mv. Для такого «ортогонального разложения» всегда выполняется SquareEuclideanLength(v) = SquareEuclideanLength(Ov) + SquareEuclideanLength(Mv).

Из-за d = Md в приведенном выше

SquareEuclideanLength(v1 + t*(v2-v1) - p - s*d) = SquareEuclideanLength(Ov1 + t*(Ov2-Ov1) - Op) + SquareEuclideanLength(Mv1 + t*(Mv2-Mv1) - Mp - s*d)

левое слагаемое не зависит от s, и, как бы вы ни выбрали t, вы можете найти s такое, что правое слагаемое равно 0! (Помните, что Mv1, Mv2, ... кратны d.)

Следовательно, чтобы найти минимум, вам просто нужно найти такие карты O, M, как указано выше, и найти минимизатор t.

Предполагая, что d нормализовано, они фактически задаются Ov := CrossProduct(v, d) и Mv := DotProduct(v, d)*d, но поверьте мне, это также работает, если d не нормализовано.

Итак, рецепт определения расстояния теперь таков: найдите 0 <= t <= 1, которое минимизирует

SquareEuclideanLength(Cross(v1 - p, d) + t*Cross(v2 - v1, d)) = SquareEuclideanLength(Cross(v1 - p, d)) + 2*t*Dot(Cross(v1 - p, d), Cross(v2 - v1, d)) + t^2 SquareEuclideanLength(Cross(v2 - v1, d)).

Вы уже знаете эту формулу из расчета расстояния точка-линия (вот что это такое), и она решается путем дифференцирования по t и приравнивания 0.

Итак, минимизатор этого уравнения t = -Dot(Cross(v1 - p, d), Cross(v2 - v1, d))/SquareEuclideanLength(Cross(v2 - v1, d))

Используя этот t, вы вычисляете v1 + t*(v2 - v1), точку на линейном сегменте A, которая является ближайшей к линии B, и вы можете вставить это в свой алгоритм расстояния точка-линия, чтобы найти искомое расстояние.

Я надеюсь, это поможет вам !

person VlltStiller    schedule 06.09.2016
comment
Большое спасибо за всю эту информацию! С наилучшими пожеланиями :) - person Farhad Reza; 01.12.2016