728x90

영상처리에서 특정한 폴리곤의 내부에서의 픽셀 정보만 처리해야 하는 경우가 많이 있다. 이 경우에 폴리곤 내부영역의 마스크를 만들어서 사용하거나 inpoly() 함수를 호출하여서 그 폴리곤의 내부인지를 판별하는 방법을 사용할 수 있다. 가장 기본적인 폴리곤은 삼각형으로 여기서는 삼각형 내부를 색상 정보를 읽거나 칠할 때 필요한 알고리즘을 알아본다.

기본적으로 스캔라인에 기반한 처리를 해야 하므로, 각각의 스캔라인에 대해서 삼각형의 변과 교차하는 점을 찾아서 두 교차점 사이의 구간을 읽거나 색칠하면 된다. 삼각의 세 꼭짓점을  y값을 기준으로 정렬을 하면 삼각형은 그림의 (A)나 (B)의 경우로 나눌 수 있어서  이 작업이 보다 간단해진다.


아래의 코드는 이것을 구현한 것이다:

#define SWAP(a, b) {double t; t = (a); (a) = (b); (b) = t;}
void trifill(double x0, double y0, double x1, double y1, double x2, double y2) {
    //sort --> y0 < y1 <y2;
    if (y1 < y0) { SWAP(y0, y1); SWAP(x0, x1);}
    if (y2 < y0) { SWAP(y2, y0); SWAP(x2, x0);}
    if (y2 < y1) { SWAP(y1, y2); SWAP(x1, x2);}
    //now, y0 <= y1 <= y2 ;
    //calc dx/dy for edge(0->1), edge(0->2), edge(1->2);
    double d10, d20, d21 ;
    if (y1 - y0 > 0) d10 = (x1 - x0) / (y1 - y0);
    else   d10 = 0; //horizontal line;
    if (y2 - y0 > 0) d20 = (x2 - x0) / (y2 - y0);
    else d20 = 0;   //horizontal line;
    if (y2 - y1 > 0) d21 = (x2 - x1) / (y2 - y1);
    else d21 = 0;   //horizontal line;
    //
    double sx, ex, x;
    sx = ex = x0 ;
    double y = y0 ; //starting from (x0,y0);
    if (d10 > d20) {
        // 0->2->1 : counter clockwise;
        // 삼각형의 밑부분 스캔;
        // 각각의 수평스캔은 (0->2)변에서 출발하여서 (0->1)변에서 끝난다;
        // 따라서 y값의 끝은 y1이다 
        for (; y < y1; y++) {
            //현재위치 ;
            x = sx;  
            for ( ; x < ex ; x++) PutPixel(x, y);
            //다음 라인으로 이동;
            sx += d20 ; //시작점 ;
            ex += d10 ; //끝점 ;
        }
        // 삼각형의 윗부분 스캔 ;
        // 각각의 수평스캔은 (0->2변에서 출발하여서 (1->2)변에서 끝난다;
        // 따라서 y의 끝값은 y2이다;
        // 새로운 끝점의 시작은 (x1,y1);
        ex = x1; y = y1;
        for ( ; y <= y2; y++) {
            x = sx; 
            for( ; x < ex ; x++) PutPixel(x, y);
            //다음 라인으로 인동;
            sx += d20 ;
            ex += d21 ;
        }
    } else { 
        // 0->1->2 : counter clockwise;
        // 삼각형 밑부분 스캔;
        // (0->1)변에서 출발하여서 (0->2)변에서 끝난다;
        // 따라서 y값의 끝은 y1이다;
        for (; y < y1; y++) {
            x = sx;
            for (; x < ex; x++) PutPixel(x,y);
            sx += d10;
            ex += d20;
        }
        //삼각형의 윗부분 스캔 ;
        //각각의 수평스캔은 (1->2)변에서 출발하여서 (0->2)변에서 끝난다;
        //따라서 y의 끝값은 y2이다;
        //새로운 시작점의 시작은 (x1,y1);
        x = x1; y = y1;
        for (; y <= y2; y++) {
            x = sx;
            for(; x < ex; x++) PutPixel(x, y);
            sx += d21;
            ex += d20;
        }
    }
}'


삼각형 영역을 읽고 invert 시킨 경우:

'Computational Geometry' 카테고리의 다른 글

Polyline Simplication  (0) 2010.01.17
한 점에서 선분까지 거리  (1) 2010.01.16
삼각형 채우기  (0) 2009.12.19
Triangulation을 이용한 Imge Effect  (0) 2009.12.18
Ellipse Drawing Algorithm  (0) 2008.06.04
Circle Drawing Algorithm  (1) 2008.06.03
Posted by helloktk

댓글을 달아 주세요

