'다각형 채우기' 태그의 글 목록

다각형 채우기

[컴퓨터그래픽스] Scanline Polygon fill 및 Boundary-4way polygon fill 2009.01.19

[컴퓨터그래픽스] Scanline Polygon fill 및 Boundary-4way polygon fill

2009. 1. 19. 13:33

이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받을 수 있습니다.

학교 과제로 제출했던 스캔라인 폴리곤 필 및 바운더리 4-웨이 폴리곤 필 ^.^

다각형채우기!!

주요 소스 코드



//━━━━━━━━━━━━━━━━━━━━━━━━┓

                          

//  ─━ 제작자 : 혼돈속의 지남차

//  ─━ 목  적 : 학교 과제

//  ─━ 과  목 : 컴퓨터 그래픽스

//  ─━ 주  제 : 다각형 색 채우기.

//  ─━ 방  법 : Scanline fill & Flood Fill

//  ─━ 날  짜 : 2008. 10. 3 03:46 AM



//━━━━━━━━━━━━━━━━━━━━━━━━┛

#include <windows.h>

#include "defines.h"  //안에 각종 헤더파일 및 define들이 쓰여져있음.

#include "GLPoints.h" //(x,y)튜플



void scanLine(vector<CGLPoints>& vecGLPoints); //vertex뭉치를 인자로 받아 ScanlineFill

// 재귀함수 이용한 version 1 (도형크기가 커지면 오버플로우 발생)

/*

void boundary_fill(int x, int y, BYTE* byBoundaryColor)
{

    cout << x << " " << y << endl;
    //현재픽셀이 테두리색이랑 같으면 중단.
    BYTE byCurrerntColor[3];
    glReadPixels(x,WINSIZEY-y,1,1,GL_RGB,GL_UNSIGNED_BYTE,byCurrerntColor);
    if((byBoundaryColor[0] == byCurrerntColor[0]
        && byBoundaryColor[1] == byCurrerntColor[1]
        && byBoundaryColor[2] == byCurrerntColor[2] )|| x<=0||WINSIZEY<=y||WINSIZEX<=x||WINSIZEY<=WINSIZEY-y || matrix[x][WINSIZEY-y] == true )
    {
        return ;
    }
    else
    {
        matrix[x][WINSIZEY-y]=true;
        glColor3f(1.0, 1.0, 0.0);
        setPixel(x,WINSIZEY-y);

boundary_fill(x+1, y, byBoundaryColor);
boundary_fill(x, y-1, byBoundaryColor);

boundary_fill(x-1, y, byBoundaryColor);
boundary_fill(x, y+1, byBoundaryColor);

}

*/

// 자체 스택을 이용한 version2 - 도형의 크기가 커도 잘 동작 !! :)
void boundary_fill(int x, int y, BYTE* byBoundaryColor)
{

stack< CGLPoints > stackStoreCoords;

stackStoreCoords.push(*(new CGLPoints(x,y)));
cout << x << " " << y << endl;
//현재픽셀이 테두리색이랑 같으면 중단.
BYTE byCurrerntColor[3];
do
{
    int nX = stackStoreCoords.top().GetX();
    int nY = stackStoreCoords.top().GetY();
    glReadPixels(nX
      ,WINSIZEY-(nY),1,1,GL_RGB,GL_UNSIGNED_BYTE,byCurrerntColor);
    if((byBoundaryColor[0] == byCurrerntColor[0]
      && byBoundaryColor[1] == byCurrerntColor[1]
      && byBoundaryColor[2] == byCurrerntColor[2] )
    )// || nX<=0 \
      ||WINSIZEY<=nY \
      ||WINSIZEX<=nX \
      ||WINSIZEY<=WINSIZEY-nY \
      || matrix[nX][WINSIZEY-nY] == true )
    {
      stackStoreCoords.pop();

    }
    else
    {
    // matrix[nX][WINSIZEY-nY]=true;
      glColor3f(1.0, 1.0, 0.0);
      setPixel(nX,WINSIZEY-nY); //점을 찍고 스택에다 4방향을 쌓는다.
      stackStoreCoords.push(*(new CGLPoints(nX+1,nY)));
      stackStoreCoords.push(*(new CGLPoints(nX,nY-1)));
      stackStoreCoords.push(*(new CGLPoints(nX-1,nY)));
      stackStoreCoords.push(*(new CGLPoints(nX,nY+1)));

    }

} while(!stackStoreCoords.empty()); //스택이 비면 루프를 빠져나온다.

}
//CGLPoints클래스를 y좌표 기준으로 정렬할때 비교함수.
bool LessByY(CGLPoints pt1, CGLPoints pt2)
{
return (pt1.GetY()<pt2.GetY());
}
//━━━━━━━━━━━━━━━━━━━━━━━━━
//      ─━   메인 시작 ━─
//━━━━━━━━━━━━━━━━━━━━━━━━━
void main(int argc, char** argv)
{
//생략
}
//━━━━━━━━━━━━━━━━━━━━━━━━━
//      ─━   함수들 정의 ━─
//━━━━━━━━━━━━━━━━━━━━━━━━━

