Алгоритм для определения точек пересечения луча с произвольным параллелепипедом.

Пересечение луча с прямоугольным параллелепипедом.

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

Например, вершинами (x_, y_, z_), (x₊, y₊, z₊).

Рассмотрим луч, исходящий из точки (x₀, y₀, z₀) в направлении вектора

(l, m, n), где l² + m² + n² =1, и опишем алгоритм, посредством которого можно определить, пересекает ли этот луч заданный прямоугольный параллелепипед или нет.

Возьмем пару плоскостей, параллельных плоскости yz: x = x_ и x = x₊

При l=0 заданный луч параллелен этим плоскостям и, если x₀ < x₊ или x₀ > x₊, то он не пересекает рассматриваемый прямоугольный параллелепипед. Если же l не равно 0, то вычисляем отношения

t_1x = (x_ - x₀)/l, t_2x = (x₊ - x₀)/l.

Можно считать, что найденные величины связаны неравенством t_1x < t_2x.

Пусть tn = t_1x , tf = t_2x

Считая, что m¹0, и рассматривая вторую пару плоскостей, несущих грани заданного параллелепипеда, y = y_ и y = y₊, находим величины

t_1y = (y_ - y₀)/m, t_2y = (y₊ - y₀)/m.

Если t_1y > tn, тогда пусть tn = t_1y .

Если t_2y < tf, тогда пусть tf = t_2y.

При tn > tf или при tf < 0 заданный луч проходит мимо прямоугольного параллелепипеда.

Считая n¹0, рассматриваем последнюю пару плоскостей z = z_ и z = z₊ , находим величины t_1z = (z_ - z₀)/n, t_2z = (z₊ - z₀)/n и повторяем предыдущие сравнения.

Если в итоге всех проведенных операций мы получим, что 0 < tn < tf или

0 < tf, то заданный луч непременно пересечет исходный параллелепипед со сторонами, параллельными координатным осям.

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