3. Если возможный интервал не является пустым (нулевым), то, согласно уравнению (4.63), отрезок от А + ctm до А + ctoM расположен внутри Р. Для задачи отсечения прямых эти точки являются конечными точками отсеченной прямой. Для задачи пересечения лучом они являются соответственно входной и выходной точками луча.
Отметим, что мы прекращаем проверку, как только возможный интервал обращается в нуль. Это называется досрочным выходом (early out): если мы до окончания процесса проверки устанавливаем, что луч находится вне полигона, то для экономии времени мы немедленно выходим из проверки.
На рис. 4.44 показан типичный пример отсечения: мы ищем часть отрезка Л С, расположенную внутри полигона Р. Начальное значение времени £п устанавливаем в нуль, a toM - в единицу. Луч «стартует» из точки А в момент t = 0 и движется к точке С, достигая ее при t = 1. Мы проверяем луч относительно каждой ограничивающей прямой L0, Lv… поочередно, причем t.n и cout при необходимости обновляются.
Предположим, что при проверке луча относительно L0 мы обнаруживаем при t - 0,83 пересечение на выходе. Тогда t)ut устанавливается в 0,83 и возможный интервал становится равным [0,0,83]. Затем луч проверяется относительно L, и обнаруживается пересечение на выходе при t = 0,66. Это уменьшает возможный интервал до [0,0,66]. Проверка относительно L2 выявляет пересечение на выходе при t = 3,4. Это не дает нам ничего нового: мы уже знаем, что луч находится вне полигона при t > 0,66. Тест относительно L3 показывает пересечение на входе при t = -4,7, то есть в более ранний момент, чем текущее значение г.п. Тест относительно Li указывает на пересечение на входе при с = 0,2, поэтому t.m обновляется до 0,2. И, наконец, проверка относительно L5 выявляет пересечение на входе при t - 0,28, и на этом про1 В задаче о пересечении луча, когда луч неограниченно распространяется в обоих направлениях, мы полагаем Г1П - -~ и гт11 = °о. На практике £!п присваивается какое-либо большое по модулю отрицательное значение, а £ - большое положительное значение.