xBR algorithm tutorial

[Hyllian]

This is an old topic I made in another forum. As Retroarch benefits from this filter, I decided to post here too. Sorry if some format are broken.

xBR Algorithm

Ok, here it is the algorithm. I’ve divided the explanation in modules. Some of them are obligatory (red) and others are optionals (green). You can implement the filter using only the obligatory modules and enhance it by implementing the optional modules later (though they may cost performance). So, let’s begin!

Introduction

This filter works by detecting edges and interpolating pixels along those edges. Edges are pixel regions in the image were pixels are very distinct (high color frequency) among them along some direction and very similar (low color frequency) perpendicular to that direction. I’ve divided it basically in two modules: Edge Detection Rule (EDR) and Interpolation Rules (IRs).

1) Edge Detection Rule (EDR)

Consider a pixel E and its neighbors like the configuration below:

The nomenclature is that way because I’m used to it and facilitate my memorization.

Before introducing the EDR, some symmetries must be shown. In the image below, it can be seen that the pixel E has a four-edge symmetry, so that any rules applied to an edge, must be applied to the others.

For that reason, from now on, all algorithm terms will be related to the down-right edge. You’ll have to apply the same rules to the other three edges by symmetry.

At last, the EDR! It took me some months thinking until I figured out this simple rule. Consider the first picture again:

I have to know if there’s an edge along pixels H and F. If yes, then pixel E must be interpolated. If no, then the predominant edge is along pixels E and I, so that E doesn’t need to be interpolated. So, how do I know that?

Consider the pictures below:

If the weighted distance (wd) among pixels in those red directions are smaller than those in blue, then I can assume there’s a predominant edge in the H-F direction. Here’s my EDR:

wd(red) = d(E,C) + d(E,G) + d(I,F4) + d(I,H5) + 4*d(H,F)

wd(blue)= d(H,D) + d(H,I5) + d(F,I4) + d(F,B) + 4*d(E,I)

EDR = (wd(red) < wd(blue))

EDR is a bool variable.

obs: The d function is presented in Annex 1.

2) Interpolation Rules (IRs)

Let’s expand the pixel E and see how the interpolation works.

2.1) Interpolation level 1

This interpolation is the most basic and only can address 45 degree diagonals. It must change the region below blue line in this picture:

That blue line extends from the middle of F side to the middle of H side.

Once EDR is true, that region below blue line must receive a new color. This new color can be F or H. There’s a rule to decide which color it’ll receive. This is the rule:

new color = (d(E,F) <= d(E,H)) ? F : H;

Depending on the scale factor, that region below blue line can encompass a number of pixels. Below you can see which pixels are affected for 2x, 3x and 4x scale factors, respectively:

Let me explain what happens to E when you use 2x scale factor. In the picture above (2x), pixel 3 is affected by 50% of its area. So, you have to blend F or H (depending on new color rule) with E in 50%. In pixel shader language, it’s the same as mix(new_color, E, 0.5). The same logic you can apply to other scale factor. Just do some geometry calculations, :P!

2.2) Interpolation level 2

This interpolation is easier said than done.

It only happens if interpolation level 1 can happen. It uses the same “new color” calculated for level 1. The difference is the region it changes. See the pictures below:

To do this interpolation, you have to test two rules:

do_LVL2_left_vertice = (F==G) ? true : false

do_LVL2_up_vertice  = (H==C) ? true : false

These two rules are independent. So that, if the left vertice rule is true and the other is false, you can do that LVL2 interpolation for the left vertice region. Also, if the two are true, you must interpolate the intersection of those two LVL2 regions!

You can see that if any of those LVL2 rules are true, the LVL1 rule is satisfied. Then, for implementation, you may test LVL2 rules before LVL1.

3) Font Enhancement

…

4) Advanced Topics

4.1) Using LVL2 Interpolation in regions plagued by shades of colors

…

4.2) Using linear equation of the Straight Line to interpolate in odd scale factors

…

Annex 1: The distance (d) function

d(A,B) calculates the distance of A and B by transforming these pixels in its YUV parts. I use the threshold used by HQx filters: 48Y + 7U + 6*V.

Here’s my slow C implementation of d(A,B):

float d(unsigned int A, unsigned int B)
{
    unsigned int r, g, b;
    unsigned int y, u, v;
   
    b = abs(((A & pg_blue_mask  )>>16) - ((B & pg_blue_mask  )>> 16));
    g = abs(((A & pg_green_mask)>>8  ) - ((B & pg_green_mask )>>  8));
    r = abs(( A & pg_red_mask        ) - ( B & pg_red_mask         ));
   
    y = abs(0.299*r + 0.587*g + 0.114*b);
    u = abs(-0.169*r - 0.331*g + 0.500*b);
    v = abs(0.500*r - 0.419*g - 0.081*b);

    return 48*y + 7*u + 6*v;
}

