ブレゼンハムのアルゴリズムを使って線を描く

最終更新 2003 09/30

サンプルのダウンロード → API_DrawLine2.lzh(38k)

全ソースコード
#include <windows.h> //マクロ #define CLASS_NAME "DrawLine Sample 2" //クラス名 #define WINDOW_WIDTH 400 //ウィンドウ横幅 #define WINDOW_HEIGHT 400 //ウィンドウ高さ #define RANDOM(x) ( rand() / ( RAND_MAX / x ) ) // 0 から x までの乱数を発生させる //プロトタイプ宣言 LRESULT CALLBACK WinProc( HWND, UINT, WPARAM, LPARAM ); void DrawLine( HWND, long, long, long, long, COLORREF ); //グローバル変数 BOOL g_bDrag = FALSE; //マウスの左ボタンをドラッグしてるかどうか short g_sStartX; //線の始点Ｘ short g_sStartY; //線の始点Ｙ //メイン int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd ) { //ウィンドウクラス設定＆登録 { WNDCLASS wc; wc.cbClsExtra = 0; wc.cbWndExtra = 0; wc.hbrBackground = (HBRUSH)GetStockObject( WHITE_BRUSH ); wc.hCursor = LoadCursor( NULL, IDC_ARROW ); wc.hIcon = LoadIcon( NULL, IDI_WINLOGO ); wc.hInstance = hInstance; wc.lpfnWndProc = WinProc; wc.lpszClassName = CLASS_NAME; wc.lpszMenuName = NULL; wc.style = 0; if( !RegisterClass( &wc ) ) return 1; } //ウィンドウ作成 HWND hWnd = CreateWindow( CLASS_NAME, "DrawLine Test 2", WS_CAPTION|WS_SYSMENU, CW_USEDEFAULT, CW_USEDEFAULT, WINDOW_WIDTH, WINDOW_HEIGHT, NULL, NULL, hInstance, NULL ); if( hWnd == NULL ) return 1; //ウィンドウ表示 ShowWindow( hWnd, SW_NORMAL ); UpdateWindow( hWnd ); //メッセージループ while( true ) { MSG msg; if( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) ) { //メッセージがあるときはメッセージを処理 if( msg.message == WM_QUIT ) break; TranslateMessage( &msg ); DispatchMessage( &msg ); } else { //メッセージがないときにやりたい事をやる HDC hDC = GetDC( hWnd ); //HDC取得 char text[100]; //表示させる文字を格納 //背景クリア BitBlt( hDC, 0, 0, WINDOW_WIDTH, WINDOW_HEIGHT, NULL, 0, 0, WHITENESS ); if( g_bDrag ) { //ドラッグ中なら始点からカーソル位置までの線を引く //カーソル位置取得 POINT mouse; GetCursorPos( &mouse ); ScreenToClient( hWnd, &mouse ); //線を引く(線の色はランダム) DrawLine( hWnd, g_sStartX, g_sStartY, mouse.x, mouse.y, RGB(RANDOM(255),RANDOM(255),RANDOM(255)) ); //ドラッグ中、始点・終点の座標を変数に格納 wsprintf( text, "Drag:ON x1:%03d y1:%03d x2:%03d y2:%03d", g_sStartX, g_sStartY, mouse.x, mouse.y ); } else { //ドラッグしていない wsprintf( text, "Drag:OFF" ); } TextOut( hDC, 10, 10, text, lstrlen( text ) ); //変数に格納した文字を表示 wsprintf( text, "ウィンドウを左クリックしたままカーソルを移動" ); TextOut( hDC, 10, 30, text, lstrlen( text ) ); ReleaseDC( hWnd, hDC ); //ＨＤＣ解放 Sleep( 10 ); //ウェイト } } return 0; } //メッセージの対応 LRESULT CALLBACK WinProc( HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam ) { switch( uMsg ) { case WM_DESTROY: PostQuitMessage(0); break; case WM_KEYDOWN: switch( wParam ){ case VK_ESCAPE:case VK_F12:case 'x':case 'X': PostQuitMessage(0); } break; case WM_LBUTTONDOWN: //カーソル位置取得 POINT mouse; GetCursorPos( &mouse ); ScreenToClient( hWnd, &mouse ); //始点の座標をセット g_sStartX = (short)mouse.x; g_sStartY = (short)mouse.y; //ドラッグ中・・・ g_bDrag = TRUE; SetCapture( hWnd ); break; case WM_LBUTTONUP: g_bDrag = FALSE; //ドラッグ終了 ReleaseCapture(); break; } return DefWindowProc( hWnd, uMsg, wParam, lParam ); } /* DrawLine ブレゼンハムのアルゴリズムを使って線を描く 引数 hWnd = 線を描くウィンドウのハンドル lStartX = 始点Ｘ lStartY = 始点Ｙ lEndX = 終点Ｘ lEndY = 終点Ｙ color = 線の色 戻り値 なし */ void DrawLine( HWND hWnd, long lStartX, long lStartY, long lEndX, long lEndY, COLORREF color ) { char cbAddX, cbAddY; long lDistX, lDistY; long lCount; long i; lDistX = lEndX - lStartX; lDistY = lEndY - lStartY; if( lDistX < 0 ) lDistX = -lDistX, cbAddX = -1; else cbAddX = 1; if( lDistY < 0 ) lDistY = -lDistY, cbAddY = -1; else cbAddY = 1; HDC hDC = GetDC( hWnd ); //処理速度を速くするためにＸ距離・Ｙ距離ごとに処理を分岐 lCount = 0; if( lDistX > lDistY ) { //X距離の方が大きい for( i = 0; i <= lDistX; i++ ) { SetPixel( hDC, lStartX, lStartY, color ); lStartX += cbAddX; lCount += lDistY; if( lCount >= lDistX ) lCount -= lDistX, lStartY += cbAddY; } } else { //Y距離の方が大きい for( i = 0; i <= lDistY; i++ ) { SetPixel( hDC, lStartX, lStartY, color ); lStartY += cbAddY; lCount += lDistX; if( lCount >= lDistY ) lCount -= lDistY, lStartX += cbAddX; } } ReleaseDC( hWnd, hDC ); }

