Алгоритм пересечения для базового куба Процесс пересечения луча с кубом по своей сути является алгоритмом Сайруса-Бека, описанным в разделе «Алгоритм Сайруса-Бека» главы 4, где прямая линия отсекается границами выпуклого окна в двумерном пространстве. Данный алгоритм был также использован для отсечения прямой линии отображаемым объемом камеры в главе 8. Основная идея заключается в том, что каждая плоскость куба определяет «внутреннее» и «внешнее» полупространства и что точка на луче лежит внутри этого куба тогда и только тогда, когда она лежит «внутри» каждого полупространства куба. Тогда пересечение луча с кубом сводится к определению интервала времени, в течение которого луч лежит внутри всех плоскостей куба.
Обозначим куб буквой Р. Протестируем луч поочередно с каждой плоскостью куба Р, вычисляя моменты времени, в которые луч или входит во внутреннее полупространство данной плоскости, или выходит из него. Мы будем отслеживать этот «возможный интервал» («candidate interval* - CI) - такой интервал времени, в который, на основе выполненных до данного момента тестов, луч может находиться внутри данного объекта. Этот интервал ограничен значениями времени tm и tout то есть CI = [rin, toiJ. По мере проверки каждой плоскости куба Р мы «усекаем» этот интервал, либо увеличивая rin, либо уменьшая tout. Если для какой-нибудь точки CI становится пустым, то луч должен пройти мимо данного объекта, определяя «досрочный выход». Если после проверки всех плоскостей куба Р мы обнаружим, что оставшийся интервал CI не пуст, то луч входит в объект в момент ta и выходит из него в момент tmt.
Рис. 14.12. Луч протыкает базовый куб (а); двумерный случай (6)
Для иллюстрации этого процесса на рис. 14.12, а показан пример, в котором луч входит в базовый куб при £ = 3,6 и выходит из него при г = 4,1. Тогда при завершении тестирования остается интервал С1 = [3,6, 4,1]. На рис. 14.12, б для простоты показан двумерный вариант того же процесса; здесь мы хотим найти пересечение луча с квадратом. С нашей «всевидящей» обзорной точки мы видим, что луч вначале соударяется с верхней плоскостью квадрата при г = 1,6 и входит во внутреннее полупростран-