リアルタイムアプリケーションでのBresenhamのアルゴリズム

そのようなデバイスがあります-スキャナーまたはスキャナーと呼ばれ、通常は形容詞「レーザー」が付いています







さまざまなレーザースキャンテクノロジで使用します。



プログラマーの観点からは、レーザースキャナーは2つの相互に垂直な平面でレーザービームを偏向する2つの回転ミラーであり、角度はDACのペア(およびDACの後ろに立つフィードバックアンプ)を使用して設定されます。 DACは通常12〜16ビットです。 実際、絵を描く作業、またはもう少し科学的な言葉を話す作業は、そのようなデバイスでの情報の出力は、古代のアナロググラフィックディスプレイでの情報の出力と同じです。



画像



このようなスキャナーは通常、コンピューターから「高レベルのコマンド」が送信される別個の(マイクロ)コントローラーを使用して制御されます。 主なコマンドは、「そのような速度で今から現在まで線を引く」ことです。 線とマイクロコントローラを作成したら、古典的なブレゼンハムアルゴリズムを思い出します。 Bresenhamのアルゴリズムは、「遅い」浮動小数点演算を使用しないという点で優れていますが、最新の32ビットマイクロコントローラーでは、8ビットまたは16ビットマイクロコントローラーほど重要ではありません。







/* Bresenham algorithm implementation   .. , .. ,  ,*/ void Line(int x1, int y1, int x2, int y2, int color) { int x1,y1,dx,dy,sx,sy,d,d1,d2; int i, x,y; if( x2 >= x1) { dx = x2 - x1; sx = 1; } else { dx = x1 - x2; sx = -1; } if( y2 >= y1) { dy = y2 - y1; sy = 1; } else { dy = y1 - y2; sy = -1; } if(dy <= dx) { d = (dy << 1) - dx; d1 = dy << 1; d2 = (dy - dx) << 1; for(x=x1+sx,y=y1,i=1; i <= dx ; i++,x+=sx) { if(d > 0) { d += d2; y += sy; } else { d += d1; } putpixel(x,y, color); } } else { d = (dx << 1) - dy; d1 = dx << 1; d2 = (dx - dy) << 1; for(x=x1,y=y1+sy,i=1;i <= dy ; i++,y += sy) { if(d > 0) { d += d2; x += sx; } else { d += d1; } putpixel(x,y, color); } } /* endif(dy <=dx) */ }
      
      







この場合、色はないため、 色は無視されます。 しかし、スピードはあります。

たとえば、 nピクセルの水平または垂直セグメントとV (1秒あたりのピクセル数)の特定の速度がある場合、各ピクセルは時間tp = 1 / Vを表示する必要があります



セグメントが水平でない場合、その長さはl = hypot(x0-x1、y0-y1)であり、セグメント全体の出力時間はt0 = l / Vですが、ポイントごとの遅延を計算するには、t0をputpixelの呼び出し数で割る必要があります。 e。



tp = t0 / max(| x0-x1 |、| y0-y1 |)



次に、アルゴリズムでは、色は単に「delay by point」 待機(= tp)に置き換えられます



 void Line(int x1, int y1, int x2, int y2, int wait) ...... putpixel(x,y, wait));
      
      







putpixel関数自体は 、一見すると次のようになります。



 void putpixel(int x, int y, int wait)) { outPortX(x); //    X  x outPortY(y); //    Y  y delay(wait); //  wait   }
      
      







ただし、DACの実装に関連するニュアンスはここから始まります。



DACは、順次および並列の両方で動作できます。 一貫して-これは、DAC番号を選択し、目的の値を設定し、準備完了、変換の終了、またはしばらく待つ必要がある場合です。 DACが並列に動作する場合、マイクロコントローラーの対応するレジスタにx値とy値を記録し、同時に準備完了または変換の終了を待つことができます。



最初の場合、XのみまたはYのみを出力するのにかかる時間は、XおよびYのシリアル出力の約2倍です。したがって、ソースコードはすでに次のようになっています。



 void Line(int x1, int y1, int x2, int y2, int wait, int waitXY) { int dx,dy,sx,sy,d,d1,d2; int i, x,y; if( x2 >= x1) { dx = x2 - x1; sx = 1; } else { dx = x1 - x2; sx = -1; } if( y2 >= y1) { dy = y2 - y1; sy = 1; } else { dy = y1 - y2; sy = -1; } /****************************/ if(dy <= dx) { d = (dy << 1) - dx; d1 = dy << 1; d2 = (dy - dx) << 1; for(x=x1+sx,y=y1,i=1; i <= dx ; i++,x+=sx) { if(d > 0) { d += d2; y += sy; putXY(x,y,waitXY); } else { d += d1; putX(x, wait); } } } else { d = (dx << 1) - dy; d1 = dx << 1; d2 = (dx - dy) << 1; for(x=x1,y=y1+sy,i=1;i <= dy ; i++,y += sy) { if(d > 0) { d += d2; x += sx; putXY(x,y,waitXY); } else { d += d1; putY(y, wait); } } } /* endif(dy <=dx) */ } void putXY(int x, int y, int wait)) { outPortXY(x,y); //    X  Y  x  y //    #define outPortXY(x,y) outPortX(x); outPortY(y); delay(wait); //  wait   } void putX(int x, int wait)) { outPortX(x); //    X  x delay(wait); //  wait   } void putY(int y, int wait)) { outPortY(y); //    Y  y delay(wait); //  wait   }
      
      







Lineを呼び出すときのwaitおよびwaitXYの値は、次の事実に基づいて計算できます。



l = hypot(x0-x1、y0-y1) 、セグメント全体の出力時間t0 = l / V 、呼び出し回数putXY n1 = min(| x0-x1 |、| y0-y1 |)、呼び出し回数putX orおよびputY n0 = max(| x0-x1 |、| y0-y1 |)-min(| x0-x1 |、| y0-y1 |)



さらに、outPortX、outPortY、およびoutPortXY関数のランタイムを調整できます。 これらの関数の実行時間は、キャリブレーションプロセス中に事前に決定できます。



マイクロプロセッサではなく、制御コンピューターの遅延のすべての計算を行いますが、問題の時間と遅延-マイクロ秒とそのシェア...



まあ、実際は今のところ。



インストールを組み立て、制御コンピューターとマイクロプロセッサー用のプログラムを作成し、電源を入れ、簡単なテスト画像を表示して、何が起こったかを確認します



誰が私たちが見るものを推測しますか? (続く)



All Articles