Annex 2: Pseudo-code implementing XBR LVL1

wd(red) = d(E,C) + d(E,G) + d(I,F4) + d(I,H5) + 4*d(H,F);
wd(blue)= d(H,D) + d(H,I5) + d(F,I4) + d(F,B) + 4*d(E,I);
EDR = (wd(red) < wd(blue));

if (EDR)
{
      new_color = (d(E,F) <= d(E,H)) ? F : H;

      do_INT_LVL1(new_color);
}


* Yes, it's that simple!

Annex 3: Pseudo-code implementing XBR LVL2

wd(red) = d(E,C) + d(E,G) + d(I,F4) + d(I,H5) + 4*d(H,F);
wd(blue)= d(H,D) + d(H,I5) + d(F,I4) + d(F,B) + 4*d(E,I);
EDR = (wd(red) < wd(blue));

if (EDR)
{
      new_color = (d(E,F) <= d(E,H)) ? F : H;

      if (F==G && H==C) {
           do INT_LVL2_left(new_color);
           do INT_LVL2_up(new_color);
      }
      else if (F==G) {
           do INT_LVL2_left(new_color);
      }
      else if (H==C) {
           do INT_LVL2_up(new_color);
      }
      else
           do_INT_LVL1(new_color);
}


* and repeat for the other three edges according to symmetry.
* the POC I released in the other thread implements this code in shader language.

• xBR means a filter that scales By Rules. ** Sorry if my english is so awkward. *** I’ll update this tutorial if more details are necessary.

[Hyllian]

I’ve already posted some of these in other thread.

They’re results obtained by combining xBR with Reverse Antialiasing and bicubic-normal or lanczos as second shader. In movement the result is even better and I think it is comparable to crt shaders.

Genesis:

Subterrania

Blades of Vengeance:

SNES:

Donkey Kong Country:

Mortal Kombat 3:

Super Mario RPG:

Donkey Kong Country 2:

Killer Instinct:

Mais de DKC:

Battletoads in Battlemaniacs:

Earthworm Jim:

Battletoads Double Dragon:

[Hyllian]

Version 3.8 of all xBR shaders released in the Repo:

https://github.com/libretro/common-shaders/tree/master/xBR

It adds anti-aliasing.

[Tanuki]

I’m probably missing something but they don’t seem to work as intended on my machine. The 3.7c variant works fine though.

Win7 x64, RetroArch 0.98.b2, AMD HD 6670

xBR 3.8c

xBR 3.7c

[Hyllian]

It’s probably some Cg incompatibility with your PC.

Maister made a cg2xml converter which can help you

He posted it in this topic: http://board.byuu.org/viewtopic.php?f=10&t=3429

[Tanuki]

Cheers! The conversion worked perfectly (447 lines, 0 errors).

The resulting shader works on my Intel HD/Linux laptop but alas, gives me a black screen on the HD 6670/Win7… Some CRT filters and CGP combinations have given me a hard time too. Damn you AMD!

It may be time to invest in an nVidia card…

Thanks again for your help and all the great Cg shaders !

[Hyllian]

Could you test if this version works?

http://pastebin.com/QtQiB3Ym

[Tanuki]

Thanks for looking into it.

Unfortunately, I get the same result I get with the first version.

[Hyllian]

Hi,

I’ve been working (on my vacations, LOL) on the hybrid version. I’ve got a new beta for anyone who wanna test.

It’s here in .cg: http://pastebin.com/x5KUhAs9 Just save it as xBR-hybrid-beta4.cg

For me, the two best configurations are these:

Config 1: Shader 1: xBR-hybrid-beta4.cg Shader 2: xBR-hybrid-beta4.cg Scale Factor: 2x hardware filter 1: point hardware filter 2: point

If the above config is too slow, try this:

Config 2: Shader 1: xBR-hybrid-beta4.cg Shader 2: ddt.cg Scale Factor: 3x hardware filter 1: point hardware filter 2: point

Here are some shots with config1 --> http://imgur.com/a/IhRMe

BTW: Tanuki! Maister has updated the cg2xml.py script. You should try the new version.

[Tanuki]

Hi there,

Thanks for the update!

I recently upgraded my PC from an AMD APU + HD6670 to an i5-2500k + 560GTX so things are very different now.

• all your xBR/xBR-hybrid Cg shaders (including the one you just posted) work flawlessly with the Direct3D driver (latest RetroArch compiled from source) but give me an appcrash in OpenGL (the culprit being nvidia’s nvogl64.dll).

