Предложения по оптимизации реализации Z-буфера?

Question

Я пишу библиотеку 3D-графики как часть моего проекта, и я нахожусь в точке, где все работает, но не достаточно хорошо.

В частности, моя главная головная боль заключается в том, что мойскорость заполнения пикселя составляет ужасно медленно - я даже не могу управлять 30 кадрами в секунду при рисовании треугольника, который охватывает половину окна 800x600 на моей целевой машине (которая по общему признанию является более старым компьютером, но это должно бытьв состоянии управлять этим ...)

Я запустил gprof на своем исполняемом файле, и я получаю следующие интересные строки:

  %   cumulative   self              self     total           
time   seconds   seconds    calls  ms/call  ms/call  name    
43.51      9.50     9.50                             vSwap
34.86     17.11     7.61   179944     0.04     0.04  grInterpolateHLine
13.99     20.17     3.06                             grClearDepthBuffer
<snip>
0.76      21.78     0.17      624     0.27    12.46  grScanlineFill

Функция vSwap - это моя функция подкачки двойного буфера, и она также выполняет всечинг, поэтому для меня имеет смысл, что тестовая программа будет проводить там большую часть своего времени.grScanlineFill - это моя функция рисования треугольника, которая создает список ребер и затем вызывает grInterpolateHLine для фактического заполнения треугольника.

Мой движок в настоящее время использует Z-буфер для выполнения скрытой очистки поверхности.Если мы сбрасываем со счетов (предполагаемые) издержки vsynch, то оказывается, что тестовая программа тратит примерно 85% своего времени либо на очистку буфера глубины, либо на запись пикселей в соответствии со значениями в буфере глубины.Моя функция очистки буфера глубины сама по себе проста: скопируйте максимальное значение с плавающей точкой в ​​каждый элемент.Функция grInterpolateHLine:

void grInterpolateHLine(int x1, int x2, int y, float z, float zstep, int colour) {
    for(; x1 <= x2; x1 ++, z += zstep) {
        if(z < grDepthBuffer[x1 + y*VIDEO_WIDTH]) {
            vSetPixel(x1, y, colour);
            grDepthBuffer[x1 + y*VIDEO_WIDTH] = z;
        }
    }
}

Я действительно не понимаю, как это можно улучшить, особенно учитывая, что vSetPixel - это макрос.

Весь мой запас идей дляоптимизация была сведена к одному:

1. Использовать буфер глубины целых чисел / фиксированной точки.

Проблема, с которой я столкнулся с буферами глубины целочисленных значений / фиксированной точкив том, что интерполяция может быть очень раздражающей, и у меня на самом деле нет библиотеки чисел с фиксированной точкой еще.Есть еще какие-нибудь мысли?Любой совет будет наиболее ценным.

Answer 1

Вам следует взглянуть на исходный код чего-то вроде Quake - учитывая, чего он мог достичь на Pentium 15 лет назад. Его реализация z-буфера использует интервалы, а не глубину на пиксель (или фрагмент). В противном случае вы можете посмотреть код растрирования в Mesa .

Answer 2

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

Нет необходимости вычислять x1 + y * VIDEO_WIDTH более одного раза в grInterpolateHLine.то есть:

void grInterpolateHLine(int x1, int x2, int y, float z, float zstep, int colour) {
    int offset = x1 + (y * VIDEO_WIDTH);
    for(; x1 <= x2; x1 ++, z += zstep, offset++) {
        if(z < grDepthBuffer[offset]) {
            vSetPixel(x1, y, colour);
            grDepthBuffer[offset] = z;
        }
    }
}

Аналогично, я предполагаю, что ваш vSetPixel выполняет аналогичные вычисления, так что вы должны иметь возможность использовать то же самое смещение там, и тогда вам нужно только увеличивать смещение, а не x1в каждой итерации цикла.Скорее всего, это может быть расширено до функции, которая вызывает grInterpolateHLine, и тогда вам нужно будет выполнять умножение только один раз для каждого треугольника.

Есть некоторые другие вещи, которые вы можете сделать с буфером глубины.В большинстве случаев, если первый пиксель линии либо не проходит тест, либо проходит тест глубины, то остальная часть строки будет иметь такой же результат.Таким образом, после первого теста вы можете написать более эффективный блок сборки, чтобы протестировать всю строку за один снимок, затем, если он пройдет, вы можете использовать более эффективный блок установки блока памяти, чтобы блокировать значения пикселей и глубины вместо того, чтобы делать их по одномувремя.Вам нужно будет только протестировать / установить для каждого пикселя, если линия только частично закрыта.

Кроме того, не уверен, что вы подразумеваете под старым компьютером, но если ваш целевой компьютер многоядерный, вы можете разбить егосреди нескольких ядер.Вы можете сделать это и для функции очистки буфера.Это может помочь совсем немного.

Answer 3

В итоге я решил эту проблему, заменив Z-буфер алгоритмом художника. Я использовал SSE для написания реализации Z-буфера, которая создала битовую маску с пикселями для рисования (плюс оптимизацию диапазона, предложенную Джеральдом), и она все еще работала слишком медленно.

Спасибо всем за ваш вклад.