//초기화
void init(void)
{
//생략

}

//점 찍기
void setPixel(GLint x, GLint y)
{
//생략
}

//선 긋기
void setLine(GLint x, GLint y, GLint x2, GLint y2)
{
  //생략
}

//다각형 선긋기 (점들을 인자로 받는다)
void setPolyLine(vector<CGLPoints>& vecGLPoints)
{
int nNumOfvertice = vecGLPoints.size();
int i;
for(i = 1 ; i < nNumOfvertice ; i++)
{
    setLine(vecGLPoints[i-1].GetX(), vecGLPoints[i-1].GetY(), vecGLPoints[i].GetX(), vecGLPoints[i].GetY());
}
setLine(vecGLPoints[nNumOfvertice-1].GetX(), vecGLPoints[nNumOfvertice-1].GetY(), vecGLPoints[0].GetX(), vecGLPoints[0].GetY());
}

//스캔라인 방식으로 다각형 내부 칠하기(점들을 인자로 받는다)
void scanLine(vector<CGLPoints>& vecGLPoints)
{
int i,j;
int color;
int minY, maxY;

//X좌표용
//y좌표를 키이며 x좌표를 value로 하는 맵
vector<int>* vecScanLineYCoord = new vector<int>[WINSIZEY];

CGLPoints* temp = new CGLPoints(0,0);
//다각형의 y의 최대값과 최소값을 찾는다.
temp = min_element(vecGLPoints.begin(),vecGLPoints.end(),LessByY); //최소값
minY = temp->GetY();
temp = max_element(vecGLPoints.begin(),vecGLPoints.end(),LessByY); //최대값
maxY = temp->GetY();

//최소최대값 콘솔출력(테스트용)
cout << minY << " "<< maxY << endl;

int nLenth = vecGLPoints.size(); //점들의 갯수
for(i = 1 ; i <= nLenth ; i++)
{
    //두점의 기울기를 구함.
    float fSlope = float(vecGLPoints[i-1].GetY() - vecGLPoints[i%nLenth].GetY())
            / float(vecGLPoints[i-1].GetX() - vecGLPoints[i%nLenth].GetX());
    //두점의 직선의 방정식의 y절편
    // y-y2 == (y2-y1)/(x2-x1) * (x-x2) where x == 0
    float yInterCept = fSlope*(-vecGLPoints[i-1].GetX())+vecGLPoints[i-1].GetY();
    //for문을 올바로 돌리기 위해 두 vertex의 y좌표 대소비교한다.
    int minimum, maximum;
    if(vecGLPoints[i-1].GetY()<vecGLPoints[i%nLenth].GetY())
    {
      minimum = vecGLPoints[i-1].GetY();
      maximum = vecGLPoints[i%nLenth].GetY();
    }
    else
    {
      minimum = vecGLPoints[i%nLenth].GetY();
      maximum = vecGLPoints[i-1].GetY();
    }
    for(j = minimum ; j < maximum ; j++ )
    {
      // j는 y좌표이며 x좌표는 y좌표에 절편을 뺀값을 (1/기울기)를 곱해주면 나온다. (y = mx + b 에서도출)
      vecScanLineYCoord[j].push_back((j-yInterCept)*(1.0f/fSlope));
    }

}

//각 scanLine y좌표에에 저장된 x좌표들을 오름차순으로 정렬한다.
for(i = minY ; i <= maxY ; i++)
    sort(vecScanLineYCoord[i].begin(),vecScanLineYCoord[i].end());

//스캔라인의 최소값에서 최대값까지
for(i = minY ; i < maxY ; i++)
{

    //정렬된 X좌표들의 PAIR들을 선을 그어 폴리곤에 색을 채운다.
    int nSize = vecScanLineYCoord[i].size();
    for(j = 0 ; j < nSize ; j+=2)
    {

      //콘솔 테스트 출력
//      cout << "scanLine Y : " << i << "X좌표 Pair : " \
        <<vecScanLineYCoord[i][j%nSize] << " "<< vecScanLineYCoord[i][(j+1)%nSize] << endl;
      setLine(vecScanLineYCoord[i][j%nSize],i,vecScanLineYCoord[i][(j+1)%nSize],i);//선긋기
    }
}
}
void displayFunc(void)
{
int i;
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(1.0, 1.0, 0.0);
// (x,y)튜플들을 가질수 있는 벡터선언
vector<CGLPoints> vecPtVertice;

//랜덤도형
srand(GetTickCount());
// for(i = 0 ; i < 100 ; i++)
//    vecPtVertice.push_back(*(new CGLPoints(rand()%WINSIZEX, rand()%WINSIZEY)     ));

//큰도형
vecPtVertice.push_back(*(new CGLPoints(100,400)));
vecPtVertice.push_back(*(new CGLPoints(300,200)));
vecPtVertice.push_back(*(new CGLPoints(500,100)));
vecPtVertice.push_back(*(new CGLPoints(700,300)));
vecPtVertice.push_back(*(new CGLPoints(500,500)));
vecPtVertice.push_back(*(new CGLPoints(400,350)));
vecPtVertice.push_back(*(new CGLPoints(300,600)));

//작은도형
/*
vecPtVertice.push_back(*(new CGLPoints(226, 143)));
vecPtVertice.push_back(*(new CGLPoints(216, 174)));
vecPtVertice.push_back(*(new CGLPoints(270, 184)));
vecPtVertice.push_back(*(new CGLPoints(287, 139)));
vecPtVertice.push_back(*(new CGLPoints(247, 132)));
*/
//테두리
setPolyLine(vecPtVertice);

if(g_MouseState.rightButton == true)
    scanLine(vecPtVertice); //스캔라인으로 다각형을 채운다. (인자로 vertice넘김)

//마우스를 클릭하면 해당영역부터 Boundary_fill 시작.
if(g_MouseState.leftButton==true)
{
    glColor3f(1.0, 1.0, 0.0);
    BYTE byBoundaryColor[3]={255,255,0};
    DWORD dwBegin = GetTickCount();
    boundary_fill(g_MouseState.x,g_MouseState.y,byBoundaryColor);
    DWORD dwEnd    = GetTickCount();
    cout << "Boundary_FILL 소요시간 : " << float((dwEnd - dwBegin)/1000.0f) << endl;
}
glFlush();

}

