если п • с > 0, то луч покидает Р; если п • с - 0, то луч параллелен прямой; (4.64) если п • с < 0, то луч входит в Р.

Для каждой из ограничивающих прямых находим: О время соударения луча с ограничивающей прямой (используется уравнение (4.59)); О входит ли луч в полигон или выходит из него (используется уравнение (4.64)).

Глава 4. Векторные инструменты для графики Если луч входит в полигон, то мы знаем, что момент времени, в который луч войдет в полигон (если войдет вообще), не может быть более ранним, чем момент пересечения £Ы[, найденный другим способом. Нам нужно определить £п как самое раннее из возможных времен входа. Для каждого момента пересечения при входе гЫ1 заменим г1п на плах(г(п, £Ы(). Аналогично мы отслеживаем гои( - самое позднее из возможных времен выхода, и для каждого момента пересечения при выходе заменяем гои[ на тт(гои[, гЫ[).

Полезно представлять себе интервал времени [t.n, tml] как возможный интервал (candidate interval) времени t - такой интервале г, в пределах которого луч может находиться внутри объекта. На рис. 4.43 приведен пример задачи отсечения. Мы знаем, что точка А + сс не может находиться внутри Р ни в какой момент времени г вне возможного интервала. По мере проверки каждой ограничивающей прямой возможный интервал сокращается, так как rjn увеличивается, a tmt уменьшается: части этого интервала как бы «отсекаются». В начале решения задачи отсечения мы устанавливаем t.n равным нулю, a taM - единице, следовательно, возможный интервал равен [0,1]. Алгоритм вычисления следующий:

1. Инициализируем возможный интервал [О, I]1.

2. Для каждой ограничивающей прямой применяем уравнение (4.59) для нахождения времени пересечения rhit и определения того, произошло данное пересечение на входе или на выходе:

• Если rhit - пересечение на входе, то устанавливаем cin - max(rin, rhit).

• Если thjt - пересечение на выходе, то устанавливаем rout - min(rout, £hit).

Если в какой-либо точке ta становится больше, чем tml, то луч вообще не пересекает Р и проверка прекращается.


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