CH32V203で遊ぶ（その５）高速なライン描画法

　前回の記事では DMA での高速転送機能によって TFT液晶 MSP2807（320 x 240 dot）での塗りつぶし処理を高速化したことについて書きました。この時のデモ表示を見ているとラインの描画が目で見えるほど遅いので何とか高速化できないものか考えてみました。
　ディバッガで追ってみると速度のネックはライン描画アルゴリズムよりもドット描画自体にあり、SPI や PIO での I/O 制御部がＣ言語での標準な制御方法ではまどろっこしい程の処理なのでレジスタ直書きやアセンブラ化すればかなり速くなりそうです。
　今回はライン描画処理の高速化を検討する中で、上記のような I/O 制御自体の高速化では無く、ライン描画アルゴリズム自体の高速化を思い付いた（以降、傾き予測法(Slope prediction method)と記す）ので記録しておきたいと思います。
　尚、後で気が付きましたが「ポケコン（G850）高速ライン描画」の記事でも引用していた「ラインルーチンの高速化の手法」のページにライン描画の高速化について判り易くまとめられていて、ここにダブルステップの手法が書かれていますが評価結果として高速化はできなかったとの結論でした。今回提案する傾き予測法は本ページの末尾にまとめたように実際に高速化への効果が確かめられた描画法です。


１．今回のお品書き
　ライン描画手法について下記の内容を記載します。

1. 標準的なライン描画処理
2. 両端からの同時描画
3. 今回提案の傾き予測法

最後にまとめとして上記手法の評価結果を記載します。


２．高速ライン描画手法
　以降にライン描画の各手法について記載します。


　２－１．標準的なライン描画処理
　高速化のために整数だけの処理でラインを描画する手法でブレゼンハムのアルゴリズムとして広く知られています。
　下記のソースはネット上のソースを参照せずに独自に起こしたものですが、ブレゼンハムのアルゴリズムと同等の処理になっています。
　高速化の観点からループ内での条件分岐を最小限にするために傾きの大きさにより場合分けし、二つのループ処理に分割しています。PSET は１ピクセルを描画する外部処理です。

標準的なライン描画処理（Ｃ言語）

void LineStd( int16_t xst, int16_t yst, int16_t xen, int16_t yen ) { int16_t x,y,difx,dify; int16_t err, xtail, ytail; LcdXPos = xen; LcdYPos = yen; difx = abs( xen - xst ) << 1; dify = abs( yen - yst ) << 1; if( ( (difx >= dify) && (xen > xst) ) || ( (difx < dify) && (yen > yst) ) ) { x = xst; y = yst; xtail = xen; ytail = yen; } else { x = xen; y = yen; xtail = xst; ytail = yst; } if( difx >= dify ) { int16_t dy; dy = ytail > y ? 1 : -1; err = difx >> 1; for( ; x <= xtail; x++ ) { PSET( x, y ); err += dify; if( err >= difx ) { err -= difx; y += dy; } } } else { int16_t dx; dx = xtail > x ? 1 : -1; err = dify >> 1; for( ; y <= ytail; y++ ) { PSET( x, y ); err += difx; if( err >= dify ) { err -= dify; x += dx; } } } }

・2024/08/16　中心部のポイントが乱れる場合がある問題に対処

　２－２．両端からの同時描画
　上記の改良版でラインが中心点から見て点対称なので始点側と同時に終点側も描画することでループ回数を１／２にして高速化しています。ループ終了後の PSET は始点～終点間の距離が偶数の場合、中心のポイントの描画が欠落してしまうことに対する対処です。

両端からの同時描画（Ｃ言語）

void LineBoth( int16_t xst, int16_t yst, int16_t xen, int16_t yen ) { int16_t x,y,difx,dify; int16_t err, xtail, ytail; LcdXPos = xen; LcdYPos = yen; difx = abs( xen - xst ) << 1; dify = abs( yen - yst ) << 1; if( ( (difx >= dify) && (xen > xst) ) || ( (difx < dify) && (yen > yst) ) ) { x = xst; y = yst; xtail = xen; ytail = yen; } else { x = xen; y = yen; xtail = xst; ytail = yst; } if( difx >= dify ) { int16_t dy; dy = ytail > y ? 1 : -1; err = difx >> 1; for( ; x < xtail; x++, xtail-- ) { PSET( x, y ); PSET( xtail, ytail ); err += dify; if( err >= difx ) { err -= difx; y += dy; ytail -= dy; } } if( x == xtail ) { PSET( x, y ); } } else { int16_t dx; dx = xtail > x ? 1 : -1; err = dify >> 1; for( ; y < ytail; y++, ytail-- ) { PSET( x, y ); PSET( xtail, ytail ); err += difx; if( err >= dify ) { err -= dify; x += dx; xtail -= dx; } } if( y == ytail ) { PSET( x, y ); } } }

