[core] Replace clipper and libtess with earcut.hpp

2 files changed, 50 insertions, 167 deletions

diff --git a/src/mbgl/renderer/fill_bucket.cpp b/src/mbgl/renderer/fill_bucket.cpp
index b0f391323c..ed8f70059a 100644
--- a/src/mbgl/renderer/fill_bucket.cpp
+++ b/src/mbgl/renderer/fill_bucket.cpp
@@ -1,7 +1,5 @@
 #include <mbgl/renderer/fill_bucket.hpp>
-#include <mbgl/geometry/fill_buffer.hpp>
 #include <mbgl/layer/fill_layer.hpp>
-#include <mbgl/geometry/elements_buffer.hpp>
 #include <mbgl/renderer/painter.hpp>
 #include <mbgl/shader/plain_shader.hpp>
 #include <mbgl/shader/pattern_shader.hpp>
@@ -10,181 +8,87 @@
 #include <mbgl/gl/gl.hpp>
 #include <mbgl/platform/log.hpp>
 
+#include <mapbox/earcut.hpp>
+
 #include <cassert>
 
-struct geometry_too_long_exception : std::exception {};
+struct GeometryTooLongException : std::exception {};
 
 using namespace mbgl;
 
-void *FillBucket::alloc(void *, unsigned int size) {
-    return ::malloc(size);
-}
+namespace mapbox {
+namespace util {
+template <> struct nth<0, GeometryCoordinate> {
+    inline static int64_t get(const GeometryCoordinate& t) { return t.x; };
+};
 
-void *FillBucket::realloc(void *, void *ptr, unsigned int size) {
-    return ::realloc(ptr, size);
+template <> struct nth<1, GeometryCoordinate> {
+    inline static int64_t get(const GeometryCoordinate& t) { return t.y; };
+};
 }
-
-void FillBucket::free(void *, void *ptr) {
-    ::free(ptr);
 }
 
-FillBucket::FillBucket()
-    : allocator(new TESSalloc{
-          &alloc,
-          &realloc,
-          &free,
-          nullptr, // userData
-          64,      // meshEdgeBucketSize
-          64,      // meshVertexBucketSize
-          32,      // meshFaceBucketSize
-          64,      // dictNodeBucketSize
-          8,       // regionBucketSize
-          128,     // extraVertices allocated for the priority queue.
-      }),
-      tesselator(tessNewTess(allocator)) {
-    assert(tesselator);
+FillBucket::FillBucket() {
 }
 
 FillBucket::~FillBucket() {
-    if (tesselator) {
-        tessDeleteTess(tesselator);
-    }
-    if (allocator) {
-        delete allocator;
-    }
-}
-
-void FillBucket::addGeometry(const GeometryCollection& geometryCollection) {
-    for (auto& line_ : geometryCollection) {
-        for (auto& v : line_) {
-            line.emplace_back(v.x, v.y);
-        }
-        if (!line.empty()) {
-            clipper.AddPath(line, ClipperLib::ptSubject, true);
-            line.clear();
-            hasVertices = true;
-        }
-    }
-
-    tessellate();
 }
 
-void FillBucket::tessellate() {
-    if (!hasVertices) {
-        return;
-    }
-    hasVertices = false;
-
-    std::vector<std::vector<ClipperLib::IntPoint>> polygons;
-    clipper.Execute(ClipperLib::ctUnion, polygons, ClipperLib::pftEvenOdd, ClipperLib::pftEvenOdd);
-    clipper.Clear();
+void FillBucket::addGeometry(const GeometryCollection& geometry) {
+    for (const auto& polygon : classifyRings(geometry)) {
+        std::size_t totalVertices = 0;
 
-    if (polygons.empty()) {
-        return;
-    }
+        for (const auto& ring : polygon) {
+            totalVertices += ring.size();
+            if (totalVertices > 65535)
+                throw GeometryTooLongException();
+        }
 
-    GLsizei total_vertex_count = 0;
-    for (const auto& polygon : polygons) {
-        total_vertex_count += polygon.size();
-    }
+        for (const auto& ring : polygon) {
+            std::size_t nVertices = ring.size();
 
-    if (total_vertex_count > 65536) {
-        throw geometry_too_long_exception();
-    }
+            if (nVertices == 0)
+                continue;
 
-    if (lineGroups.empty() || (lineGroups.back()->vertex_length + total_vertex_count > 65535)) {
-        // Move to a new group because the old one can't hold the geometry.
-        lineGroups.emplace_back(std::make_unique<LineGroup>());
-    }
+            if (lineGroups.empty() || lineGroups.back()->vertex_length + nVertices > 65535)
+                lineGroups.emplace_back(std::make_unique<LineGroup>());
 
-    assert(lineGroups.back());
-    LineGroup& lineGroup = *lineGroups.back();
-    GLsizei lineIndex = lineGroup.vertex_length;
+            LineGroup& lineGroup = *lineGroups.back();
+            GLsizei lineIndex = lineGroup.vertex_length;
 
-    for (const auto& polygon : polygons) {
-        const GLsizei group_count = static_cast<GLsizei>(polygon.size());
-        assert(group_count >= 3);
+            vertexBuffer.add(ring[0].x, ring[0].y);
+            lineElementsBuffer.add(lineIndex + nVertices - 1, lineIndex);
 
-        std::vector<TESSreal> clipped_line;
-        for (const auto& pt : polygon) {
-            clipped_line.push_back(pt.X);
-            clipped_line.push_back(pt.Y);
-            vertexBuffer.add(pt.X, pt.Y);
-        }
+            for (uint32_t i = 1; i < nVertices; i++) {
+                vertexBuffer.add(ring[i].x, ring[i].y);
+                lineElementsBuffer.add(lineIndex + i - 1, lineIndex + i);
+            }
 
-        for (GLsizei i = 0; i < group_count; i++) {
-            const GLsizei prev_i = (i == 0 ? group_count : i) - 1;
-            lineElementsBuffer.add(lineIndex + prev_i, lineIndex + i);
+            lineGroup.vertex_length += nVertices;
+            lineGroup.elements_length += nVertices;
         }
 
-        lineIndex += group_count;
-
-        tessAddContour(tesselator, vertexSize, clipped_line.data(), stride, (int)clipped_line.size() / vertexSize);
-    }
-
-    lineGroup.elements_length += total_vertex_count;
+        std::vector<uint32_t> indices = mapbox::earcut(polygon);
 
-    if (tessTesselate(tesselator, TESS_WINDING_ODD, TESS_POLYGONS, vertices_per_group, vertexSize, 0)) {
-        const TESSreal *vertices = tessGetVertices(tesselator);
-        const GLsizei vertex_count = tessGetVertexCount(tesselator);
-        TESSindex *vertex_indices = const_cast<TESSindex *>(tessGetVertexIndices(tesselator));
-        const TESSindex *elements = tessGetElements(tesselator);
-        const int triangle_count = tessGetElementCount(tesselator);
+        std::size_t nIndicies = indices.size();
+        assert(nIndicies % 3 == 0);
 
-        for (GLsizei i = 0; i < vertex_count; ++i) {
-            if (vertex_indices[i] == TESS_UNDEF) {
-                vertexBuffer.add(::round(vertices[i * 2]), ::round(vertices[i * 2 + 1]));
-                vertex_indices[i] = (TESSindex)total_vertex_count;
-                total_vertex_count++;
-            }
-        }
-
-        if (triangleGroups.empty() || (triangleGroups.back()->vertex_length + total_vertex_count > 65535)) {
-            // Move to a new group because the old one can't hold the geometry.
+        if (triangleGroups.empty() || triangleGroups.back()->vertex_length + totalVertices > 65535) {
             triangleGroups.emplace_back(std::make_unique<TriangleGroup>());
         }
 
-        // We're generating triangle fans, so we always start with the first
-        // coordinate in this polygon.
-        assert(triangleGroups.back());
         TriangleGroup& triangleGroup = *triangleGroups.back();
         GLsizei triangleIndex = triangleGroup.vertex_length;
 
-        for (int i = 0; i < triangle_count; ++i) {
-            const TESSindex *element_group = &elements[i * vertices_per_group];
-
-            if (element_group[0] != TESS_UNDEF && element_group[1] != TESS_UNDEF && element_group[2] != TESS_UNDEF) {
-                const TESSindex a = vertex_indices[element_group[0]];
-                const TESSindex b = vertex_indices[element_group[1]];
-                const TESSindex c = vertex_indices[element_group[2]];
-
-                if (a != TESS_UNDEF && b != TESS_UNDEF && c != TESS_UNDEF) {
-                    triangleElementsBuffer.add(triangleIndex + a, triangleIndex + b, triangleIndex + c);
-                } else {
-#if defined(DEBUG)
-                    // TODO: We're missing a vertex that was not part of the line.
-                    Log::Error(Event::OpenGL, "undefined element buffer");
-#endif
-                }
-            } else {
-#if defined(DEBUG)
-                Log::Error(Event::OpenGL, "undefined element buffer");
-#endif
-            }
+        for (uint32_t i = 0; i < nIndicies; i += 3) {
+            triangleElementsBuffer.add(triangleIndex + indices[i],
+                                       triangleIndex + indices[i + 1],
+                                       triangleIndex + indices[i + 2]);
         }
 
-        triangleGroup.vertex_length += total_vertex_count;
-        triangleGroup.elements_length += triangle_count;
-    } else {
-#if defined(DEBUG)
-        Log::Error(Event::OpenGL, "tessellation failed");
-#endif
+        triangleGroup.vertex_length += totalVertices;
+        triangleGroup.elements_length += nIndicies / 3;
     }
-
-    // We're adding the total vertex count *after* we added additional vertices
-    // in the tessellation step. They won't be part of the actual lines, but
-    // we need to skip over them anyway if we draw the next group.
-    lineGroup.vertex_length += total_vertex_count;
 }
 
 void FillBucket::upload(gl::GLObjectStore& glObjectStore) {
diff --git a/src/mbgl/renderer/fill_bucket.hpp b/src/mbgl/renderer/fill_bucket.hpp
index e8ef8cc67d..1ffe27db1b 100644
--- a/src/mbgl/renderer/fill_bucket.hpp
+++ b/src/mbgl/renderer/fill_bucket.hpp
@@ -5,29 +5,17 @@
 #include <mbgl/geometry/elements_buffer.hpp>
 #include <mbgl/geometry/fill_buffer.hpp>
 
-#include <clipper/clipper.hpp>
-#include <libtess2/tesselator.h>
-
 #include <vector>
 #include <memory>
 
 namespace mbgl {
 
-class FillVertexBuffer;
-class OutlineShader;
 class OutlinePatternShader;
 class PlainShader;
 class PatternShader;
+class OutlineShader;
 
 class FillBucket : public Bucket {
-
-    static void *alloc(void *data, unsigned int size);
-    static void *realloc(void *data, void *ptr, unsigned int size);
-    static void free(void *userData, void *ptr);
-
-    typedef ElementGroup<2> TriangleGroup;
-    typedef ElementGroup<2> LineGroup;
-
 public:
     FillBucket();
     ~FillBucket() override;
@@ -38,7 +26,6 @@ public:
     bool needsClipping() const override;
 
     void addGeometry(const GeometryCollection&);
-    void tessellate();
 
     void drawElements(PlainShader&, gl::GLObjectStore&);
     void drawElements(PatternShader&, gl::GLObjectStore&);
@@ -46,23 +33,15 @@ public:
     void drawVertices(OutlinePatternShader&, gl::GLObjectStore&);
 
 private:
-    TESSalloc *allocator;
-    TESStesselator *tesselator;
-    ClipperLib::Clipper clipper;
-
     FillVertexBuffer vertexBuffer;
     TriangleElementsBuffer triangleElementsBuffer;
     LineElementsBuffer lineElementsBuffer;
 
+    typedef ElementGroup<2> TriangleGroup;
+    typedef ElementGroup<2> LineGroup;
+
     std::vector<std::unique_ptr<TriangleGroup>> triangleGroups;
     std::vector<std::unique_ptr<LineGroup>> lineGroups;
-
-    std::vector<ClipperLib::IntPoint> line;
-    bool hasVertices = false;
-
-    static const int vertexSize = 2;
-    static const int stride = sizeof(TESSreal) * vertexSize;
-    static const int vertices_per_group = 3;
 };
 
 } // namespace mbgl