728x90

MFC를 써서 폴리곤의 내부를 칠하기 위해서는 윈도  GDI region을 다루는  CRgn  클래스의 CRgn::CreatePolygonRgn() 메쏘드를 써서 해당 폴리곤으로 bound 된 영역을 만든 이후에 CDC::FillRgn() 함수를 이용하여서 원하는 색으로 칠할 수 있다. 직접  raster에 칠하려고 할 때는 이러한 방법이 너무 불편하다 (물론 라스터(DIB)를 윈도 비트맵으로 변환한 후에 위의 방법대로 칠하고, 다시 윈도 비트맵을 라스터로 바꾸는 작업을 하면 되는데 번거롭다).

쉽게 생각할 수 있는 방법은  point_in_polygon()  방법을 써서 각각의 픽셀이 주어진 폴리곤 내부점인지를 확인하면서 작업을 할 수 있다. 그러나 이 방법은 한 픽셀을 검사하기 위해서 주어진 폴리곤의 모든 에지를 다 건들어야 하는 낭비를 하게 된다. 보다 효율적인 방법은 point_in_polygon 알고리즘을 구현할 때 사용하는 원리를 이용하면 적어도 한 스캔라인의 모든 픽셀에 대해서는 딱 한 번만 전체 폴리곤의 에지를 검사하게 만들 수 있다. inclusion 테스트는 해당점에서 출발하는 수평 반직선이 폴리곤과 몇 번 교차하는지를 세서 내부점인지 외부점인지를 판별한다. 이것을 생각하면 수평선이 폴리곤과 교차하는 점들을 모두 구하여서(한번 폴리곤의 전체 에지 검사가 필요) 크기의 순서대로 정렬할 때, 짝수번째 구간(0->1, 2->3,.....)에 들어가는 스캔라인의 픽셀들은 모두 폴리곤의 내부점이 된다는 것을 알 수 있다.

사용자 삽입 이미지


알고리즘 순서:
(1) 각각의 스캔라인에 대해서 교차점들을 구한다:
       꼭짓점-i와 꼭짓점-j(=i-1)를 잇는 직선의 방정식: x = x[i] + (x[j] - x[i])*(y - y[i]) / (y[j] - y[i]) 이므로
       현재의 scanline 위치에서 y값이 두 꼭지점의 y값 (y[i], y[j]) 사이에 있으면, 교차점의 x-좌표는 윗식의
       좌변 값이 된다.
(2) 교차점들을 크기의 순서대로 정렬한다.

(3) 짝수번째 구간에 들어가는 스캔라인상의 픽셀들은 해당 색깔로 칠한다.


static int comp(const void *a, const void *b);

더보기
// qsort용 비교함수;
static int comp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
};
/*코드 샘플
** 폴리곤을 플로팅타입으로 변환이 필요?
*/
void FillPolygon(POINT poly[], int npoly,
                 DWORD color,
                 BYTE *image, int width, int height, int bpp) {
    int *nodeX = new int [npoly] ; //never exceeds npoly;
    for (int y = 0; y < height; y++) {
        // find intersection nodes;
        int nodes = 0;
        for (int i = 0, j = npoly - 1; i < npoly; j = i++) {
            if (poly[i].y < y && poly[j].y >= y || poly[j].y < y && poly[i].y >= y) {
                // 수평인 에지는 그리지 않는다(부등식을 자세히 보라)
                nodeX[nodes++] = (int)(poly[i].x + double(y - poly[i].y) * double(poly[j].x \
                                 - poly[i].x) / double(poly[j].y - poly[i].y) + .5); 
                                 // round to integer!!.
            }
        }
        // sort nodes (ascending order);
        qsort(nodeX, nodes, sizeof(int), comp) ;
        // fill the pixels between node pairs.
        for (INT i = 0; i < nodes; i += 2) {
            if (nodeX[i    ] >= width) break;
            if (nodeX[i + 1] > 0) {
                if (nodeX[i    ] < 0)     nodeX[i  ] = 0 ;
                if (nodeX[i + 1] > width) nodeX[i + 1] = width;
                for (int x = nodeX[i]; x < nodeX[i + 1]; x++) 
                    SetPixel(x, y, color, image, width, height, bpp); 
                    //SetPixel()은 다른 프로토타입을 가질 수 있다.
            }
        }
    } 
    delete[] nodeX;
};

사용자 삽입 이미지

/**
** http://blog.naver.com/helloktk/80050645334 에서 옮김.
*/

'Computational Geometry' 카테고리의 다른 글

Polygon Triangulation (II)  (0) 2008.05.26
Polygon Triangulation  (4) 2008.05.25
Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Trapezoidalization  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요