Tessellator에 대한 고찰

Tessellator에 대한 고찰

삽질일기 2008/02/05 16:52

한동안 손을 놓고 있던 프로젝트에 다시 집중하기 시작.
전에 작성한 Tessellator의 버그로 인해 내부의 hole이 있는 경우나 혹은 복잡도가 높은 shape의 폴리곤의 Tessellation시 원하지 않는 결과를 출력하였다.

이 문제의 해결을 위해 다음과 같은 방안을 고려하였다.
1. OpenGL의 Tessellator를 사용한다.
2. Computational Geometry에서 연구된 Tessellator를 조사하여 사용한다.

일단 쉬워 보이는 OpenGL의 Tessellator를 사용해 보았다.

프로그래밍 튜토리얼은 아니지만 일단 간단히 코드를 보면 아래와 같다.

GLUtesselator* pTess = gluNewTess();
gluTessCallback(pTess, GLU_TESS_BEGIN, (void (__stdcall*)(void))glBegin);
gluTessCallback(pTess, GLU_TESS_END, (void (__stdcall*)(void))glEnd);
gluTessCallback(pTess, GLU_TESS_VERTEX, (void (__stdcall*)(void))glVertex3dv);

gluTessProperty(pTess, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_ODD);
gluTessBeginPolygon(pTess, NULL);
gluTessBeginContour(pTess);

// polygon을 그려준다.
for(i = 0 ; i < size; i++)
    gluTessVertex(pTess, vertex[i], vertex[i]);

gluTessEndContour(pTess);
gluTessEndPolygon(pTess);

지난번에 OpenGL의 Tessellator를 사용하지 않았던 이유는 Texture Mapping이랑 함께 사용하는 법을 몰라서였는데, Texture Mapping을 적용하기 위해서는 아래와 같이하면 된다. Tessellation 함수에 Texture Coordinate를 함께 넣어준다.

gluTessCallback(pTess, GLU_TESS_VERTEX, (void (__stdcall*)(void))glVertex3dv);
gluTessCallback(pTess, GLU_TESS_VERTEX, (void (__stdcall*)(void))TessVertex);

// double lpData[5]를 받아서 처리한다.
void __stdcall TessVertex(void* lpData)
{
    double* pItem = (double*)lpData;
    glVertex3d(pItem);
    glTexCoord2dv(&pItem[3]);
{

어쨋거나 저리하여 렌더링을 돌려보니, shape이 좀 복잡해지면 느리다. 아무래도 렌더링할 때마다 Tessellator가 돌아가니 느릴 수 밖에 없는 것인가? 미리 쪼개는 수 밖에 대안이 없을 듯 하다.

차선책으로 고려했던 Computational Geometry 쪽을 찾아보았다. 간단히 구현 가능한 Ear-Cutting, FIST(Fast Industrial-Strength Triangulation of Polygon) 등이 있는데 Ear-Cutting 같은 경우는 내부에 Hole이 존재하지 않는 것을 전제로 하므로 일단 패스하고, FIST를 찾아보았다. 관심있는 사람은 아래의 링크를 참고하자.

FIST : Fast Industrial-Strength Triangulation of Polygons

다음과 같은 limitation이 있다고 한다.

• does not compute constrained Delaunay triangulations (CDT), although it tends to generate fairly "nice" triangulations, see below;
• cannot handle a 3D point cloud (e.g., to generate a surface based on data obtained from laser scanning);
• cannot handle a 2D point cloud, unless a bounding box of those points is included as input; if you need to triangulate 2D point data then you'd be better off with my Voronoi/Delaunay code Voronoi/Delaunay code "VRONI";
• cannot handle open polygonal curves (unless the curves are transformed into closed zero-area polygons placed inside of a closed polygon or bounding box);
• does not determine points of (self-)intersection of the input contour(s).

논문을 첨부하니 관심있다면 읽어보길.

triangulation.held.ps.pdf

좀 다른 이야기지만 Approximate Convex Decomposition of Polygons이라는게 있던데 이것도 시간날때 읽어둬야지.