14.6.9. Пересечение с тетраэдром Найдите интервал времени г, для которого луч (0,0,0) + (1,2,3) t находится внутри тетраэдра с вершинами (1,0,0), (-1,0, -1), (-1,0,1), (0,1,0).
14.6.10. О сложности вычислений Сколько умножений/делений требуется для тестирования каждой плоскости выпуклого полиэдра? Иногда время tin превышает tOut уже после тестирования всего нескольких плоскостей. Какова будет эвристическая оценка среднего числа тестов, выполняемых для выпуклого полиэдра из N плоскостей, если тестируется случайно выбранный луч? Сравните получившийся уровень сложности с тем, который использовался при пересечении луча со сферой.
Можно выйти за пределы рассмотренных до сих пор примитивов и добавить другие типы форм. Требуется только знать для этой формы неявную запись уравнения Р(Р). Тогда, как и прежде, для нахождения места пересечения луча 5 + сг с поверхностью подставляем 5 + сг вместо Р в уравнение Р(Р), в результате чего получается следующая функция от времени £ Эта функция: О положительна при тех значениях времени t, для которых луч (точнее, точка на луче) лежит вне объекта; О равна нулю, когда луч совпадает с поверхностью объекта; О отрицательна, когда луч находится внутри объекта.
При поиске пересечений мы ищем такие значения г, при которых d(t) = 0, поэтому пересечение луча эквивалентно решению данного уравнения. Мы уже видели, что для сферы и других квадратичных поверхностей d(t) является обычным квадратным уравнением.
Иная ситуация возникает в случае тора. Неявная функция для базового тора имеет следующий вид (см. табл. б. 11): вследствие чего получается уравнение четвертого порядка. Решение такого уравнения значительно сложнее, хотя его решения в аналитическом виде можно найти в математических справочниках.
Рассмотрим вид функции d(t) при возрастающих значениях t. Если луч направлен на рассматриваемый объект и стартовая точка S лежит вне объекта, то мы получаем кривые, аналогичные изображенным на рис. 14.14. Значение d(0) положительно, поскольку луч стартует вне объекта. По мере приближения луча к объекту d(t) уменьшается, достигая нуля, если луч пересекает поверхность объекта (на рисунке это £,). В тот период времени, когда луч находится внутри объекта, d(t) < 0. Когда луч появляется вновь, то d{t) проходит через нуль и продолжает возрастать. (При работе с такими объектами, как тор, луч может повторно войти в объект, так что нарисуйте типичную форму кривой d(t) для этого случая.) Если же луч проходит мимо объекта (этот случай показан на рисунке пунктиром), то хотя значение d(t) в течение какого-то времени уменьшается, однако затем все время возрастает, не достигая нуля.