RaspberryPiで有機ELディスプレイ(4)
SSD1306で直線を描画する
(Bresenhamのアルゴリズムで最適化)

どもです。

前回のエントリで、直線を描画しました。
その中で紹介したコードですが、見ての通り計算が多いです。
RaspberryPiレベルであれば、それほど問題はないのですが、計算量を減らして処理を高速化しても損はありません。
そこで今回は、直線の描画処理に「Bresenhamのアルゴリズム」を適用し、前回のエントリで紹介したコードと処理速度を比較してみたいと思います。

1. 開発環境

毎度ですが、開発環境です。

開発/実行環境
項目 内容
OS Windows10 Pro(1909)
CPU i7-8700
メモリ 16GB
IDE Eclipse
Ver.2019-06(4.12.0)
Build id 20190614-1200

また、RaspebrryPi/pigpioの環境は以下の通りです。

RaspberryPi
項目 内容
HW RaspberryPi3 model B
OS Raspbian GNU/Linux
buster
ライブラリ pigpio Version 71
(gpioVersion()関数で確認)

SSD1306の設定です。


2. Bresenhamのアルゴリズム(実装)

Bresenhamのアルゴリズムについては、非常に多くの情報が得られます。
なので、ここではアルゴリズムの紹介は省略し、実装の紹介のみとします。

int steep = abs(y1 - y0) > abs(x1 - x0);
if (steep) {
	SWAP(&x0, &y0);
	SWAP(&x1, &y1);
}

if (x1 < x0) {
	SWAP(&x0, &x1);
	SWAP(&y0, &y1);
}

//線の描画(高速アルゴリズム)で必要な値の算出
int16_t dx = x1 - x0;
int16_t dy = abs(y1 - y0);
int16_t err = dx / 2;	//誤差
int16_t	yStep = 1;

for (; x0 ≤ x1; x0++) {
	if (steep) {
		drawPixel(y0, x0);
	} else {
		drawPixel(x0, y0);
	}
	err -= dy;
	if (err < 0) {
		y0 += yStep;
		err += dx;
	}
}

3. 処理速度の比較

処理速度の比較は、以下の方法で実施します。

  • 描画する線は、対角線。
  • 実施回数は1000回
  • 要した時間の平均値で比較
  • バッファにデータをセットする処理を計測する
    (表示処理は除く)

実施した結果は、以下の通りです。

処理 処理時間(マイクロ秒)
非最適化 24
最適化
(Bresenham)
17

このように、確かにBresenhamのアルゴリズムを適用した方が処理が速いことが分かります。

4. でも…

Bresenhamのアルゴリズムを適用することで、処理速度が向上することは分かりました。
しかし、実際に画面に表示する処理に10ミリ秒程度かかります。
ドットの描画には、座標の計算の1000倍程度の時間がかかります。
最適化しても、それを書き消してしまう処理時間…。

5. まとめ

今回は、直線の描画処理にBresenhamのアルゴリズムを適用して、最適化/処理の高速化を確認しました。
結果として、処理が高速化できることは確認できました。
しかしながら、描画に要する時間がとても長いため、高速化してもそれほど効果が無い、ということが明らかになってしまいました…。
ま。
それでも処理は高速化できるので、コチラの処理を適用する方がよいと思います。

ではっ!