Notice removed Content dispute by CommunityBot

occurred May 19 at 13:40

Post Unlocked by CommunityBot

occurred May 19 at 13:40

Removed from Network Questions by Mast♦

occurred May 12 at 13:40

Post Locked by Mast♦

occurred May 12 at 13:38

Notice added Content dispute by Mast♦

occurred May 12 at 13:38

Rollback to Revision 5

Source Link

edited May 12 at 13:30

pacmaninbw ♦

24.8k
11
46
109

Line The Wu line drawing algorithm for anti-aliased lines optimization

I need to optimize the following function with low-level optimizations (No SIMD, Multithreading). I already applied a lot of optimizations and got it ~35%~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. After profiling this part was the slowest piece of my code. I really want to get rid ofIt takes into account the branch insidesensitivity of the functionhuman eye which can't be changed. Approximations are completely fine.

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

 rl ? ( uint primaryColor, secondaryColor;

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

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

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

    int grayl = ((clrLine.r grayl<grayb?Weighting:* 19595) + (WeightingclrLine.g ^* 25538469) + (clrLine.b * 7471)) >> 16;

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

        while (--DeltaY) {

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

            ErrorAcc = (ErrorAcc + ErrorAdj) & 0xFFFF;
            Weighting = (ErrorAcc BYTE>> 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 double* 38469) + (bb grayl<grayb* 7471)) >> 16;
            
            int weightXOR = (~Weighting) & 0xFF;

            bool isLighter = grayl < grayb;

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

            uint rr = horizontalWeighting * abs(Weightingrb ^- 255clrLine.r) + std::min(rb, (int) clrLine.r);
 / 255.0          uint gr = horizontalWeighting * abs( rlgb - rb clrLine.g) + rbstd::min(gb, (int) clrLine.g);
            uint br = horizontalWeighting * abs(bb - clrLine.b) + std::min(bb, (int) clrLine.b);
    BYTE gr       
            primaryColor = (br gb<< >16) gl| ?(gr << 8) | rr;

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

            isLighter = grayl < grayb;

            float verticalWeighting = (isLighter grayl<grayb?Weighting weightXOR :( Weighting) ^* 255))pixelNormalization;
            
            rr = verticalWeighting * abs(rb - clrLine.r) /+ 255std::min(rb, (int)clrLine.0r);
            gr = verticalWeighting * abs( gb - gl clrLine.g) + glstd::min(rb, (int)clrLine.g);
            br = verticalWeighting * abs(bb - clrLine.b) + std::min(rb, (int)clrLine.b);

            secondaryColor = (br BYTE<< 16)( (| (gr double<< 8) | rr;
            
            screen->Plot(X0, grayl<grayb?Weighting:Y0, primaryColor);
            screen->Plot(Weighting ^X0 255+ XDir, Y0, secondaryColor);
        }
      
        screen->Plot( X1, Y1, clrLine.RGBA );

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

 * ( gl while (--DeltaX) gb{
 )      
        if (((ErrorAcc + gbErrorAdj) & 0xFFFF) <= ErrorAcc) {
            Y0++;
        }
        
        X0 += XDir; 

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

        int weightXOR = (~Weighting) grayl<grayb& 0xFF;

        bool isLighter = grayl < grayb;

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

        uint rr = horizontalWeighting * abs(Weightingrb ^- 255clrLine.r) + std::min(rb, (int)clrLine.r);
        uint gr = horizontalWeighting * abs(gb - clrLine.g) /+ 255std::min(gb, (int)clrLine.0g);
        uint br = horizontalWeighting * abs( bb - bl clrLine.b) + blstd::min(bb, (int)clrLine.b);

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

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

        isLighter = grayl < grayb;

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

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

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

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

Line drawing algorithm for anti-aliased lines optimization

I need to optimize the following function (No SIMD, Multithreading). I already applied a lot of optimizations and got it ~35% faster, but it is possible to get it 200% faster.

The function describes the anti-aliased Wu line drawing algorithm. It draws colored lines. After profiling this part was the slowest piece of my code. I really want to get rid of the branch inside of the function

void DrawWuLine( Surface *screen, int X0, int Y0, int X1, int Y1, Color& clrLine )
{
    BYTE rr = ( rb > rl ? ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( rb - rl ) + rl ) ) : ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( rl - rb ) + rb ) ) );
    BYTE gr = ( gb > gl ? ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( gb - gl ) + gl ) ) : ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( gl - gb ) + gb ) ) );
    BYTE br = ( bb > bl ? ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( bb - bl ) + bl ) ) : ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( bl - bb ) + bb ) ) );
}

The Wu line drawing algorithm for anti-aliased lines optimization