• Joshua Street’s SABR Cg shader crashes with OpenGL and gives me a black screen with Direct3D. However, the XML version (from the xml-shader repo at gitorious) works as intended in OpenGL but shows all pixellated (as if the shader had no effect) in Direct3D.

I don’t know if this is the expected behavior… It’s all very puzzling to me!

If I convert your latest shader to XML with the newest cg2xml, I get a syntax error with OpenGL (see below) and a pixellated result in Direct3D.

RetroArch: Shader log: 0(52) : error C0000: syntax error, unexpected type identifier, expecting '{' at token "vec2"
0(53) : error C0000: syntax error, unexpected type identifier, expecting '{' at token "vec2"
0(54) : error C0000: syntax error, unexpected type identifier, expecting '{' at token "vec2"

Don’t know if this will be of much help!

EDIT: I really like the double pass with the new hybrid. Games like Pitfall look gorgeous!

[Chthon]

1. This shader is far and away the best I’ve ever seen. I wouldn’t say it’s “comparable to crt shaders”; I’d say it’s flat out superior.

2. I’m experiencing the same problem as Tanuki with hard crashes in nvogl64.dll when using OpenGL. (GTX480 here.) In fact, the vast majority of shaders cause the same crash. I’m suspecting it’s a bug in nvidia’s driver, but, I hold out some hope that maybe it can be fixed on retroarch’s side. (Btw, it works OK on my laptop (Intel HD4000) in OpenGL mode.)

Towards that end: A. Google found me a post on a different forum for a different program that claimed nvogl64.dll crashes could be fixed by changing “threaded optimization” in the nvidia control panel from “auto” to either “on” or “off.” “On” does not work. “Off” works insofar as stackhash crashes instead of nvogl64.dll. B. I don’t know enough about OpenGL to judge its value, but this post on the nvidia forums might be pertinent.

3. I wouldn’t mind OpenGL mode not working, but for the fact that Retroarch simply refuses to use .cgp metashaders in Direct3D mode. Judging from the log, it looks like it’s trying to parse .cgp as if it were .cg.

4. I would, really, really appreciate a continuation of the algorithm’s description from the first few posts, and a description of the reverse-AA algorithm. (Not sure why, but I find .cg virtually impossible to read and comprehend.)

5. Stupid question: What do you mean by “hardware filter 1: point”?

6. I don’t like feeding the results from xBR-hybrid-beta4.cg back into xBR-hybrid-beta4.cg. This breaks down into two major issues for me:

First, this a jarring difference between horizontal/vertical straight edges – which are perfectly crisp – and diagonal edges/curves – which are pretty blurred. As your eye follows a line, you suddenly encounter this abrupt change in the crispness of the edge and it’s really distracting. You can see this on the image below. Look at the text on the left side. The best possible solution would be to reduce that blur down to a discrete anti-aliased edge. That’s probably impossible. The second-best solution is to apply a very gentle blur to the horizontal/vertical edges so that everything matches better. Out of the shader I have on hand, applying lanczos16 as the second shader seems to introduce enough blur while having the least negative impact on sharpness.

Second, xBR-hybrid-beta4.cg -> xBR-hybrid-beta4.cg tends to create sharp edges in places where there ought to be a smooth color gradient. This tends to give it a “plastic-y” look a lot like the HQ shader. You can also see this in the picture below, especially on the “figurine” icon and the highlights on the character’s backs.

Image: top row: xBR-hybrid-beta4.cg -> xBR-hybrid-beta4.cg bottom row: xBR-hybrid-beta4.cg -> lanczos16 left column: enlarged 3x (no interpolation) right column: enlarged 1.5x (no interpolation)

(Apparently, the board will not let me post more than one link in a post, so the image is deferred to the next post. Sorry.)

[Chthon]

This is the image mentioned in my previous post: (right-click and “view image” to bypass the board’s scaling to fit)

[Hyllian]

1. This shader is far and away the best I’ve ever seen. I wouldn’t say it’s “comparable to crt shaders”; I’d say it’s flat out superior.

Thanks for the opinion.

2. I’m experiencing the same problem as Tanuki with hard crashes in nvogl64.dll when using OpenGL. (GTX480 here.) In fact, the vast majority of shaders cause the same crash. I’m suspecting it’s a bug in nvidia’s driver, but, I hold out some hope that maybe it can be fixed on retroarch’s side. (Btw, it works OK on my laptop (Intel HD4000) in OpenGL mode.)

