| 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 // If we have a larger polyline and the fill type is non-zero, we can split
82 // the tessellation up per contour. Since in general the complexity is at
83 // least nlog(n), this speeds up the processes substantially.
84 if (polyline.contours.size() > kMultiContourThreshold &&
85 fill_type == FillType::kNonZero) {
86 std::vector<Point> points;
87 std::vector<float> data;
88
89 //----------------------------------------------------------------------------
90 /// Feed contour information to the tessellator.
91 ///
92 size_t total = 0u;
93 static_assert(sizeof(Point) == 2 * sizeof(float));
94 for (size_t contour_i = 0; contour_i < polyline.contours.size();
95 contour_i++) {
96 size_t start_point_index, end_point_index;
97 std::tie(start_point_index, end_point_index) =
98 polyline.GetContourPointBounds(contour_i);
99
100 ::tessAddContour(tessellator, // the C tessellator
101 kVertexSize, //
102 polyline.points.data() + start_point_index, //
103 sizeof(Point), //
104 end_point_index - start_point_index //
105 );
106
107 //----------------------------------------------------------------------------
108 /// Let's tessellate.
109 ///
110 auto result = ::tessTesselate(tessellator, // tessellator
111 ToTessWindingRule(fill_type), // winding
112 TESS_POLYGONS, // element type
113 kPolygonSize, // polygon size
114 kVertexSize, // vertex size
115 nullptr // normal (null is automatic)
116 );
117
118 if (result != 1) {
119 return Result::kTessellationError;
120 }
121
122 int vertex_item_count = tessGetVertexCount(tessellator) * kVertexSize;
123 auto vertices = tessGetVertices(tessellator);
124 for (int i = 0; i < vertex_item_count; i += 2) {
125 points.emplace_back(vertices[i], vertices[i + 1]);
126 }
127
128 int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
129 auto elements = tessGetElements(tessellator);
130 total += element_item_count;
131 for (int i = 0; i < element_item_count; i++) {
132 data.emplace_back(points[elements[i]].x);
133 data.emplace_back(points[elements[i]].y);
134 }
135 points.clear();
136 }
137 if (!callback(data.data(), total, nullptr, 0u)) {
138 return Result::kInputError;
139 }
140 } else {
141 //----------------------------------------------------------------------------
142 /// Feed contour information to the tessellator.
143 ///
144 static_assert(sizeof(Point) == 2 * sizeof(float));
145 for (size_t contour_i = 0; contour_i < polyline.contours.size();
146 contour_i++) {
147 size_t start_point_index, end_point_index;
148 std::tie(start_point_index, end_point_index) =
149 polyline.GetContourPointBounds(contour_i);
150
151 ::tessAddContour(tessellator, // the C tessellator
152 kVertexSize, //
153 polyline.points.data() + start_point_index, //
154 sizeof(Point), //
155 end_point_index - start_point_index //
156 );
157 }
158
159 //----------------------------------------------------------------------------
160 /// Let's tessellate.
161 ///
162 auto result = ::tessTesselate(tessellator, // tessellator
163 ToTessWindingRule(fill_type), // winding
164 TESS_POLYGONS, // element type
165 kPolygonSize, // polygon size
166 kVertexSize, // vertex size
167 nullptr // normal (null is automatic)
168 );
169
170 if (result != 1) {
171 return Result::kTessellationError;
172 }
173
174 int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
175
176 // We default to using a 16bit index buffer, but in cases where we generate
177 // more tessellated data than this can contain we need to fall back to
178 // dropping the index buffer entirely. Instead code could instead switch to
179 // a uint32 index buffer, but this is done for simplicity with the other
180 // fast path above.
181 if (element_item_count < USHRT_MAX) {
182 int vertex_item_count = tessGetVertexCount(tessellator);
183 auto vertices = tessGetVertices(tessellator);
184 auto elements = tessGetElements(tessellator);
185
186 // libtess uses an int index internally due to usage of -1 as a sentinel
187 // value.
188 std::vector<uint16_t> indices(element_item_count);
189 for (int i = 0; i < element_item_count; i++) {
190 indices[i] = static_cast<uint16_t>(elements[i]);
191 }
192 if (!callback(vertices, vertex_item_count, indices.data(),
193 element_item_count)) {
194 return Result::kInputError;
195 }
196 } else {
197 std::vector<Point> points;
198 std::vector<float> data;
199
200 int vertex_item_count = tessGetVertexCount(tessellator) * kVertexSize;
201 auto vertices = tessGetVertices(tessellator);
202 for (int i = 0; i < vertex_item_count; i += 2) {
203 points.emplace_back(vertices[i], vertices[i + 1]);
204 }
205
206 int element_item_count = tessGetElementCount(tessellator) * kPolygonSize;
207 auto elements = tessGetElements(tessellator);
208 for (int i = 0; i < element_item_count; i++) {
209 data.emplace_back(points[elements[i]].x);
210 data.emplace_back(points[elements[i]].y);
211 }
212 if (!callback(data.data(), element_item_count, nullptr, 0u)) {
213 return Result::kInputError;
214 }
215 }
216 }
217
218 return Result::kSuccess;
219 }
220
221 void DestroyTessellator(TESStesselator* tessellator) {
222 if (tessellator != nullptr) {
223 ::tessDeleteTess(tessellator);
224 }
225 }
226
227 } // 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::Tessellator::kMultiContourThreshold
static constexpr size_t kMultiContourThreshold
An arbitrary value to determine when a multi-contour non-zero fill path should be split into multiple...
Definition: tessellator.h:49
impeller::DestroyTessellator
void DestroyTessellator(TESStesselator *tessellator)
Definition: tessellator.cc:221
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:58
impeller::CTessellator
std::unique_ptr< TESStesselator, decltype(&DestroyTessellator)> CTessellator
Definition: tessellator.h:22