| // Copyright 2013 The Flutter Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "tessellator.h" |
| |
| #include <memory> |
| #include <vector> |
| |
| #include "third_party/libtess2/Include/tesselator.h" |
| |
| namespace impeller { |
| |
| void DestroyTessellator(TESStesselator* tessellator) { |
| if (tessellator != nullptr) { |
| ::tessDeleteTess(tessellator); |
| } |
| } |
| |
| using CTessellator = |
| std::unique_ptr<TESStesselator, decltype(&DestroyTessellator)>; |
| |
| static int ToTessWindingRule(FillType fill_type) { |
| switch (fill_type) { |
| case FillType::kOdd: |
| return TESS_WINDING_ODD; |
| case FillType::kNonZero: |
| return TESS_WINDING_NONZERO; |
| } |
| return TESS_WINDING_ODD; |
| } |
| |
| static void* HeapAlloc(void* userData, unsigned int size) { |
| return malloc(size); |
| } |
| |
| static void* HeapRealloc(void* userData, void* ptr, unsigned int size) { |
| return realloc(ptr, size); |
| } |
| |
| static void HeapFree(void* userData, void* ptr) { |
| free(ptr); |
| } |
| |
| // Note: these units are "number of entities" for bucket size and not in KB. |
| static const TESSalloc kAlloc = { |
| HeapAlloc, HeapRealloc, HeapFree, 0, /* =userData */ |
| 16, /* =meshEdgeBucketSize */ |
| 16, /* =meshVertexBucketSize */ |
| 16, /* =meshFaceBucketSize */ |
| 16, /* =dictNodeBucketSize */ |
| 16, /* =regionBucketSize */ |
| 0 /* =extraVertices */ |
| }; |
| |
| class LibtessTessellator { |
| public: |
| LibtessTessellator() : c_tessellator_(nullptr, &DestroyTessellator) { |
| TESSalloc alloc = kAlloc; |
| { |
| // libTess2 copies the TESSalloc despite the non-const argument. |
| CTessellator tessellator(::tessNewTess(&alloc), &DestroyTessellator); |
| c_tessellator_ = std::move(tessellator); |
| } |
| } |
| |
| ~LibtessTessellator() {} |
| |
| enum class Result { |
| kSuccess, |
| kInputError, |
| kTessellationError, |
| }; |
| |
| /// @brief A callback that returns the results of the tessellation. |
| /// |
| /// The index buffer may not be populated, in which case [indices] will |
| /// be nullptr and indices_count will be 0. |
| using BuilderCallback = std::function<bool(const float* vertices, |
| size_t vertices_count, |
| const uint16_t* indices, |
| size_t indices_count)>; |
| |
| //---------------------------------------------------------------------------- |
| /// @brief Generates filled triangles from the path. A callback is |
| /// invoked once for the entire tessellation. |
| /// |
| /// @param[in] path The path to tessellate. |
| /// @param[in] tolerance The tolerance value for conversion of the path to |
| /// a polyline. This value is often derived from the |
| /// Matrix::GetMaxBasisLength of the CTM applied to the |
| /// path for rendering. |
| /// @param[in] callback The callback, return false to indicate failure. |
| /// |
| /// @return The result status of the tessellation. |
| /// |
| Result Tessellate(const Path& path, |
| Scalar tolerance, |
| const BuilderCallback& callback) { |
| if (!callback) { |
| return Result::kInputError; |
| } |
| |
| std::unique_ptr<std::vector<Point>> buffer = |
| std::make_unique<std::vector<Point>>(); |
| auto polyline = path.CreatePolyline(tolerance, std::move(buffer)); |
| |
| auto fill_type = path.GetFillType(); |
| |
| if (polyline.points->empty()) { |
| return Result::kInputError; |
| } |
| |
| auto tessellator = c_tessellator_.get(); |
| if (!tessellator) { |
| return Result::kTessellationError; |
| } |
| |
| constexpr int kVertexSize = 2; |
| constexpr int kPolygonSize = 3; |
| |
| //---------------------------------------------------------------------------- |
| /// Feed contour information to the tessellator. |
| /// |
| static_assert(sizeof(Point) == 2 * sizeof(float)); |
| for (size_t contour_i = 0; contour_i < polyline.contours.size(); |
| contour_i++) { |
| size_t start_point_index, end_point_index; |
| std::tie(start_point_index, end_point_index) = |
| polyline.GetContourPointBounds(contour_i); |
| |
| ::tessAddContour(tessellator, // the C tessellator |
| kVertexSize, // |
| polyline.points->data() + start_point_index, // |
| sizeof(Point), // |
| end_point_index - start_point_index // |
| ); |
| } |
| |
| //---------------------------------------------------------------------------- |
| /// Let's tessellate. |
| /// |
| auto result = ::tessTesselate(tessellator, // tessellator |
| ToTessWindingRule(fill_type), // winding |
| TESS_POLYGONS, // element type |
| kPolygonSize, // polygon size |
| kVertexSize, // vertex size |
| nullptr // normal (null is automatic) |
| ); |
| |
| if (result != 1) { |
| return Result::kTessellationError; |
| } |
| |
| int element_item_count = tessGetElementCount(tessellator) * kPolygonSize; |
| |
| // We default to using a 16bit index buffer, but in cases where we generate |
| // more tessellated data than this can contain we need to fall back to |
| // dropping the index buffer entirely. Instead code could instead switch to |
| // a uint32 index buffer, but this is done for simplicity with the other |
| // fast path above. |
| if (element_item_count < USHRT_MAX) { |
| int vertex_item_count = tessGetVertexCount(tessellator); |
| auto vertices = tessGetVertices(tessellator); |
| auto elements = tessGetElements(tessellator); |
| |
| // libtess uses an int index internally due to usage of -1 as a sentinel |
| // value. |
| std::vector<uint16_t> indices(element_item_count); |
| for (int i = 0; i < element_item_count; i++) { |
| indices[i] = static_cast<uint16_t>(elements[i]); |
| } |
| if (!callback(vertices, vertex_item_count, indices.data(), |
| element_item_count)) { |
| return Result::kInputError; |
| } |
| } else { |
| std::vector<Point> points; |
| std::vector<float> data; |
| |
| int vertex_item_count = tessGetVertexCount(tessellator) * kVertexSize; |
| auto vertices = tessGetVertices(tessellator); |
| points.reserve(vertex_item_count); |
| for (int i = 0; i < vertex_item_count; i += 2) { |
| points.emplace_back(vertices[i], vertices[i + 1]); |
| } |
| |
| int element_item_count = tessGetElementCount(tessellator) * kPolygonSize; |
| auto elements = tessGetElements(tessellator); |
| data.reserve(element_item_count); |
| for (int i = 0; i < element_item_count; i++) { |
| data.emplace_back(points[elements[i]].x); |
| data.emplace_back(points[elements[i]].y); |
| } |
| if (!callback(data.data(), element_item_count, nullptr, 0u)) { |
| return Result::kInputError; |
| } |
| } |
| |
| return Result::kSuccess; |
| } |
| |
| CTessellator c_tessellator_; |
| }; |
| |
| PathBuilder* CreatePathBuilder() { |
| return new PathBuilder(); |
| } |
| |
| void DestroyPathBuilder(PathBuilder* builder) { |
| delete builder; |
| } |
| |
| void MoveTo(PathBuilder* builder, Scalar x, Scalar y) { |
| builder->MoveTo(Point(x, y)); |
| } |
| |
| void LineTo(PathBuilder* builder, Scalar x, Scalar y) { |
| builder->LineTo(Point(x, y)); |
| } |
| |
| void CubicTo(PathBuilder* builder, |
| Scalar x1, |
| Scalar y1, |
| Scalar x2, |
| Scalar y2, |
| Scalar x3, |
| Scalar y3) { |
| builder->CubicCurveTo(Point(x1, y1), Point(x2, y2), Point(x3, y3)); |
| } |
| |
| void Close(PathBuilder* builder) { |
| builder->Close(); |
| } |
| |
| struct Vertices* Tessellate(PathBuilder* builder, |
| int fill_type, |
| Scalar tolerance) { |
| auto path = builder->CopyPath(static_cast<FillType>(fill_type)); |
| std::vector<float> points; |
| if (LibtessTessellator{}.Tessellate( |
| path, tolerance, |
| [&points](const float* vertices, size_t vertices_count, |
| const uint16_t* indices, size_t indices_count) { |
| // Results are expected to be re-duplicated. |
| std::vector<Point> raw_points; |
| for (auto i = 0u; i < vertices_count * 2; i += 2) { |
| raw_points.emplace_back(Point{vertices[i], vertices[i + 1]}); |
| } |
| for (auto i = 0u; i < indices_count; i++) { |
| auto point = raw_points[indices[i]]; |
| points.push_back(point.x); |
| points.push_back(point.y); |
| } |
| return true; |
| }) != LibtessTessellator::Result::kSuccess) { |
| return nullptr; |
| } |
| |
| Vertices* vertices = new Vertices(); |
| vertices->points = new float[points.size()]; |
| if (!vertices->points) { |
| return nullptr; |
| } |
| vertices->length = points.size(); |
| std::copy(points.begin(), points.end(), vertices->points); |
| return vertices; |
| } |
| |
| void DestroyVertices(Vertices* vertices) { |
| delete vertices->points; |
| delete vertices; |
| } |
| |
| } // namespace impeller |