У меня есть 3D поверхность, образованную n точками (v1, v2, v3, ..., vn), в 3D-координаты, и у меня есть луч уравнения:Рэй и 3D лица Пересечение
P=P0+t(P1-P0).
, где 0<=t<=1.
Теперь, как найти точку пересечения (или отсутствие) между этим лучом и лицом?
Кроме того, было бы здорово, если бы на этом существовала существующая реализация C#?
Редактировать: 3D лицо может быть вогнутым или выпуклое. Все точки копланарны.
Я полагаю, ваш 3D многоугольник является плоской (в противном случае это на самом деле не полигон, и это не очень хорошо определены). Поэтому вы можете найти 2D ортонормированный базис для этой плоскости. Это означает, что вы можете использовать любой 2D-алгоритм триангуляции (вы можете найти множество реализаций C# в Интернете) и вернуться в 3D, используя ортонормированную основу. Таким образом вы получите 3D-треугольники и сможете легко выполнить тест пересечения лучей и полигонов, выполнив несколько тестов пересечения лучей-треугольников.
Другой способ - выполнить расчет пересечения лучевой плоскости. Возьмите точку пересечения P, представив ее с помощью 2D-координат с указанным выше ортонормированным базисом. Кроме того, как и в предыдущем решении, представляем ваш многоугольник в 2D с использованием той же основы. Затем запустите любой 2D-алгоритм «точка в полигоне», и вы получите свои результаты.
Update: Вот математика Вы можете взять любые две точки на плоскости p1, p2 (например две из точек многоугольника) и взять вектор и = p2 - p1. Нормализовать его, и это первый базисный вектор. Затем вы берете нормальный N плоскости и вычисляете v = cross_product (u, N) и нормализуете v. Это второй базисный вектор. Обратите внимание, что оба вектора имеют единичную длину, и они ортогональны друг другу. Поэтому они образуют ортонормированный базис.
Теперь определите p1 как начало плоскости. Затем перевод в 2D любой точки д на полигоне (д может быть одна из вершин многоугольника, или любая другая точка на плоскости полигона):
x = dot_product(q - p1, u)
y = dot_product(q - p1, v)
Здесь х, у 2D точки в системе координат.
Таким образом, после перевода все в 2D и делать ваши 2D алгоритмы вы можете перевести любой 2D точки (х, у) обратно в 3D, как это:
q = p1 + x * u + y * v
Здесь * скалярное-векторное произведение (х, y - скаляры, u, v - векторы).
Alex.
Вы после того, как алгоритм пересечения луча многоугольник, вот ссылка на запись графика Gems для него: http://www-graphics.stanford.edu/courses/cs348b-98/gg/intersect.html
Если ваши точки не являются копланарными (т. Е. Все не лежат на одной плоскости), то вам нужно разделить поверхность на множество плоскостей, а затем пересечь линию-многоугольник для каждой плоскости ,Еще лучше определите список треугольников, а затем выполните поиск по результатам пересечения линий треугольника.
Однако вы не говорите, если ваши точки определяют граненый объект (т. Е. Из треугольников) или определяют набор контрольных точек для криволинейной поверхности. Первый обрабатывается приведенным выше. Если это изогнутая поверхность, я думаю, что это в непреодолимой проблеме, т. Е. Нет никакого тривиального решения проблемы определения пересечения прямой и криволинейной поверхности, определяемой множеством точек. Лучшее, что вы можете сделать, это использовать итеративный процесс нахождения точки пересечения, но даже это может привести к неустойчивым поисковым запросам (т. Е. Поискам, которые никогда не завершаются).
Я думаю, что наилучшим ответом является преобразование в набор треугольников.
это луч-треугольник, не луч-многоугольник. Я понимаю, что вы можете сказать, что мы можем разбить треугольник на многоугольник. Но в моем случае триангуляция может быть нелегкой, поскольку я делаю 3D-многоугольник. Кроме того, многоугольник, который у меня есть, может быть вогнутым, поэтому решение, существующее внутри вашей ссылки, может не работать. – Graviton 2010-12-15 08:49:08
@Ngu, Да, это не будет работать для вогнутых полигонов. Используйте решение Алекса. – 2010-12-15 09:04:04
ссылка больше не работает – Joh 2015-12-02 11:34:41