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

2021年9月12日2022年7月3日

どもです。

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

1. 開発環境

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

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

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回
• 要した時間の平均値で比較
• バッファにデータをセットする処理を計測する
  (表示処理は除く)

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

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

4. でも…

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

5. まとめ

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

ではっ！