3 ms·

Very cool. Something that would make me very happy would be a tessellator that takes this http://www.humus.name/index.php?page=News&ID=228 http://www.humus.nam

• Kristine1975 10y ago
  This one seems to do (did a test recently): http://www.geeksforgeeks.org/minimum-cost-polygon-triangulation/ http://www.geeksforgeeks.org/minimum-cost-polygon-triangulat... Uses O(n^3) time and O(n^2) space though, and only works for convex polygons. It's also fairly easy to implement an algorithm that creates the exact same tesselation for a circle that Humus describes in his article: static unsigned int moduloToZero(unsigned int const a, unsigned int const b) { // If the vertex is outside the valid range start again at the beginning return a >= b ? 0 : a; } template <typename VerticesT> static void fillVertexRangeHelper(Mesh& inOutMesh, VerticesT const vertices) { unsigned int const vertexCount = vertices.size(); if (vertexCount >= 3) { unsigned int stepSize = 2U; // C.f. http://www.humus.name/index.php?page=News&ID=228 // // Create triangles from vertices 0-1-2, 2-3-4, 4-5-6, 6-7-8, 8-9-10, 10-11-12, 12-13-14, 14-15-16, ... // then from vertices 0-2-4, 4-6-8, 8-10-12, 12-14-16, ... // then from vertices 0-4-8, 8-12-16, ... // then from vertices 0-8-16, ... // until no more triangles can be created. // When the final vertex of a triangle is bigger than the number of vertices, use vertex 0 instead while (vertexCount >= stepSize) { for (unsigned int i = 0; i < vertexCount; i += stepSize) { // Check if there are at least three vertices left to create a triangle with (including vertex 0 in case of // wrap-around) unsigned int const v0 = vertices[i]; unsigned int const v1 = vertices[moduloToZero(i + stepSize / 2U, vertexCount)]; unsigned int const v2 = vertices[moduloToZero(i + stepSize, vertexCount)]; if (v0 != v1 && v0 != v2 && v1 != v2) makeTri(inOutMesh, v0, v1, v2); } stepSize *= 2U; } } } "VerticesT" is an array of vertex numbers, e.g. an std::vector<unsigned int>. Just add a function "makeTri" that adds a single indexed triangle to the mesh, and you should be good to go.