OpenGL中認為合法的多邊形必須是凸多邊形，凹多邊形、自交多邊形、帶孔的多邊形等非凸的多邊形在OpenGL中繪制會出現出乎意料的結果。例如，在大多數系統中，隻有多邊形的凸包被填充，而在有些系統中，并非所有的凸包都被填充。OpenGL之是以對合法多邊形類型做出限制，是為了更友善地提供能夠對符合條件的多邊形進行快速渲染的硬體。簡單多邊形可被快速地渲染，而複雜多邊形難以快速檢測出來。為了最大限度的提高性能，OpenGL假定多邊形是簡單的。
解決凹多邊形渲染的方法有以下幾種：
第一種解決方案：多邊形網格化法 - 已實作并測試
對于非簡單多邊形、非凸多邊形或有洞的多邊形，OpenGL在GLU庫中提供了一個多邊形網格化對象GLUtesselator，對多邊形進行網格化————将它們分解成一組簡單的、能夠進行渲染的OpenGL多邊形。
經測試這種方法對凹凸多邊形和自交、帶孔多邊形都能正确的渲染。
第二種解決方案：模闆緩沖法stencil Buffer - 以實作并測試
// 具體流程闡述：
// 1.申請模闆緩存區 為了使用OpenGL的模闆功能，首先必須使用平台特定的OpenGL設定過程請求一個模闆緩存區。在以VC++.NET為基礎的OpenGL平台中，是在設定像素格式時在PIXELFORMATDESCRIPTOR結構中指定的模闆緩存，并且需要指定模闆緩存的位數。如果使用GLUT，在初始化顯示模式時請求一個模闆緩存區，下面的代碼設定了帶模闆緩存的雙緩存RGB顔色緩存區： glutInitDisplayMode(GLUT_RGB|GLUT_DOUBLE|GLUT_STENCIL)。如果使用了全屏反走樣功能，wglChoosePixelFormatARB 使用的參數 中
int iAttributes[] =
{
WGL_DRAW_TO_WINDOW_ARB,GL_TRUE,
WGL_SUPPORT_OPENGL_ARB,GL_TRUE,
WGL_ACCELERATION_ARB,WGL_FULL_ACCELERATION_ARB,
WGL_COLOR_BITS_ARB,24,
WGL_ALPHA_BITS_ARB,8,
WGL_DEPTH_BITS_ARB,16,
WGL_STENCIL_BITS_ARB,8,
WGL_DOUBLE_BUFFER_ARB,GL_TRUE,
WGL_SAMPLE_BUFFERS_ARB,GL_TRUE,
WGL_SAMPLES_ARB,4,
0,0
};
WGL_STENCIL_BITS_ARB後面的參數決不能為0，用8就可以。
// 2. 首先清除模闆緩存，并禁用顔色緩存的寫入狀态glColorMask(GL_FALSE,GL_FALSE,GL_FALSE,GL_FALSE)，将模闆緩存操作函數設定為GL_INVERT,glStencilFunc(GL_ALWAYS, 0x1, 0x1); glStencilOp(GL_KEEP, GL_KEEP, GL_INVERT);
// 3. 任取一個點P（這裡取所有點的平均坐标，也可以是非第一個點的），繪制三角扇，注意首末點要是同一個點，這樣繪制所有三角形後，像素被覆寫偶數次相應的模闆緩存值為零，否則非零
// 4. 恢複狀态glEnable(GL_DEPTH_TEST); 設定模闆緩存函數glStencilFunc(GL_NOTEQUAL,0,0x1); glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP); glColorMask(GL_TRUE,GL_TRUE,GL_TRUE,GL_TRUE);
// 繪制一個大的覆寫所有區域的多邊形（我用的是四邊形），隻繪制模闆緩存為非零的像素，OK效果達到
// 5. 使用顯示清單加快渲染速度
經測試這種方法對凹凸多邊形和自交、帶孔多邊形都能正确的渲染。
第三種解決方案: 凹多邊形凸分解法
思路： 使用算法将凹多邊形分解為多個凸多邊形或一系列的三角形，然後進行渲染。
這種思路對于由一條邊組成的凹多邊形還是可行的，但對于自交和帶孔的多邊形複雜度會很大，很難解決所有問題，是以就沒有再深入寫下去了，把我找到的一個算法附在下面，有興趣的同志可以繼續做下去，有成果的話記得發給我一份呀，O(∩_∩)O~
一個三角化多邊形的算法
在使用OpenGL畫圖的過程中，由于OpenGL不支援直接繪制凹多邊形，是以我們通常需要先将凹多邊形轉化為一組三角形下面就是一個三角化多邊形的算法
1) 用單向循環連結清單儲存多邊形頂點,并計算這個連結清單中每一個頂點的凸凹性。
2) 在循環連結清單中順序取三個結點P、Q、R ,如果Q 為凸點,并且由P、Q、R 所構成的三角形PQR不包含多邊形上其他頂點,則計算△PQR 的特征角(三角形内最小的角)。求出所有這樣的三角形,從中選擇特征角最大的△PQR ,儲存該三角形,并從連結清單中删去結點Q。
3) 如果連結清單中不存在三個以上頂點,則轉步驟2)。
4) 由連結清單中的最後三個頂點構成一個三角形。
實作代碼貢獻給大家吧：
……
// 設定像素格式
static PIXELFORMATDESCRIPTOR pfd= // pfd Tells Windows How We Want Things To Be
{
sizeof(PIXELFORMATDESCRIPTOR), // Size Of This Pixel Format Descriptor
1, // Version Number
PFD_DRAW_TO_WINDOW | // Format Must Support Window
PFD_SUPPORT_OPENGL | // Format Must Support OpenGL
PFD_DOUBLEBUFFER, // Must Support Double Buffering
PFD_TYPE_RGBA, // Request An RGBA Format
bits, // Select Our Color Depth
0, 0, 0, 0, 0, 0, // Color Bits Ignored
0, // No Alpha Buffer
0, // Shift Bit Ignored
0, // No Accumulation Buffer
0, 0, 0, 0, // Accumulation Bits Ignored
16, // 16Bit Z-Buffer (Depth Buffer)
1, // Use Stencil Buffer ( * Important * ) -------此處必須為1！！！
0, // No Auxiliary Buffer
PFD_MAIN_PLANE, // Main Drawing Layer
0, // Reserved
0, 0, 0 // Layer Masks Ignored
};
……
GLuint nTesselatorList = 0;
void CALLBACK beginCallback(GLenum which)
{
glBegin(which);
}
void CALLBACK errorCallback(GLenum errorCode)
{
const GLubyte *estring;
estring = gluErrorString(errorCode);
fprintf(stderr, "Tessellation Error: %s\n", estring);
exit(0);
}
void CALLBACK endCallback(void)
{
glEnd();
}
void CALLBACK vertexCallback(GLvoid *vertex)
{
const GLdouble *pointer;
pointer = (GLdouble *) vertex;
glColor3dv(pointer+3);
glVertex3dv(pointer);
}
void CALLBACK combineCallback(GLdouble coords[3],
GLdouble *vertex_data[4],
GLfloat weight[4], GLdouble **dataOut )
{
GLdouble *vertex;
int i;
vertex = (GLdouble *) malloc(6 * sizeof(GLdouble));
vertex[0] = coords[0];
vertex[1] = coords[1];
vertex[2] = coords[2];
for (i = 3; i < 7; i++)
vertex[i] = weight[0] * vertex_data[0][i]
+ weight[1] * vertex_data[1][i]
+ weight[2] * vertex_data[2][i]
+ weight[3] * vertex_data[3][i];
*dataOut = vertex;
}
void _polygonRender(int mode)
{// 多邊形渲染器
// define concave quad data (vertices only)
// 0 2
// \ \/ /
// \3 /
// \/
// 1
//GLdouble quad1[4][3] = { {-1,3,0}, {0,0,0}, {1,3,0}, {0,2,0} };
GLdouble quad1[4][3] = { {-1,1,2}, {0,0,2}, {1,1,2}, {0,0.7,2} };
// define concave quad with a hole
// 0--------3
// | 4----7 |
// | | | |
// | 5----6 |
// 1--------2
GLdouble quad2[12][3] = { {-2,3,0}, {-2,0,0}, {2,0,0}, { 2,3,0},
{-1,2,0}, {-1,1,0}, {1,1,0}, { 1,2,0}
, {-0.5,1,0}, {-0.5,2,0}, {0.5,2,0}, { 0.5,1,0} };
if (mode == 0)
{// 多邊形網格化對象渲染
if (nTesselatorList == 0)
{
nTesselatorList = glGenLists(1);
// 方法1: 多邊形網格化 (測試通過)
// 檢測glu版本
const GLubyte * pgluVersion = gluGetString(GLU_VERSION);
GLUtesselator* tobj = gluNewTess();
if (!tobj) return;
gluTessCallback(tobj, GLU_TESS_VERTEX, (void (CALLBACK *)())vertexCallback);
gluTessCallback(tobj, GLU_TESS_BEGIN, (void (CALLBACK *)())beginCallback);
gluTessCallback(tobj, GLU_TESS_END, (void (CALLBACK *)())endCallback);
gluTessCallback(tobj, GLU_TESS_ERROR, (void (CALLBACK *)())errorCallback);
gluTessCallback(tobj, GLU_TESS_COMBINE, (void (CALLBACK *)())combineCallback);
glNewList(nTesselatorList,GL_COMPILE);
//glShadeModel(GL_FLAT);
//gluTessProperty(tobj,GLU_TESS_WINDING_RULE,GLU_TESS_WINDING_POSITIVE); //GLU_TESS_WINDING_ODD
gluTessBeginPolygon(tobj,NULL);
gluTessBeginContour(tobj);
gluTessVertex(tobj, quad2[0], quad2[0]);
gluTessVertex(tobj, quad2[1], quad2[1]);
gluTessVertex(tobj, quad2[2], quad2[2]);
gluTessVertex(tobj, quad2[3], quad2[3]);
gluTessEndContour(tobj);
gluTessBeginContour(tobj); // inner quad (hole)
gluTessVertex(tobj, quad2[4], quad2[4]);
gluTessVertex(tobj, quad2[5], quad2[5]);
gluTessVertex(tobj, quad2[6], quad2[6]);
gluTessVertex(tobj, quad2[7], quad2[7]);
gluTessEndContour(tobj);
//gluTessBeginContour(tobj); // inner quad (hole)
//gluTessVertex(tobj, quad2[8], quad2[8]);
//gluTessVertex(tobj, quad2[9], quad2[9]);
//gluTessVertex(tobj, quad2[10], quad2[10]);
//gluTessVertex(tobj, quad2[11], quad2[11]);
//gluTessEndContour(tobj);
//gluTessBeginContour(tobj);
//gluTessVertex(tobj, quad1[0], quad1[0]);
//gluTessVertex(tobj, quad1[1], quad1[1]);
//gluTessVertex(tobj, quad1[2], quad1[2]);
//gluTessVertex(tobj, quad1[3], quad1[3]);
//gluTessEndContour(tobj);
gluTessEndPolygon(tobj);
gluDeleteTess(tobj);
glEndList();
}
else
{
glCallList(nTesselatorList);
}
}
else if (mode == 1)
{// 蒙闆緩沖
glClear(GL_STENCIL_BUFFER_BIT);
glClearStencil(0x0);
glEnable(GL_STENCIL_TEST);
glColorMask(GL_FALSE,GL_FALSE,GL_FALSE,GL_FALSE); // 禁用顔色緩存寫入 重要！！
// 設定模闆緩存操作函數為GL_INVERT
glStencilFunc(GL_ALWAYS, 0x1, 0x1);
glStencilOp(GL_KEEP, GL_KEEP, GL_INVERT);
glDisable(GL_DEPTH_TEST); // 禁用深度緩存 重要！！
GLdouble center[3];
center[0] = (quad1[0][0] + quad1[1][0] + quad1[2][0] + quad1[3][0]) / 4.0;
center[1] = (quad1[0][1] + quad1[1][1] + quad1[2][1] + quad1[3][1]) / 4.0;
center[2] = (quad1[0][2] + quad1[1][2] + quad1[2][2] + quad1[3][2]) / 4.0;
//center[0] = quad2[1][0];
//center[1] = quad2[1][1];
center[2] = quad2[1][2];
// 繪制多邊形
glBegin(GL_TRIANGLE_FAN);
glVertex3dv(center);
//glVertex3dv(quad1[0]);
//glVertex3dv(quad1[1]);
//glVertex3dv(quad1[2]);
//glVertex3dv(quad1[3]);
//glVertex3dv(quad1[0]);
glVertex3dv(quad2[0]);
glVertex3dv(quad2[1]);
glVertex3dv(quad2[2]);
glVertex3dv(quad2[3]);
glVertex3dv(quad2[0]);
glEnd();
glBegin(GL_TRIANGLE_FAN);
glVertex3dv(center);
glVertex3dv(quad2[4]);
glVertex3dv(quad2[5]);
glVertex3dv(quad2[6]);
glVertex3dv(quad2[7]);
glVertex3dv(quad2[4]);
glEnd();
GLdouble quad3[4][3] = { {-2,6,0}, {0,0,0}, {2,6,0}, {0,4,0} };
glEnable(GL_DEPTH_TEST);
// 重繪多邊形,隻繪制模闆緩存值非0的像素
glStencilFunc(GL_NOTEQUAL,0,0x1);
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
//glStencilOp(GL_REPLACE, GL_REPLACE, GL_REPLACE);
glColorMask(GL_TRUE,GL_TRUE,GL_TRUE,GL_TRUE); // 重要！！
// 再繪制一次所有的三角面片
glBegin(GL_TRIANGLE_FAN);
glVertex3dv(center);
//glVertex3dv(quad1[0]);
//glVertex3dv(quad1[1]);
//glVertex3dv(quad1[2]);
//glVertex3dv(quad1[3]);
//glVertex3dv(quad1[0]);
glVertex3dv(quad2[0]);
glVertex3dv(quad2[1]);
glVertex3dv(quad2[2]);
glVertex3dv(quad2[3]);
glVertex3dv(quad2[0]);
glEnd();
glDisable(GL_STENCIL_TEST);
glEndList();
}
else if(mode == 2)
{// 算法實作 凹多邊形凸分解算法
}
}
另附 ： 判斷多邊形凹凸性的函數以供參考
// 傳回值為true,表示該多邊形為凹多邊形，否則為凸多邊形。
BOOL IsConcavePolygon(IGPolygon * poly)
{ // 思路:
// 把兩個邊作為向量：進行差積
// 然後按下列規則判斷：
// 如果全部大于等于零則是凸多邊形。
// 如果全為零，則是所有邊共線；
// 小于零則表明是凹多邊形；
if (!poly)
return FALSE;
long pathcount;
GLdouble coord[3];
poly->get_PathCount(&pathcount);
IGPath *path = NULL;
if (pathcount < 1)
{// 至少要有一條曲線
return FALSE;
}
else if (pathcount < 2)
{// 一條曲線圍成的多邊形
std::vector<GLdouble> nodeArray;
for (long i = 0; i < pathcount; i++)
{// 閉合曲線數量==1
poly->GetPath(i,&path);
long nodecount;
path->get_NodeCount(&nodecount);
if (nodecount < 3)// 不足3個點無法組成面
continue;
IGNode *node = NULL;
for (long j = 0; j < nodecount; j++)
{// 曲線上節點數
path->GetNode(j,&node);
if (!node) continue;
node->get_X(&coord[0]);
node->get_Y(&coord[1]);
node->get_Z(&coord[2]);
nodeArray.push_back(coord[0]);
nodeArray.push_back(coord[1]);
nodeArray.push_back(coord[2]);
node->Release();
}
}
// 起點和終點要重合(系統做多邊形時已經将其首尾坐标重合了)
//nodeArray.push_back(nodeArray.at(0));
//nodeArray.push_back(nodeArray.at(1));
//nodeArray.push_back(nodeArray.at(2));
// 判斷凹凸性
int node_size = nodeArray.size() / 3;
for (int i = 0; i < node_size-1; i++)
{
GLdouble res = Dot(nodeArray[i*3],nodeArray[i*3+1],nodeArray[i*3+2],
nodeArray[(i+1)*3],nodeArray[(i+1)*3]+1,nodeArray[(i+1)*3]+2);
if (res < 0) // 凹多邊形
{
nodeArray.clear();
return TRUE;
}
}
nodeArray.clear();
}
else
{// 多條曲線圍成的多邊形 - 還有問題
// 思路： 第一重判斷 ： 組成多邊形的的閉合曲線中任意一條圍成的是凹多邊形，則為凹多邊形
// 第二重判斷 ： （簡單判斷，并不準确，但速度快） 判斷每條曲線的範圍矩形是否相交或包含，是則為凹多邊形，否則為凸多邊形
// 多條閉合曲線組成凹多邊形兩兩不想交這種情況存在嗎？ 也許隻有飛地适合這種情況如：本土和飛地不直接相連
// 暫時認為凡是由多條曲線組成的多邊形都是凹多邊形 2010.5.18 ml
return TRUE;
}
// 凸多邊形
return FALSE;
}
GLdouble Dot(GLdouble x1,GLdouble y1,GLdouble z1,GLdouble x2,GLdouble y2,GLdouble z2)
{
GLdouble res = x1*x2 + y1*y2 + z1*z2;
return res;
}
源代碼二：（跟上面的有些不同）
///
// draw a simple concave quad
///
void draw1()
{
// define concave quad data (vertices only)
// 0 2
// \ \/ /
// \3 /
// \/
// 1
GLdouble quad1[4][3] = { {-1,3,0}, {0,0,0}, {1,3,0}, {0,2,0} };
// We are going to do 2-pass draw: draw to stencil buffer first,
// then draw to color buffer.
glEnable(GL_STENCIL_TEST); // enable stencil test
// PASS 1: draw to stencil buffer only
// The reference value will be written to the stencil buffer plane if test passed
// The stencil buffer is initially set to all 0s.
glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE); // disable writing to color buffer
glStencilFunc(GL_ALWAYS, 0x1, 0x1);
glStencilOp(GL_KEEP, GL_INVERT, GL_INVERT); // 重要
glBegin(GL_TRIANGLE_FAN);
glVertex3dv(quad1[0]);
glVertex3dv(quad1[1]);
glVertex3dv(quad1[2]);
glVertex3dv(quad1[3]);
glEnd();
// PASS 2: draw color buffer
// Draw again the exact same polygon to color buffer where the stencil
// value is only odd number(1). The even(0) area will be descarded.
glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE); // enable writing to color buffer
glStencilFunc(GL_EQUAL, 0x1, 0x1); // test if it is odd(1) 重要
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
glColor3f(1,1,1);
glBegin(GL_TRIANGLE_FAN);
glVertex3dv(quad1[0]);
glVertex3dv(quad1[1]);
glVertex3dv(quad1[2]);
glVertex3dv(quad1[3]);
glEnd();
glDisable(GL_STENCIL_TEST);
}
///
// draw a polygon with a hole
///
void draw2()
{
// define concave quad with a hole
// 0--------3
// | 4----7 |
// | | | |
// | 5----6 |
// 1--------2
GLdouble quad2[8][3] = { {-2,3,0}, {-2,0,0}, {2,0,0}, { 2,3,0},
{-1,2,0}, {-1,1,0}, {1,1,0}, { 1,2,0} };
glEnable(GL_STENCIL_TEST); // enable stencil test
// PASS 1: draw to stencil buffer only
glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE); // disable writing to color buffer
glStencilFunc(GL_ALWAYS, 0x1, 0x1);
glStencilOp(GL_KEEP, GL_INVERT, GL_INVERT);
// outer contour
glBegin(GL_TRIANGLE_FAN);
glVertex3dv(quad2[0]);
glVertex3dv(quad2[1]);
glVertex3dv(quad2[2]);
glVertex3dv(quad2[3]);
glEnd();
//inner contour
glBegin(GL_TRIANGLE_FAN);
glVertex3dv(quad2[4]);
glVertex3dv(quad2[5]);
glVertex3dv(quad2[6]);
glVertex3dv(quad2[7]);
glEnd();
// PASS 2: draw color buffer
glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE); // enable writing to color buffer
glStencilFunc(GL_EQUAL, 0x1, 0x1); // test if it is odd(1)
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
glColor3f(1,1,1);
// outer contour
glBegin(GL_TRIANGLE_FAN);
glVertex3dv(quad2[0]);
glVertex3dv(quad2[1]);
glVertex3dv(quad2[2]);
glVertex3dv(quad2[3]);
glEnd();
//inner contour
glBegin(GL_TRIANGLE_FAN);
glVertex3dv(quad2[4]);
glVertex3dv(quad2[5]);
glVertex3dv(quad2[6]);
glVertex3dv(quad2[7]);
glEnd();
}
///
// draw a self-intersecting polygon (star)
///
void draw3()
{
// define self-intersecting star shape (with color)
// 0
// / \
//3---+---+---2
// \ | | /
// \| |/
// + +
// |\ /|
// | + |
// |/ \|
// 1 4
GLdouble star[5][6] = { { 0.0, 3.0, 0, 1, 0, 0}, // 0: x,y,z,r,g,b
{-1.0, 0.0, 0, 0, 1, 0}, // 1:
{ 1.6, 1.9, 0, 1, 0, 1}, // 2:
{-1.6, 1.9, 0, 1, 1, 0}, // 3:
{ 1.0, 0.0, 0, 0, 0, 1} }; // 4:
glEnable(GL_STENCIL_TEST); // enable stencil test
// PASS 1: draw to stencil buffer only
glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE); // disable writing to color buffer
glStencilFunc(GL_ALWAYS, 0x1, 0x1);
glStencilOp(GL_KEEP, GL_INVERT, GL_INVERT);
glBegin(GL_TRIANGLE_FAN);
glColor3dv(star[0]+3);
glVertex3dv(star[0]);
glColor3dv(star[1]+3);
glVertex3dv(star[1]);
glColor3dv(star[2]+3);
glVertex3dv(star[2]);
glColor3dv(star[3]+3);
glVertex3dv(star[3]);
glColor3dv(star[4]+3);
glVertex3dv(star[4]);
glEnd();
// PASS 2: draw color buffer
glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE); // enable writing to color buffer
glStencilFunc(GL_EQUAL, 0x1, 0x1); // test if it is odd(1)
glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
glColor3f(1,1,1);
glDisable(GL_DEPTH_TEST);
glBegin(GL_TRIANGLE_FAN);
glColor3dv(star[0]+3);
glVertex3dv(star[0]);
glColor3dv(star[1]+3);
glVertex3dv(star[1]);
glColor3dv(star[2]+3);
glVertex3dv(star[2]);
glColor3dv(star[3]+3);
glVertex3dv(star[3]);
glColor3dv(star[4]+3);
glVertex3dv(star[4]);
glEnd();
glEnable(GL_DEPTH_TEST);
}