線を引くアルゴリズムでよく使われるのはブレゼンハムのアルゴリズムです。
足し算と引き算しか使わないので処理速度が速く、ゲームでもよく使われます。
このアルゴリズムを応用すると、ある点からある点へキャラクターを直線移動
させたり（ライン移動）、円を描画したり、弧を描きながら目標を追跡する
ミサイルの飛行軌道などに使えます。
３Ｄでもよく使われるみたいですね。
考えたのは名前のとおりブレゼンハムという人です。

ブレゼンハムのアルゴリズムを使って線を引くサンプルを以下に示します。

short startX, startY; //線を引く最初の点
short endX, endY;     //線を引く目標の点
short addX, addY;     //Ｘ、Ｙの値を毎回どれだけ増やすか
short distX, distY;   //startX-endX と startY-endY の距離
short count;          //カウンタ

distX = endX - startX; //目標の点から視点までのＸ方向の距離を求める
distY = endY - startY; //同じくＹ方向

//Ｘ、Ｙそれぞれ移動する方向を求める
if( distX < 0 ){ distX *= -1; addX = -1; }
else{ addX = 1; }

if( distY < 0 ){ distY *= -1; addY = -1; }
else{ addY = 1; }

count = 0;
if( distX > distY )
{
    //Ｘ距離の方が大きい
    for( i=0; i<=distX; i++ )
    {
        //startX,startYの位置に点を打つ処理をここに書く
        startX += addX;  //ひとつ先の点へ移動
        count += distY;
        if( count >= distX )
        {
            //countの値がdistX以上になったらＹ方向をひとつ移動させる
            count -= distX;
            startY += addY;
        }
    }
}
else
{
    //Y距離の方が大きい
    for( i=0; i<=distY; i++ )
    {
        //startX,startYの位置に点を打つ処理をここに書く
        startY += addY;  //ひとつ先の点へ移動
        count += distX;
        if( count >= distY )
        {
            //countの値がdistY以上になったらＸ方向をひとつ移動させる
            count -= distY;
            startX += addX;
        }
    }
}


distX と distY の大きさで処理を振り分けているのは、直線を引く時は
２つのケースを考える必要があるのと、高速化のためです。

いろいろな種類の線を描いてみて、Ｘ方向の長さとＹ方向の長さで比べると
分かるのですが、Ｘ（水平）方向の方が長い線と、Ｙ（垂直）方向の方が
長い線の２種類あります。

どっちが長いかで点を打っていく方向が変わるので、distX と distY の
大きさで処理を振り分けます。

変数をうまく使えば処理を振り分けないでも線を引くことはできますが
条件分岐やそのための計算が増えるので処理速度が遅くなります。

あとの細かい所はサンプルを見ながらよく考えてみて下さい。
言葉で説明してもピンとこないと思うので・・・。

| back | home |