Можно ли оптимизировать этот алгоритм рисования линий? - SDL

Question

Для проекта, над которым я работал, возможность рисовать линии с градиентом (т.е. они меняют цвет в течение интервала, в котором они нарисованы) была бы очень полезна. У меня есть алгоритм для этого, как я вставлю ниже, но он оказывается УЖАСНО медленным. Я использую алгоритм Брезенхэма, чтобы найти каждую точку, но боюсь, что я достиг пределов программного рендеринга. До сих пор я использовал SDL2, и мой алгоритм рисования линий выглядит в 200 раз медленнее, чем SDL_RenderDrawLine, Это приблизительная оценка, полученная из сравнения времен двух функций, чтобы нарисовать 10000 линий. Моя функция займет около 500 мс, и SDL_RenderDrawLine сделал это за 2-3мс на моей машине. Я даже протестировал функции с горизонтальными линиями, чтобы убедиться, что это не просто неуклюжий алгоритм Брезенхэма, и заштрихована похожая медлительность. К сожалению, SDL не имеет API для рисования линий с градиентом (или, если он есть, я слепой). Я знал, что любой программный рендеринг будет значительно медленнее, чем аппаратный, но сдвиговая величина медлительности застала меня врасплох. Есть ли способ, который можно использовать для ускорения этого? Я только что испортил систему рисования без причины? Я подумал о том, чтобы сохранить массив пикселей, которые я хочу нарисовать, а затем сразу же перенести их на экран, но я не знаю, как это сделать с SDL2, и я не могу найти API в вики. или документация, которая позволяет это. Будет ли это даже быстрее?

Спасибо за внимание!

void DRW_LineGradient(SDL_Renderer* rend, SDL_Color c1, int x1, int y1, SDL_Color c2, int x2, int y2){
Uint8 tmpr, tmpg, tmpb, tmpa;
SDL_GetRenderDrawColor(rend, &tmpr, &tmpg, &tmpb, &tmpa);

int dy = y2 - y1;
int dx = x2 - x1;

/* Use doubles for a simple gradient */
double d = (abs(x1 - x2) > abs(y1 - y2) ? abs(x1 - x2) : abs(y1 - y2));
double dr = (c2.r - c1.r) / d;
double dg = (c2.g - c1.g) / d;
double db = (c2.b - c1.b) / d;
double da = (c2.a - c1.a) / d;

double r = c1.r, g = c1.g, b = c1.b, a = c1.a;

/* The line is vertical */
if (dx == 0) {
    int y;
    if (y2 >= y1) {
        for (y = y1; y <= y2; y++) {
            SDL_SetRenderDrawColor(rend, r, g, b, a);
            SDL_RenderDrawPoint(rend, x1, y);
            r += dr;
            g += dg;
            b += db;
            a += da;
        }
        return;
    }
    else{
        for (y = y1; y >= y2; y--) {
            SDL_SetRenderDrawColor(rend, r, g, b, a);
            SDL_RenderDrawPoint(rend, x1, y);

            r += dr;
            g += dg;
            b += db;
            a += da;
        }
        return;
    }
}
/* The line is horizontal */
if (dy == 0) {
    int x;
    if (x2 >= x1) {
        for (x = x1; x <= x2; x++) {
            SDL_SetRenderDrawColor(rend, r, g, b, a);
            SDL_RenderDrawPoint(rend, x, y1);
            r += dr;
            g += dg;
            b += db;
            a += da;
        }
        return;
    }
    else{
        for (x = x1; x >= x2; x--) {
            SDL_SetRenderDrawColor(rend, r, g, b, a);
            SDL_RenderDrawPoint(rend, x, y1);

            r += dr;
            g += dg;
            b += db;
            a += da;
        }
        return;
    }
}
/* The line has a slope of 1 or -1 */
if (abs(dy) == abs(dx)) {
    int xmult = 1, ymult = 1;
    if (dx < 0) {
        xmult = -1;
    }
    if (dy < 0) {
        ymult = -1;
    }
    int x = x1, y = y1;
    do {
        SDL_SetRenderDrawColor(rend, r, g, b, a);
        SDL_RenderDrawPoint(rend, x, y);
        x += xmult;
        y += ymult;
        r += dr;
        g += dg;
        b += db;
        a += da;
    } while (x != x2);
    return;
}

/* Use bresenham's algorithm to render the line */

int checky = dx >> 1;
int octant = findOctant((Line){x1, y1, x2, y2, dx, dy});

dy = abs(dy);
dx = abs(dx);
x2 = abs(x2 - x1) + x1;
y2 = abs(y2 - y1) + y1;

if (octant == 1 || octant == 2 || octant == 5 || octant == 6) {
    int tmp = dy;
    dy = dx;
    dx = tmp;
}

int x, y = 0;
for (x = 0; x <= dx; x++) {
    SDL_SetRenderDrawColor(rend, r, g, b, a);
    switch (octant) {
        case 0:
            SDL_RenderDrawPoint(rend, x + x1, y + y1);
            break;
        case 1:
            SDL_RenderDrawPoint(rend, y + x1, x + y1);
            break;
        case 2:
            SDL_RenderDrawPoint(rend, -y + x1, x + y1);
            break;
        case 3:
            SDL_RenderDrawPoint(rend, -x + x1, y + y1);
            break;
        case 4:
            SDL_RenderDrawPoint(rend, -x + x1, -y + y1);
            break;
        case 5:
            SDL_RenderDrawPoint(rend, -y + x1, -x + y1);
            break;
        case 6:
            SDL_RenderDrawPoint(rend, y + x1, -x + y1);
            break;
        case 7:
            SDL_RenderDrawPoint(rend, x + x1, -y + y1);
            break;
        default:
            break;
    }

    checky += dy;
    if (checky >= dx) {
        checky -= dx;
        y++;
    }

    r += dr;
    g += dg;
    b += db;
    a += da;
}

SDL_SetRenderDrawColor(rend, tmpr, tmpg, tmpb, tmpa);
}

