Определение, где и где фотон столкнется с многоугольником в трехмерном пространстве

Question

Проблема проста:

1) У нас есть фотон, путешествующий из точки 1 (x, y, z) в точку 2 (x, y, z), обе из которых могут быть расположены где угоднов трехмерном пространстве.

2) У нас есть многоугольник, который вращается случайным образом по оси x и / или по оси y, а также расположен где угодно в трехмерном пространстве.

3) Мы хотимнайти: а) если фотон вообще столкнется с многоугольником и б) если это произойдет, где это будет (х, у, z)?

Изображение проблемы: http://dl.dropbox.com/u/3150177/Programming/3D/Math/Photon%20Path/Photon%20Path.png

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

Я сейчас читаю на эту тему, но мне было интересно, если кто-нибудь может дать мне преимущество.Заранее спасибо.

Answer 1

Звучит так, будто вы ищете тест пересечения луча / многоугольника.

Я не могу вспомнить детали, но я думаю, что вы разделили это на две части. Сначала вы найдете точку на плоскости многоугольника, в которой пересекается луч. Это можно получить из простого теста пересечения луча / плоскости. Во-вторых, используйте систему координат на плоскости многоугольника, чтобы проверить, находится ли точка пересечения внутри многоугольника. Это можно получить из теста точка-полигон.

Answer 2

Вы делаете трассировку лучей. Наиболее эффективным является разбиение многоугольника на треугольники и использование теста луча-треугольника Мёллера. Или, может быть, тест Вальда. Существуют также варианты, которые используют дополнительные сохраненные данные, помимо информации о вершине, что может быть еще быстрее, если вы делаете несколько лучей против одного и того же треугольника. Google предоставляет так много результатов, что я не выбрал «лучший» для размещения здесь.

Answer 3

Общий обзор:

1) Пересечение плоскости сегмента: Определите, пересекает ли отрезок отрезка линии 1 и 2 плоскость, содержащую многоугольник. Если этого не произойдет, то он никогда не пересечет многоугольник, и все готово.

2) Найти точку пересечения: Определить точку, в которой пересекаются отрезок и плоскость. Это предоставит информацию, которую вы хотите в 3-б в вашем вопросе. Назовите эту точку Q

3) Определите, является ли Q внутренним для многоугольника: Один из методов определения этого - здесь , но хорошо продуманный поиск Google, вероятно, приведет к другие. Вы можете оптимизировать работу с ожидаемыми различными типами многоугольников (то есть выпуклыми) или если плоскость, содержащая многоугольник, выровнена по оси (то есть одна из осей вашей системы координат является нормальной к плоскости, содержащей многоугольник).

Предположение: Все точки многоугольника копланарны.

Answer 4

Лучевые / треугольные пересечения хорошо понятны и довольно просты. Вращения сложнее, хотя.

Возможно, вы могли бы преобразовать вершины треугольника, используя матрицу вращения , а затем использовать простое пересечение луч / треугольник?

Answer 5

Фотон путешествует с вектором v = p2 - p1, начиная с p1, создавая эту линию:

p1 + v * a 

Чтобы узнать, сталкивается ли фотон с многоугольником, вы должны найти значение для:

p1 + v * a = polygon

Например:

p1 is (15, 4, 5)
p2 is (10, 1, 3) 
and polygon is a 10x10 square: (-5...5, -5...5, 0)

v = p2 - p1 = (-5, -3, -2)

p1 + v * a = pol составляет:

p1.x + v.x * a = pol.x
p1.y + v.y * a = pol.y
p1.z + v.z * a = pol.z

a = (pol.z - p1.z) / v.z = (0 - 15) / -2 = 7.5
pol.x = p1.x + v.x * a = 15 + -5 * 7.5 = -22.5
pol.y = p1.y + v.y * a = 10 + -3 * 7.5 = -12.5

-22,5 не между -5 и 5 и -12,5 не между -5 и 5, поэтому фотон не сталкивается с многоугольником.

Прошло много времени с тех пор, как я это сделал, поэтому, возможно, я допустил некоторые ошибки. Я использовал тот факт, что pol.z = 0, чтобы вычислить. Возможно, вам придется вращать многоугольник, чтобы он совпал с одной осью, если только вы вращаете p1 вокруг центра многоугольника.