Polygon Tessellation/Triangulation Implementations

Started by
29 comments, last by Zakwayda 13 years, 6 months ago
Quote:Original post by Yann L
In conclusion, if your code cannot handle zero area faces, then it is broken.
I think I must still be missing something here, but maybe you can help clarify.

Using the version of GLU that was included with my Windows installation (XP), I get the same results as samster581 and others. It seems to me that with these results, even without removing the zero-area triangles, rendering artifacts could result. Using the following test code:

#include <vector>#include "SDL.h"#include "SDL_opengl.h"double verts[] = {    -128, -23, 0, -128, 23, 0, -94, 23, 0, -94, 15, 0,    -119, 15, 0, -119, 5, 0, -96, 5, 0, -96, -3, 0,    -119, -3, 0, -119, -15, 0, -93, -15, 0, -93, -23, 0};std::vector<int> indices;void CALLBACK Vertex(GLvoid* index){    indices.push_back((int)index);}void CALLBACK EdgeFlag(GLboolean flag) {}void Tesselate(){    GLUtesselator* tesselator = gluNewTess();    gluTessCallback(        tesselator,        GLU_TESS_VERTEX,        reinterpret_cast<GLvoid (CALLBACK *)()>(&Vertex)    );    gluTessCallback(        tesselator,        GLU_TESS_EDGE_FLAG,        reinterpret_cast<GLvoid (CALLBACK *)()>(&EdgeFlag)    );    gluTessBeginPolygon(tesselator, 0);    gluTessBeginContour(tesselator);    for (int i = 0; i < 12; ++i) {        gluTessVertex(tesselator, &verts, (<span class="cpp-keyword">void</span>*)i);<br>    }<br>    gluTessEndContour(tesselator);<br>    gluTessEndPolygon(tesselator);<br>    gluDeleteTess(tesselator);<br>}<br><br><span class="cpp-keyword">int</span> main( <span class="cpp-keyword">int</span> argc, <span class="cpp-keyword">char</span>* args[] )<br>{<br>    Tesselate();<br><br>    SDL_Init(SDL_INIT_VIDEO);<br>    SDL_GL_SetAttribute(SDL_GL_DOUBLEBUFFER, <span class="cpp-number">1</span>);<br>    SDL_SetVideoMode(<span class="cpp-number">800</span>, <span class="cpp-number">600</span>, <span class="cpp-number">0</span>, SDL_OPENGL);<br>    glMatrixMode(GL_PROJECTION);<br>    gluOrtho2D(-<span class="cpp-number">40</span>.f, <span class="cpp-number">40</span>.f, -<span class="cpp-number">30</span>.f, <span class="cpp-number">30</span>.f);<br>    glMatrixMode(GL_MODELVIEW);<br>    glColor4f(<span class="cpp-number">1</span>.f, <span class="cpp-number">0</span>.f, <span class="cpp-number">1</span>.f, .25f);<br>    glEnable(GL_BLEND);<br>    glBlendFunc(GL_SRC_ALPHA, GL_ONE);<br>    glDisable(GL_CULL_FACE);<br><br>    <span class="cpp-keyword">bool</span> quit = <span class="cpp-keyword">false</span>;<br>    <span class="cpp-keyword">float</span> angle = <span class="cpp-number">0</span>.f;<br>    <span class="cpp-keyword">while</span> (!quit) {<br>        SDL_Event event;<br>        <span class="cpp-keyword">while</span> (SDL_PollEvent(&amp;event)) {<br>            <span class="cpp-keyword">if</span> (event.type == SDL_KEYDOWN || event.type == SDL_QUIT) {<br>                quit = <span class="cpp-keyword">true</span>;<br>            }<br>        }<br><br>        angle += .01f;<br><br>        glClear(GL_COLOR_BUFFER_BIT);<br>        glLoadIdentity();<br>        glRotatef(angle, <span class="cpp-number">0</span>.f, <span class="cpp-number">0</span>.f, <span class="cpp-number">1</span>.f);<br>        glTranslatef(<span class="cpp-number">112</span>.f, <span class="cpp-number">0</span>.f, <span class="cpp-number">0</span>.f);<br><br>        glBegin(GL_TRIANGLES);<br>        <span class="cpp-keyword">for</span> (size_t i = <span class="cpp-number">0</span>; i &lt; indices.size(); ++i) {<br>            glVertex3dv(&amp;verts[indices<span style="font-weight:bold;"> * <span class="cpp-number">3</span>]);<br>        }<br>        glEnd();<br><br><br>        SDL_GL_SwapBuffers();<br>    }<br><br>    SDL_Quit();<br><br>    <span class="cpp-keyword">return</span> <span class="cpp-number">0</span>;<br>}<br><br><br></pre></div><!–ENDSCRIPT–><br>I generated this image:<br><br><img src="http://members.gamedev.net/jyk/glu_tesselator.png"/><br><br>Note the two 'sparklies' (naturally the effect is more pronounced when the geometry is in motion).<br><br>I'll admit I tested this &#111;n some old cards (at least &#111;ne of which has sort of questionable drivers), but I tested &#111;n two different machines (Windows and OS X) with different cards and got similar results. In any case, it makes sense to me that such artifacts might occur. It seems to me that &#111;nce the orientation deviates from identity, the neighboring polygons might overlap due to numerical error, which indeed is what appears to be happening.<br><br>So if I'm understanding correctly, it sounds like you're saying that a) the zero-area faces are no problem, b) the tesselator is behaving correctly, and c) it's up to the user to handle this sort of triangulation appropriately.<br><br>It's not immediately clear to me though how the aforementioned rendering artifacts can be avoided without 'fixing' the triangulation somehow. What am I missing?

This topic is closed to new replies.

Advertisement