Луч и 3D пересечение граней

Question

У меня есть трехмерное лицо, определенное n точками (v1, v2, v3, ..., vn), в трехмерных координатах, и у меня есть луч уравнения:

P=P0+t(P1-P0).

где 0<=t<=1.

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

Также было бы замечательно, если бы существовала реализация C # для этого?

Редактировать: 3D-грань может быть вогнутой или выпуклой.Все точки копланарны.

Answer 1

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

Другой способ - выполнить вычисление пересечения плоскости луча.Возьмем точку пересечения P, представим ее, используя 2D координаты с указанным выше ортонормированным базисом.Кроме того, как и в предыдущем решении, представьте свой многоугольник в 2D, используя ту же основу.Затем запустите любой двухмерный алгоритм «точка в многоугольнике», и вы получите свои результаты.

Обновление : вот математика Вы можете взять любые две точки на плоскости p1, p2 (например,две точки многоугольника) и возьмем вектор u = p2 - p1.Нормализовать это, и это первый базисный вектор.Затем вы берете нормаль N плоскости и вычисляете v = cross_product (u, N) и нормализуете v. Это второй базисный вектор.Обратите внимание, что оба вектора имеют единичную длину и они ортогональны друг другу.Поэтому они образуют ортонормированный базис.

Теперь определим p1 как начало плоскости.Тогда перевод в 2D любой точки q на многоугольнике (q может быть одной из вершин многоугольника или любой другой точкой на плоскости многоугольника):

x = dot_product(q - p1, u)
y = dot_product(q - p1, v)

Здесь x, y - двумерные координаты точки,

Так что после перевода всего в 2D и выполнения ваших 2D алгоритмов вы можете перевести любую 2D точку (x, y) обратно в 3D следующим образом:

q = p1 + x * u + y * v

Здесь * - скалярный векторпроизведение (x, y - скаляры, а u, v - векторы).

Алекс.

Answer 2

Если ваши точки не копланарны (т. Е. Не все лежат на одной плоскости), то вам нужно разделить поверхность на набор плоскостей, а затем выполнить пересечение линий с многоугольниками для каждой плоскости.Более того, определите список треугольников, а затем выполните поиск по результатам пересечения линии-треугольника.

Однако вы не говорите, определяют ли ваши точки граненый объект (т.е. состоящий из треугольников) или задаете наборконтрольных точек для изогнутой поверхности.Первый обрабатывается выше.Если это криволинейная поверхность, я думаю, что это непростительная задача, то есть нет тривиального решения задачи определения пересечения линии и криволинейной поверхности, определяемой набором точек.Лучшее, что вы можете сделать, - это использовать итеративный процесс поиска точки пересечения, но даже это может привести к нестабильному поиску (то есть поиску, который никогда не завершится).

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

Answer 3

Вы после алгоритма пересечения луча с полигоном, вот ссылка на запись Graphics Gems для него: http://www -graphics.stanford.edu / courses / cs348b-98 / gg / intersect.html