4
\$\begingroup\$

I wrote this variant of Bresenham's for fun. I am looking to see what I can optimize as it is still slower than Bresenham's.

The idea here was that if I could isolate out the IFs in Bresenham's loop it'd be more efficient. Well go figure, the added multiplication (A) or array lookups (B) in the pre-calc destroy said efficiency in overhead. That said, might be more efficient in a shader on GPUs? Haven't tested yet.

Both versions A and B have the same efficiency, weirdly enough.

Version A:

void bresenprecalcA(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1, dy = y2 - y1,
        // dxyA is the sign of the quadrant xy delta.
        dxA = sgn(dx), dyA = sgn(dy),
        // dyB is the absolute quadrant xy delta (to isolate the quadrant math).
        dxB = abs(dx), dyB = abs(dy),
        // check if x>y or y>x for quadrant determination.
        cx = dxB >= dyB, cy = dyB >= dxB,
        // qx is whether we're in a horz-x facing quadrant.
        // qy is whether we're in a vert-y facing quadrant.
        qx = cy * dxB, qy = cx * dyB,
        // qr checks if we lie in a quadrant rather than one of the 8 cardinal dir.
        // pd is for the incremental error check below.
        qr = qx != qy, pd = qx + qy,
        // if the line is horz, move horz other move vert.
        xm = cx * dxA, ym = cy * dyA,
        // if the line is horz, move horz other move vert.
        xym = cx? dxB : dyB,
        // Incremental error check (see Bresenhams algorithm).
        er = pd - (xym/2), ec;

    // Create a lookup table, rather than use multiplication in the for(;;) below.
    // look*[0] is if the line is horz, vert or diag.
    // look*[1] is if the line is in between angles (direction is not mod 45 == 0).
    int lookx[2] = {xm,xm + (qr * cy * dxA)},
        looky[2] = {ym,ym + (qr * cx * dyA)},
        lookd[2] = {qr * pd, qr * (pd - xym)};

    //draw_point(xx, yy);
    for(;;) {
        // Error check above/below the line.
        ec = er >= 0;
        // Increment lookup table based on error check.
        // ec==0 -> line is horz/vert/diagonal (dir%45 = 0).
        // ec==1 -> line is between cardinals (dir%45 != 0).
        x1 += lookx[ec];
        y1 += looky[ec];
        er += lookd[ec];
        // Break loop when line is done.
        //draw_point(xx, yy);
        if (x2 == x1 && y2 == y1) break;
    };
}

Version B:

void bresenprecalcB(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1, dy = y2 - y1,
        dxA = sgn(dx), dyA = sgn(dy),
        dxB = abs(dx), dyB = abs(dy),
        cx = dxB >= dyB, cy = dyB >= dxB;

    int lookm[10] = {0,dxB,0,dyB,0,dxA,0,dyA,dyB,dxB};
    int qx = lookm[cy],
        qy = lookm[2+cx],
        xm = lookm[4+cx],
        ym = lookm[6+cy],
        xym = lookm[8+cx],
        qr = qx != qy, pd = qx + qy,
        er = pd - (xym / 2), ec;

    int lookx[2] = {xm,xm + (qr * cy * dxA)},
        looky[2] = {ym,ym + (qr * cx * dyA)},
        lookd[2] = {qr * pd, qr * (pd - xym)};

    //draw_point(x1, y1);
    for(;;) {
        ec = er >= 0;
        x1 += lookx[ec];
        y1 += looky[ec];
        er += lookd[ec];
       //draw_point(x1, y1);
        if (x2 == x1 && y2 == y1) break;
    };
};

Bresenham's from this StackOverflow post:

