BresenhamAlgorithm

UserPreferences

1. 개요
2. 2D 라인 알고리즘
3. 3D 라인 알고리즘
4. 원 알고리즘
5. 링크

1 개요

원래는 2D 그래픽에서 사용하는 알고리즘이지만, PathFinding 등 여러 가지 목적으로 사용할 수 있다.

2 2D 라인 알고리즘

struct POINT2
{
    int x, z;
    POINT2(int _x = 0, int _z = 0) : x(_x), z(_z) {}
};

void GetPointsInLine(
    int x0, int y0, int x1, int y1, std::vector<POINT2>& line)
{
    // 시작점.
    int x = x0, y = y0; 

    // 라인의 기울기.
    int dx = x1-x0, dy = y1-y0; 

    // 라인의 기울기에 따라 옵셋 결정.
    int sx = (dx > 0 ? 1 : (dx < 0 ? -1 : 0)); 
    int sy = (dy > 0 ? 1 : (dy < 0 ? -1 : 0)); 

    // 복셀 선택을 위한 파라미터 계산.
    dx = abs(dx); 
    dy = abs(dy); 
    int ax = 2 * dx, ay = 2 * dy; 
    int decx, decy; 

    // 가장 긴 축을 판단한다..
    int maximum = dx, var = 0; 
    if (dy > maximum) { maximum = dy; var = 1; } 

    // 브레센햄.
    if (var == 0)
    {
        for (decy=ay-dx; ; x += sx, decy += ay) 
        { 
            line.push_back(POINT2(x, y));

            if (x == x1) break; 
            if (decy >= 0) { decy -= ax; y += sy; } 
        } 
    }
    else
    {
        for (decx=ax-dy; ; y += sy, decx += ax) 
        { 
            line.push_back(POINT2(x, y));

            if (y == y1) break; 
            if (decx >= 0) { decx -= ay; x += sx; } 
        } 
    }
}

3 3D 라인 알고리즘

3D 라인 같은 경우에는 렌더링용이라기보다는 뭔가 다른 처리를 위한 것이다. "Voxel Traversal"로 검색해 보기 바란다.


struct POINT3
{
    int x, y, z;
    POINT3(int _x = 0, int _y = 0, int _z = 0) : x(_x), y(_y), z(_z) {}
};

void GetPointsInLine(
    int x0, int y0, int z0, int x1, int y1, int z1, std::vector<POINT3>& line)
{
    // 시작점.
    int x = x0, y = y0, z = z0; 

    // 라인의 기울기.
    int dx = x1 - x0, dy = y1 - y0, dz = z1 - z0; 

    // 라인의 기울기에 따라 옵셋 결정.
    int sx = dx > 0 ? 1 : (dx < 0 ? -1 : 0); 
    int sy = dy > 0 ? 1 : (dy < 0 ? -1 : 0); 
    int sz = dz > 0 ? 1 : (dz < 0 ? -1 : 0); 

    // 복셀 선택을 위한 파라미터 계산.
    dx = abs(dx); 
    dy = abs(dy); 
    dz = abs(dz); 
    int ax = 2 * dx, ay = 2 * dy, az = 2 * dz; 
    int decx, decy, decz; 

    // 가장 긴 축을 판단한다.
    int maximum = dx, var = 0; 
    if (dy > maximum) { maximum = dy; var = 1; } 
    if (dz > maximum) { maximum = dz; var = 2; } 

    // 브레센햄.
    if (var == 0) 
    { 
        for (decy=ay-dx, decz=az-dx; ; x += sx, decy += ay, decz += az) 
        { 
            line.push_back(POINT3(x, y, z));

            if (x == x1) break; 
            if (decy >= 0) { decy -= ax; y += sy; } 
            if (decz >= 0) { decz -= ax; z += sz; } 
        } 
    }
    else if (var == 1)
    {
        for (decx=ax-dy, decz=az-dy; ; y += sy, decx += ax, decz += az) 
        { 
            line.push_back(POINT3(x, y, z));

            if (y == y1) break; 
            if (decx >= 0) { decx -= ay; x += sx; } 
            if (decz >= 0) { decz -= ay; z += sz; } 
        } 
    }
    else
    {
        for (decx=ax-dz, decy=ay-dz; ; z += sz, decx += ax, decy += ay) 
        { 
            line.push_back(POINT3(x, y, z));

            if (z == z1) break; 
            if (decx >= 0) { decx -= az; x += sx; } 
            if (decy >= 0) { decy -= az; y += sy; } 
        } 
    }
}

4 원 알고리즘

struct POINT2
{
    int x, z;
    POINT2(int _x = 0, int _z = 0) : x(_x), z(_z) {}
};

void GetPointsInCircle(int cx, int cy, int radius, std::vector<POINT2>& circle)
{
    if (radius <= 0) return;

    int tx = 0;
    int ty = radius;
    int tp = 3 - 2 * radius;

    do
    {
        circle.push_back(POINT2(cx + tx, cy + ty));
        circle.push_back(POINT2(cx + ty, cy + tx));
        circle.push_back(POINT2(cx + ty, cy - tx));
        circle.push_back(POINT2(cx + tx, cy - ty));
        circle.push_back(POINT2(cx - tx, cy - ty));
        circle.push_back(POINT2(cx - ty, cy - tx));
        circle.push_back(POINT2(cx - ty, cy + tx));
        circle.push_back(POINT2(cx - tx, cy + ty));

        tx++;

        if (tp < 0)
        {
            tp += 4 * tx + 6;
        }
        else
        {
            ty--;
            tp += 4 * (tx - ty) + 10;
        }
    }
    while (tx <= ty);
}

5 링크

• The Bresenham Line-Drawing Algorithm
  
• Bresenham's Line Drawing Algorithm
  
• Fast Computer Graphics Line-Drawing Algorithms
  
• Bresenham's Line and Circle Algorithms
  
• Line-Drawing Algorithms
  

• CategoryAlgorithm, CategoryGraphicProgramming