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