| Flutter Impeller |

tessellator.cc
Go to the documentation of this file.
1 // Copyright 2013 The Flutter Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "impeller/tessellator/tessellator.h"
6
7 #include "third_party/libtess2/Include/tesselator.h"
8
9 namespace impeller {
10
11 static void* HeapAlloc(void* userData, unsigned int size) {
12 return malloc(size);
13 }
14
15 static void* HeapRealloc(void* userData, void* ptr, unsigned int size) {
16 return realloc(ptr, size);
17 }
18
19 static void HeapFree(void* userData, void* ptr) {
20 free(ptr);
21 }
22
23 // Note: these units are "number of entities" for bucket size and not in KB.
24 static const TESSalloc kAlloc = {
25 HeapAlloc, HeapRealloc, HeapFree, 0, /* =userData */
26 16, /* =meshEdgeBucketSize */
27 16, /* =meshVertexBucketSize */
28 16, /* =meshFaceBucketSize */
29 16, /* =dictNodeBucketSize */
30 16, /* =regionBucketSize */
31 0 /* =extraVertices */
32 };
33
34 Tessellator::Tessellator() : c_tessellator_(nullptr, &DestroyTessellator) {
35 TESSalloc alloc = kAlloc;
36 {
37 // libTess2 copies the TESSalloc despite the non-const argument.
38 CTessellator tessellator(::tessNewTess(&alloc), &DestroyTessellator);
39 c_tessellator_ = std::move(tessellator);
40 }
41 }
42
43 Tessellator::~Tessellator() = default;
44
45 static int ToTessWindingRule(FillType fill_type) {
46 switch (fill_type) {
47 case FillType::kOdd:
48 return TESS_WINDING_ODD;
49 case FillType::kNonZero:
50 return TESS_WINDING_NONZERO;
51 case FillType::kPositive:
52 return TESS_WINDING_POSITIVE;
53 case FillType::kNegative:
54 return TESS_WINDING_NEGATIVE;
55 case FillType::kAbsGeqTwo:
56 return TESS_WINDING_ABS_GEQ_TWO;
57 }
58 return TESS_WINDING_ODD;
59 }
60
61 Tessellator::Result Tessellator::Tessellate(
62 FillType fill_type,
63 const Path::Polyline& polyline,
64 const BuilderCallback& callback) const {
65 if (!callback) {
66 return Result::kInputError;
67 }
68
69 if (polyline.points.empty()) {
70 return Result::kInputError;
71 }
72
73 auto tessellator = c_tessellator_.get();
74 if (!tessellator) {
75 return Result::kTessellationError;
76 }
77
78 constexpr int kVertexSize = 2;
79 constexpr int kPolygonSize = 3;
80
81 //----------------------------------------------------------------------------
82 /// Feed contour information to the tessellator.
83 ///
84 static_assert(sizeof(Point) == 2 * sizeof(float));
85 for (size_t contour_i = 0; contour_i < polyline.contours.size();
86 contour_i++) {
87 size_t start_point_index, end_point_index;
88 std::tie(start_point_index, end_point_index) =
89 polyline.GetContourPointBounds(contour_i);
90
91 ::tessAddContour(tessellator, // the C tessellator
92 kVertexSize, //
93 polyline.points.data() + start_point_index, //
94 sizeof(Point), //
95 end_point_index - start_point_index //
96 );
97 }
98
99 //----------------------------------------------------------------------------
100 /// Let's tessellate.
101 ///
102 auto result = ::tessTesselate(tessellator, // tessellator
103 ToTessWindingRule(fill_type), // winding
104 TESS_POLYGONS, // element type
105 kPolygonSize, // polygon size
106 kVertexSize, // vertex size
107 nullptr // normal (null is automatic)
108 );
109
110 if (result != 1) {
111 return Result::kTessellationError;
112 }
113
114 int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
115
116 // We default to using a 16bit index buffer, but in cases where we generate
117 // more tessellated data than this can contain we need to fall back to
118 // dropping the index buffer entirely. Instead code could instead switch to
119 // a uint32 index buffer, but this is done for simplicity with the other
120 // fast path above.
121 if (element_item_count < USHRT_MAX) {
122 int vertex_item_count = tessGetVertexCount(tessellator);
123 auto vertices = tessGetVertices(tessellator);
124 auto elements = tessGetElements(tessellator);
125
126 // libtess uses an int index internally due to usage of -1 as a sentinel
127 // value.
128 std::vector<uint16_t> indices(element_item_count);
129 for (int i = 0; i < element_item_count; i++) {
130 indices[i] = static_cast<uint16_t>(elements[i]);
131 }
132 if (!callback(vertices, vertex_item_count, indices.data(),
133 element_item_count)) {
134 return Result::kInputError;
135 }
136 } else {
137 std::vector<Point> points;
138 std::vector<float> data;
139
140 int vertex_item_count = tessGetVertexCount(tessellator) * kVertexSize;
141 auto vertices = tessGetVertices(tessellator);
142 points.reserve(vertex_item_count);
143 for (int i = 0; i < vertex_item_count; i += 2) {
144 points.emplace_back(vertices[i], vertices[i + 1]);
145 }
146
147 int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
148 auto elements = tessGetElements(tessellator);
149 data.reserve(element_item_count);
150 for (int i = 0; i < element_item_count; i++) {
151 data.emplace_back(points[elements[i]].x);
152 data.emplace_back(points[elements[i]].y);
153 }
154 if (!callback(data.data(), element_item_count, nullptr, 0u)) {
155 return Result::kInputError;
156 }
157 }
158
159 return Result::kSuccess;
160 }
161
162 void DestroyTessellator(TESStesselator* tessellator) {
163 if (tessellator != nullptr) {
164 ::tessDeleteTess(tessellator);
165 }
166 }
167
168 } // namespace impeller
impeller::kAlloc
static const TESSalloc kAlloc
Definition: tessellator.cc:24
impeller::Tessellator::~Tessellator
~Tessellator()
impeller::FillType::kOdd
@ kOdd
impeller::HeapRealloc
static void * HeapRealloc(void *userData, void *ptr, unsigned int size)
Definition: tessellator.cc:15
impeller::HeapFree
static void HeapFree(void *userData, void *ptr)
Definition: tessellator.cc:19
impeller::Tessellator::Result::kInputError
@ kInputError
impeller::FillType::kAbsGeqTwo
@ kAbsGeqTwo
impeller::FillType::kPositive
@ kPositive
tessellator.h
impeller::Path::Polyline
Definition: path.h:78
impeller::Tessellator::Result::kTessellationError
@ kTessellationError
impeller::DestroyTessellator
void DestroyTessellator(TESStesselator *tessellator)
Definition: tessellator.cc:162
impeller::Path::Polyline::points
std::vector< Point > points
Definition: path.h:81
impeller::Path::Polyline::GetContourPointBounds
std::tuple< size_t, size_t > GetContourPointBounds(size_t contour_index) const
Definition: path.cc:20
impeller::Tessellator::Result::kSuccess
@ kSuccess
impeller::FillType
FillType
Definition: path.h:29
impeller::FillType::kNonZero
@ kNonZero
impeller::HeapAlloc
static void * HeapAlloc(void *userData, unsigned int size)
Definition: tessellator.cc:11
impeller::Tessellator::Tessellate
Tessellator::Result Tessellate(FillType fill_type, const Path::Polyline &polyline, const BuilderCallback &callback) const
Generates filled triangles from the polyline. A callback is invoked once for the entire tessellation.
Definition: tessellator.cc:61
impeller::TPoint< Scalar >
impeller::Tessellator::Tessellator
Tessellator()
Definition: tessellator.cc:34
impeller::Path::Polyline::contours
std::vector< PolylineContour > contours
Definition: path.h:82
impeller::ToTessWindingRule
static int ToTessWindingRule(FillType fill_type)
Definition: tessellator.cc:45
impeller::FillType::kNegative
@ kNegative
impeller::Tessellator::Result
Result
Definition: tessellator.h:37
impeller
Definition: aiks_context.cc:10
impeller::Tessellator::BuilderCallback
std::function< bool(const float *vertices, size_t vertices_count, const uint16_t *indices, size_t indices_count)> BuilderCallback
A callback that returns the results of the tessellation.
Definition: tessellator.h:54
impeller::CTessellator
std::unique_ptr< TESStesselator, decltype(&DestroyTessellator)> CTessellator
Definition: tessellator.h:22