Skip to main content
3 of 9
edited tags
Toby Speight
  • 81.7k
  • 14
  • 101
  • 308

The Wu line drawing algorithm for anti-aliased lines

I need to optimize the following function with low level optimizations (No SIMD, Multi threading). I already applied a lot of optimizations and got it ~65% faster, but it is possible to get it 200% faster. I am practicing on code optimization, some explanation would be welcome.

The function describes the anti-aliased Wu line drawing algorithm. It draws colored lines. it takes in account the sensitivity of the human eye which can't be changed. Approximations are completely fine.

void DrawWuLine( Surface *screen, int X0, int Y0, int X1, int Y1, Color& clrLine )
{
    /* Make sure the line runs top to bottom */
    constexpr float pixelNormalization = 1.f / 255.f;

    uint primaryColor, secondaryColor;

    if (Y0 > Y1)
    {
        std::swap(Y0, Y1);
        std::swap(X0, X1);
    }

    int XDir = 1;
    int DeltaX = X1 - X0;
    int DeltaY = Y1 - Y0;

    if (DeltaX < 0)
    {
        XDir = -1;
        DeltaX = 0 - DeltaX;
    }
    
    int ErrorAdj, ErrorAcc = 0;
    int Weighting;

    int grayl = ((clrLine.r * 19595) + (clrLine.g * 38469) + (clrLine.b * 7471)) >> 16;

    screen->Plot(X0, Y0, clrLine.RGBA);
    
    /* Is this an X-major or Y-major line? */
    if (DeltaY > DeltaX)
    {
        ErrorAdj = (DeltaX << 16) / DeltaY;

        while (--DeltaY) {

            if (((ErrorAcc + ErrorAdj) & 0xFFFF) <= ErrorAcc) {
                X0 += XDir;
            }
            Y0++; 

            ErrorAcc = (ErrorAcc + ErrorAdj) & 0xFFFF;
            Weighting = (ErrorAcc >> 8) & 0xFF;
            
            uint clrBackGround = screen->pixels[X0 + Y0 * SCRWIDTH];

            int rb = clrBackGround & 0xFF;
            int gb = (clrBackGround >> 8) & 0xFF;
            int bb = (clrBackGround >> 16) & 0xFF;
            
            int grayb = ((rb * 19595) + (gb * 38469) + (bb * 7471)) >> 16;
            
            int weightXOR = (~Weighting) & 0xFF;

            bool isLighter = grayl < grayb;

            float horizontalWeighting = (isLighter ? Weighting : weightXOR) * pixelNormalization;

            uint rr = horizontalWeighting * abs(rb - clrLine.r) + std::min(rb, (int) clrLine.r);
            uint gr = horizontalWeighting * abs(gb - clrLine.g) + std::min(gb, (int) clrLine.g);
            uint br = horizontalWeighting * abs(bb - clrLine.b) + std::min(bb, (int) clrLine.b);
            
            primaryColor = (br << 16) | (gr << 8) | rr;

            clrBackGround = screen->pixels[X0 + XDir + Y0 * SCRWIDTH];
            
            rb = clrBackGround & 0xFF;
            gb = (clrBackGround >> 8) & 0xFF;
            bb = (clrBackGround >> 16) & 0xFF;
            
            grayb = ((rb * 19595) + (gb * 38469) + (bb * 7471)) >> 16;

            isLighter = grayl < grayb;

            float verticalWeighting = (isLighter ? weightXOR : Weighting) * pixelNormalization;
            
            rr = verticalWeighting * abs(rb - clrLine.r) + std::min(rb, (int)clrLine.r);
            gr = verticalWeighting * abs(gb - clrLine.g) + std::min(rb, (int)clrLine.g);
            br = verticalWeighting * abs(bb - clrLine.b) + std::min(rb, (int)clrLine.b);

            secondaryColor = (br << 16) | (gr << 8) | rr;
            
            screen->Plot(X0, Y0, primaryColor);
            screen->Plot( X0 + XDir, Y0, secondaryColor);
        }
      
        screen->Plot( X1, Y1, clrLine.RGBA );

        return;
    }
    
    ErrorAdj = (DeltaY << 16) / DeltaX;

    while (--DeltaX) {
       
        if (((ErrorAcc + ErrorAdj) & 0xFFFF) <= ErrorAcc) {
            Y0++;
        }
        
        X0 += XDir; 

        ErrorAcc = (ErrorAcc + ErrorAdj) & 0xFFFF;
        Weighting = (ErrorAcc >> 8) & 0xFF;
        
        uint clrBackGround = screen->pixels[X0 + Y0 * SCRWIDTH];
        int rb = clrBackGround & 0xFF;
        int gb = (clrBackGround >> 8) & 0xFF;
        int bb = (clrBackGround >> 16) & 0xFF;
        
        int grayb = ((rb * 19595) + (gb * 38469) + (bb * 7471)) >> 16;

        int weightXOR = (~Weighting) & 0xFF;

        bool isLighter = grayl < grayb;

        float horizontalWeighting = (isLighter ? Weighting : weightXOR) * pixelNormalization;

        uint rr = horizontalWeighting * abs(rb - clrLine.r) + std::min(rb, (int)clrLine.r);
        uint gr = horizontalWeighting * abs(gb - clrLine.g) + std::min(gb, (int)clrLine.g);
        uint br = horizontalWeighting * abs(bb - clrLine.b) + std::min(bb, (int)clrLine.b);

        primaryColor = (br << 16) | (gr << 8) | rr;
        
        clrBackGround = screen->pixels[X0 + (Y0 + 1) * SCRWIDTH];
        
        rb = clrBackGround & 0xFF;
        gb = (clrBackGround >> 8) & 0xFF;
        bb = (clrBackGround >> 16) & 0xFF;

        grayb = ((rb * 19595) + (gb * 38469) + (bb * 7471)) >> 16;

        isLighter = grayl < grayb;

        float verticalWeighting = (isLighter ? weightXOR : Weighting) * pixelNormalization;

        rr = verticalWeighting * abs(rb - clrLine.r) + std::min(rb, (int)clrLine.r);
        gr = verticalWeighting * abs(gb - clrLine.g) + std::min(rb, (int)clrLine.g);
        br = verticalWeighting * abs(bb - clrLine.b) + std::min(rb, (int)clrLine.b);

        secondaryColor = (br << 16) | (gr << 8) | rr;

        screen->Plot(X0, Y0, primaryColor);
        screen->Plot( X0, Y0 + 1, secondaryColor );
    }
    
    screen->Plot( X1, Y1, clrLine.RGBA );
}

Any body tips or insights on how to get rid of branches inside of the while loops. Other optimizations are welcome.

user282937