Алгоритм целочисленного масштабирования

Авторский алгоритм цело­численного масштаби­рования (integer scaling). Алгоритм — последовательность действий для достижения нужного результата. Если вас интересует готовая реализация, см. библиотеку IntegerScaling (C++/Rust/JS/PHP). Алгоритм используется, например, в SNES-эмуляторе bsnes-mt и DOSBox-шейдере pixel_perfect от tyrells.

Кратко

Без коррекции соотношения сторон (квадратные пикселы)

Делим ширину и высоту экрана на ширину и высоту изобра­жения соответ­ственно. Отбрасываем дробные части. Меньший из результатов — искомый цело­численный масштаб.

В виде математической формулы это можно представить так:

R = min(⌊(SW/W)⌋, ⌊(SH/H)⌋)

где R, SW, SH, W, H — цело­численный масштаб, ширина экрана, высота экрана, ширина изображения и высота изображения соответственно.

С коррекцией соотношения сторон (прямоугольные пикселы)

  1. Делим ширину и высоту экрана на ширину и высоту изобра­жения соответ­ственно. Отбрасываем дробные части. Это макси­мальные цело­численные масштабы по горизонтали и вертикали соответственно.
  2. Умножаем их на ширину и высоту изобра­жения соответ­ственно, получаем размеры области, куда будет вписано отмасшта­бированное изображение.
  3. Если соотношение сторон области равно целевому, искомые цело­численные масштабы равны макси­мальным.
  4. В зависимости от того, меньше или больше соотношение сторон области по сравнению с целевым, принимаем искомый цело­численный масштаб по горизонтали или вертикали равным макси­мальному по этой оси.
  5. Масштаб по второй оси прибли­зительно вычисляем исходя из масштаба по первой оси и целевого соотношения сторон. Результат округляем вверх или вниз исходя из мини­мизации погрешности соотношения сторон.

Подробно

  1. Делим ширину SW и высоту SH экрана в физических пикселах соответ­ственно на ширину W и высоту H подлежащего масштаби­рованию изображения. Отбрасываем дробные части у полученных соотношений, получаем макси­мальные цело­численные коэффициенты MRX по горизонтали и MRY по вертикали соответственно.
  2. Если коррекция соотношения сторон изобра­жения не требуется (пикселы квадратные, масштабные коэффициенты по горизонтали и вертикали одинаковы):

    1. Цело­численный масштабный коэффициент R равен меньшему из соотношений MRX и MRY.
    2. Отображаем каждый пиксел исходного изобра­жения как квадратную группу из R×R физических пикселов одинакового цвета, равного цвету пиксела исходного изображения.
    3. Вычисляем ширину UW и высоту UH отмасшта­бированного изобра­жения умножением соответ­ственно ширины W и высоты H исходного изобра­жения на масштабный коэффициент R.
  3. Если коррекция соотношения сторон изобра­жения требуется (пикселы потен­циально прямо­угольные, масштабные коэффи­циенты по горизонтали и вертикали потен­циально разные):

    1. Умножаем ширину W и высоту H изобра­жения на MRX и MRY соответ­ственно, получаем ширину MW и высоту MH области, в которую будет вписано отмасшта­бированное изображение.
    2. Делим ширину MW этой области на её высоту MH, получаем соотношение сторон MA этой области.
    3. Если соотношение MA равно целевому соотношению сторон TA:

      1. Масштабные коэффициенты RX по горизонтали и RY по вертикали принимаем равными MRX и MRY соответственно.
      2. Переходим к центри­рованию отмасшта­бированного изобра­жения (шаг 4.1).
    4. Если соотношение MA меньше целевого соотношения сторон TA:

      1. Масштабный коэффициент RX по горизонтали принимаем равным MRX.
      2. Делим макси­мальную ширину MW на целевое соотношение сторон TA, получаем приблизительную отмасшта­бированную высоту AUH.
    5. Если соотношение MA больше целевого соотношения сторон TA:

      1. Масштабный коэффициент RY по вертикали принимаем равным MRY.
      2. Умножаем макси­мальную высоту MH на целевое соотношение сторон TA, получаем приблизительную отмасшта­бированную ширину AUW.
    6. Приблизительный отмасшта­бированный размер AUW или AUH делим на исходный размер изобра­жения W или H по этой оси. Округляем результат в направлении, при котором погрешность соотношения сторон мини­мальна. Если погрешности в обоих направлениях одинаковы или близки, округляем результат в направлении, при котором соотношение сторон ближе к исходному (масштабы по разным осям ближе друг к другу, пиксел по форме ближе к квадрату). Полученное целое число — масштабный коэффициент по этой оси — RX (по горизонтали) или RY (по вертикали).
    7. Вычисляем ширину UW и высоту UH отмасшта­бированного изобра­жения умножением ширины W и высоты H исходного изобра­жения на масштабные коэффициенты RX по горизонтали и RY по вертикали соответственно.
  4. Выравниваем отмасшта­бированное изобра­жение по центру экрана:

    1. Из ширины SW и высоты SH экрана вычитаем соответ­ственно ширину UW и высоту UH отмасшта­бированного изобра­жения, результаты делим на 2, отрасываем дробную часть, полученные числа обозначаем X и Y соответственно.
    2. Отмасшта­бированное изобра­жение выводим на расстоянии X по горизонтали и Y по вертикали от верхнего-левого угла экрана.
  5. Оставшееся экранное прост­ранство вокруг отмасшта­бированного изобра­жения заполняем чёрным цветом.