Towards that end: A. Google found me a post on a different forum for a different program that claimed nvogl64.dll crashes could be fixed by changing “threaded optimization” in the nvidia control panel from “auto” to either “on” or “off.” “On” does not work. “Off” works insofar as stackhash crashes instead of nvogl64.dll. B. I don’t know enough about OpenGL to judge its value, but this post on the nvidia forums might be pertinent.

It seems a driver problem. Maister was investigating it and developed that cg2xml scritpt to help people with these problems. I don’t have the knowledge to address driver issues, I only make shaders and test it on PS3 (my main and only test platform).

3. I wouldn’t mind OpenGL mode not working, but for the fact that Retroarch simply refuses to use .cgp metashaders in Direct3D mode. Judging from the log, it looks like it’s trying to parse .cgp as if it were .cg.

It’s an issue I have even on PS3 (not exatly the same bug). But I can’t use .cgp files properly on PS3 by now. Squarepusher is already aware of this.

4. I would, really, really appreciate a continuation of the algorithm’s description from the first few posts, and a description of the reverse-AA algorithm. (Not sure why, but I find .cg virtually impossible to read and comprehend.)

The ReverseAA algorithm isn’t mine. It was developed by Christoph Feck, who posted in his blog: http://kdepepo.wordpress.com/2012/08/15/reverse-antialiasing-for-image-scaling/ I asked him about the theory behind it, but it seems he’s very busy.

About the xBR description, well, what I wrote are the base ideas behind it. From there to now, I’ve just improved implementations and combinations with other algorithms (like ReverseAa, for example). The core idea is the edge direction calculation.

5. Stupid question: What do you mean by “hardware filter 1: point”?

Retroarch provides hardware filtering (GPU builtin), like linear or point. Linear interpolation uses the bilinear algorithm. Point interpolation uses the nearest neighbor algorithm.

6. I don’t like feeding the results from xBR-hybrid-beta4.cg back into xBR-hybrid-beta4.cg. This breaks down into two major issues for me:

First, this a jarring difference between horizontal/vertical straight edges – which are perfectly crisp – and diagonal edges/curves – which are pretty blurred. As your eye follows a line, you suddenly encounter this abrupt change in the crispness of the edge and it’s really distracting. You can see this on the image below. Look at the text on the left side. The best possible solution would be to reduce that blur down to a discrete anti-aliased edge. That’s probably impossible. The second-best solution is to apply a very gentle blur to the horizontal/vertical edges so that everything matches better. Out of the shader I have on hand, applying lanczos16 as the second shader seems to introduce enough blur while having the least negative impact on sharpness.

Second, xBR-hybrid-beta4.cg -> xBR-hybrid-beta4.cg tends to create sharp edges in places where there ought to be a smooth color gradient. This tends to give it a “plastic-y” look a lot like the HQ shader. You can also see this in the picture below, especially on the “figurine” icon and the highlights on the character’s backs.

Image: top row: xBR-hybrid-beta4.cg -> xBR-hybrid-beta4.cg bottom row: xBR-hybrid-beta4.cg -> lanczos16 left column: enlarged 3x (no interpolation) right column: enlarged 1.5x (no interpolation)

(Apparently, the board will not let me post more than one link in a post, so the image is deferred to the next post. Sorry.)

It seems a question of taste. As I display my games in a Plasma TV and 2 meters away, I don’t see those changes distracting. Though I recognize if you’re playing with your PC monitor, it’s very easy to see those imperfections.

To solve this, you have many options to use as second shader. From the sharper to the blurrer you can use this:

1- ReverseAA.cg 2- double pass (use the same as the first xBR-Hybrid) 3- Lanczos16.cg 4- Bicubic-Sharper.cg 5- ddt.cg

The first shader acts over the Image Geometry and Depth. The second shader is more suitable to control Image Sharpness and Blurriness.

[Spinvis]

Hi Hyllian,

I have just tried your xBR-hybrid-beta4 shader. While it works perfectly in Direct3D compared to SABR (which doesn’t for me), i must say it is not as sharp as SABR and even shows some artifacts.

I am using your suggested setup with: Shader 1: xBR-hybrid-beta4.cg Shader 2: xBR-hybrid-beta4.cg

Comparing to SABR+AA and xBR-hybrid-beta4+AA and xBR-hybrid-beta4+xBR-hybrid-beta4. While i cannot see a difference between xBR-hybrid-beta4+AA and xBR-hybrid-beta4+xBR-hybrid-beta4 the difference compared to SABR is there.

Screenshots

If you look at Ifrits body for example and compare that (the guy sitting in the middle), he has a small white spot in his chin. But also the art decoration surrounding the text, here you can clearly see some artifacts with xBR while SABR doesn’t (tiny white spots where the blue line is supposed to be). I hope this will help you a bit on your way.