I need to optimize the following function with low-level optimizations (No SIMD, Multithreading). 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 into 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 );
}

Highlighted the code that is slow after profiling

Source Link

edited May 12 at 9:46

user282937

The Wu line Line drawing algorithm for anti-aliased lines optimization

I need to optimize the following function with low-level optimizations (No SIMD, Multithreading). I already applied a lot of optimizations and got it ~65%~35% 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 into accountAfter profiling this part was the sensitivityslowest piece of the human eye which can't be changed. Approximations are completely finemy code. I really want to get rid of the branch inside of the function

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

    uint primaryColor, secondaryColor;

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

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

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

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

    screen->Plot(X0, Y0, clrLine.RGBA);
    
    /* Is this an X-major or Y-major linegrayl<grayb? */
    if Weighting:(DeltaYWeighting >^ DeltaX255)
    {
        ErrorAdj = (DeltaX << 16) / DeltaY;

        while (--DeltaY) {

          / 255.0 if* (((ErrorAcc + ErrorAdj) &rb 0xFFFF)- <=rl ErrorAcc) {
                X0 += XDir;
            }
            Y0++; 

            ErrorAcc = (ErrorAcc + ErrorAdj) & 0xFFFF;
            Weighting = (ErrorAcc >>rl 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 *BYTE 19595) + (gb * 38469) + (bb * 7471)) >> 16;
            
            int weightXOR = (~Weighting) & 0xFF;

            bool isLighter = grayl < grayb;

            float horizontalWeighting =double )(isLighter grayl<grayb? Weighting : weightXOR) * pixelNormalization;

            uint rr = horizontalWeighting * abs(rbWeighting -^ clrLine.r255) + std::min(rb, (int) clrLine.r);
            uint gr =/ horizontalWeighting255.0 * abs(gb - clrLine.g) +rl std::min(gb,- (int)rb clrLine.g);
            uint br = horizontalWeighting * abs(bb+ -rb clrLine.b) + std::min(bb, (int) clrLine.b);
            
            primaryColor = (br << 16) |BYTE (gr << 8) | rr;

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

            isLighter = grayl < grayb;

            float verticalWeighting = (isLighter grayl<grayb? weightXOR : Weighting) * pixelNormalization;
            
            rr = verticalWeighting * abs(rb - clrLine.r) + std::min(rb,Weighting (int^ 255)clrLine.r);
            gr) =/ verticalWeighting255.0 * abs( gb - clrLine.ggl ) + std::min(rb,gl (int)clrLine.g);
            br = verticalWeighting * abs(bb - clrLine.b) + std::min(rb, (int)clrLine.b);

            secondaryColor = (br <<BYTE 16) | (gr << 8) | rr;
            
            screen->Plot(X0, Y0, primaryColor);
            screen->Plot( X0 + XDir, Y0,double secondaryColor);
        }
      
        screen->Plot( X1, Y1,grayl<grayb?Weighting:(Weighting clrLine.RGBA^ 255);

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

   255.0 while* (--DeltaX) {
       
      gl - ifgb (((ErrorAcc) + ErrorAdj) &gb 0xFFFF) <= ErrorAcc) {
            Y0++;
        }
        
        X0 += XDir; 

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

        int weightXOR = (~Weighting) & 0xFF;

        bool isLighter = grayl < grayb;

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

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

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

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

        isLighter = grayl < grayb;

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

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

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

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

The Wu line drawing algorithm for anti-aliased lines optimization

I need to optimize the following function with low-level optimizations (No SIMD, Multithreading). 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 into 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 );
}

Line drawing algorithm for anti-aliased lines optimization

I need to optimize the following function (No SIMD, Multithreading). I already applied a lot of optimizations and got it ~35% faster, but it is possible to get it 200% faster.

The function describes the anti-aliased Wu line drawing algorithm. It draws colored lines. After profiling this part was the slowest piece of my code. I really want to get rid of the branch inside of the function

void DrawWuLine( Surface *screen, int X0, int Y0, int X1, int Y1, Color& clrLine )
{
    BYTE rr = ( rb > rl ? ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( rb - rl ) + rl ) ) : ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( rl - rb ) + rb ) ) );
    BYTE gr = ( gb > gl ? ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( gb - gl ) + gl ) ) : ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( gl - gb ) + gb ) ) );
    BYTE br = ( bb > bl ? ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( bb - bl ) + bl ) ) : ( ( BYTE )( ( ( double )( grayl<grayb?Weighting:(Weighting ^ 255)) ) / 255.0 * ( bl - bb ) + bb ) ) );
}

Rollback to Revision 5

Source Link

edited May 12 at 1:12

Peilonrayz ♦

43.5k
7
76
155

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 );
}

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;
}

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 );
}