Образец реализации

Авторская библиотека IntegerScaling пред­ставляет собой образец реализации алгоритма на нескольких языках програм­мирования: C++, Rust, JavaScript, PHP. Библиотека используется, например, в SNES-эмуляторе bsnes-mt.

Пример без коррекции соотношения сторон

Требуется вывести изобра­жение 640×480 (VGA) на экране 1920×1080 (Full HD):

1920 / 640 = 3
1080 / 480 = 2,25

Отбрасываем дробную часть 0,25, получаем 2. 2 меньше, чем 3. Значит, выводим каждый пиксел исходного изобра­жения как группу 2×2 физических пиксела.

Ширина и высота отмасшта­бированного изобра­жения — 1280 (640 × 2) и 960 (480 × 2) соответ­ственно. Значит, для центри­рования на экране выводим отмасшта­бированное изобра­жение на расстоянии 320 ((1920 − 1280) / 2) пикселов по горизонтали и 60 ((1080 − 960) / 2) пикселов по вертикали от верхнего-левого угла экрана.

Пример с коррекцией соотношения сторон

Требуется вывести изобра­жение 400×254 с целевым соотношением сторон 4:3 на экране 3840×2160 (4K):

3840 / 400 = 9,6
2160 / 254 ≈ 8,5

Отбрасываем дробные части полученных соотношений, получаем макси­мальные цело­численные коэффициенты 9 по горизонтали и 8 по вертикали соответ­ственно.

Умножаем ширину 400 и высоту 254 изобра­жения на 9 и 8 соответ­ственно, получаем ширину 3600 и высоту 2032 области, в которую будет вписано отмасшта­бированное изобра­жение.

Соотношение сторон области 1,77 больше целевого соотношения сторон 4:3 (≈ 1,333). Поэтому:

  • масштабный коэффициент по вертикали принимаем равным 8;
  • умножаем макси­мальную высоту 2032 на целевое соотношение сторон 4:3 (≈ 1,333), получаем приблизительную отмасшта­бированную ширину 2709,333.

Делим 2709,333 на исходную ширину 400 изобра­жения, получаем 6,773, округляем, получаем масштабный коэффициент 7 по горизонтали. Таким образом, размер пиксела — 7×8.

Ширина и высота отмасшта­бированного изобра­жения — 2800 (400 × 7) и 2032 (254 × 8) соответ­ственно. Фактическое соотношение сторон — около 1,378 (2800 / 2032), погрешность относительно целевого соотношения 4:3 (≈ 1,333) — около 3,35%.

Для центри­рования на экране выводим отмасшта­бированное изобра­жение на расстоянии 520 ((3840 − 2800) / 2) пикселов по горизонтали и 64 ((2160 − 2032) / 2) пиксела по вертикали от верхнего-левого угла экрана.

Эталонная отрисовка

Изобра­жения ниже показывают, как должны выглядеть результаты цело­численного масштаби­рования без коррекции соотношения сторон. При правильной реализации цело­численного масштаби­рования результаты масштаби­рования приведённых исходных изобра­жений должны быть идентичны приведённым образцам отмасшта­бированных изобра­жений.

Во избежание влияния искажений, вносимых веб-браузером, рекомендуется сохранить изобра­жения на компьютер и просматривать их сторонней само­стоя­тельной программой в масштабе 100%. Вы также можете скачать все изобра­жения в виде единого архива (55 КБ).

Изображения Масштаб Чёрный фон Примечание
Исходное В масштабе Полный Целоч. Слева +
справа
Сверху +
снизу
320×240
qVGA, 4:3
3840×2160
4K UHD, 16:9
9
900%
480+480 0 Изобра­жение на всю высоту, чёрный фон только слева/справа
640×480
VGA, 4:3
1920×1080
Full HD, 16:9
2,25
225%
2
200%
320+320 60+60
1280×720
HD, 16:9
1920×1080
Full HD, 16:9
1,5
150%
1
100%
320+320 180+180 Идентично режиму центри­рования
1280×720
HD, 16:9
2560×1600
WQXGA, 16:10
2
200%
0 80+80 Изобра­жение на всю ширину, чёрный фон только сверху/снизу
1920×1080
Full HD, 16:9
3840×2160
4K UHD, 16:9
2
200%
0 0 Разрешения кратны, поэтому чёрного фона нет

См. также статью о цело­численном масштабировании.