Anyway, other then that it seems to work great, so thanks a lot for another great shader and keep up the great work. I will be monitoring this thread to see what you come up with next.

Cheers,

Spin

[Hyllian]

If you look at Ifrits body for example and compare that (the guy sitting in the middle), he has a small white spot in his chin. But also the art decoration surrounding the text, here you can clearly see some artifacts with xBR while SABR doesn’t (tiny white spots where the blue line is supposed to be). I hope this will help you a bit on your way.

Anyway, other then that it seems to work great, so thanks a lot for another great shader and keep up the great work. I will be monitoring this thread to see what you come up with next.

Cheers,

Spin

Actually, xBR-hybrid and SABR aren’t comparable. They have distinct goals. You should compare it with xBR pure (3.8 versions).

The hybrid means it uses two algorithms to filter. It compares the results between ReverseAA and xBR and chooses what’s more suitable to give a depth feel to a 2D image.

Pure xBR and SABR are specialized in 2D flat images only, while ReverseAA was designed to highlight depth of a 2D image in perspective. The weak point of xBR is the strong point of ReverseAA and vice-versa. They complement each other. That’s why I’m developing this hybrid.

So, the transition between xBR and ReverseAA algorithms isn’t completely seamless yet. My task now is to minimize these small transitions.

For you to have an idea of 2d depth, play Donkey Kong Country or Killer Instinct with xBR 3.8 or SABR and then with xBR-hybrid. You’ll see more depth on textures.

[Maister]

3. I wouldn’t mind OpenGL mode not working, but for the fact that Retroarch simply refuses to use .cgp metashaders in Direct3D mode. Judging from the log, it looks like it’s trying to parse .cgp as if it were .cg.

Are you using 0.9.8? Pretty sure that bug was fixed quite some time ago.

[Spinvis]

[quote=“Hyllian”]

If you look at Ifrits body for example and compare that (the guy sitting in the middle), he has a small white spot in his chin. But also the art decoration surrounding the text, here you can clearly see some artifacts with xBR while SABR doesn’t (tiny white spots where the blue line is supposed to be). I hope this will help you a bit on your way.

Anyway, other then that it seems to work great, so thanks a lot for another great shader and keep up the great work. I will be monitoring this thread to see what you come up with next.

Cheers,

Spin

Actually, xBR-hybrid and SABR aren’t comparable. They have distinct goals. You should compare it with xBR pure (3.8 versions).

The hybrid means it uses two algorithms to filter. It compares the results between ReverseAA and xBR and chooses what’s more suitable to give a depth feel to a 2D image.

Pure xBR and SABR are specialized in 2D flat images only, while ReverseAA was designed to highlight depth of a 2D image in perspective. The weak point of xBR is the strong point of ReverseAA and vice-versa. They complement each other. That’s why I’m developing this hybrid.

So, the transition between xBR and ReverseAA algorithms isn’t completely seamless yet. My task now is to minimize these small transitions.

For you to have an idea of 2d depth, play Donkey Kong Country or Killer Instinct with xBR 3.8 or SABR and then with xBR-hybrid. You’ll see more depth on textures.[/quote]

I see, didn’t know that, very interesting, i would love to see some more depth in 2d games, and only the more reason for me to keep watch on this. A question, you said, and i quote:

Retroarch provides hardware filtering (GPU builtin), like linear or point. Linear interpolation uses the bilinear algorithm. Point interpolation uses the nearest neighbor algorithm.

Where exactly is that option enabled in RetroArch?

[Hyllian]

Where exactly is that option enabled in RetroArch?

Speaking only for the PS3 version, those options are available in the video options (the same screen where you choose shaders). For PC or other systems, I don’t know. Ask maister or Squarepusher.

[hunterk]

On PC/Mac/Linux, under Settings > Video, you can check/uncheck a box to enable/disable bilinear filtering. Bilinear is enabled by default, but if it is disabled, RetroArch will use point filtering instead.

There is a second bilinear box for the 2-pass/FBO option in the shader settings. It functions the same but applies only to the second shader.

Individual shaders can also override those settings if they are designed to work with one or the other.

[Hyllian]

First version of xBR-Hybrid plus CRT is done. It’s in beta stage yet.

If you wanna test, 4xBR-Hybrid+CRT.cg -> https://anonfiles.com/file/325895016131af9e5b087c88d29b3d4e

It only works fullspeed on PS3 at 4x scaling.

The best config for me is:

Shader 1: 4xBR-Hybrid+CRT.cg Shader 2: stock.cg Scale Factor: 4x hardware filter 1: point hardware filter 2: point