PathTessellator.cpp revision 272a685f17cc4828257e521a6f62b7b17870f75e
1/* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16#define LOG_NDEBUG 1 17 18#define VERTEX_DEBUG 0 19 20#if VERTEX_DEBUG 21#define DEBUG_DUMP_ALPHA_BUFFER() \ 22 for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) { \ 23 ALOGD("point %d at %f %f, alpha %f", \ 24 i, buffer[i].x, buffer[i].y, buffer[i].alpha); \ 25 } 26#define DEBUG_DUMP_BUFFER() \ 27 for (unsigned int i = 0; i < vertexBuffer.getSize(); i++) { \ 28 ALOGD("point %d at %f %f", i, buffer[i].x, buffer[i].y); \ 29 } 30#else 31#define DEBUG_DUMP_ALPHA_BUFFER() 32#define DEBUG_DUMP_BUFFER() 33#endif 34 35#include <SkPath.h> 36#include <SkPaint.h> 37#include <SkPoint.h> 38#include <SkGeometry.h> // WARNING: Internal Skia Header 39 40#include <stdlib.h> 41#include <stdint.h> 42#include <sys/types.h> 43 44#include <utils/Log.h> 45#include <utils/Trace.h> 46 47#include "PathTessellator.h" 48#include "Matrix.h" 49#include "Vector.h" 50#include "Vertex.h" 51#include "utils/MathUtils.h" 52 53namespace android { 54namespace uirenderer { 55 56#define OUTLINE_REFINE_THRESHOLD 0.5f 57#define ROUND_CAP_THRESH 0.25f 58#define PI 3.1415926535897932f 59#define MAX_DEPTH 15 60 61/** 62 * Extracts the x and y scale from the transform as positive values, and clamps them 63 */ 64void PathTessellator::extractTessellationScales(const Matrix4& transform, 65 float* scaleX, float* scaleY) { 66 if (CC_LIKELY(transform.isPureTranslate())) { 67 *scaleX = 1.0f; 68 *scaleY = 1.0f; 69 } else { 70 float m00 = transform.data[Matrix4::kScaleX]; 71 float m01 = transform.data[Matrix4::kSkewY]; 72 float m10 = transform.data[Matrix4::kSkewX]; 73 float m11 = transform.data[Matrix4::kScaleY]; 74 *scaleX = MathUtils::clampTessellationScale(sqrt(m00 * m00 + m01 * m01)); 75 *scaleY = MathUtils::clampTessellationScale(sqrt(m10 * m10 + m11 * m11)); 76 } 77} 78 79/** 80 * Produces a pseudo-normal for a vertex, given the normals of the two incoming lines. If the offset 81 * from each vertex in a perimeter is calculated, the resultant lines connecting the offset vertices 82 * will be offset by 1.0 83 * 84 * Note that we can't add and normalize the two vectors, that would result in a rectangle having an 85 * offset of (sqrt(2)/2, sqrt(2)/2) at each corner, instead of (1, 1) 86 * 87 * NOTE: assumes angles between normals 90 degrees or less 88 */ 89inline static Vector2 totalOffsetFromNormals(const Vector2& normalA, const Vector2& normalB) { 90 return (normalA + normalB) / (1 + fabs(normalA.dot(normalB))); 91} 92 93/** 94 * Structure used for storing useful information about the SkPaint and scale used for tessellating 95 */ 96struct PaintInfo { 97public: 98 PaintInfo(const SkPaint* paint, const mat4& transform) : 99 style(paint->getStyle()), cap(paint->getStrokeCap()), isAA(paint->isAntiAlias()), 100 halfStrokeWidth(paint->getStrokeWidth() * 0.5f), maxAlpha(1.0f) { 101 // compute inverse scales 102 if (CC_LIKELY(transform.isPureTranslate())) { 103 inverseScaleX = 1.0f; 104 inverseScaleY = 1.0f; 105 } else { 106 float scaleX, scaleY; 107 PathTessellator::extractTessellationScales(transform, &scaleX, &scaleY); 108 inverseScaleX = 1.0f / scaleX; 109 inverseScaleY = 1.0f / scaleY; 110 } 111 112 if (isAA && halfStrokeWidth != 0 && inverseScaleX == inverseScaleY && 113 2 * halfStrokeWidth < inverseScaleX) { 114 // AA, with non-hairline stroke, width < 1 pixel. Scale alpha and treat as hairline. 115 maxAlpha *= (2 * halfStrokeWidth) / inverseScaleX; 116 halfStrokeWidth = 0.0f; 117 } 118 } 119 120 SkPaint::Style style; 121 SkPaint::Cap cap; 122 bool isAA; 123 float inverseScaleX; 124 float inverseScaleY; 125 float halfStrokeWidth; 126 float maxAlpha; 127 128 inline void scaleOffsetForStrokeWidth(Vector2& offset) const { 129 if (halfStrokeWidth == 0.0f) { 130 // hairline - compensate for scale 131 offset.x *= 0.5f * inverseScaleX; 132 offset.y *= 0.5f * inverseScaleY; 133 } else { 134 offset *= halfStrokeWidth; 135 } 136 } 137 138 /** 139 * NOTE: the input will not always be a normal, especially for sharp edges - it should be the 140 * result of totalOffsetFromNormals (see documentation there) 141 */ 142 inline Vector2 deriveAAOffset(const Vector2& offset) const { 143 return (Vector2){offset.x * 0.5f * inverseScaleX, offset.y * 0.5f * inverseScaleY}; 144 } 145 146 /** 147 * Returns the number of cap divisions beyond the minimum 2 (kButt_Cap/kSquareCap will return 0) 148 * Should only be used when stroking and drawing caps 149 */ 150 inline int capExtraDivisions() const { 151 if (cap == SkPaint::kRound_Cap) { 152 // always use 2 points for hairline 153 if (halfStrokeWidth == 0.0f) return 2; 154 155 float threshold = MathUtils::min(inverseScaleX, inverseScaleY) * ROUND_CAP_THRESH; 156 return MathUtils::divisionsNeededToApproximateArc(halfStrokeWidth, PI, threshold); 157 } 158 return 0; 159 } 160 161 /** 162 * Outset the bounds of point data (for line endpoints or points) to account for stroke 163 * geometry. 164 * 165 * bounds are in pre-scaled space. 166 */ 167 void expandBoundsForStroke(Rect* bounds) const { 168 if (halfStrokeWidth == 0) { 169 // hairline, outset by (0.5f + fudge factor) in post-scaling space 170 bounds->outset(fabs(inverseScaleX) * (0.5f + Vertex::GeometryFudgeFactor()), 171 fabs(inverseScaleY) * (0.5f + Vertex::GeometryFudgeFactor())); 172 } else { 173 // non hairline, outset by half stroke width pre-scaled, and fudge factor post scaled 174 bounds->outset(halfStrokeWidth + fabs(inverseScaleX) * Vertex::GeometryFudgeFactor(), 175 halfStrokeWidth + fabs(inverseScaleY) * Vertex::GeometryFudgeFactor()); 176 } 177 } 178}; 179 180void getFillVerticesFromPerimeter(const std::vector<Vertex>& perimeter, 181 VertexBuffer& vertexBuffer) { 182 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size()); 183 184 int currentIndex = 0; 185 // zig zag between all previous points on the inside of the hull to create a 186 // triangle strip that fills the hull 187 int srcAindex = 0; 188 int srcBindex = perimeter.size() - 1; 189 while (srcAindex <= srcBindex) { 190 buffer[currentIndex++] = perimeter[srcAindex]; 191 if (srcAindex == srcBindex) break; 192 buffer[currentIndex++] = perimeter[srcBindex]; 193 srcAindex++; 194 srcBindex--; 195 } 196} 197 198/* 199 * Fills a vertexBuffer with non-alpha vertices, zig-zagging at each perimeter point to create a 200 * tri-strip as wide as the stroke. 201 * 202 * Uses an additional 2 vertices at the end to wrap around, closing the tri-strip 203 * (for a total of perimeter.size() * 2 + 2 vertices) 204 */ 205void getStrokeVerticesFromPerimeter(const PaintInfo& paintInfo, 206 const std::vector<Vertex>& perimeter, VertexBuffer& vertexBuffer) { 207 Vertex* buffer = vertexBuffer.alloc<Vertex>(perimeter.size() * 2 + 2); 208 209 int currentIndex = 0; 210 const Vertex* last = &(perimeter[perimeter.size() - 1]); 211 const Vertex* current = &(perimeter[0]); 212 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 213 lastNormal.normalize(); 214 for (unsigned int i = 0; i < perimeter.size(); i++) { 215 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 216 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 217 nextNormal.normalize(); 218 219 Vector2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 220 paintInfo.scaleOffsetForStrokeWidth(totalOffset); 221 222 Vertex::set(&buffer[currentIndex++], 223 current->x + totalOffset.x, 224 current->y + totalOffset.y); 225 226 Vertex::set(&buffer[currentIndex++], 227 current->x - totalOffset.x, 228 current->y - totalOffset.y); 229 230 current = next; 231 lastNormal = nextNormal; 232 } 233 234 // wrap around to beginning 235 buffer[currentIndex++] = buffer[0]; 236 buffer[currentIndex++] = buffer[1]; 237 238 DEBUG_DUMP_BUFFER(); 239} 240 241static inline void storeBeginEnd(const PaintInfo& paintInfo, const Vertex& center, 242 const Vector2& normal, Vertex* buffer, int& currentIndex, bool begin) { 243 Vector2 strokeOffset = normal; 244 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 245 246 Vector2 referencePoint = {center.x, center.y}; 247 if (paintInfo.cap == SkPaint::kSquare_Cap) { 248 Vector2 rotated = {-strokeOffset.y, strokeOffset.x}; 249 referencePoint += rotated * (begin ? -1 : 1); 250 } 251 252 Vertex::set(&buffer[currentIndex++], referencePoint + strokeOffset); 253 Vertex::set(&buffer[currentIndex++], referencePoint - strokeOffset); 254} 255 256/** 257 * Fills a vertexBuffer with non-alpha vertices similar to getStrokeVerticesFromPerimeter, except: 258 * 259 * 1 - Doesn't need to wrap around, since the input vertices are unclosed 260 * 261 * 2 - can zig-zag across 'extra' vertices at either end, to create round caps 262 */ 263void getStrokeVerticesFromUnclosedVertices(const PaintInfo& paintInfo, 264 const std::vector<Vertex>& vertices, VertexBuffer& vertexBuffer) { 265 const int extra = paintInfo.capExtraDivisions(); 266 const int allocSize = (vertices.size() + extra) * 2; 267 Vertex* buffer = vertexBuffer.alloc<Vertex>(allocSize); 268 269 const int lastIndex = vertices.size() - 1; 270 if (extra > 0) { 271 // tessellate both round caps 272 float beginTheta = atan2( 273 - (vertices[0].x - vertices[1].x), 274 vertices[0].y - vertices[1].y); 275 float endTheta = atan2( 276 - (vertices[lastIndex].x - vertices[lastIndex - 1].x), 277 vertices[lastIndex].y - vertices[lastIndex - 1].y); 278 const float dTheta = PI / (extra + 1); 279 280 int capOffset; 281 for (int i = 0; i < extra; i++) { 282 if (i < extra / 2) { 283 capOffset = extra - 2 * i - 1; 284 } else { 285 capOffset = 2 * i - extra; 286 } 287 288 beginTheta += dTheta; 289 Vector2 beginRadialOffset = {cosf(beginTheta), sinf(beginTheta)}; 290 paintInfo.scaleOffsetForStrokeWidth(beginRadialOffset); 291 Vertex::set(&buffer[capOffset], 292 vertices[0].x + beginRadialOffset.x, 293 vertices[0].y + beginRadialOffset.y); 294 295 endTheta += dTheta; 296 Vector2 endRadialOffset = {cosf(endTheta), sinf(endTheta)}; 297 paintInfo.scaleOffsetForStrokeWidth(endRadialOffset); 298 Vertex::set(&buffer[allocSize - 1 - capOffset], 299 vertices[lastIndex].x + endRadialOffset.x, 300 vertices[lastIndex].y + endRadialOffset.y); 301 } 302 } 303 304 int currentIndex = extra; 305 const Vertex* last = &(vertices[0]); 306 const Vertex* current = &(vertices[1]); 307 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 308 lastNormal.normalize(); 309 310 storeBeginEnd(paintInfo, vertices[0], lastNormal, buffer, currentIndex, true); 311 312 for (unsigned int i = 1; i < vertices.size() - 1; i++) { 313 const Vertex* next = &(vertices[i + 1]); 314 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 315 nextNormal.normalize(); 316 317 Vector2 strokeOffset = totalOffsetFromNormals(lastNormal, nextNormal); 318 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 319 320 Vector2 center = {current->x, current->y}; 321 Vertex::set(&buffer[currentIndex++], center + strokeOffset); 322 Vertex::set(&buffer[currentIndex++], center - strokeOffset); 323 324 current = next; 325 lastNormal = nextNormal; 326 } 327 328 storeBeginEnd(paintInfo, vertices[lastIndex], lastNormal, buffer, currentIndex, false); 329 330 DEBUG_DUMP_BUFFER(); 331} 332 333/** 334 * Populates a vertexBuffer with AlphaVertices to create an anti-aliased fill shape tessellation 335 * 336 * 1 - create the AA perimeter of unit width, by zig-zagging at each point around the perimeter of 337 * the shape (using 2 * perimeter.size() vertices) 338 * 339 * 2 - wrap around to the beginning to complete the perimeter (2 vertices) 340 * 341 * 3 - zig zag back and forth inside the shape to fill it (using perimeter.size() vertices) 342 */ 343void getFillVerticesFromPerimeterAA(const PaintInfo& paintInfo, 344 const std::vector<Vertex>& perimeter, VertexBuffer& vertexBuffer, 345 float maxAlpha = 1.0f) { 346 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(perimeter.size() * 3 + 2); 347 348 // generate alpha points - fill Alpha vertex gaps in between each point with 349 // alpha 0 vertex, offset by a scaled normal. 350 int currentIndex = 0; 351 const Vertex* last = &(perimeter[perimeter.size() - 1]); 352 const Vertex* current = &(perimeter[0]); 353 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 354 lastNormal.normalize(); 355 for (unsigned int i = 0; i < perimeter.size(); i++) { 356 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 357 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 358 nextNormal.normalize(); 359 360 // AA point offset from original point is that point's normal, such that each side is offset 361 // by .5 pixels 362 Vector2 totalOffset = paintInfo.deriveAAOffset(totalOffsetFromNormals(lastNormal, nextNormal)); 363 364 AlphaVertex::set(&buffer[currentIndex++], 365 current->x + totalOffset.x, 366 current->y + totalOffset.y, 367 0.0f); 368 AlphaVertex::set(&buffer[currentIndex++], 369 current->x - totalOffset.x, 370 current->y - totalOffset.y, 371 maxAlpha); 372 373 current = next; 374 lastNormal = nextNormal; 375 } 376 377 // wrap around to beginning 378 buffer[currentIndex++] = buffer[0]; 379 buffer[currentIndex++] = buffer[1]; 380 381 // zig zag between all previous points on the inside of the hull to create a 382 // triangle strip that fills the hull, repeating the first inner point to 383 // create degenerate tris to start inside path 384 int srcAindex = 0; 385 int srcBindex = perimeter.size() - 1; 386 while (srcAindex <= srcBindex) { 387 buffer[currentIndex++] = buffer[srcAindex * 2 + 1]; 388 if (srcAindex == srcBindex) break; 389 buffer[currentIndex++] = buffer[srcBindex * 2 + 1]; 390 srcAindex++; 391 srcBindex--; 392 } 393 394 DEBUG_DUMP_BUFFER(); 395} 396 397/** 398 * Stores geometry for a single, AA-perimeter (potentially rounded) cap 399 * 400 * For explanation of constants and general methodoloyg, see comments for 401 * getStrokeVerticesFromUnclosedVerticesAA() below. 402 */ 403inline static void storeCapAA(const PaintInfo& paintInfo, const std::vector<Vertex>& vertices, 404 AlphaVertex* buffer, bool isFirst, Vector2 normal, int offset) { 405 const int extra = paintInfo.capExtraDivisions(); 406 const int extraOffset = (extra + 1) / 2; 407 const int capIndex = isFirst 408 ? 2 * offset + 6 + 2 * (extra + extraOffset) 409 : offset + 2 + 2 * extraOffset; 410 if (isFirst) normal *= -1; 411 412 // TODO: this normal should be scaled by radialScale if extra != 0, see totalOffsetFromNormals() 413 Vector2 AAOffset = paintInfo.deriveAAOffset(normal); 414 415 Vector2 strokeOffset = normal; 416 paintInfo.scaleOffsetForStrokeWidth(strokeOffset); 417 Vector2 outerOffset = strokeOffset + AAOffset; 418 Vector2 innerOffset = strokeOffset - AAOffset; 419 420 Vector2 capAAOffset = {0, 0}; 421 if (paintInfo.cap != SkPaint::kRound_Cap) { 422 // if the cap is square or butt, the inside primary cap vertices will be inset in two 423 // directions - both normal to the stroke, and parallel to it. 424 capAAOffset = (Vector2){-AAOffset.y, AAOffset.x}; 425 } 426 427 // determine referencePoint, the center point for the 4 primary cap vertices 428 const Vertex& point = isFirst ? vertices.front() : vertices.back(); 429 Vector2 referencePoint = {point.x, point.y}; 430 if (paintInfo.cap == SkPaint::kSquare_Cap) { 431 // To account for square cap, move the primary cap vertices (that create the AA edge) by the 432 // stroke offset vector (rotated to be parallel to the stroke) 433 Vector2 rotated = {-strokeOffset.y, strokeOffset.x}; 434 referencePoint += rotated; 435 } 436 437 AlphaVertex::set(&buffer[capIndex + 0], 438 referencePoint.x + outerOffset.x + capAAOffset.x, 439 referencePoint.y + outerOffset.y + capAAOffset.y, 440 0.0f); 441 AlphaVertex::set(&buffer[capIndex + 1], 442 referencePoint.x + innerOffset.x - capAAOffset.x, 443 referencePoint.y + innerOffset.y - capAAOffset.y, 444 paintInfo.maxAlpha); 445 446 bool isRound = paintInfo.cap == SkPaint::kRound_Cap; 447 448 const int postCapIndex = (isRound && isFirst) ? (2 * extraOffset - 2) : capIndex + (2 * extra); 449 AlphaVertex::set(&buffer[postCapIndex + 2], 450 referencePoint.x - outerOffset.x + capAAOffset.x, 451 referencePoint.y - outerOffset.y + capAAOffset.y, 452 0.0f); 453 AlphaVertex::set(&buffer[postCapIndex + 3], 454 referencePoint.x - innerOffset.x - capAAOffset.x, 455 referencePoint.y - innerOffset.y - capAAOffset.y, 456 paintInfo.maxAlpha); 457 458 if (isRound) { 459 const float dTheta = PI / (extra + 1); 460 const float radialScale = 2.0f / (1 + cos(dTheta)); 461 float theta = atan2(normal.y, normal.x); 462 int capPerimIndex = capIndex + 2; 463 464 for (int i = 0; i < extra; i++) { 465 theta += dTheta; 466 467 Vector2 radialOffset = {cosf(theta), sinf(theta)}; 468 469 // scale to compensate for pinching at sharp angles, see totalOffsetFromNormals() 470 radialOffset *= radialScale; 471 472 AAOffset = paintInfo.deriveAAOffset(radialOffset); 473 paintInfo.scaleOffsetForStrokeWidth(radialOffset); 474 AlphaVertex::set(&buffer[capPerimIndex++], 475 referencePoint.x + radialOffset.x + AAOffset.x, 476 referencePoint.y + radialOffset.y + AAOffset.y, 477 0.0f); 478 AlphaVertex::set(&buffer[capPerimIndex++], 479 referencePoint.x + radialOffset.x - AAOffset.x, 480 referencePoint.y + radialOffset.y - AAOffset.y, 481 paintInfo.maxAlpha); 482 483 if (isFirst && i == extra - extraOffset) { 484 //copy most recent two points to first two points 485 buffer[0] = buffer[capPerimIndex - 2]; 486 buffer[1] = buffer[capPerimIndex - 1]; 487 488 capPerimIndex = 2; // start writing the rest of the round cap at index 2 489 } 490 } 491 492 if (isFirst) { 493 const int startCapFillIndex = capIndex + 2 * (extra - extraOffset) + 4; 494 int capFillIndex = startCapFillIndex; 495 for (int i = 0; i < extra + 2; i += 2) { 496 buffer[capFillIndex++] = buffer[1 + i]; 497 // TODO: to support odd numbers of divisions, break here on the last iteration 498 buffer[capFillIndex++] = buffer[startCapFillIndex - 3 - i]; 499 } 500 } else { 501 int capFillIndex = 6 * vertices.size() + 2 + 6 * extra - (extra + 2); 502 for (int i = 0; i < extra + 2; i += 2) { 503 buffer[capFillIndex++] = buffer[capIndex + 1 + i]; 504 // TODO: to support odd numbers of divisions, break here on the last iteration 505 buffer[capFillIndex++] = buffer[capIndex + 3 + 2 * extra - i]; 506 } 507 } 508 return; 509 } 510 if (isFirst) { 511 buffer[0] = buffer[postCapIndex + 2]; 512 buffer[1] = buffer[postCapIndex + 3]; 513 buffer[postCapIndex + 4] = buffer[1]; // degenerate tris (the only two!) 514 buffer[postCapIndex + 5] = buffer[postCapIndex + 1]; 515 } else { 516 buffer[6 * vertices.size()] = buffer[postCapIndex + 1]; 517 buffer[6 * vertices.size() + 1] = buffer[postCapIndex + 3]; 518 } 519} 520 521/* 522the geometry for an aa, capped stroke consists of the following: 523 524 # vertices | function 525---------------------------------------------------------------------- 526a) 2 | Start AA perimeter 527b) 2, 2 * roundDivOff | First half of begin cap's perimeter 528 | 529 2 * middlePts | 'Outer' or 'Top' AA perimeter half (between caps) 530 | 531a) 4 | End cap's 532b) 2, 2 * roundDivs, 2 | AA perimeter 533 | 534 2 * middlePts | 'Inner' or 'bottom' AA perimeter half 535 | 536a) 6 | Begin cap's perimeter 537b) 2, 2*(rD - rDO + 1), | Last half of begin cap's perimeter 538 roundDivs, 2 | 539 | 540 2 * middlePts | Stroke's full opacity center strip 541 | 542a) 2 | end stroke 543b) 2, roundDivs | (and end cap fill, for round) 544 545Notes: 546* rows starting with 'a)' denote the Butt or Square cap vertex use, 'b)' denote Round 547 548* 'middlePts' is (number of points in the unclosed input vertex list, minus 2) times two 549 550* 'roundDivs' or 'rD' is the number of extra vertices (beyond the minimum of 2) that define the 551 round cap's shape, and is at least two. This will increase with cap size to sufficiently 552 define the cap's level of tessellation. 553 554* 'roundDivOffset' or 'rDO' is the point about halfway along the start cap's round perimeter, where 555 the stream of vertices for the AA perimeter starts. By starting and ending the perimeter at 556 this offset, the fill of the stroke is drawn from this point with minimal extra vertices. 557 558This means the outer perimeter starts at: 559 outerIndex = (2) OR (2 + 2 * roundDivOff) 560the inner perimeter (since it is filled in reverse) starts at: 561 innerIndex = outerIndex + (4 * middlePts) + ((4) OR (4 + 2 * roundDivs)) - 1 562the stroke starts at: 563 strokeIndex = innerIndex + 1 + ((6) OR (6 + 3 * roundDivs - 2 * roundDivOffset)) 564 565The total needed allocated space is either: 566 2 + 4 + 6 + 2 + 3 * (2 * middlePts) = 14 + 6 * middlePts = 2 + 6 * pts 567or, for rounded caps: 568 (2 + 2 * rDO) + (4 + 2 * rD) + (2 * (rD - rDO + 1) 569 + roundDivs + 4) + (2 + roundDivs) + 3 * (2 * middlePts) 570 = 14 + 6 * middlePts + 6 * roundDivs 571 = 2 + 6 * pts + 6 * roundDivs 572 */ 573void getStrokeVerticesFromUnclosedVerticesAA(const PaintInfo& paintInfo, 574 const std::vector<Vertex>& vertices, VertexBuffer& vertexBuffer) { 575 576 const int extra = paintInfo.capExtraDivisions(); 577 const int allocSize = 6 * vertices.size() + 2 + 6 * extra; 578 579 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(allocSize); 580 581 const int extraOffset = (extra + 1) / 2; 582 int offset = 2 * (vertices.size() - 2); 583 // there is no outer/inner here, using them for consistency with below approach 584 int currentAAOuterIndex = 2 + 2 * extraOffset; 585 int currentAAInnerIndex = currentAAOuterIndex + (2 * offset) + 3 + (2 * extra); 586 int currentStrokeIndex = currentAAInnerIndex + 7 + (3 * extra - 2 * extraOffset); 587 588 const Vertex* last = &(vertices[0]); 589 const Vertex* current = &(vertices[1]); 590 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 591 lastNormal.normalize(); 592 593 // TODO: use normal from bezier traversal for cap, instead of from vertices 594 storeCapAA(paintInfo, vertices, buffer, true, lastNormal, offset); 595 596 for (unsigned int i = 1; i < vertices.size() - 1; i++) { 597 const Vertex* next = &(vertices[i + 1]); 598 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 599 nextNormal.normalize(); 600 601 Vector2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 602 Vector2 AAOffset = paintInfo.deriveAAOffset(totalOffset); 603 604 Vector2 innerOffset = totalOffset; 605 paintInfo.scaleOffsetForStrokeWidth(innerOffset); 606 Vector2 outerOffset = innerOffset + AAOffset; 607 innerOffset -= AAOffset; 608 609 AlphaVertex::set(&buffer[currentAAOuterIndex++], 610 current->x + outerOffset.x, 611 current->y + outerOffset.y, 612 0.0f); 613 AlphaVertex::set(&buffer[currentAAOuterIndex++], 614 current->x + innerOffset.x, 615 current->y + innerOffset.y, 616 paintInfo.maxAlpha); 617 618 AlphaVertex::set(&buffer[currentStrokeIndex++], 619 current->x + innerOffset.x, 620 current->y + innerOffset.y, 621 paintInfo.maxAlpha); 622 AlphaVertex::set(&buffer[currentStrokeIndex++], 623 current->x - innerOffset.x, 624 current->y - innerOffset.y, 625 paintInfo.maxAlpha); 626 627 AlphaVertex::set(&buffer[currentAAInnerIndex--], 628 current->x - innerOffset.x, 629 current->y - innerOffset.y, 630 paintInfo.maxAlpha); 631 AlphaVertex::set(&buffer[currentAAInnerIndex--], 632 current->x - outerOffset.x, 633 current->y - outerOffset.y, 634 0.0f); 635 636 current = next; 637 lastNormal = nextNormal; 638 } 639 640 // TODO: use normal from bezier traversal for cap, instead of from vertices 641 storeCapAA(paintInfo, vertices, buffer, false, lastNormal, offset); 642 643 DEBUG_DUMP_ALPHA_BUFFER(); 644} 645 646 647void getStrokeVerticesFromPerimeterAA(const PaintInfo& paintInfo, 648 const std::vector<Vertex>& perimeter, VertexBuffer& vertexBuffer) { 649 AlphaVertex* buffer = vertexBuffer.alloc<AlphaVertex>(6 * perimeter.size() + 8); 650 651 int offset = 2 * perimeter.size() + 3; 652 int currentAAOuterIndex = 0; 653 int currentStrokeIndex = offset; 654 int currentAAInnerIndex = offset * 2; 655 656 const Vertex* last = &(perimeter[perimeter.size() - 1]); 657 const Vertex* current = &(perimeter[0]); 658 Vector2 lastNormal = {current->y - last->y, last->x - current->x}; 659 lastNormal.normalize(); 660 for (unsigned int i = 0; i < perimeter.size(); i++) { 661 const Vertex* next = &(perimeter[i + 1 >= perimeter.size() ? 0 : i + 1]); 662 Vector2 nextNormal = {next->y - current->y, current->x - next->x}; 663 nextNormal.normalize(); 664 665 Vector2 totalOffset = totalOffsetFromNormals(lastNormal, nextNormal); 666 Vector2 AAOffset = paintInfo.deriveAAOffset(totalOffset); 667 668 Vector2 innerOffset = totalOffset; 669 paintInfo.scaleOffsetForStrokeWidth(innerOffset); 670 Vector2 outerOffset = innerOffset + AAOffset; 671 innerOffset -= AAOffset; 672 673 AlphaVertex::set(&buffer[currentAAOuterIndex++], 674 current->x + outerOffset.x, 675 current->y + outerOffset.y, 676 0.0f); 677 AlphaVertex::set(&buffer[currentAAOuterIndex++], 678 current->x + innerOffset.x, 679 current->y + innerOffset.y, 680 paintInfo.maxAlpha); 681 682 AlphaVertex::set(&buffer[currentStrokeIndex++], 683 current->x + innerOffset.x, 684 current->y + innerOffset.y, 685 paintInfo.maxAlpha); 686 AlphaVertex::set(&buffer[currentStrokeIndex++], 687 current->x - innerOffset.x, 688 current->y - innerOffset.y, 689 paintInfo.maxAlpha); 690 691 AlphaVertex::set(&buffer[currentAAInnerIndex++], 692 current->x - innerOffset.x, 693 current->y - innerOffset.y, 694 paintInfo.maxAlpha); 695 AlphaVertex::set(&buffer[currentAAInnerIndex++], 696 current->x - outerOffset.x, 697 current->y - outerOffset.y, 698 0.0f); 699 700 current = next; 701 lastNormal = nextNormal; 702 } 703 704 // wrap each strip around to beginning, creating degenerate tris to bridge strips 705 buffer[currentAAOuterIndex++] = buffer[0]; 706 buffer[currentAAOuterIndex++] = buffer[1]; 707 buffer[currentAAOuterIndex++] = buffer[1]; 708 709 buffer[currentStrokeIndex++] = buffer[offset]; 710 buffer[currentStrokeIndex++] = buffer[offset + 1]; 711 buffer[currentStrokeIndex++] = buffer[offset + 1]; 712 713 buffer[currentAAInnerIndex++] = buffer[2 * offset]; 714 buffer[currentAAInnerIndex++] = buffer[2 * offset + 1]; 715 // don't need to create last degenerate tri 716 717 DEBUG_DUMP_ALPHA_BUFFER(); 718} 719 720void PathTessellator::tessellatePath(const SkPath &path, const SkPaint* paint, 721 const mat4& transform, VertexBuffer& vertexBuffer) { 722 ATRACE_CALL(); 723 724 const PaintInfo paintInfo(paint, transform); 725 726 std::vector<Vertex> tempVertices; 727 float threshInvScaleX = paintInfo.inverseScaleX; 728 float threshInvScaleY = paintInfo.inverseScaleY; 729 if (paintInfo.style == SkPaint::kStroke_Style) { 730 // alter the bezier recursion threshold values we calculate in order to compensate for 731 // expansion done after the path vertices are found 732 SkRect bounds = path.getBounds(); 733 if (!bounds.isEmpty()) { 734 threshInvScaleX *= bounds.width() / (bounds.width() + paint->getStrokeWidth()); 735 threshInvScaleY *= bounds.height() / (bounds.height() + paint->getStrokeWidth()); 736 } 737 } 738 739 // force close if we're filling the path, since fill path expects closed perimeter. 740 bool forceClose = paintInfo.style != SkPaint::kStroke_Style; 741 PathApproximationInfo approximationInfo(threshInvScaleX, threshInvScaleY, 742 OUTLINE_REFINE_THRESHOLD); 743 bool wasClosed = approximatePathOutlineVertices(path, forceClose, 744 approximationInfo, tempVertices); 745 746 if (!tempVertices.size()) { 747 // path was empty, return without allocating vertex buffer 748 return; 749 } 750 751#if VERTEX_DEBUG 752 for (unsigned int i = 0; i < tempVertices.size(); i++) { 753 ALOGD("orig path: point at %f %f", 754 tempVertices[i].x, tempVertices[i].y); 755 } 756#endif 757 758 if (paintInfo.style == SkPaint::kStroke_Style) { 759 if (!paintInfo.isAA) { 760 if (wasClosed) { 761 getStrokeVerticesFromPerimeter(paintInfo, tempVertices, vertexBuffer); 762 } else { 763 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 764 } 765 766 } else { 767 if (wasClosed) { 768 getStrokeVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 769 } else { 770 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 771 } 772 } 773 } else { 774 // For kStrokeAndFill style, the path should be adjusted externally. 775 // It will be treated as a fill here. 776 if (!paintInfo.isAA) { 777 getFillVerticesFromPerimeter(tempVertices, vertexBuffer); 778 } else { 779 getFillVerticesFromPerimeterAA(paintInfo, tempVertices, vertexBuffer); 780 } 781 } 782 783 Rect bounds(path.getBounds()); 784 paintInfo.expandBoundsForStroke(&bounds); 785 vertexBuffer.setBounds(bounds); 786 vertexBuffer.setMeshFeatureFlags(paintInfo.isAA ? VertexBuffer::kAlpha : VertexBuffer::kNone); 787} 788 789template <class TYPE> 790static void instanceVertices(VertexBuffer& srcBuffer, VertexBuffer& dstBuffer, 791 const float* points, int count, Rect& bounds) { 792 bounds.set(points[0], points[1], points[0], points[1]); 793 794 int numPoints = count / 2; 795 int verticesPerPoint = srcBuffer.getVertexCount(); 796 dstBuffer.alloc<TYPE>(numPoints * verticesPerPoint + (numPoints - 1) * 2); 797 798 for (int i = 0; i < count; i += 2) { 799 bounds.expandToCoverVertex(points[i + 0], points[i + 1]); 800 dstBuffer.copyInto<TYPE>(srcBuffer, points[i + 0], points[i + 1]); 801 } 802 dstBuffer.createDegenerateSeparators<TYPE>(verticesPerPoint); 803} 804 805void PathTessellator::tessellatePoints(const float* points, int count, const SkPaint* paint, 806 const mat4& transform, VertexBuffer& vertexBuffer) { 807 const PaintInfo paintInfo(paint, transform); 808 809 // determine point shape 810 SkPath path; 811 float radius = paintInfo.halfStrokeWidth; 812 if (radius == 0.0f) radius = 0.5f; 813 814 if (paintInfo.cap == SkPaint::kRound_Cap) { 815 path.addCircle(0, 0, radius); 816 } else { 817 path.addRect(-radius, -radius, radius, radius); 818 } 819 820 // calculate outline 821 std::vector<Vertex> outlineVertices; 822 PathApproximationInfo approximationInfo(paintInfo.inverseScaleX, paintInfo.inverseScaleY, 823 OUTLINE_REFINE_THRESHOLD); 824 approximatePathOutlineVertices(path, true, approximationInfo, outlineVertices); 825 826 if (!outlineVertices.size()) return; 827 828 Rect bounds; 829 // tessellate, then duplicate outline across points 830 VertexBuffer tempBuffer; 831 if (!paintInfo.isAA) { 832 getFillVerticesFromPerimeter(outlineVertices, tempBuffer); 833 instanceVertices<Vertex>(tempBuffer, vertexBuffer, points, count, bounds); 834 } else { 835 // note: pass maxAlpha directly, since we want fill to be alpha modulated 836 getFillVerticesFromPerimeterAA(paintInfo, outlineVertices, tempBuffer, paintInfo.maxAlpha); 837 instanceVertices<AlphaVertex>(tempBuffer, vertexBuffer, points, count, bounds); 838 } 839 840 // expand bounds from vertex coords to pixel data 841 paintInfo.expandBoundsForStroke(&bounds); 842 vertexBuffer.setBounds(bounds); 843 vertexBuffer.setMeshFeatureFlags(paintInfo.isAA ? VertexBuffer::kAlpha : VertexBuffer::kNone); 844} 845 846void PathTessellator::tessellateLines(const float* points, int count, const SkPaint* paint, 847 const mat4& transform, VertexBuffer& vertexBuffer) { 848 ATRACE_CALL(); 849 const PaintInfo paintInfo(paint, transform); 850 851 const int extra = paintInfo.capExtraDivisions(); 852 int numLines = count / 4; 853 int lineAllocSize; 854 // pre-allocate space for lines in the buffer, and degenerate tris in between 855 if (paintInfo.isAA) { 856 lineAllocSize = 6 * (2) + 2 + 6 * extra; 857 vertexBuffer.alloc<AlphaVertex>(numLines * lineAllocSize + (numLines - 1) * 2); 858 } else { 859 lineAllocSize = 2 * ((2) + extra); 860 vertexBuffer.alloc<Vertex>(numLines * lineAllocSize + (numLines - 1) * 2); 861 } 862 863 std::vector<Vertex> tempVertices(2); 864 Vertex* tempVerticesData = &tempVertices.front(); 865 Rect bounds; 866 bounds.set(points[0], points[1], points[0], points[1]); 867 for (int i = 0; i < count; i += 4) { 868 Vertex::set(&(tempVerticesData[0]), points[i + 0], points[i + 1]); 869 Vertex::set(&(tempVerticesData[1]), points[i + 2], points[i + 3]); 870 871 if (paintInfo.isAA) { 872 getStrokeVerticesFromUnclosedVerticesAA(paintInfo, tempVertices, vertexBuffer); 873 } else { 874 getStrokeVerticesFromUnclosedVertices(paintInfo, tempVertices, vertexBuffer); 875 } 876 877 // calculate bounds 878 bounds.expandToCoverVertex(tempVerticesData[0].x, tempVerticesData[0].y); 879 bounds.expandToCoverVertex(tempVerticesData[1].x, tempVerticesData[1].y); 880 } 881 882 // since multiple objects tessellated into buffer, separate them with degen tris 883 if (paintInfo.isAA) { 884 vertexBuffer.createDegenerateSeparators<AlphaVertex>(lineAllocSize); 885 } else { 886 vertexBuffer.createDegenerateSeparators<Vertex>(lineAllocSize); 887 } 888 889 // expand bounds from vertex coords to pixel data 890 paintInfo.expandBoundsForStroke(&bounds); 891 vertexBuffer.setBounds(bounds); 892 vertexBuffer.setMeshFeatureFlags(paintInfo.isAA ? VertexBuffer::kAlpha : VertexBuffer::kNone); 893} 894 895/////////////////////////////////////////////////////////////////////////////// 896// Simple path line approximation 897/////////////////////////////////////////////////////////////////////////////// 898 899bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, float threshold, 900 std::vector<Vertex>& outputVertices) { 901 PathApproximationInfo approximationInfo(1.0f, 1.0f, threshold); 902 return approximatePathOutlineVertices(path, true, approximationInfo, outputVertices); 903} 904 905class ClockwiseEnforcer { 906public: 907 void addPoint(const SkPoint& point) { 908 double x = point.x(); 909 double y = point.y(); 910 911 if (initialized) { 912 sum += (x + lastX) * (y - lastY); 913 } else { 914 initialized = true; 915 } 916 917 lastX = x; 918 lastY = y; 919 } 920 void reverseVectorIfNotClockwise(std::vector<Vertex>& vertices) { 921 if (sum < 0) { 922 // negative sum implies CounterClockwise 923 const int size = vertices.size(); 924 for (int i = 0; i < size / 2; i++) { 925 Vertex tmp = vertices[i]; 926 int k = size - 1 - i; 927 vertices[i] = vertices[k]; 928 vertices[k] = tmp; 929 } 930 } 931 } 932private: 933 bool initialized = false; 934 double lastX = 0; 935 double lastY = 0; 936 double sum = 0; 937}; 938 939bool PathTessellator::approximatePathOutlineVertices(const SkPath& path, bool forceClose, 940 const PathApproximationInfo& approximationInfo, std::vector<Vertex>& outputVertices) { 941 ATRACE_CALL(); 942 943 // TODO: to support joins other than sharp miter, join vertices should be labelled in the 944 // perimeter, or resolved into more vertices. Reconsider forceClose-ing in that case. 945 SkPath::Iter iter(path, forceClose); 946 SkPoint pts[4]; 947 SkPath::Verb v; 948 ClockwiseEnforcer clockwiseEnforcer; 949 while (SkPath::kDone_Verb != (v = iter.next(pts))) { 950 switch (v) { 951 case SkPath::kMove_Verb: 952 outputVertices.push_back(Vertex{pts[0].x(), pts[0].y()}); 953 ALOGV("Move to pos %f %f", pts[0].x(), pts[0].y()); 954 clockwiseEnforcer.addPoint(pts[0]); 955 break; 956 case SkPath::kClose_Verb: 957 ALOGV("Close at pos %f %f", pts[0].x(), pts[0].y()); 958 clockwiseEnforcer.addPoint(pts[0]); 959 break; 960 case SkPath::kLine_Verb: 961 ALOGV("kLine_Verb %f %f -> %f %f", pts[0].x(), pts[0].y(), pts[1].x(), pts[1].y()); 962 outputVertices.push_back(Vertex{pts[1].x(), pts[1].y()}); 963 clockwiseEnforcer.addPoint(pts[1]); 964 break; 965 case SkPath::kQuad_Verb: 966 ALOGV("kQuad_Verb"); 967 recursiveQuadraticBezierVertices( 968 pts[0].x(), pts[0].y(), 969 pts[2].x(), pts[2].y(), 970 pts[1].x(), pts[1].y(), 971 approximationInfo, outputVertices); 972 clockwiseEnforcer.addPoint(pts[1]); 973 clockwiseEnforcer.addPoint(pts[2]); 974 break; 975 case SkPath::kCubic_Verb: 976 ALOGV("kCubic_Verb"); 977 recursiveCubicBezierVertices( 978 pts[0].x(), pts[0].y(), 979 pts[1].x(), pts[1].y(), 980 pts[3].x(), pts[3].y(), 981 pts[2].x(), pts[2].y(), 982 approximationInfo, outputVertices); 983 clockwiseEnforcer.addPoint(pts[1]); 984 clockwiseEnforcer.addPoint(pts[2]); 985 clockwiseEnforcer.addPoint(pts[3]); 986 break; 987 case SkPath::kConic_Verb: { 988 ALOGV("kConic_Verb"); 989 SkAutoConicToQuads converter; 990 const SkPoint* quads = converter.computeQuads(pts, iter.conicWeight(), 991 approximationInfo.thresholdForConicQuads); 992 for (int i = 0; i < converter.countQuads(); ++i) { 993 const int offset = 2 * i; 994 recursiveQuadraticBezierVertices( 995 quads[offset].x(), quads[offset].y(), 996 quads[offset+2].x(), quads[offset+2].y(), 997 quads[offset+1].x(), quads[offset+1].y(), 998 approximationInfo, outputVertices); 999 } 1000 clockwiseEnforcer.addPoint(pts[1]); 1001 clockwiseEnforcer.addPoint(pts[2]); 1002 break; 1003 } 1004 default: 1005 break; 1006 } 1007 } 1008 1009 bool wasClosed = false; 1010 int size = outputVertices.size(); 1011 if (size >= 2 && outputVertices[0].x == outputVertices[size - 1].x && 1012 outputVertices[0].y == outputVertices[size - 1].y) { 1013 outputVertices.pop_back(); 1014 wasClosed = true; 1015 } 1016 1017 // ensure output vector is clockwise 1018 clockwiseEnforcer.reverseVectorIfNotClockwise(outputVertices); 1019 return wasClosed; 1020} 1021 1022/////////////////////////////////////////////////////////////////////////////// 1023// Bezier approximation 1024// 1025// All the inputs and outputs here are in path coordinates. 1026// We convert the error threshold from screen coordinates into path coordinates. 1027/////////////////////////////////////////////////////////////////////////////// 1028 1029// Get a threshold in path coordinates, by scaling the thresholdSquared from screen coordinates. 1030// TODO: Document the math behind this algorithm. 1031static inline float getThreshold(const PathApproximationInfo& info, float dx, float dy) { 1032 // multiplying by sqrInvScaleY/X equivalent to multiplying in dimensional scale factors 1033 float scale = (dx * dx * info.sqrInvScaleY + dy * dy * info.sqrInvScaleX); 1034 return info.thresholdSquared * scale; 1035} 1036 1037void PathTessellator::recursiveCubicBezierVertices( 1038 float p1x, float p1y, float c1x, float c1y, 1039 float p2x, float p2y, float c2x, float c2y, 1040 const PathApproximationInfo& approximationInfo, 1041 std::vector<Vertex>& outputVertices, int depth) { 1042 float dx = p2x - p1x; 1043 float dy = p2y - p1y; 1044 float d1 = fabs((c1x - p2x) * dy - (c1y - p2y) * dx); 1045 float d2 = fabs((c2x - p2x) * dy - (c2y - p2y) * dx); 1046 float d = d1 + d2; 1047 1048 if (depth >= MAX_DEPTH 1049 || d * d <= getThreshold(approximationInfo, dx, dy)) { 1050 // below thresh, draw line by adding endpoint 1051 outputVertices.push_back(Vertex{p2x, p2y}); 1052 } else { 1053 float p1c1x = (p1x + c1x) * 0.5f; 1054 float p1c1y = (p1y + c1y) * 0.5f; 1055 float p2c2x = (p2x + c2x) * 0.5f; 1056 float p2c2y = (p2y + c2y) * 0.5f; 1057 1058 float c1c2x = (c1x + c2x) * 0.5f; 1059 float c1c2y = (c1y + c2y) * 0.5f; 1060 1061 float p1c1c2x = (p1c1x + c1c2x) * 0.5f; 1062 float p1c1c2y = (p1c1y + c1c2y) * 0.5f; 1063 1064 float p2c1c2x = (p2c2x + c1c2x) * 0.5f; 1065 float p2c1c2y = (p2c2y + c1c2y) * 0.5f; 1066 1067 float mx = (p1c1c2x + p2c1c2x) * 0.5f; 1068 float my = (p1c1c2y + p2c1c2y) * 0.5f; 1069 1070 recursiveCubicBezierVertices( 1071 p1x, p1y, p1c1x, p1c1y, 1072 mx, my, p1c1c2x, p1c1c2y, 1073 approximationInfo, outputVertices, depth + 1); 1074 recursiveCubicBezierVertices( 1075 mx, my, p2c1c2x, p2c1c2y, 1076 p2x, p2y, p2c2x, p2c2y, 1077 approximationInfo, outputVertices, depth + 1); 1078 } 1079} 1080 1081void PathTessellator::recursiveQuadraticBezierVertices( 1082 float ax, float ay, 1083 float bx, float by, 1084 float cx, float cy, 1085 const PathApproximationInfo& approximationInfo, 1086 std::vector<Vertex>& outputVertices, int depth) { 1087 float dx = bx - ax; 1088 float dy = by - ay; 1089 // d is the cross product of vector (B-A) and (C-B). 1090 float d = (cx - bx) * dy - (cy - by) * dx; 1091 1092 if (depth >= MAX_DEPTH 1093 || d * d <= getThreshold(approximationInfo, dx, dy)) { 1094 // below thresh, draw line by adding endpoint 1095 outputVertices.push_back(Vertex{bx, by}); 1096 } else { 1097 float acx = (ax + cx) * 0.5f; 1098 float bcx = (bx + cx) * 0.5f; 1099 float acy = (ay + cy) * 0.5f; 1100 float bcy = (by + cy) * 0.5f; 1101 1102 // midpoint 1103 float mx = (acx + bcx) * 0.5f; 1104 float my = (acy + bcy) * 0.5f; 1105 1106 recursiveQuadraticBezierVertices(ax, ay, mx, my, acx, acy, 1107 approximationInfo, outputVertices, depth + 1); 1108 recursiveQuadraticBezierVertices(mx, my, bx, by, bcx, bcy, 1109 approximationInfo, outputVertices, depth + 1); 1110 } 1111} 1112 1113}; // namespace uirenderer 1114}; // namespace android 1115