# Tessallation algorithm

Hello,

Do you know where can I find any information about tessellation’s algorithm ? I can’t find any detail information on Google or wiki. Do you have any sample code in C++ ?

Thanks

About “tessellation algorithm”? That’s extremely vague. Like searching for an article on ray tracing. If I google “OpenGL tessellation” I get tons of information.

What are you trying to tessellate and why?

If suitable for your problem, you could just use the tessellation stage provided by OpenGL 4.x . Then you don’t need to know the details of tessellation algorithms. Plus you get the potential performance advantages and model simplifications of dynamic level of detail of tessellation in hardware. Detailed information about programming the tessellation stage is available in any of the OpenGL and OpenGL Shading Language 4.x specification documents available for free on this website.

Yes, but you still need to understand what you’re tessellating. For example, tessellating for geomorphing, terrain heightmaps, and subdivision surfaces are totally different things. So you really do know what type of tessellation algorithm to use. There’s no “make awesome” setting for everything you might want to do.

The algorithm is described in the specs (page 104) and in the tessellation shader extension.

As described in the specs the algorithm is implementation dependent, but basically there are two parameters, inner tessellation and outer tessellation.
The inner tessellation is a parameter that tell openGl how many concentric triangle generate for that triangle.
Outer tessellation tell in how many part subdivide the edge.
http://prideout.net/blog/?p=48

Certainly you need to understand what you’re tessellating, but that doesn’t mean you need to understand how to write a tessellation algorithm when using the OpenGL 4.x tessellation stage.

The OpenGL 4.x tessellation stage is impressively versatile, capable, and easy to use. The OpenGL programmer implements geo-morphing, for example, simply by choosing a suitable input layout qualifier for the tessellation evaluation shader (either “fractional_even_spacing” or “fractional_odd_spacing”).

As far as terrain heightmaps or subdivision surfaces, etc., go, you need to understand how the OpenGL 4.x tessellation stage works. It consists of three parts, the tessellation control shader, the tessellation primitive generator, and the tessellation evaluation shader. Rosario Leonardi discussed the purpose of the tessellation control shader, above. But the reason it’s controlled in a shader is for dynamic level-of-detail control. The tessellation primitive generator tessellates either triangles or rectangles, but it does so in a planar parametric space, which makes it completely generic. The coordinates of the points output from the tessellation primitive generator always lie between zero and one, inclusive. It is the tessellation evaluation shader that uses those planar parametric points from the tessellation primitive generator along with the patch’s 3D vertices and vertex attributes and performs whatever 3D transformation the programmer has written.

There is a distinction between mesh generation, and mesh transformation. The tessellation primitive generator generates a planar mesh, and handles all the mesh connectivity issues, i.e., water-tight triangle (or line for isolines) assembly. I think of that as the implementation of the tessellation algorithm, per se, so a programmer only needs to know how to control it, by way of a few parameters, but not how to implement it.

The tessellation evaluation shader transforms the points of the planar parametric mesh to create the tessellated 3D geometry. That’s where the programmer must apply knowledge of terrain heightmaps or subdivision surfaces or whatever is desired. But that’s just the evaluation of a parametric function at a point, independent of all other points and geometry and connectivity information, and not what I define as tessellation, per se.

So, for a heightmap, for example, the tessellation evaluation shader would typically use the parametric point from the tessellation primitive generator to interpolate between the texture coordinates of the patch’s vertex attributes to obtain the coordinates to lookup a texel from a 2D texture map, and apply that to the surface normal or Y coordinate or whatever at the interpolated position between the patch’s 3D vertices.

But, for a subdivision surface, for example, the tessellation evaluation shader would typically evaluate some formula using values that are a function of the parametric point from the primitive generator and the patch’s vertices, or some variation thereof. Up to 32 vertices, and their vertex attributes, are allowed per patch, so bicubic Bezier surface patches can be directly accommodated, for example.

[Update: implementing general subdivision surfaces won’t be this simple, as they’re defined by the limit of an infinite recursion. GLSL isn’t real good with infinite anything, in general, such as ray tracing. But if you can define a surface such that each point on it can be determined independently of other arbitrary points on it (just in terms of a parametric point and a set of defining patch vertices and any formulas), then the OpenGL 4.x tessellation stage is ideal. You’d need to make some use of feedback buffers to use the tessellation stage to generally evaluate subdivision surfaces, but even this might not work well. Or, just don’t use generalized subdivision surfaces, and the problem disappears!]

Well, there’s no “make awesome” setting, but, in my opinion, the OpenGL 4.x tessellation stage is genuinely awesome. I’m speaking after having 2.5 months of experience programming it under my belt.

One more question: do you know if openGL ES 2.0 provides sth for tessellation ? I need to draw concave polygon somehow.

Thanks

OpenGL 4.x’s tessellation “make awesome” filter howto http://codeflow.org/entries/2010/nov/07/opengl-4-tessellation/