ПРИМЕЧАНИЕ:

Я неохотно просто перехожу к использованию OpenGL 3.0+ (который, как я слышал, поддерживает SDL2), потому что я не знаю, как его использовать. Большинство учебных пособий, которые я нашел, объясняли процесс настройки контекстов с помощью SDL, а затем окрашивали экран одним сплошным цветом, но затем остановились, прежде чем объяснять, как рисовать фигуры и тому подобное. Если бы кто-то мог предложить хорошее место, чтобы начать узнавать об этом, это также было бы чрезвычайно полезно.

Answer 1

Большая часть вашей функции связана с повторными вызовами SDL_RenderDrawPoint, Это (скорее всего) универсальная функция, которая должна выполнять следующие операции:

1. проверить, если x а также y находятся в пределах досягаемости для вашей текущей поверхности;
2. рассчитать положение внутри поверхности, умножив y с surface->pitch а также x с surface->format->BytesPerPixel;
3. проверить текущую цветовую модель поверхности, используя SDL_PixelFormat;
4. преобразовать предоставленный цвет в правильный формат для этой цветовой модели.

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

Вы можете:

1. пропускать x а также y проверка диапазона, если вы уверены, что начальная и конечная точки линии всегда видны;
2. пропустите шаг преобразования в адрес, рассчитав его один раз для начала строки, а затем обновив его, добавив BytesPerPixel а также pitch для горизонтального или вертикального движения;
3. пропустите шаг модели преобразования в цвет, рассчитав правильные значения RGB один раз (ну, по крайней мере, для одной цветовой линии - для градиента немного сложнее);
4. пропустите вызов функции, вставив код, чтобы установить один пиксель внутри line рутина.

Другая, меньшая проблема: вы называете свою рутину "Брезенхэмом... но это не так. Оптимизация Брезенхэма заключается в том, что она избегает double полностью расчеты (и его сильная сторона в том, что он по-прежнему дает математически правильный вывод; на что-то, на что я не рассчитывал бы при использовании double переменные...).

