Fractional Bilinear Interpolation

Discuss emulation of the Nintendo Entertainment System and Famicom.

Moderator: Moderators

User avatar
James
Posts: 431
Joined: Sat Jan 22, 2005 8:51 am
Location: Chicago, IL
Contact:

Fractional Bilinear Interpolation

Post by James »

I've been playing around with some image scaling stuff tonight and came up with the following. I'm interested in your opinions.

In this post, tepples talks about doubling the image size with nearest-neighbor interpolation before performing any additional resizing with bilinear interpolation. The method I came up with is essentially an extension of this idea, except that it's done in one step and the amount of bilinear interpolation is adjustable (hence the 'fractional' in fractional bilinear filtering).

The implementation is pretty simple. Here's the shader code.

fbi.fx:

Code: Select all

/*
Copyright (c) 2013 James Slepicka

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

Texture2D tex;

SamplerState sam_linear
{
 Filter = MIN_MAG_MIP_LINEAR;
 AddressU = Clamp;
 AddressV = Clamp;
};

matrix world;
matrix view;
matrix proj;

float2 tex_size;
float2 input_size;
float2 output_size;
float sharpness = 1.0;

struct VS_INPUT
{
 float4 pos : POSITION;
 float2 tex : TEXCOORD0;
};

struct PS_INPUT
{
 float4 pos : SV_POSITION;
 float2 tex : TEXCOORD0;
};

PS_INPUT VS (VS_INPUT input)
{
 PS_INPUT output = (PS_INPUT)0;
 output.pos = mul (input.pos, world);
 output.pos = mul (output.pos, view);
 output.pos = mul (output.pos, proj);
 output.tex = input.tex;	
 return output;
}

float4 PS (PS_INPUT input) : SV_Target
{
 float2 scale = output_size / input_size;
 float2 interp = saturate((scale - lerp(scale, 1.0, sharpness))/(scale * 2.0));
 float2 p = input.tex.xy * tex_size + .5;
 float2 i = floor(p);
 float2 f = p - i;
 f = saturate((f - interp) / (1.0 - interp * 2.0));
 p = ((i + f) - .5) / tex_size;
 float4 r = tex.Sample(sam_linear, p);
 r.a = 1.0;
 return r;
}

technique10 render
{
 pass P0
 {
  SetVertexShader(CompileShader(vs_4_0, VS()));
  SetGeometryShader(NULL);
  SetPixelShader(CompileShader(ps_4_0, PS()));
 }
}
Some sample images to help illustrate the concept:

Nearest-neighbor:
Image

Bilinear interpolation:
Image

And somewhere in-between:
Image

If you'd like to play around with it, I put together a demo app. Use the up and down arrows (or page up/down) to adjust the amount of interpolation. DX10 (Win Vista+) is required and you may need to download some libraries from Microsoft if you get messages about missing dlls: MSVC++ redistributable and the DirectX runtime.
Last edited by James on Wed Jan 08, 2014 9:16 pm, edited 9 times in total.
get nemulator
http://nemulator.com
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Re: Fractional Bilinear Interpolation

Post by blargg »

In that post tepples describes I believe a practical way to achieve the following (and additionally how to achieve it with other filters like Scale2x, without rewriting any of the filter code).

Overlay the output display pixel grid over the NES pixel image. Wherever an output pixel covers part of only a single NES pixel, output that color. Where an output pixel covers more than one NES pixel, mix the colors in ratios equal to the relative areas of the overlap.

This results in sharp-edged blocky pixels with minimal inconsistencies in appearance, even when the NES image is being expanded into rectangular pixels on an output display only slightly larger than the original NES image, e.g. 256x240 to 584x480. Vertically there will be no mixing. Horizontally there will only be at most one pixel of intermediate mixed color between two pixels.

Examining more closely, consider the case of expanding a 4x1 image (in) into 10x1. The output pixels will consist of in[0], in[0], in[0]*0.5+in[1]*0.5, in[1], in[1], in[2], in[2], in[2]*0.5+in[3]*0.5, in[3], in[3]. If the output were 100 pixels wide, the output pixels would be each input pixel repeated 25 times, without any mixing. With linear rescaling there would be massive mixing of most pixels, making it a big blur.

Can your shader do the above? I notice that the 0.30 example showed vertical mixing. An easy way to test it is to do a large integer expansion on both axes and be sure there is no pixel mixing at all. Then do a non-integer expansion on only the X axis and ensure that there is no pixel mixing between horizontal edges (vertically), only horizontally, and that the mixing is no more than one pixel wide. [maybe yours passes this test and you're expanding a non-integer amount vertically in your example]

Thinking more about this, it gets at the core of the basic meaning of a pixel image. Is it a set of infinitely-small samples at the center of each grid rectangle, or is it a representation of the color across the entire grid rectangle? The former is the interpretation that leads to linear (or similar) interpolation, while the latter is what leads to the rescaling described here. In a way, this is what nearest-neighbor scaling is a poor approximation of.
User avatar
James
Posts: 431
Joined: Sat Jan 22, 2005 8:51 am
Location: Chicago, IL
Contact:

Re: Fractional Bilinear Interpolation

Post by James »

blargg wrote:Can your shader do the above?
Yes; at sufficiently high levels of interp_adjust (this is at .3), there is no mixing between edges on axes scaled by an integer ratio. On axes scaled by non-integer ratios, mixing is limited to one pixel.

Image
get nemulator
http://nemulator.com
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Re: Fractional Bilinear Interpolation

Post by blargg »

Nice. Apologies for one more request, but I lack Windows. What happens when you use interp_adjust of 0.3 with an X scaling of say 4.9? Still only one-pixel-wide mixing between pixels?
User avatar
James
Posts: 431
Joined: Sat Jan 22, 2005 8:51 am
Location: Chicago, IL
Contact:

Re: Fractional Bilinear Interpolation

Post by James »

blargg wrote:Nice. Apologies for one more request
No worries -- I'm happy to discuss and try out stuff.
blargg wrote:What happens when you use interp_adjust of 0.3 with an X scaling of say 4.9? Still only one-pixel-wide mixing between pixels?
interp_adjust needs to be increased with higher scaling factors. 8x scaling needs about .425, for example. It should be easy to programmatically determine the optimal value. I'll work on that.
get nemulator
http://nemulator.com
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Fractional Bilinear Interpolation

Post by tepples »

So interp_adjust appears to set the flat area of each texel in units of the width of 2 texels. In that case, the optimal value would be (scalefactor - 1) / (2 * scalefactor). This works fine as long as the horizontal and vertical scale factors are within 1 pixel/texel of each other, such as most uses on NES. But what happens in SNES pseudo-hires mode, where the horizontal and vertical scale operations need separate interp_adjust values due to the decidedly rectangular (4:7) pixel aspect ratio?

In any case, TVs themselves introduce blurring, and interp_adjust = 0.25 might produce a more accurate simulation of a PlayChoice, RGB SNES, or component Wii.
User avatar
James
Posts: 431
Joined: Sat Jan 22, 2005 8:51 am
Location: Chicago, IL
Contact:

Re: Fractional Bilinear Interpolation

Post by James »

tepples wrote:(scalefactor - 1) / (2 * scalefactor)
Yep -- this works well. Thanks.
tepples wrote:But what happens in SNES pseudo-hires mode, where the horizontal and vertical scale operations need separate interp_adjust values due to the decidedly rectangular (4:7) pixel aspect ratio?
If you need separate interp_adjust values, you can do this:

Code: Select all

 f.x = (f.x-interp_adjust_x)/(1.0-interp_adjust_x*2.0);
 f.x = saturate(f.x);
 
 f.y = (f.y-interp_adjust_y)/(1.0-interp_adjust_y*2.0);
 f.y = saturate(f.y);
get nemulator
http://nemulator.com
Grapeshot
Posts: 85
Joined: Thu Apr 14, 2011 9:27 pm
Contact:

Re: Fractional Bilinear Interpolation

Post by Grapeshot »

I knew I'd seen something like this mentioned somewhere before, and i guess ImageWorsener's documentation calls itpixel mixing.
User avatar
James
Posts: 431
Joined: Sat Jan 22, 2005 8:51 am
Location: Chicago, IL
Contact:

Re: Fractional Bilinear Interpolation

Post by James »

Yeah, I guess it is the same thing. So much for fame and fortune.

In any event, I've incorporated it into the latest release of my emulator.
tepples wrote:TVs themselves introduce blurring, and interp_adjust = 0.25 might produce a more accurate simulation
Can't really comment on accuracy, but just a bit of blurring looks better, I think. I've included a sharpness adjustment to allow for this.
get nemulator
http://nemulator.com
User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Re: Fractional Bilinear Interpolation

Post by blargg »

It's great that you added a blur adjustment, to go from no mixing at all, one-pixel-wide mixing, or full bilinear. And it's a shader, so less CPU load. As far as I can tell, it's still rare for an emulator to support this kind of rescaling, so you can preserve the aspect ratio and still get sharp pixels.
Near
Founder of higan project
Posts: 1553
Joined: Mon Mar 27, 2006 5:23 pm

Re: Fractional Bilinear Interpolation

Post by Near »

A trick I used to use a long time ago, prior to having pixel shaders ...

Blit the image to the screen using nearest-neighbor (eg GL_NEAREST), and then blit the image again using bilinear filtering (eg GL_LINEAR) with a source alpha. This alpha value is effectively a blur factor (0.0 = sharp, 0.5 = middle-of-the-road, 1.0 = blurry)

This works with any hardware accelerated API that supports alpha blending (Direct3D, OpenGL, etc) and does not require any pixel shaders.

Of course if you have shaders, there are much better techniques. Fes' pixellate shader is particularly impressive, for instance. It's effectively the absolute minimum blurring needed to make non-even-multiple scaling look perfect in pixellated form.
User avatar
James
Posts: 431
Joined: Sat Jan 22, 2005 8:51 am
Location: Chicago, IL
Contact:

Re: Fractional Bilinear Interpolation

Post by James »

byuu wrote: Fes' pixellate shader is particularly impressive, for instance. It's effectively the absolute minimum blurring needed to make non-even-multiple scaling look perfect in pixellated form.
Assuming that you're talking about the pixellate shader distributed with higan, this method produces identical output. edit: identical output in center mode, but mine looks better in scale and stretch modes.

Code: Select all

<?xml version="1.0" encoding="UTF-8"?>
<shader language="HLSL">
  <source><![CDATA[
    texture rubyTexture;
    float4 rubyInputSize;
    float4 rubyOutputSize;
    float4 rubyTextureSize;
    sampler s0 = sampler_state { texture = <rubyTexture>; };

    float4 PS (in float2 Tex : TEXCOORD0) : COLOR0
    {
     float2 scale = rubyOutputSize / rubyInputSize;
     float2 interp = (scale - 1.0) / (scale * 2.0);
     saturate(interp);

     float2 p = Tex.xy;
     p = p * rubyTextureSize + .5;
     float2 i = floor(p);
     float2 f = p - i;

     f = (f-interp) / (1.0-interp*2.0);
     f = saturate(f);

     p = i + f;
     p = (p - .5) / rubyTextureSize;
     float4 r = tex2D(s0, p);
     r.w = 1.0;
     return r;
    }

    Technique T0
    {
      pass p0 { PixelShader = compile ps_2_0 PS(); }
    }
  ]]></source>
</shader>
get nemulator
http://nemulator.com
Near
Founder of higan project
Posts: 1553
Joined: Mon Mar 27, 2006 5:23 pm

Re: Fractional Bilinear Interpolation

Post by Near »

I can't compare GLSL to HLSL to verify that claim, but it sounds very impressive!

Would you consider writing your shader in GLSL? None of my primary PCs support Direct3D, and even on my Windows build box, I've removed HLSL support in an effort to promote portability.

I've changed the uniform names and use GLSL 1.5 (no fixed functions), however. I can ask on my forum for a port and post if back here if that's okay with you, too.

EDIT: aliaspider ported it.

Code: Select all

#version 150

uniform sampler2D   source[];
uniform vec4      sourceSize[];
uniform vec4      targetSize;

in Vertex {
   vec2 texCoord;
};
out vec4 fragColor;

void main() {
   vec2 scale = targetSize.xy*sourceSize[0].zw;
   vec2 interp = (scale - vec2(1.0,1.0)) / (scale * 2.0);
   clamp(interp,0.0,1.0);
   vec2 p = texCoord.xy;
    p = p * sourceSize[0].xy + 0.5;
    vec2 i = floor(p);
    vec2 f = p - i;

    f = (f-interp) / (1.0-interp*2.0);
    f = clamp(f,0.0,1.0);

    p = i + f;
    p = (p - 0.5) * sourceSize[0].zw;
    vec4 r = texture(source[0], p);
    r.w = 1.0;
    fragColor=r;
}
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Fractional Bilinear Interpolation

Post by tepples »

Does OpenGL work on Windows RT and Xbox One? I was under the impression that these were supposed to be "legacy-free" platforms, and OpenGL was legacy. Perhaps someone is aiming for a publisher to use this to port old software to new consoles, just as Atlus, Jaleco, and Konami used PocketNES.
User avatar
James
Posts: 431
Joined: Sat Jan 22, 2005 8:51 am
Location: Chicago, IL
Contact:

Re: Fractional Bilinear Interpolation

Post by James »

byuu wrote: EDIT: aliaspider ported it.
There's something wrong with it; it looks blurry.
get nemulator
http://nemulator.com
Post Reply