iDevGames Forums
gluTesselate questions - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Graphics & Audio Programming (/forum-9.html)
+--- Thread: gluTesselate questions (/thread-2707.html)



gluTesselate questions - TomorrowPlusX - Mar 20, 2008 01:16 PM

I'm about to use gluTesselate to do, well obviously, do some tesselation. I know there are better frameworks for triangulation out there and I may check them out, but for right now I just want to get some triangles up so I can see if my code generating contours is any good.

So first, can anybody point me to some good documentation on it? I've googled, but had very little luck. Fortunately I have the OpenGL SuperBible which has a section on it, so I'm not completely in the dark.

Secondly, and this is the big one, I'm curious about how how it handles contours in 3D. The samples I've seen seem biased towards 2D poly tesselation, and in principle what I'm doing can be massaged into this context, but there are some situations where 3d is requisite.

it's best described this way. Say you have two circular line loops made up of the same points along x&y, but which have different z coords. This would intuitively be triangulated into a cylinder. gluTesselate seems to take an odd-even rule for filling contours, and I think it wouldn't work in this situation since the loops are colinear. However, if one of the line loops were smaller ( making not a cylinder but a truncated cone ) I could see the even-odd system working fine.

Is there a way to make the cylindrical situation work?

Obviously, I'm not triangulating cylinders, but the data I expect to triangulate is a pile of contours coming from voxel space. Most of the time the even-odd approach will work, but I expect colinear line segments to be unavoidable, and I should be able to handle them.

Any suggestions would be appreciated!


gluTesselate questions - AnotherJake - Mar 20, 2008 10:06 PM

You lost me at voxel space.Wink

I don't know (or rather remember) about performance with non-co-planar vertices on any given n-sided face though (if that's what you were asking about).

I will say this: Documentation I found on glu tess routines was very hard to come by and I don't remember any of it being any good. In fact, I pretty much had to figure it out on my own by experimentation and extrapolation between docs. Even the Red Book's (third edition) explanation was either wrong or misleading (don't remember which, but maybe both).

I don't remember enough off-hand to say how it works, but it wasn't very complicated at all once I fit the pieces together -- which is how I dare claim with such apparent and reckless authority that all existing documentation sucks.

Some hints that I discovered (and sort of remember right now), which might help decode the voodoo that is glu tessellation:

1) Don't believe everything you read about it, or allow it to mislead your thinking about how it works because just about all the docs try to describe it the same goofy way.

2) Which relates heavily to point 1 -- don't forget that glu routines need have NOTHING to do with gl routines. They can stand all on there own. So what I'm saying is that you will read lots of tutorials and docs using display lists. Forget about the display lists or OpenGL. You can use glu routines all on their own, no context needed or anything else at all. You can use it with DirectX if you wish. I found it very hard to find documentation assuming you wouldn't want to tessellate directly into a display list (as I recall at the moment).

3) The Mac implementation of the glu tess callbacks apparently do not work according to spec, or at least do not behave like other platforms. I still don't understand what is up with that. It's probably my fault (as usual), but here is my actual GLU_TESS_COMBINE_DATA callback, with relevant comments:

Code:
static void TessCombineCallback(GLdouble coords[3], VertexData *vertex_data[4], GLfloat weight[4], VertexData **dataOut, MyObjLoader *objLoader)
{
    VertexData    *vertexData;
    float        normalize;
    
    vertexData = malloc(sizeof(VertexData));
    vertexData->vertex[0] = coords[0];
    vertexData->vertex[1] = coords[1];
    vertexData->vertex[2] = coords[2];
    
    // - assume they all have at least two vertices to combine. need to check for nil to include any more,
    // even though the spec says they're supposed to be valid (I have received nil values on at least one occasion during testing)
    // - also, the spec says to release the malloc'd memory yourself, but uh, I get a double free error if I try that, so GLU must
    // be doing that itself
    vertexData->texCoord[0] =    vertex_data[0]->texCoord[0] * weight[0] +
                                vertex_data[1]->texCoord[0] * weight[1];
    vertexData->texCoord[1] =    vertex_data[0]->texCoord[1] * weight[0] +
                                vertex_data[1]->texCoord[1] * weight[1];
    if (vertex_data[2] != nil)
    {
        vertexData->texCoord[0] += vertex_data[2]->texCoord[0] * weight[2];
        vertexData->texCoord[1] += vertex_data[2]->texCoord[1] * weight[2];
    }
    if (vertex_data[3] != nil)
    {
        vertexData->texCoord[0] += vertex_data[3]->texCoord[0] * weight[3];
        vertexData->texCoord[1] += vertex_data[3]->texCoord[1] * weight[3];
    }
    
    // just do a simple weighted interpolation for the normals, then renormalize
    vertexData->normal[0] =        vertex_data[0]->normal[0] * weight[0] +
                                vertex_data[1]->normal[0] * weight[1];
    vertexData->normal[1] =        vertex_data[0]->normal[1] * weight[0] +
                                vertex_data[1]->normal[1] * weight[1];
    vertexData->normal[2] =        vertex_data[0]->normal[2] * weight[0] +
                                vertex_data[1]->normal[2] * weight[1];
    if (vertex_data[2] != nil)
    {
        vertexData->normal[0] += vertex_data[2]->normal[0] * weight[2];
        vertexData->normal[1] += vertex_data[2]->normal[1] * weight[2];
        vertexData->normal[2] += vertex_data[2]->normal[2] * weight[2];
    }
    if (vertex_data[3] != nil)
    {
        vertexData->normal[0] += vertex_data[3]->normal[0] * weight[3];
        vertexData->normal[1] += vertex_data[3]->normal[1] * weight[3];
        vertexData->normal[2] += vertex_data[3]->normal[2] * weight[3];
    }
    normalize = 1.0f / sqrtf(    vertexData->normal[0] * vertexData->normal[0] +
                                vertexData->normal[1] * vertexData->normal[1] +
                                vertexData->normal[2] * vertexData->normal[2]);    
    vertexData->normal[0] *= normalize;
    vertexData->normal[1] *= normalize;
    vertexData->normal[2] *= normalize;
    *dataOut = vertexData;
}


