こんにちは．だいみょーじんです．
この記事は，自作OS Advent Calendar 24日の記事です．
また，第28回 自作OSもくもく会オンラインで発表した「アルファ値を含む重ね合わせ処理」の内容をそのまま記事にしたものです．
対象読者：OS自作をやっていたり，興味がある人．
背景
OSには周辺機器とのやり取り，各アプリケーションへのメモリやCPU実行時間の分配，UIなど様々な要素があります．
その中でも，GUIの実装はOSの見た目を決定し，自分で作ったものが一番わかりやすく目に見える部分です．
よくあるGUIの実装として，画面を複数のシートの重ね合わせとして表示するというものがあります．
最下層には壁紙があり，その上に何枚かウィンドウが配置され，最上層にマウスカーソルがあります．
これらの壁紙，ウィンドウ，マウスカーソルはシートという画像で表現され，OSはこれらのシートを重ね合わせて一枚の画像にし，それを画面に表示します．
今回はここからさらに一歩進んで，半透明のウィンドウを表示できるようにします．
方法
RGB色空間
まず前提知識として，定量的な色の表現方法であるRGB色空間について知っておく必要があります．
RGBは光の三原色であるRed，Green，Blueの略で，これら3種類の色の明るさを調整することで，画面は様々な色を出すことができます．
一般的な画面はR,G,Bそれぞれの明るさが0から255までの256段階に調整可能で，合計256×256×256=16777216種類の色を出すことができます．
Rの明るさをr，Gの明るさをg，Bの明るさをbとし，これら3つの値をまとめた色ベクトル(r, g, b)として色を表しています．
半透明とはどういうことか
さて，ここから本題に入ります．
どうすれば半透明のウィンドウを表示できるでしょうか？
まず，「半透明」ってどういうことでしょうか？
身の回りにある半透明のものを思い浮かべてみましょう．
半透明のビニール袋とか．
半透明の物体を見ると，物体自体も見えていながら，その物体の向こう側が透けて見えると思います．
つまり，物体自体の色と，物体の向こう側からやってくる光が混ぜ合わされているということです．
アルファブレンド
ここで登場するのが，「アルファブレンド」と呼ばれる簡単な画像合成です．
シートに不透明度を意味する「アルファ値」を設定し，アルファ値にしたがってシートの下側からやってくる色とシート自身の色を合成し，その合成色を出します．
言い換えると，アルファ値を含むシートの各画素は，色を入力し，色を出力する関数として表現できます．
入力色ベクトルをx，シート自身の色ベクトルをc，シートのアルファ値をα(0以上1以下)，出力色ベクトルをcとすると，以下の式が成り立ちます．
y = \alpha c + \left( 1 - \alpha \right) x
これがアルファブレンドと呼ばれる色の合成方法です．
シートが重なっている部分でアルファブレンドを使って色を混ぜ合わせることで，半透明なウィンドウを実現できます．
実装
さて，半透明なウィンドウの実現方法が定まったところで，具体的なアルゴリズムを決めていきましょう．
Color構造体
まず，シート内の1画素の色を表す構造体を作成し，アルファ値を持たせます．
typedef struct //シート上の1画素の色を表す構造体
{
unsigned char red; //赤の輝度0~255
unsigned char green; //緑の輝度0~255
unsigned char blue; //青の輝度0~255
unsigned char alpha; //α値0~255(0が完全透明，255が完全不透明)
} Color;
シート自体にアルファ値を持たせるのではなく，シート内の各画素にアルファ値を持たせることで，1枚のシート内に異なる透明度の領域を混在させることができます．
また，アルファ値を0から255までの整数として表現しているので，式の変形が必要になります．
0 \leq \alpha \leq 1
なので，
A = 255 \alpha
とすれば，
0 \leq A \leq 255
よって，
y = \frac{Ac + \left(255 - A \right)x}{255}
となります．
アルファ値を含む重ね合わせ処理
さて画素単位の処理が決まったら次は複数のシートが重なり合った状態をどう再現するかです．
簡単のため，2次元ではなく1次元の画面を想定します．
下の図のように，最下層に背景シートがあり，その上に3枚のウィンドウシート(wndシート1，2，3)があり，これらの重ね合わせが画面に出力されます．
このとき，wndシート2の左から2番目の画素が書き換えられたとき，その書き換えをどのように画面に反映させるかを追ってみましょう．
まず，wndシート2が書き換えられたらその色を出力する必要がありますが，アルファブレンドにおいて画素は入力色から出力色への関数となるため，入力色を取得しなければなりません．
wndシート2の入力色は(画素の場所とシートの重なり具合にもよりますがこの場合は)wndシート1の出力色であるため，wndシート2からwndシート1に色を問い合わせます．
wndシート1がwndシート2に色を渡す場合も同様に入力色が必要になるので，wndシート1から背景シートに色を問い合わせます．
背景シートは，それよりも下層にシートが存在しないため，自身の色をそのままwndシート1に渡します．
wndシート1は，背景シートから取得した色と自身の色をアルファブレンドし，その色をwndシート2に渡します．
wndシート2も同様にwndシート1から取得した色と自身の色をアルファブレンドし，その色を出力します．
wndシート2が出力した色は，上層のwndシート3に渡され，wndシート3は渡された色と自身の色をアルファブレンドし，その色を出力します．
最後にwndシート3の出力色が画面に表示されます．
このアルゴリズムを実装した結果，下の図のように半透明なウィンドウを作ることができました．
(GitHub上のソースコード)
高速化
さて，これで半透明のウィンドウが実現できるわけですが，一回画素を書き換えるだけでこれだけの処理を行うとなると，画面がカクカクになることが予想できます．
(実際にウィンドウのドラッグを実装した際に若干カクカクした動作になりました．)
そこで，2つの高速化処理を実装しました．
- A = 255における色伝達処理の打ち切り
- アルファブレンドの出力の保持
A = 255における色伝達処理の打ち切り
アルファブレンドでは，最下層の背景シートの色が，各シートのアルファブレンド関数を通り抜けて画面に色が出力されます．
しかし，あるシートのある画素がA = 255の場合，それは完全に不透明で全く色を通さないため，下の図のように色伝達処理を途中で打ち切ることができます．
wndシート2の画素が書き換えられ，wndシート2からwndシート1へ色を問い合わせます．
wndシート1の当該画素は完全に不透明であるため，さらに下層の背景シートに色を問い合わせることなく自身の色をそのままwndシート2に渡せばよいことになります．
wndシート2は出力色をwndシート3に渡しますが，wndシート3の当該画素も完全に不透明であり，wndシート2の出力色はwndシート3によって完全にさえぎられ，画面出力には影響を及ぼさないため，ここで色伝達処理を打ち切ります．
このように，完全に不透明な画素が存在した場合，そこで下層シートへの色の問い合わせおよび上層シートへの色伝達処理を打ち切ることで無駄な処理を省きます．
各シートの入力画像の保持
また現状のアルゴリズムでは，画素の色が書き換えられていなくても当該画素におけるアルファブレンドの計算を複数回行ってしまいます．
今，wndシート2の画素が書き換わり，wndシート1に色を問い合わせ，アルファブレンドし，wndシート3でA = 255のため色伝達処理が打ち切られました．
その後，wndシート3の当該画素が書き換えられ，半透明な色が設定されたとしましょう．
すると，wndシート3はwndシート2に色を問い合わせ，wndシート2はwndシート1に色を問い合わせます．
wndシート1はwndシート2に色を渡し，wndシート2はアルファブレンドを計算して出力色をwndシート3に渡します．
wndシート3も同様にアルファブレンドを計算し，出力色を画面に表示します．
動作としては正しいですが，赤色で示した部分は，wndシート2の画素を書き換えた時にも全く同様の計算をしていたはずです．
なぜ同じ結果になるはずの同様の計算を繰り返しているのか？
それは，各層におけるアルファブレンドの出力色をスタック上で計算している関係で，画素書き換え処理が終わるたびに各層の出力色の計算結果が捨てられてしまうからです．
ならばアルファブレンドをスタックではない別の場所で計算して，計算結果を捨てずに再利用すればより高速に処理できるはずです．
シートを表す構造体は以下のようになっています．
（GitHub上のソースコード）
typedef struct _Sheet
{
Color *image; // シート自体のイメージ
short x, y; // シートの位置
unsigned short width, height; // シートの大きさ
struct _Sheet *upper_sheet; // ひとつ上層のシート
struct _Sheet *lower_sheet; // ひとつ下層のシート
} Sheet;
ここに，下層シートから送られてくる入力色からなるイメージを追加します．
typedef struct _Sheet
{
Color *image; // シート自体のイメージ
Color *background; // 下の層から送られてくるイメージを保存する用
short x, y; // シートの位置
unsigned short width, height; // シートの大きさ
struct _Sheet *upper_sheet; // ひとつ上層のシート
struct _Sheet *lower_sheet; // ひとつ下層のシート
} Sheet;
下層シートから色を受け取るたびにbackgroundにその色を保存することで，過去に計算したアルファブレンドの計算結果を再利用できるようになります．
この改良版アルゴリズムを使って，先ほどの例を実行すると以下のようになります．
今，wndシート2の画素が書き換わり，wndシート1に色を問い合わせ，アルファブレンドし，wndシート3に出力色を送りました．
wndシート3は受け取った色を自身のbackgroundに保存し，そこで色伝達処理が打ち切られます．
その後，wndシート3の当該画素が書き換えられ，半透明な色が設定されたとしましょう．
wndシート3は自身のbackgroundから入力色を取得し，アルファブレンドして出力色を画面に出力します．
後日談
この記事の内容は第28回 自作OSもくもく会オンラインで発表したものですが，その際にhikalium氏よりさらなる高速化のための以下の改良案をいただきました．（感謝）
- アルファブレンドの計算で255除算を8ビット右シフトに変更する．
- 大量の画素の計算にSIMD命令やGPUを使用する．
アルファブレンドの計算で255除算を8ビット右シフトに変更する．
アルファブレンドの式を再掲します．
y = \frac{Ac + \left(255 - A \right)x}{255}
これを以下のように変更します．
y = \frac{Ac + \left(256 - A \right)x}{256}
この式だけ見るとA = 255でも下層からの入力色xの項が残るため，完全な不透明が実現できないように見えますが，高速化の項目で述べたようにA = 255の場合色伝達処理を打ち切ることで完全な不透明を実現しているので，問題ないです．
すると，256除算を8ビット右シフトに変更できます．
除算よりもシフト演算の方が高速なので，高速化が期待できます．
測定はしていませんが，多分速くなったでしょう．
大量の画素の計算にSIMD命令やGPUを使用する．
こちらは未実装ですが，SIMD命令やGPUについて勉強するいい機会なので，そのうち実装します．
まとめ
- アルファ値を含む重ね合わせ処理により半透明なウィンドウを実装した．
- A=255では入力色によらずに出力色が決定できることを利用して高速化した．
- 下の層から送られるイメージをbackgroundとして保持しておくことで，下の層への色の問い合わせやアルファブレンドの再計算をなくし高速化した．
- hikalium氏の改良案により，割り算をシフト演算に変更して（多分）高速化した．
- SIMD命令やGPUを勉強しよう．