The tessellate polygon drawing algorithm

w0utert · on July 25, 2016

Shameless plug: I wrote a series of long form blog posts about implementing this algorithm as part of my game side-project. These are mostly directed to the development process for my game but also contain some links to interesting source material I used to implement the algorithm. If anyone is interested, the first of three posts can be found here [1]

[1] http://www.wouterbijlsma.nl/blog/2k14thegame/2014/06/24/surf...

corysama · on July 25, 2016

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 into account.

A bit more background on the problem: http://blog.selfshadow.com/publications/overdraw-in-overdriv...

Kristine1975 · on July 25, 2016

This one seems to do (did a test recently): 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.

amelius · on July 25, 2016

Suggestion for better title:

"The tessellate polygon drawing algorithm"

waruqi · on July 25, 2016

Oh, thanks!