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