Субпиксельная точность

 

Обзор

Субпиксельная точность (Sub-pixel accuracy) - это термин, определяющий технику обработки трехмерного изображения с целью улучшения качества конечного изображения и решения некоторых проблем трехмерной графики (например "дыр" между соседними полигонами). Вот образное понятие субпиксельной точности: "Отображаются только пикселы, чьи центры находятся внутри полигона". Но не обязательно придерживаться этого непонятного на первый взгляд определения вслепую. Для приложений и игр, работающих в реальном времени, любая точка внутри пиксела (например правый нижний угол) может быть использована вместо центра. Единственный побочный эффект этого - то, что все полученное изображение будет смещено вниз-влево примерно на 0.5 пиксела. Приведу пример, использующий эту технику (пока вам еще ничего не понятно, но скоро все станет на свои места ;).

ОК, представьте себе лист бумаги. Это не сложно ;). Теперь представьте что этот лист разделен на некоторое количество квадратных сегментов (небольшое). В самом центре каждого такого сегмента стоит маленькая точка. Над листом бумаги находится контур треугольника размером почти во всю страницу. Предположим все линии - и стороны треугольника и сетка на листе бумаги имеют бесконечно малую толщину, то есть будем рассматривать только их математическую модель, а не физическую.

А теперь представьте, что каждый сегмент листа бумаги - это и есть пиксел. А теперь самое главное - только те пикселы, чьи центы лежат внутри контура треугольника, примут цвет этого треугольника. Это все не так сложно как кажется, надеюсь вы это уже поняли ;). Воссоздание этого метода "ручками" (© Philosoph ;) делается очень просто а при должной оптимизации скорость приложения практически не должна измениться.

 

Применение субпиксельной точности

Субпиксельная точность используется по одной причине: все наши дисплеи - цифровые (пиксельные), а в связи с современной тенденцией постоянного уменьшения размера пикселя на экране, скоро необходимость в субпиксельной точности отпадет вообще. Однако пока, увы, эта методика - один из важнейших основополагающих алгоритмов улучшения качества изображения, ведь даже в разрешении 1027*768 субпиксельная точность оказывает свое благотворное влияние на картинку.

Теперь немного теории: на растровых цифровых мониторах мы часто сталкиваемся с проблемой - какой пиксель нужно включать в фигуру, а какой - нет. Без субпиксельной точности мы бы просто использовали все пиксели, касающиеся фигуры, что само по себе не очень хорошо. Рассмотрим такой пример: представьте один полигон с почти горизонтальной верхней гранью. Верхние две точки находятся очень близко от сотой строки - причем одна из них чуть-чуть выше ее (y=100.1), а вторая чуть-чуть ниже (y=99.9). Без субпиксельной точности эта линия бы была прямой линией плюс один пиксель сверху одной из точек. А должна получиться линия с "изломом" посередине на одну строку вниз - вот это как-раз и достигается с помощью субпиксельной точности.

 

Алгоритм (как ни странно, получилось по материалам demo.design.3D.programming FAQ - хммм)

Теперь к делу. Рассмотрим, как же сделать субпиксельную точность.

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

sx_start += dx_start;

sx_end += dx_end;

теряет субпиксельную точность из-за этого самого округления, так как sx_start инициализируется как A.sx, A.sx соотвествует линии y = A.sy, а рисовать мы начинаем с какого-то округленного значения. Кстати, ни один из примеров к FAQ'у потерей субпиксельной точности не страдает, так как для каждой строки sx_start и sx_end заново вычисляются по точной формуле.

Точная формула для расчета sx_start выглядит как

sx_start = A.sx + dx_start * (current_sy - A.sy);

и для самой первой линии мы тоже должны ее честно применить, а не просто положить sx_start = A.sx. Получаем, что

sx_start = A.sx + dx_start * (ceil(A.sy) - A.sy);

sx_end = A.sx + dx_end * (ceil(A.sy) - A.sy);

Ту же самую операцию надо сделать и со всем остальными переменными, которые мы будем интерполировать по ребрам (например u, v, интенсивность для Гуро); и то же самое надо сделать при переходе с ребра на ребро.

// ...

u_start += du_start * (ceil(start_y) - start_y);

u_end += du_end * (ceil(start_y) - start_y);

// ...

Ну и, разумеется, рисовать начинать надо с той строки, которую мы использовали в формулах. То есть, ceil(start_y).

 

Ну и немножко ассемблера….

Можно также написать "инлайновую" процедуру для любителей языка Си на Ассемблере (соответсвенно для любителей этого многопланового, мощного, выдающегося, можно сказать, языка) ;)

Примерно выглядеть эта процедурина ;) будет так:

inline float SUB_PIX(const float input)

{

float retCode;

__asm fld input

__asm fld input

__asm fsub dword ptr half

__asm frndint

__asm fsubp st(1),st

__asm fldl

__asm fsubrp st(1),st

__asm fstp retCode

return retCode;

}

здесь half - 32-разрядная floating point переменная содержащая значение 0.5f.

Эта процедура уменьшает наше уравнение до

sx_start += dx_start * SUB_PIX(A.sy);

sx_end += dx_end * SUB_PIX(A.sy);

Чтобы увидеть изменения - покрутите теперь ваш трехмерный мир на доли градуса (примерно 1/256) со включенной субпиксельной точностью и с выключенной.