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