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