・2024/08/16　中心部のポイントが乱れる場合がある問題に対処

　２－３．今回提案の傾き予測法
　上記の描画では傾きが１（４５°）以下の場合と１より大きい場合の二通りに場合分けして処理しましたが、傾き予測法では傾きの大きさによりループ処理を更に２分割します。
　下図に示すように傾きの大きさと移動方向の条件により、次の移動方向を決定できるケースがあり、これを利用して高速化しています。前述の両端からの描画手法も併用します。

• 傾きが 0 ～ 0.5 の場合
  　縦移動／横移動 は１／２以下なので下図の上側の緑色の■のように縦移動直後は必ず横移動になります。
  
  
• 傾きが 0.5 ～ 1.0 の場合
  　縦移動／横移動 は１／２以上なので下図の下側の緑色の■のように横移動直後は必ず縦移動になります。
  

傾き予測法での予測方法

　例えば、上記の「標準的なライン描画処理」において単純にループ内で2ドット分の進みを処理すれば、ループ回数が 1/2 になるので for ループのための条件ジャンプの比率が１／２になり効果は少ないですが若干高速化します（ループ処理の展開による高速化）。逆に言うと１回のループ処理で多くのドットを処理してもそれに比例して条件分岐が増えれば高速化できません（当然処理量が比例して多くなっても高速化できません）。従って高速化するためには上図のようにループ内の条件ジャンプの増加を抑えつつ、より多くのドットを処理するようにする必要があります。

傾き予測法によるライン描画処理（Ｃ言語）

// draw line Ver 0.02b void LcdLine( int16_t xst, int16_t yst, int16_t xen, int16_t yen ) { int16_t x,y,difx,dify,until; int16_t err, xtail, ytail; LcdXPos = xen; LcdYPos = yen; difx = abs( xen - xst ) << 1; dify = abs( yen - yst ) << 1; if( ( (difx >= dify) && (xen > xst) ) || ( (difx < dify) && (yen > yst) ) ) { x = xst; y = yst; xtail = xen; ytail = yen; } else { x = xen; y = yen; xtail = xst; ytail = yst; } if( difx >= dify ) { int16_t dy; dy = ytail > y ? 1 : -1; err = difx >> 1; until = x + (difx>>1) + ( (difx&1) ? 0 : -1); if( difx >= (dify<<1) ) { // slope:[0,0.5] for( ; x < until; x++, xtail-- ) { PSET( x, y ); PSET( xtail, ytail ); err += dify; if( err >= difx ) { err += dify - difx; x++; xtail--; y += dy; ytail -= dy; PSET( x, y ); PSET( xtail, ytail ); } } } else { // slope:(0.5,1] for( ; x < until; x++, xtail-- ) { PSET( x, y ); PSET( xtail, ytail ); err += dify; if( err >= difx ) { err -= difx; y += dy; ytail -= dy; } else { x++; xtail--; PSET( x, y ); PSET( xtail, ytail ); err += dify - difx; y += dy; ytail -= dy; } } } for( ; x <= xtail; x++ ) { PSET( x, y ); err += dify; if( err >= difx ) { err -= difx; y += dy; } } } else { int16_t dx; dx = xtail > x ? 1 : -1; err = dify >> 1; until = y + (dify>>1) + ( (dify&1) ? 0 : -1); if( dify >= (difx<<1) ) { for( ; y < until; y++, ytail-- ) { PSET( x, y ); PSET( xtail, ytail ); err += difx; if( err >= dify ) { err += difx - dify; x += dx; xtail -= dx; y++; ytail--; PSET( x, y ); PSET( xtail, ytail ); } } } else { for( ; y < until; y++, ytail-- ) { PSET( x, y ); PSET( xtail, ytail ); err += difx; if( err >= dify ) { err -= dify; x += dx; xtail -= dx; } else { y++; ytail--; PSET( x, y ); PSET( xtail, ytail ); err += difx - dify; x += dx; xtail -= dx; } } } for( ; y <= ytail; y++ ) { PSET( x, y ); err += difx; if( err >= dify ) { err -= dify; x += dx; } } } }