Следующая процедура не проверяет диапазон, цветовую модель, цветовые значения или (действительно) поверхность должна быть заблокирована. Все эти операции в идеале должны выполняться за пределами жесткого цикла рисования. Как таковой, он предполагает 24-битный RGB цветной экран, с красным байтом первым. [*]

Я написал этот код для моей текущей среды SDL, которая все еще является SDL-1.0, но она должна работать и для более новых версий.

Можно использовать вычисления Брезенхэма и для значений delta-Red, delta-Green и delta-Blue, но я намеренно здесь их опущу :) Они добавили бы много дополнительных переменных - по-видимому, три на цветовой канал - дополнительные проверки и, что немаловажно, на самом деле заметно лучшего качества. Разница между двумя последовательными значениями для красного, скажем, 127 и 128, как правило, слишком мала, чтобы заметить ее шириной в один пиксель. Кроме того, этот маленький шаг будет происходить только в том случае, если длина вашей линии составляет не менее 256 пикселей, и вы покрываете весь диапазон красного от 0 до 255 в градиенте.

[*] Если вы на 100% уверены, что нацеливаетесь на конкретную модель экрана с помощью собственной программы, вы можете использовать ее (конечно, с учетом этой конкретной модели экрана). Целесообразно нацелиться и на несколько разных моделей экрана; написать индивидуальную подпрограмму для каждого и использовать указатель функции для вызова правильной.
Скорее всего это как SDL_RenderDrawLine способен выжать каждую миллисекунду производительности. Стоит написать весь этот код для библиотеки (которая будет использоваться на самых разных экранах), но, скорее всего, не для одной программы, такой как ваша. Обратите внимание, что я прокомментировал одну проверку диапазона, которая возвращается к простой line рутина в случае необходимости. Вы можете сделать то же самое для необычных или неожиданных настроек экрана, и в этом случае просто вызовите свою собственную, более медленную, процедуру рисования. (Ваша процедура более надежна, поскольку использует собственные процедуры SDL.)

Оригинал line Подпрограмма, приведенная ниже, была скопирована из Интернета более десяти лет назад, поскольку я использую ее целую вечность. Я с удовольствием приписал бы это кому-то; если кто-то распознает комментарии (они в основном соответствуют оригинальному коду), оставьте комментарий.

