Cheap Upscaling Triangulation (CUT) is a family of single-image upscaling algorithms for retro and modern games designed to be:

• Versatile: can upscale from and to any image resolution and are applicable to all the 2D and 3D consoles that Lemuroid supports
• Efficient: keep the number of samples and calculations as low as possible to minimize battery consumption

In order to achieve this, we need to CUT some corners... Literally!

The family is composed of three algorithms CUT1, CUT2 and CUT3, which share the same basic steps:

• Triangulation: Inspired by the method in [1], we analyze the luma plane of each 2x2 square to identify if the square has a vertical, horizontal, or diagonal orientation. In this last case we split the square into two triangles.
• Pattern Recognition: We examine neighboring samples and the results of the triangulation to create an interpolation function for each side of the square.
• Interpolation: We use the triangulation and the function on each side to interpolate colors within the square or triangles.

The three algorithms have different levels of quality and features:

• Passes: Number of passes required to render the final image. Except the last one, every step outputs a buffer with the same resolution as the input image.
• Samples: Number of texture samples read from the original image.
• Angle Resolution: The minimal angle the algorithm is able to correctly represent. Using an approach similar to [2] CUT3 is able to follow those edges.
• Soft Edges: CUT2 and CUT3 are also able to improve the definition of edges which are wider than one pixel. This greatly helps with anti-aliased content.

• I: Input image resolution
• O: Output image resolution
• D: Edge search distance in each direction (this is tied to angle resolution)

Check a simple webapp that applies the filters to some game screenshots:

https://swordfish90.github.io/cheap-upscaling-triangulation/

The look of every variant can be customized with a set of parameters:

// Available in CUT1, CUT2 and CUT3
#define USE_DYNAMIC_BLEND 1                 // Dynamically blend color with respect to contrast
#define BLEND_MIN_CONTRAST_EDGE 0.0         // Minimum contrast level at which sharpness starts increasing [0, 1]
#define BLEND_MAX_CONTRAST_EDGE 1.0         // Maximum contrast level at which sharpness stops increasing [0, 1]
#define BLEND_MIN_SHARPNESS 0.0             // Minimum sharpness level [0, 1]
#define BLEND_MAX_SHARPNESS 1.0             // Maximum sharpness level [0, 1]
#define STATIC_BLEND_SHARPNESS 0.5          // Sharpness level used when dynamic blending is disabled [0, 1]
#define EDGE_USE_FAST_LUMA 0                // Use quick luma approximation in edge detection
#define EDGE_MIN_VALUE 0.05                 // Minimum luma difference used in edge detection [0, 1]
#define LUMA_ADJUST_GAMMA 0                 // Correct gamma to better approximate luma human perception

// Available in CUT2 and CUT3
#define SOFT_EDGES_SHARPENING 1             // Enable soft-edges sharpening
#define SOFT_EDGES_SHARPENING_AMOUNT 0.75   // Maximum size reduction of soft-edges pixels (antialiased pixels) [0, 1]

// Available in CUT3
#define MAX_SEARCH_DISTANCE 8               // Maximum search distance in each direction (N,E,S,W) to find a continuous edge [1, ∞[ 

There aren't yet extensive performance tests, but I tried measuring GPU load on my device, a Galaxy S21 FE with Snapdragon 888 playing Final Fantasy VI Advance.

• [1] D. Su and P. Willis, "Image interpolation by pixel level data-dependent triangulation", Computer Graphics Forum, pp. 23, 2004.
• [2] A. Reshetov, "Morphological antialiasing", Proceedings of the Conference on High Performance Graphics 2009, pp. 109-116, 2009.