void HandleMouseState(int button, int state, int x, int y)
{
//생략
}

실 행 화 면

Boundary Fill을 이용

재귀함수를 이용한 Boundary_fill

그림1) 이 정도 크기는 문제없다

그림2) 프로그램이 멎어버린다.

그러나 이 재귀함수의 문제점은 폴리곤의 크기가 시스템 스택이 저장할 수 있는 임계값을 넘으면 Stack Overflow가 나서
더 이상 진행을 못하고 프로그램 자체가 죽어버린다.

그래서 자체적인 스택을 구현해야하는데 (힙 메모리를 써서 한계값이 훨씬 큼) STL의 stack을 썼다.

그림3> 자체적인 스택을 이용한 비교적 큰 사이즈의 도형 색채우기.

Scanline 이용하여 채우기.

같은 도형으로 실험했을때 똑같이 채워졌다.
차이점이라면 수행속도는 0초에 가깝게 훨씬 빠르게 채워졌다.

점 백개를 랜덤으로 찍어 올바르게 수행하는지 테스트 했다.

도형의 내부 외부를 잘 구분하여 올바르게 색칠이 되었다.

Discussion

똑같은 도형을 다른 두 방식으로 채웠을때 수행시간

두 방식은 소요시간에서 엄청난 차이가 난다.

