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