void bresenhams(int x1, int y1, int x2, int y2) {
    int xx, yy, dx, dy, dx1, dy1, px, py, xe, ye, i;
    dx = x2 - x1;
    dy = y2 - y1;
    dx1 = abs(dx);
    dy1 = abs(dy);
    px = 2 * dy1 - dx1;
    py = 2 * dx1 - dy1;
    if (dy1 <= dx1)
    {
        if (dx >= 0)
        {
            xx = x1;
            yy = y1;
            xe = x2;
        }
        else
        {
            xx = x2;
            yy = y2;
            xe = x1;
        }
        //draw_point(xx, yy);
        for (i = 0; xx < xe; i++)
        {
            xx = xx + 1;
            if (px < 0)
            {
                px = px + 2 * dy1;
            }
            else
            {
                if ((dx < 0 && dy < 0) || (dx > 0 && dy > 0))
                {
                    yy = yy + 1;
                }
                else
                {
                    yy = yy - 1;
                }
                px = px + 2 * (dy1 - dx1);
            }
            //draw_point(xx, yy);
        }
    }
    else
    {
        if (dy >= 0)
        {
            xx = x1;
            yy = y1;
            ye = y2;
        }
        else
        {
            xx = x2;
            yy = y2;
            ye = y1;
        }
        //draw_point(xx, yy);
        for (i = 0; yy < ye; i++)
        {
            yy = yy + 1;
            if (py <= 0)
            {
                py = py + 2 * dx1;
            }
            else
            {
                if ((dx < 0 && dy < 0) || (dx > 0 && dy > 0))
                {
                    xx = xx + 1;
                }
                else
                {
                    xx = xx - 1;
                }
                py = py + 2 * (dx1 - dy1);
            }
            //draw_point(xx, yy);
        }
    }
};
\$\endgroup\$
3
\$\begingroup\$

Removing unncessary branches

Looking at the assembly generated by your code, you indeed managed to get rid of all branches save for the one needed by the loop itself. Nice! But maybe you removed too many? The main issue is the speed of the loop itself. Branches outside the loop do not impact performance much, and they can actually help performance! Consider for example that in the "non-compact" Bresenham implementation, they basically have two specialized loops, and choose which one to use depending on the slope. You could do that as well and perhaps reduce the amount of pre-calculation necessary in each case.

Another issue is the use of multiplications in lines such as these:

int lookx[2] = {xm, xm + (qr * cy * dxA)},
    looky[2] = {ym, ym + (qr * cx * dyA)},
    lookd[2] = {qr * pd, qr * (pd - xym)};

Here, qr, cx and cy are both booleans. By using a multiplication here, it seems that at least on some CPU architectures, GCC actually generates multiplication instructions, when it could have used fast instructions such as and and conditional moves. Rewriting the above to the following lines seems to get rid of the multiplication instructions:

int lookx[2] = {xm, xm + ((qr & cy) * dxA)},
    looky[2] = {ym, ym + ((qr & cx) dyA)},
    lookd[2] = {qr ? pd : 0, qr ? (pd - xym) : 0};

Clang seems to see that it can use conditional moves here without having to rewrite it, at least on x86_64. Of course, this is not so important unless you expect to draw many short lines, where the setup cost dominates.

Again, if you allow branches in the setup, you can have specialized init functions for the 8 distinct slope ranges which will be much simpler.

Branch predictors are awesome

Branches are bad on GPUs, but on CPUs a lot of effort has been spent optimizing the branch predictors. Conditions that are static during a loop are probably predicted with 100% accuracy and cost basically nothing. But even conditions that change often, like if (px < 0), might be predicted with a high degree of accuracy if they follow a pattern. And they do in the case of drawing lines using Bresenham's algorithm. It probably works better for some slopes than others though.

The above can very well explain why the "non-compact" version performs just as well. But it will probably also depend a lot on what CPU it is running on, what optimization level is used, and what kind of lines you are drawing (long/short, right angles/arbitrary angles).

Other possible optimizations

Assuming you keep the loop the same, you can thing about vectorizing it a little bit. You could group x1, y1 and ec together in a single 128-bit register, and also make a single __m128 lookup[2], so you can just do a single _mm_add_epi32() to add the three components of the lookup table to x1, y1 and ec in one go.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.