void gradient_line (int x1,int y1,int x2,int y2,
    int r1,int g1, int b1,
    int r2,int g2, int b2)
{
    int     d;                      /* Decision variable                */
    int     dx,dy;                  /* Dx and Dy values for the line    */
    int     Eincr,NEincr;           /* Decision variable increments     */
    int     t;                      /* Counters etc.                    */
    unsigned char *ScrPos;
    int LineIncr;

    int rd,gd,bd;

    if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0 ||
        x1 >= SCREEN_WIDE || x2 >= SCREEN_WIDE ||
        y1 >= SCREEN_HIGH || y2 >= SCREEN_HIGH)
    {
        line (x1,y1, x2,y2, (r1<<16)+(g1<<8)+b1);
        return;
    }

    rd = (r2-r1)<<8;
    gd = (g2-g1)<<8;
    bd = (b2-b1)<<8;

    dx = x2 - x1;
    if (dx < 0)
        dx = -dx;
    dy = y2 - y1;
    if (dy < 0)
        dy = -dy;

    if (dy <= dx)
    {
        /* We have a line with a slope between -1 and 1
         *
         * Ensure that we are always scan converting the line from left to
         * right to ensure that we produce the same line from P1 to P0 as the
         * line from P0 to P1.
         */
        if (x2 < x1)
        {
            t = x2; x2 = x1; x1 = t;    /* Swap X coordinates           */
            t = y2; y2 = y1; y1 = t;    /* Swap Y coordinates           */
            /* Swap colors */
            r1 = r2;
            g1 = g2;
            b1 = b2;
            rd = -rd;
            gd = -gd;
            bd = -bd;
        }
        r1 <<= 8;
        g1 <<= 8;
        b1 <<= 8;

        if (y2 > y1)
        {
            LineIncr = screen->pitch;
        } else
        {
            LineIncr = -screen->pitch;
        }

        d = 2*dy - dx;              /* Initial decision variable value  */
        Eincr = 2*dy;               /* Increment to move to E pixel     */
        NEincr = 2*(dy - dx);       /* Increment to move to NE pixel    */

        ScrPos = (unsigned char *)(screen->pixels+screen->pitch*y1+x1*screen->format->BytesPerPixel);

        rd /= dx;
        gd /= dx;
        bd /= dx;

        /* Draw the first point at (x1,y1)  */
        ScrPos[0] = r1 >> 8;
        ScrPos[1] = g1 >> 8;
        ScrPos[2] = b1 >> 8;

        r1 += rd;
        g1 += gd;
        b1 += bd;

        /* Incrementally determine the positions of the remaining pixels */
        for (x1++; x1 <= x2; x1++)
        {
            if (d < 0)
            {
                d += Eincr;         /* Choose the Eastern Pixel         */
            } else
            {
                d += NEincr;        /* Choose the North Eastern Pixel   */
                ScrPos += LineIncr;
            }
            ScrPos[0] = r1>>8;
            ScrPos[1] = g1>>8;
            ScrPos[2] = b1>>8;

            ScrPos += screen->format->BytesPerPixel;

            r1 += rd;
            g1 += gd;
            b1 += bd;
        }
    } else
    {
        /* We have a line with a slope between -1 and 1 (ie: includes
         * vertical lines). We must swap our x and y coordinates for this.
         *
         * Ensure that we are always scan converting the line from left to
         * right to ensure that we produce the same line from P1 to P0 as the
         * line from P0 to P1.
         */

        if (y2 < y1)
        {
            t = x2; x2 = x1; x1 = t;    /* Swap X coordinates           */
            t = y2; y2 = y1; y1 = t;    /* Swap Y coordinates           */
            /* Swap colors */
            r1 = r2;
            g1 = g2;
            b1 = b2;
            rd = -rd;
            gd = -gd;
            bd = -bd;
        }

        r1 <<= 8;
        g1 <<= 8;
        b1 <<= 8;

        if (x2 > x1)
        {
            LineIncr = screen->format->BytesPerPixel;
        } else
        {
            LineIncr = -screen->format->BytesPerPixel;
        }

        d = 2*dx - dy;              /* Initial decision variable value  */
        Eincr = 2*dx;               /* Increment to move to E pixel     */
        NEincr = 2*(dx - dy);       /* Increment to move to NE pixel    */

        rd /= dy;
        gd /= dy;
        bd /= dy;

        /* Draw the first point at (x1,y1)  */
        ScrPos = (unsigned char *)(screen->pixels+screen->pitch*y1+x1*screen->format->BytesPerPixel);

        ScrPos[0] = r1 >> 8;
        ScrPos[1] = g1 >> 8;
        ScrPos[2] = b1 >> 8;

        r1 += rd;
        g1 += gd;
        b1 += bd;

        /* Incrementally determine the positions of the remaining pixels
         */

        for (y1++; y1 <= y2; y1++)
        {
            ScrPos += screen->pitch;
            if (d < 0)
            {
                d += Eincr;         /* Choose the Eastern Pixel         */
            } else
            {
                d += NEincr;        /* Choose the North Eastern Pixel   */
                ScrPos += LineIncr; /* (or SE pixel for dx/dy < 0!)     */
            }
            ScrPos[0] = r1 >> 8;
            ScrPos[1] = g1 >> 8;
            ScrPos[2] = b1 >> 8;

            r1 += rd;
            g1 += gd;
            b1 += bd;
        }
    }
}

... и это часть экрана со случайными линиями со случайными цветами, с крупным планом справа:

Я не рассчитывал разницу между "родным" рисованием линий SDL, вашим наивным методом, реализацией Брезенхэма в чистом сплошном цвете и этой; с другой стороны, это не должно быть намного медленнее, чем собственная строка SDL.