chromium/third_party/skia/src/gpu/tessellate/MiddleOutPolygonTriangulator.h

/*
 * Copyright 2020 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef skgpu_tessellate_MiddleOutPolygonTriangulator_DEFINED
#define skgpu_tessellate_MiddleOutPolygonTriangulator_DEFINED

#include "include/core/SkPath.h"
#include "include/core/SkPathTypes.h"
#include "include/core/SkPoint.h"
#include "include/private/base/SkAssert.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkTemplates.h"
#include "src/base/SkMathPriv.h"
#include "src/core/SkPathPriv.h"

#include <algorithm>
#include <cstring>
#include <tuple>

namespace skgpu::tess {

// This class generates a middle-out triangulation of a polygon. Conceptually, middle-out emits one
// large triangle with vertices on both endpoints and a middle point, then recurses on both sides of
// the new triangle. i.e.:
//
//     void emit_middle_out_triangulation(int startIdx, int endIdx) {
//         if (startIdx + 1 == endIdx) {
//             return;
//         }
//         int middleIdx = startIdx + SkNextPow2(endIdx - startIdx) / 2;
//
//         // Recurse on the left half.
//         emit_middle_out_triangulation(startIdx, middleIdx);
//
//         // Emit a large triangle with vertices on both endpoints and a middle point.
//         emit_triangle(vertices[startIdx], vertices[middleIdx], vertices[endIdx - 1]);
//
//         // Recurse on the right half.
//         emit_middle_out_triangulation(middleIdx, endIdx);
//     }
//
// Middle-out produces drastically less work for the rasterizer as compared a linear triangle strip
// or fan.
//
// This class is designed to not know or store all the vertices in the polygon at once. The caller
// pushes each vertex in linear order (perhaps while parsing a path), then rather than relying on
// recursion, we manipulate an O(log N) stack to determine the correct middle-out triangulation.
class MiddleOutPolygonTriangulator { … };

// This is a helper class that transforms and pushes a path's inner fan vertices onto a
// MiddleOutPolygonTriangulator. Example usage:
//
//   for (PathMiddleOutFanIter it(pathMatrix, path); !it.done();) {
//       for (auto [p0, p1, p2] : it.nextStack()) {
//           vertexWriter << p0 << p1 << p2;
//       }
//   }
//
class PathMiddleOutFanIter { … };

}  // namespace skgpu::tess

#endif  // skgpu_tessellate_MiddleOutPolygonTriangulator_DEFINED