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