LibTessDotNet

Goal

Provide a robust and fast tessellator (polygons with N vertices in the output) for .NET, also does triangulation.

Requirements

• .NET Standard 2.0 (see here for more information)

Features

• Tessellate arbitrary complex polygons
  • self-intersecting (see "star-intersect" sample)
  • with coincident vertices (see "clipper" sample)
  • advanced winding rules : even/odd, non zero, positive, negative, |winding| >= 2 (see "redbook-winding" sample)
• Custom input
  • Custom vertex attributes (eg. UV coordinates) with merging callback
  • Force orientation of input contour (clockwise/counterclockwise, eg. for GIS systems, see "force-winding" sample)
• Choice of output
  • polygons with N vertices (with N >= 3)
  • connected polygons (didn't quite tried this yet, but should work)
  • boundary only (to have a basic union of two contours)
• Handles polygons computed with Clipper - an open source freeware polygon clipping library
• Single/Double precision support

Screenshot

Comparison

Build

dotnet build

Example

From TessExample/Program.cs

usingLibTessDotNet;usingSystem;usingSystem.Drawing;namespaceTessExample{classProgram{// The data array contains 4 values, it's the associated data of the vertices that resulted in an intersection.privatestaticobjectVertexCombine(LibTessDotNet.Vec3position,object[]data,float[]weights){// Fetch the vertex data.varcolors=newColor[]{(Color)data[0],(Color)data[1],(Color)data[2],(Color)data[3]};// Interpolate with the 4 weights.varrgba=newfloat[]{(float)colors[0].R*weights[0]+(float)colors[1].R*weights[1]+(float)colors[2].R*weights[2]+(float)colors[3].R*weights[3],(float)colors[0].G*weights[0]+(float)colors[1].G*weights[1]+(float)colors[2].G*weights[2]+(float)colors[3].G*weights[3],(float)colors[0].B*weights[0]+(float)colors[1].B*weights[1]+(float)colors[2].B*weights[2]+(float)colors[3].B*weights[3],(float)colors[0].A*weights[0]+(float)colors[1].A*weights[1]+(float)colors[2].A*weights[2]+(float)colors[3].A*weights[3]};// Return interpolated data for the new vertex.returnColor.FromArgb((int)rgba[3],(int)rgba[0],(int)rgba[1],(int)rgba[2]);}staticvoidMain(string[]args){// Example input data in the form of a star that intersects itself.varinputData=newfloat[]{0.0f,3.0f,-1.0f,0.0f,1.6f,1.9f,-1.6f,1.9f,1.0f,0.0f};// Create an instance of the tessellator. Can be reused.vartess=newLibTessDotNet.Tess();// Construct the contour from inputData.// A polygon can be composed of multiple contours which are all tessellated at the same time.intnumPoints=inputData.Length/2;varcontour=newLibTessDotNet.ContourVertex[numPoints];for(inti=0;i<numPoints;i++){// NOTE : Z is here for convenience if you want to keep a 3D vertex position throughout the tessellation process but only X and Y are important.contour[i].Position=newLibTessDotNet.Vec3(inputData[i*2],inputData[i*2+1],0);// Data can contain any per-vertex data, here a constant color.contour[i].Data=Color.Azure;}// Add the contour with a specific orientation, use "Original" if you want to keep the input orientation.tess.AddContour(contour,LibTessDotNet.ContourOrientation.Clockwise);// Tessellate!// The winding rule determines how the different contours are combined together.// See http://www.glprogramming.com/red/chapter11.html (section "Winding Numbers and Winding Rules") for more information.// If you want triangles as output, you need to use "Polygons" type as output and 3 vertices per polygon.tess.Tessellate(LibTessDotNet.WindingRule.EvenOdd,LibTessDotNet.ElementType.Polygons,3,VertexCombine);// Same call but the last callback is optional. Data will be null because no interpolated data would have been generated.//tess.Tessellate(LibTessDotNet.WindingRule.EvenOdd, LibTessDotNet.ElementType.Polygons, 3); // Some vertices will have null Data in this case.Console.WriteLine("Output triangles:");intnumTriangles=tess.ElementCount;for(inti=0;i<numTriangles;i++){varv0=tess.Vertices[tess.Elements[i*3]].Position;varv1=tess.Vertices[tess.Elements[i*3+1]].Position;varv2=tess.Vertices[tess.Elements[i*3+2]].Position;Console.WriteLine("#{0} ({1:F1},{2:F1}) ({3:F1},{4:F1}) ({5:F1},{6:F1})",i,v0.X,v0.Y,v1.X,v1.Y,v2.X,v2.Y);}Console.ReadLine();}}}

Notes

• When using ElementType.BoundaryContours, Tess.Elements will contain a list of ranges [startVertexIndex, vertexCount]. Those ranges are to used with Tess.Vertices.

TODO

• No allocations with the same input twice, all coming from pool
• Any suggestions are welcome ;)

License

SGI FREE SOFTWARE LICENSE B (Version 2.0, Sept. 18, 2008) More information in LICENSE.txt.

Links

• Reference implementation - the original SGI reference implementation
• libtess2 - Mikko Mononen cleaned up the original GLU tesselator
• Poly2Tri - another triangulation library for .NET (other ports also available)
  • Does not support polygons from Clipper, more specifically vertices with same coordinates (coincident)
• Clipper - an open source freeware polygon clipping library