In the end, my implementation uses very few glu calls. Here are some snippets which are pretty much everything to do with glu.:

Code:
...
    tobj = gluNewTess();
    gluTessCallback(tobj, GLU_TESS_VERTEX_DATA, TessVertexCallback);
    gluTessCallback(tobj, GLU_TESS_BEGIN_DATA, TessBeginCallback);
    gluTessCallback(tobj, GLU_TESS_ERROR_DATA, TessErrorCallback);
    gluTessCallback(tobj, GLU_TESS_COMBINE_DATA, TessCombineCallback);
...

// - use the GLU tessellator for any face with more than four sides
                // - NOTE: I don't know if GLU is thread safe, so maybe a lock here might help if there are problems
                // - sending self as the user data will allow the callbacks to reference back to self and stay object-oriented,
                // see the function callbacks below on how that's done (it's real easy)
                gluTessBeginPolygon(tobj, self);
                    gluTessBeginContour(tobj);
                    vertexData = firstVertex;
                    while (vertexData)
                    {
                        gluTessVertex(tobj, vertexData->vertex, vertexData);
                        vertexData = vertexData->next;
                    }
                    gluTessEndContour(tobj);
                gluTessEndPolygon(tobj);
...


- (void)tessErrorCallBack:(GLenum)errorCode
{
    FatalError("Encountered a tessellation error while processing %s.\n\n"
                    "GLU error:\n %s", [objName UTF8String], gluErrorString(errorCode));
}

- (void)tessBeginCallback:(GLenum)renderingMode
{
    currMode = renderingMode;
    tessVert = 1;
}

- (void)tessVertexCallback:(VertexData *)vertexData
{
    if (currMode == GL_TRIANGLES)
        [self addVertexDataToCurrRenderingGroup:vertexData];
    else if (currMode == GL_TRIANGLE_FAN)
    {
        if (tessVert == 1)
        {
            tessVertex1 = [self createNewVertexDataWithVertexData:vertexData];
        }
        else if (tessVert == 2)
        {
            tessVertex2 = [self createNewVertexDataWithVertexData:vertexData];
        }
        else
        {
            [self addVertexDataToCurrRenderingGroup:tessVertex1];
            [self addVertexDataToCurrRenderingGroup:tessVertex2];
            [self addVertexDataToCurrRenderingGroup:vertexData];
            tessVertex2 = [self createNewVertexDataWithVertexData:vertexData];
        }
    }
    else if (currMode == GL_TRIANGLE_STRIP)
    {
        if (tessVert == 1)
        {
            tessVertex1 = [self createNewVertexDataWithVertexData:vertexData];
        }
        else if (tessVert == 2)
        {
            tessVertex2 = [self createNewVertexDataWithVertexData:vertexData];
        }
        else
        {
            if ((tessVert % 2) == 0)
            {
                [self addVertexDataToCurrRenderingGroup:vertexData];
                [self addVertexDataToCurrRenderingGroup:tessVertex2];
                [self addVertexDataToCurrRenderingGroup:tessVertex1];
            }
            else
            {
                [self addVertexDataToCurrRenderingGroup:tessVertex1];
                [self addVertexDataToCurrRenderingGroup:tessVertex2];
                [self addVertexDataToCurrRenderingGroup:vertexData];
            }
            tessVertex1 = tessVertex2;
            tessVertex2 = [self createNewVertexDataWithVertexData:vertexData];
        }
    }
    tessVert++;
}

#pragma mark -

// since we don't get easy access to the instance variables from within C functions,
// translate the callbacks that need instance vars into the appropriate obj-c methods to be handled there instead

static void TessErrorCallback(GLenum errorCode, MyObjLoader *objLoader)
{
    [objLoader tessErrorCallBack:errorCode];
}

static void TessBeginCallback(GLenum renderingMode, MyObjLoader *objLoader)
{
    [objLoader tessBeginCallback:renderingMode];
}