Scanline_fill 같은 경우는 직선의 방정식을 이용한 coherence 특징을 이용해서 거의 0초에 가깝게 나왔지만
Boundary_fill 같은 경우는 픽셀하나씩 찍을때 마다 glReadPixels를 호출하기 때문에 그에 따른 오버헤드 및 한점 한점 처리를 하기 때문에 21~24초에 가까운 시간이 걸렸다.(실행화면에 있는 큰 도형의 경우)

구현시 어려웠던 점은 glReadPixels의 y인자를 창의 Y크기에서 뺀 값을 넣어줘야 올바르게 작동하는 것이었다.
이 것 때문에 수 구현상 수 많은 시행착오를 겪었다.
OPENGL에서는 맨 아래가 y좌표 0인 반면 윈도우상에서 실제로 디스플레이 될 때는 맨 윗쪽이 0으로 찍혔다.

Scanline_fill 구현 시 ,두 점의 직선의 방정식을 이용 y-y1 = (y2-y1)/(x2-x1)(x-x1)
두 점 사이에서 스캔라인값을 1증가 혹은 감소 시킬때 x값을 추정후 그 x값의 y인덱스에 x의 밸류를 넣어주고
다른점들에 대해서도 이와 같이 반복후 스캔라인의 특정 vector를 sort한후 pair를 이루게 하여 선을 그어주었다.

원래 좀 더 직관적인 방법인 아래에서 부터 픽셀하나하나 검사하며 점을 만나면 그리기 시작하고 다시 만나면 그리기를 중단하는 식으로 할려고 했으나 시간도 많이 걸리고 예외사항이 너무 많이 나와서 "직관적"이긴 하지만 구현시에는
coherence 를 이용한 방법보다 더 많은 수고로움이 필요했다. (실제로 OPENGL을 이용하여 선을 그으면 x좌표에 각도에 따라 2개이상의 점이 찍히는 경우가 있기때문에 책에서 나온 예외사항 외에도 생각할 거리가 많다.)

Boundary fill 이 도형크기에 따라 시간이 달리 소요되긴 하지만 위의 실험에서 23초쯔음 걸리는것을 보고 약간 의문점이 드는것이 , 포통 Graphic 툴에서도 Boundary_fill 이나 숙제엔 나오지 않은 Flood_fill 같은 방법 또한 사용할텐데
어떻게 그렇게 짧은 순간에 다각형을 칠할 수 있는지 궁금해졌다.

이번 과제를 통해 보너스로 STL에서 제공하는 vector 및 stack에 대해서 좀 더 친숙해질 수 있었고 새삼 상용그래픽툴의 위대함을 느끼게 되었다.

PREV 1 NEXT

🙇세상의 중심🌐

다각형 채우기

[컴퓨터그래픽스] Scanline Polygon fill 및 Boundary-4way polygon fill

+ Recent posts

티스토리툴바