사용자 도구

사이트 도구


kb:bresenhamalgorithm

차이

문서의 선택한 두 판 사이의 차이를 보여줍니다.

차이 보기로 링크

kb:bresenhamalgorithm [2014/11/06 19:04] (현재)
줄 1: 줄 1:
 +====== Bresenham Algorithm ======
 +attachment:​bresenham.gif
 +
 +원래는 2D 그래픽에서 사용하는 알고리즘이지만,​ [[PathFinding]] 등 여러 가지 목적으로 사용할 수 있다. ​
 +
 +
 +====== 2D 라인 알고리즘 ======
 +<code cpp>
 +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; } 
 +        } 
 +    }
 +}
 +</​code>​
 +
 +====== 3D 라인 알고리즘 ======
 +3D 라인 같은 경우에는 렌더링용이라기보다는 뭔가 다른 처리를 위한 것이다. "Voxel Traversal"​로 검색해 보기 바란다.
 +<code cpp>
 +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; } 
 +        } 
 +    }
 +}
 +</​code>​
 +
 +====== 원 알고리즘 ======
 +<code cpp>
 +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);
 +}
 +</​code>​
 +
 += 링크 =
 +  * [[http://​www.cs.helsinki.fi/​group/​goa/​mallinnus/​lines/​bresenh.html | The Bresenham Line-Drawing Algorithm]]
 +  * [[http://​www.funducode.com/​freec/​graphics/​graphics2.htm | Bresenham'​s Line Drawing Algorithm]]
 +  * [[http://​www.edepot.com/​algorithm.html | Fast Computer Graphics Line-Drawing Algorithms]]
 +  * [[http://​www.gamedev.net/​reference/​articles/​article767.asp | Bresenham'​s Line and Circle Algorithms]]
 +  * [[http://​www.cs.unc.edu/​~mcmillan/​comp136/​Lecture6/​Lines.html | Line-Drawing Algorithms]]
  
kb/bresenhamalgorithm.txt · 마지막으로 수정됨: 2014/11/06 19:04 (바깥 편집)