static void TessVertexCallback(VertexData *vertexData, MyObjLoader *objLoader)
{
    [objLoader tessVertexCallback:vertexData];
}



gluTesselate questions - TomorrowPlusX - Mar 21, 2008 05:22 AM

@AnotherJake: Thanks, I appreciate the guidance. But the issue isn't so much the mechanics of how to use gluTesselate ( though I appreciate it ) but rather what gluTesselate can and cannot do.

As such, I thought I might clarify a little what I'm doing. Basically, I'm working on a terrain system that will allow overhangs, tunneling, and ( this is my favorite part ) be editable in game, in real time.

It uses a voxel space for storage, a 3d array of booleans representing where there is, and where there is not matter. I've only been working on it for a couple weeks, using throwaway Cocoa code to test my ideas. No 3d yet.

The approach I'm taking is to generate contours for slices of the voxel grid. E.g., for a given Z value ( where z is up ) there is a 2D image of where there is and isn't material. I trace the edges of that slice, generating an array of "contours" which are line loops.

Then to make the solid geometry, I intend to tesselate these contours. I'd tesselate contour N with contour N+1. This would produce some number of triangle strips ( though not necessarily a GL_TRIANGLE_STRIP, I'm happy with just a soup of triangles, I've written code to stitch them together and store a VBO )

So below are three screenshots of my app. Since I'm just developing the algorithm now, I'm using a heightmap instead of a real voxel space. I'm generating contours for 3 z values in the heightmap.

[Image: Contour_0.png]
[Image: Contour_1.png]
[Image: Contour_2.png]

The intent would be to use gluTesselate to triangulate 105 with 106, and 106 with 107. Do this for the whole thing and I'd have a tesselated terrain.


gluTesselate questions - AnotherJake - Mar 21, 2008 08:01 AM

I'm still not sure I understand exactly what you're doing, but it doesn't seem like it would fit with the glu polygon tessellator. What I was describing is really just for n-sided faces (I think they have to be co-planar verts, so I guess it'd be 2D only). Maybe you should be looking into NURBS tessellation instead?

It looks like you could just tessellate a triangle strip yourself between each slice. Either way, you'd still have to make sure there are the same number of quads, radially around each slice, (and aligned vertically of course) otherwise you'd get pretty bad edge cracking between the triangle strips.


gluTesselate questions - memon - Mar 23, 2008 07:09 AM

I did not completely get what you are trying to do. If you wish to render the a your voxel data, you may want to take a look at marching cubes:

http://en.wikipedia.org/wiki/Marching_cubes

Be sure to check the links there too.


gluTesselate questions - maximile - Mar 23, 2008 11:59 AM

I think I get what you're trying to achieve, and Blender does it pretty well, so maybe you can glean something from its source code (never dared to look at it). I have no idea if it uses gluTesselate.

Here's what I think you mean:

[Image: tess1.gif]

To make:

[Image: tess2.jpg]


gluTesselate questions - TomorrowPlusX - Mar 24, 2008 07:15 AM

maximile Wrote:I think I get what you're trying to achieve, and Blender does it pretty well, so maybe you can glean something from its source code (never dared to look at it). I have no idea if it uses gluTesselate.

Here's what I think you mean:

[Image: tess1.gif]

To make:

[Image: tess2.jpg]

On the nose!

I'm writing a throwaway test app using gluTesselate to figure out if it will do what I'm hoping it will do. I may post back with results...


gluTesselate questions - TomorrowPlusX - Mar 24, 2008 07:17 AM

memon Wrote:I did not completely get what you are trying to do. If you wish to render the a your voxel data, you may want to take a look at marching cubes:

http://en.wikipedia.org/wiki/Marching_cubes

Be sure to check the links there too.

Marching Cubes was the first thing I looked into, but I don't like its output. Kind of ugly -- I'm looking for a more organic output, like Maximile's screenshots below.

I'm confident gluTesselate will handle 99% of what I'm throwing at it, but there are some corner cases which I'm worried about.

The upside is that if I can make this work, I'll be able to have in-game editable terrain supporting overhangs and tunneling!


gluTesselate questions - TomorrowPlusX - Apr 8, 2008 02:38 PM

Well, I just wanted to come back with an update. I gave up & went with Marching Cubes. And BOY DOES IT ROCK. I'm know there are better algorithms out there -- but MC was easy to implement, and so far appears pretty robust.

I've got it loading a heightmap into voxel space, and support for live re-tessellation when the voxel space is modified. In the screenshots below I'm adding 20 random spheres, and then subtracting a large sphere from that mass. It works!

[Image: MarchingCubes-2008-04-08-01.png]
[Image: MarchingCubes-2008-04-08-02.png]

Next, I'm going to do live sculpting of the terrain. I'm really excited.


gluTesselate questions - AnotherJake - Apr 8, 2008 03:39 PM

Hey, that looks really cool! Good job on finding a solution. Can't wait to see the finished product in action. Smile