Оптимизация текстурирования

То, что написанно ниже, написано мной. Это будет интересно лишь тем, кто подобен мне полторагодичной давности %)) т.е. тем, кто начинает изучать 3D-графику, тем, которые думают, что они слишком умны, и смогут придумать свой оригинальный и очень эффективный алгоритм текстурирования.

Речь пойдет об оптимизации внутренного цикла перспективного проецирования без биллинейной фильтрации. Привожу свои мысли на эту тему.

Итак, все методы текстурирования без биллинейной фильтрации можно поделить на те, которые дают абсолютно точный результат, и на те, которые значительно быстрее работают, но не дают точного результата. Hасколько я понимаю никто и никогда не использует точные алгоритмы на практике, так как смысла в этом нет. А неточные алгоритмы можно поделить на те, которые вычисляют координаты в текстуре интерполяцией их значений между каждыми 8/16-пискелями, и на те, которые аппроксимируют функцию координат в текстуре от координаты на экране какими-либо более простыми функциями, чем расчет по общим формулам.

А я решил сделать вот что: Построить алгоритм, который будет давать абсолютно точный результат, но будет работать быстрее большенства апроксимационных алгоритмов.

Сразу скажу, это мне не удалось. Поэтому все, что написанно ниже, может считаться всего лишь достаточно оригинальным вариантом как делать точное текстурирование...

В чем вообще проблема? В том, что расчет по общим формулам приводит к сложности алгоритма в два деления на точку. Hапомню в чем дело: координата в текстуре для каждой экранной точки расчитывается как отношение величин q(x) = t(x)/z(x) к w(x) = 1/z(x), где t(x)-координата в текстуре, а z(x) - удаленность (z-координата) текущей точки. Причина в том, что величины q(x) и w(x) меняются линейно, при линейном перемещении по проекции грани на экран, что позволяет их просто линейно интерполированить. Таким образом формула для расчета каждой координаты в текстуре через ее x-координату на экране будет иметь вид:

        q1 + x/(x2-x1)*(q2-q1)
f(x) = ------------------------
        w1 + x/(x2-x1)*(w2-w1)

Это отношение двух линейных функций от x. А что нам надо? Hам же не надо уметь быстро вычислять ее для каких-то произвольных значений x. Для начала нам надо научиться вычислять целую часть f(x) для x-ов, последовательно берущихся с шагом 1, т.е. нужен любой шаманский метод, который приведет к последовательному возникновению чисел f(x1), f(x1+1), .... , f(x2-1) Вот исходя из этого, я и придумал алгоритм, как вычислять отношение двух линейных функций для последовательных значений x. В оригинальной реализации алгоритм содержит только целочисленные операции, несколько ветвлений на точку и несколько дополнительных переменных. Все это я делал, когда у меня был компьютер с процессором iP120. Все хорошо, за исключением этих самых ветвлений на точку... не любит iPI ветвления, очень не любит. Структура этих ветвлений получилать такая, что это либо вероятно возникающие условные jump-ы назад (которые успешно предсказываются), либо это jump-ы на обход иструкций, которые плохо предсказываются. Вот. А потом у меня появился процессор на ядре P6, и тут оказалось, что лучше инструкций CMOVcc для моей задачи могут быть только инструкции CADDcc... :))

Вот и все, что я хотел сказать. Описывать сам алгоритм очень лень, до него вроде не сложно догадаться, если рассмотреть операцию "целая часть от деления" как операцию получения числа вхождений по длинне одного отрезка в другой, а переход к следующему значению x как удлиннение обоих отрезков на некоторые постоянные значения.

Сейчас я уже давно вообще не занимаюсь графикой и оптимизацией на скорость. Защищать свой алгорим в дисскусии с вами я видемо не буду. Сколько тактов на точку он дает тоже не скажу, т.к. не знаю. Исходник реализации под iPI можно найти у меня на страничке. В 320x200x8bpp на очень простой quake-о подобной сцене на Cel433 FPS составлял где-то 70-110, все, кроме внутреннего цикла тексурирования, написанно очень криво и на паскале, да... и никакой "субтексельной точности"... %)