Кэтмулл предлагает несколько путей повышения эффективности этого метода. Определение размера проекции лоскута является дорогостоящей операцией, поэтому вместо лоскута проецируется полигон, сформированный из четырех угловых точек лоскута, и определяется размер этого полигона. Кроме того, перед тем как проталкивать каждый лоскут в стек, его можно пометить как находящийся целиком внутри отображаемого объема или нет. Когда впоследствии этот лоскут выталкивается из стека, его не нужно отсекать, а если он будет разбиваться дальше, то будет известно, что все четыре его куска также целиком находятся внутри.
Блинн и Уиттед (Whitted) [Blinn, 28] независимо друг от друга разработали похожие алгоритмы построчного сканирования, в которых видимые куски лоскутов отслеживаются от одной строки раз-
13.7. HSR-методы для криволинейных поверхностей вертки к другой. Оба метода требуют сложных численных расчетов для нахождения значений параметров (и, v), при которых координата у лоскута Р(и, v) принимает заданное значение строки развертки.
Существует и другой достаточно успешный подход, в котором лоскуты разбиваются до тех пор, пока они не станут «достаточно плоскими», чтобы рассматривать их как плоскостные четырехугольники, после чего они визуализируются с помощью HSR-алгоритма построчного сканирования. Если лоскуты, вовлеченные в процесс, являются лоскутами Безье или ß-сплайн лоскутами, то существуют эффективные методы их разбиения посредством формирования нового контрольного полиэдра (эти методы описаны в работе [Foley, 65]). Похожие методы для строк развертки были разработаны Лэйном и Кар-пентером, а также Кларком ([Clark, 41; Lane, 129]). При подходе Лэйна-Карпентера лоскут разбивается только тогда, когда строка развертки начинает пересекать его; в методе Кларка все лоскуты разбиваются заранее, до начала процесса. В первом методе требуется большее число разбиений, но последний метод требует больше памяти.
Листинг 13.9. Метод построчного сканирования Лэйна-Карпентера (псевдокод)