Уравнения (4.52) и (4.53) содержат нужные ответы. Выражая их с помощью введенных ранее обозначений, получаем:

Френсис Хилл

Если вектор е1 равен нулю, то г-е ребро параллельно направлению с луча, и, следовательно, пересечения нет. Истинное пересечение с f-м ребром происходит только в том случае, если и попадает в интервал [0,1].

Нам необходимо найти все истинные пересечения луча с ребрами полигона Р и поместить их в список моментов соударения. Назовем этот список hitList. Тогда псевдокод для такого процесса будет выглядеть примерно так:

initialize hitList to empty

for(int i - 0: i < N: i++)

// for each edge of P

// для каждого ребра полигона Р

{

build bi. ei for the i-th edge // строим bi. ei для- i-го ребра

solve for t. u // решаем относительно t. u N

if(u lies in [0.1]) // если u расположено в интервале [0. 1]

add t to the hitList // добавляем t к списку hitList }

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

Задача пересечения лучом Где луч впервые сталкивается с полигоном Р? Ответить на этот вопрос можно, найдя наименьшее значение t в hitList. Назовем это значение tmin. В таком случае точка соударения, как всегда, равна А + ctmjn.

Задача отсечения прямой Для решения данной задачи нам требуется последовательность интервалов времени t, в течение которых луч находится внутри полигона Р. Поэтому необходимо отсортировать hitList по возрастанию t и затем взять значения t попарно. Луч входит в полигон Рв первый момент времени каждой пары и выходит из Р во второй момент времени каждой пары.

Пример 4.8.2. Отсечение отрезка прямой АВ границами полигона Р

Пусть АВ - прямая, подлежащая отсечению, как показано на рис. 4.46, где А = (1,1), В = (8, 2). Полигон Р задан списком вершин: (3, 2), (2,0), (6, -1), (4,1). Рассматривая каждое ребро поочередно, получаем при пересечениях следующие значения t и и.

Ребро

U

t

0,3846

0,2308

-0,727

-0,2727

0,9048

0,7142

0,4

0,6

0,375

0,375

Глава 4. Векторные инструменты для графики

Френсис Хилл

Рис. 4.46. Отсечение прямой границами полигона Соударение с ребром 1 происходит при значении с, находящемся вне промежутка [0,1], поэтому оно отбрасывается. Проведем сортировку (по возрастанию) оставшихся значений г и получим следующий отсортированный список соударений: {0,2308, 0,375, 0,6, 0,7142}. Таким образом, луч входит в р при г = 0,2308, выходит из него при £ = 0,375, снова входит при с = 0,6 и выходит из него в последний раз при с = 0,7142.


⇐ Предыдущая| |Следующая ⇒