Jump to content
  • Advertisement
dst

2D Old school fill algorithm (looking for optimization tricks)

Recommended Posts

Advertisement
Posted (edited)
On 3/10/2019 at 10:31 PM, dst said:

I'm reviving some of my graphics programming abilities by playing around with some old HW of mine and trying to do graphics programming without any external libraries.

Since you are doing low-level optimization, it would help to mention what architecture you are targeting. I assume, it is x86/x64.

Precisely describing the task might also help. I'm assuming it is solid fill of memory surface with 32-bit color (as opposed to, say, sprite blit, or 8-bit fill).

I also assume that your claim is correct, and this spot is indeed a bottleneck (which might happen, if you are drawing a lot of tiny rectangles).

Then, I suppose, this might help:

void fill(int x0, int y0, int x1, int y1, int color) {
    int MX=(x0-x1)>>31; // Only works if subtraction does not overflow int.
    int MY=(y0-y1)>>31; // Only works if subtraction does not overflow int.
    int XL=x1^((x0^x1)&MX);
    int XH=x0^((x0^x1)&MX);
    int YL=y1^((y0^y1)&MY);
    int YH=y0^((y0^y1)&MY);
    if((XH|YH|(1023-XL)|(767-YL))<0) return; // Only works if subtraction does not overflow int.
    // Rest of code... 
}

Additionaly, almost obligatory link to the collection of bithacks:

https://graphics.stanford.edu/~seander/bithacks.html

Edited by FordPerfect

Share this post


Link to post
Share on other sites
Posted (edited)

Sorry, there was also clipping part, which my post missed.

Here goes:

void fill(int x0, int y0, int x1, int y1, int color) {
    int MX=(x0-x1)>>31; // Only works if subtraction does not overflow int.
    int MY=(y0-y1)>>31; // Only works if subtraction does not overflow int.
    int XL=x1^((x0^x1)&MX);
    int XH=x0^((x0^x1)&MX);
    int YL=y1^((y0^y1)&MY);
    int YH=y0^((y0^y1)&MY);
    if((XH|YH|(1023-XL)|(767-YL))<0) return; // Only works if subtraction does not overflow int.
    XL=XL&~(XL>>31);
    YL=YL&~(YL>>31);
    XH=1023+((XH-1023)&((XH-1023)>>31)));
    YH= 767+((YH- 767)&((YH- 767)>>31)));
    // Rest of code... 
}

 

Edited by FordPerfect

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!