・Ver 0.02 2024/08/03　中心部のポイントが描画されない場合がある問題に対処し、下記の実行時間も再測定 ・Ver 0.02a 2024/08/16　中心部のポイントが乱れる場合がある問題に対処 ・Ver 0.02b 2024/09/04　傾きが0.5以上で線が太くなる問題に対処

★追記　2024/08/06　{
　上記は速度優先で同様な処理が２カ所にありましたが、速度低下を最小限にしてコードを短くしたバージョンを追記します。

傾き予測法によるライン描画処理[shorter code ver]（Ｃ言語）

// draw line Ver 0.03b void LcdLine( int16_t xst, int16_t yst, int16_t xen, int16_t yen ) { int16_t x,y,difx,dify,until; int16_t err, xtail, ytail,dy; int16_t *px,*py,*pxtail, *pytail; LcdXPos = xen; LcdYPos = yen; difx = abs( xen - xst ) << 1; dify = abs( yen - yst ) << 1; if( ( (difx >= dify) && (xen > xst) ) || ( (difx < dify) && (yen > yst) ) ) { x = xst; y = yst; xtail = xen; ytail = yen; } else { x = xen; y = yen; xtail = xst; ytail = yst; } if( difx >= dify ) { px = &x; py = &y; pxtail = &xtail; pytail = &ytail; } else { int16_t tmp; px = &y; py = &x; pxtail = &ytail; pytail = &xtail; tmp = difx; difx = dify; dify = tmp; } dy = *pytail > *py ? 1 : -1; err = difx >> 1; until = *px + (difx>>1) + ( (difx&1) ? 0 : -1); if( difx >= (dify<<1) ) { // slope:[0,0.5] for( ; *px < until; (*px)++, (*pxtail)-- ) { PSET( x, y ); PSET( xtail, ytail ); err += dify; if( err >= difx ) { err += dify - difx; (*px)++; (*pxtail)--; *py += dy; *pytail -= dy; PSET( x, y ); PSET( xtail, ytail ); } } } else { // slope:(0.5,1] for( ; *px < until; (*px)++, (*pxtail)-- ) { PSET( x, y ); PSET( xtail, ytail ); err += dify; if( err >= difx ) { err -= difx; *py += dy; *pytail -= dy; } else { (*px)++; (*pxtail)--; PSET( x, y ); PSET( xtail, ytail ); err += dify - difx; *py += dy; *pytail -= dy; } } } for( ; *px <= *pxtail; (*px)++ ) { PSET( x, y ); err += dify; if( err >= difx ) { err -= difx; *py += dy; } } }

・Ver 0.03a 2024/08/16　中心部のポイントが乱れる場合がある問題に対処 ・Ver 0.03b 2024/09/04　傾きが0.5以上で線が太くなる問題に対処

}

３．各ライン描画法の評価
　上述のライン描画法の評価環境として、前回の記事でも使用した CH32V203（8MHz動作）に TFT液晶 MSP2807（320 x 240 dot）を接続した環境を使いました。評価方法としては事前に乱数で生成した 512 本のラインデータに従ってライン描画処理を実行した際の時間を計測しました。時間計測は systick タイマの内部カウンタだけでも計測できそうでしたが、今回は systick を使った 1ms 毎の割込み処理でインクリメントするカウンタ値で時間を計測しています。コンパイル時のオプティマイズはディフォルトのままの -Os（サイズ優先）です。

　下図は評価時の LCD 表示です。

ライン描画法評価時の LCD 画面

　計測結果を下表に示します。

No.	method	time[s]
1	標準的なライン描画	13.185
2	両端からの同時描画	13.121
3	今回提案の傾き予測法	13.109

　上記の表では殆ど時間差が無いように見えますが、冒頭で書いたようにドット描画処理（PSET）が重いので PSET を何もしないダミー関数にし、ライン描画アルゴリズムの処理自体の時間を計測し直した結果が下表です。

No.	method	time[s]	speed ratio
1	標準的なライン描画	0.200	1.00
2	両端からの同時描画	0.124	1.61
3	今回提案の傾き予測法	0.112	1.79

　期待通り、今回提案の傾き予測法は標準的なライン描画より約 1.8 倍速いという結果になりました。


[TOP] [ 前へ ] CH32V203で遊ぶ [ 次へ ]