Вопросы о растеризации: стохастическая выборка, функция ребра Пинеды и числа с фиксированной точкой
Я пытаюсь изучить / понять алгоритм растеризации и уже опубликовал несколько сообщений, которые связаны с этим и, к сожалению, не получил много ответов:
Алгоритм растеризации: нахождение "ST" координаты точки в 2D-квадрате и обратной проекции
В первом вопросе я хотел растеризовать квад, но теперь я ограничусь треугольником, который в любом случае является стандартным примитивом рендеринга.
Поэтому моя проблема заключается в том, чтобы точно знать, какой метод используется для определения того, находится ли данный пиксель в треугольнике. Я использую краевой подход, который в порядке. Допустим, мне нужно перебрать все пиксели bbox, окружающего 2D Triange.
float dX0 = (v1.x - v0.x);
float dY0 = (v1.y - v0.y);
float dX1 = (v2.x - v1.x);
float dY1 = (v2.y - v1.y);
float dX2 = (v0.x - v2.x);
float dY2 = (v0.y - v2.y);
for (int y = ymin; y <= ymax; ++y) {
for (int x = xmin; x <= xmax; ++x) {
float xctr = x + 0.5;
float yctr = y + 0.5;
float s0 = (xctr - v0.x) * dX0 - (yctr - v0.y) * dY0;
float s1 = (xctr - v1.x) * dX1 - (yctr - v1.y) * dY1;
float s2 = (xctr - v2.x) * dX2 - (yctr - v2.y) * dY2;
if (s0 >= 0 && s1 >= 0 && s2 >= 0) {
// point is in triangle
}
}
}
Я также попробовал барицентрический подход. Вычислить s и t для точки в треугольнике и если (s + t) <= 1 тогда я знаю, что точка находится в треугольнике.
Так что оттуда у меня есть несколько вопросов:
1) В статье из Пинеда [88] хотя говорят, что если вы двигаетесь вдоль x или y, вы можете просто обновить результат функции ребра простым добавлением. Я цитирую:
The edge functions may then be computed incrementally for a unit step in the X or Y direction:
Ei(x+l,y)=Ei(x,y)+dYi,
Ei(x-1,y)=Ei(x,y)-dYi,
Ei(x,y+l)=Ei(x,y)-dXi,
Ei(x,y-l)=Ei(x,y)+dXi.
Так что все в порядке, я понимаю, почему это работает, но в общем случае, когда мы делаем суперсэмплинг или даже стохастическую сэмплирование (деление пикселя, скажем, на сэмплы 4×4, которые имеют дрожание), этот метод все еще будет полезен вообще?
2) Я до сих пор не знаю, как с помощью функции края мы можем вычислить s / t / z путем интерполяции? Может ли кто-нибудь помочь мне с этим или указать несколько страниц, на которых это объясняется?
3) Сейчас я изучаю другой подход для растеризации треугольников, такой как алгоритм Брезенхэма, но кажется, что везде говорят, что он работает только с координатами с фиксированной точкой? Я сбит с толку. После проекции треугольников вершины находятся в плавающих точках. Как вы можете перейти от точки с плавающей точкой к координатам с фиксированной точкой?
Решение
растеризации
Прежде всего, типичный алгоритм растеризации не будет повторяться по всему ограничивающему прямоугольнику спроецированного треугольника, как то, что вы пытаетесь, потому что это будет слишком медленно.
Идея состоит в том, чтобы:
- вершины проекта в пространство изображения,
- упорядочить 2D вершины по горизонтали или по вертикали (предпочтительно с использованием направления меньшего размера ограничительной рамки)
- разделить треугольник на две части:
- от первой вершины до вертикальной или горизонтальной, проходящей через вторую вершину,
- от вертикального / горизонтального прохода через вторую вершину к третьей вершине,
- растеризовать каждую половину
Вы бы получили что-то похожее на это:
* v2
/|\
/ | \
/ | \
/ T1|T2 \
v1 *----+----* v3
Теперь для растеризации треугольника T1 вы можете задать итерацию X от v1.x до v2.x и использовать наклон ребер для вычисления диапазона, по которому Y должен выполнить итерацию для среза треугольника в X.
Границы этого Y-диапазона будут иметь постоянные приращения для каждого вертикального среза, поэтому вы можете либо представить эти приращения в виде дробных чисел (либо с фиксированной, либо с плавающей запятой), либо использовать алгоритм Брезенхэма.
Идея та же для треугольника T2.
Multisampling
При выполнении мультисэмплинга с дрожащими выборками вы должны решить, лежит ли каждая отдельная выборка внутри треугольника в основном так, как вы пытались, но это необходимо только для пикселей на краю треугольника.
Однако поиск текстуры должен выполняться только один раз для каждого пикселя (охватывающий несколько выборок).
Если вы хотите вычислить глубину для каждой выборки, приращение глубины на пиксель в основном должно быть умножено на дробное дрожание выборки от центроида пикселя.
КООРДИНАТЫ ИНТЕРПОЛЯЦИОННОЙ ТЕКСТУРЫ
Теперь, если мы рассмотрим алгоритм растеризации, можно подумать, что каждое приращение в X или Y переводит в приращение в S, T и Z. Это в основном работает нормально, но вызывает искажения, потому что линейная интерполяция S, T, Z не учитывает для глубинного разделения.
Вместо того чтобы пытаться преобразовать координаты пространства изображения обратно в координаты трехмерной сцены, можно (и дешевле) вычислить скорректированные S, T, Z из наивно вычисленных.
Вы можете проверить этот PDF, чтобы найти формулу для поправочного коэффициента:
http://web.cs.ucdavis.edu/~amenta/s12/perspectiveCorrect.pdf
Другие решения