1 /* 2 * Copyright (C) 2011 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include "config.h" 27 28 #include "LoopBlinnPathProcessor.h" 29 30 #include "FloatPoint.h" 31 #include "FloatRect.h" 32 #include "LoopBlinnClassifier.h" 33 #include "LoopBlinnConstants.h" 34 #include "LoopBlinnLocalTriangulator.h" 35 #include "LoopBlinnMathUtils.h" 36 #include "LoopBlinnPathCache.h" 37 #include "LoopBlinnTextureCoords.h" 38 #include "PODArena.h" 39 #include "PODIntervalTree.h" 40 #include "Path.h" 41 #include "internal_glu.h" 42 #include <algorithm> 43 #include <wtf/Assertions.h> 44 #include <wtf/FastMalloc.h> 45 #include <wtf/UnusedParam.h> 46 47 48 #if USE(SKIA) 49 #include "SkGeometry.h" 50 #include "SkPath.h" 51 #include "SkScalar.h" 52 #else 53 // Must port to your platform. 54 #endif 55 56 namespace WebCore { 57 58 using LoopBlinnMathUtils::XRay; 59 using LoopBlinnMathUtils::chopCubicAt; 60 using LoopBlinnMathUtils::numXRayCrossingsForCubic; 61 using LoopBlinnMathUtils::trianglesOverlap; 62 using LoopBlinnMathUtils::xRayCrossesLine; 63 using LoopBlinnPathProcessorImplementation::Contour; 64 using LoopBlinnPathProcessorImplementation::Segment; 65 66 namespace { 67 68 #ifndef NDEBUG 69 String valueToString(const FloatRect& arg) 70 { 71 StringBuilder builder; 72 builder.append("[FloatRect x="); 73 builder.append(String::number(arg.x())); 74 builder.append(" y="); 75 builder.append(String::number(arg.y())); 76 builder.append(" maxX="); 77 builder.append(String::number(arg.maxX())); 78 builder.append(" maxY="); 79 builder.append(String::number(arg.maxY())); 80 builder.append("]"); 81 return builder.toString(); 82 } 83 #endif 84 85 struct SweepData; 86 87 } // anonymous namespace 88 89 namespace LoopBlinnPathProcessorImplementation { 90 class Segment; 91 } 92 93 #ifndef NDEBUG 94 // Routines needed to print the types of IntervalNodes we instantiate 95 // in this file. 96 template <> 97 struct ValueToString<float> { 98 static String string(const float& value) 99 { 100 return String::number(value); 101 } 102 }; 103 104 template <> 105 struct ValueToString<SweepData*> { 106 static String string(SweepData* const& value) 107 { 108 return String::format("0x%p", value); 109 } 110 }; 111 112 template <> 113 struct ValueToString<LoopBlinnPathProcessorImplementation::Segment*> { 114 static String string(LoopBlinnPathProcessorImplementation::Segment* const& value) 115 { 116 return String::format("0x%p", value); 117 } 118 }; 119 #endif 120 121 namespace LoopBlinnPathProcessorImplementation { 122 123 //---------------------------------------------------------------------- 124 // Segment 125 // 126 127 // Describes a segment of the path: either a cubic or a line segment. 128 // These are stored in a doubly linked list to speed up curve 129 // subdivision, which occurs due to either rendering artifacts in the 130 // loop case or due to overlapping triangles. 131 class Segment { 132 WTF_MAKE_NONCOPYABLE(Segment); 133 public: 134 enum Kind { 135 Cubic, 136 Line 137 }; 138 139 // No-argument constructor allows construction by the PODArena class. 140 Segment() 141 : m_arena(0) 142 , m_kind(Cubic) 143 , m_prev(0) 144 , m_next(0) 145 , m_contour(0) 146 , m_triangulator(0) 147 , m_markedForSubdivision(false) 148 { 149 } 150 151 // Initializer for cubic curve segments. 152 void setup(PODArena* arena, 153 Contour* contour, 154 FloatPoint cp0, 155 FloatPoint cp1, 156 FloatPoint cp2, 157 FloatPoint cp3) 158 { 159 m_arena = arena; 160 m_contour = contour; 161 m_kind = Cubic; 162 m_points[0] = cp0; 163 m_points[1] = cp1; 164 m_points[2] = cp2; 165 m_points[3] = cp3; 166 computeBoundingBox(); 167 } 168 169 // Initializer for line segments. 170 void setup(PODArena* arena, 171 Contour* contour, 172 FloatPoint p0, 173 FloatPoint p1) 174 { 175 m_arena = arena; 176 m_contour = contour; 177 m_kind = Line; 178 m_points[0] = p0; 179 m_points[1] = p1; 180 computeBoundingBox(); 181 } 182 183 Kind kind() const { return m_kind; } 184 185 // Returns the i'th control point, 0 <= i < 4. 186 const FloatPoint& getPoint(int i) 187 { 188 ASSERT(i >= 0 && i < 4); 189 return m_points[i]; 190 } 191 192 Segment* next() const { return m_next; } 193 Segment* prev() const { return m_prev; } 194 195 void setNext(Segment* next) { m_next = next; } 196 void setPrev(Segment* prev) { m_prev = prev; } 197 198 // The contour this segment belongs to. 199 Contour* contour() const { return m_contour; } 200 201 // Subdivides the current segment at the given parameter value (0 <= 202 // t <= 1) and replaces it with the two newly created Segments in 203 // the linked list, if possible. Returns a pointer to the leftmost 204 // Segment. 205 Segment* subdivide(float param) 206 { 207 FloatPoint dst[7]; 208 chopCubicAt(m_points, dst, param); 209 Segment* left = m_arena->allocateObject<Segment>(); 210 Segment* right = m_arena->allocateObject<Segment>(); 211 left->setup(m_arena, m_contour, dst[0], dst[1], dst[2], dst[3]); 212 right->setup(m_arena, m_contour, dst[3], dst[4], dst[5], dst[6]); 213 left->setNext(right); 214 right->setPrev(left); 215 // Try to set up a link between "this->prev()" and "left". 216 if (prev()) { 217 left->setPrev(prev()); 218 prev()->setNext(left); 219 } 220 // Try to set up a link between "this->next()" and "right". 221 Segment* n = next(); 222 if (n) { 223 right->setNext(n); 224 n->setPrev(right); 225 } 226 // Set up a link between "this" and "left"; this is only to 227 // provide a certain amount of continuity during forward iteration. 228 setNext(left); 229 return left; 230 } 231 232 // Subdivides the current segment at the halfway point and replaces 233 // it with the two newly created Segments in the linked list, if 234 // possible. Returns a pointer to the leftmost Segment. 235 Segment* subdivide() { return subdivide(0.5f); } 236 237 const FloatRect& boundingBox() const { return m_boundingBox; } 238 239 // Computes the number of times a query line starting at the given 240 // point and extending to x=+infinity crosses this segment. Outgoing 241 // "ambiguous" argument indicates whether the query intersected an 242 // endpoint or tangent point of the segment, indicating that another 243 // query point is preferred. 244 int numCrossingsForXRay(const XRay& xRay, bool& ambiguous) const 245 { 246 if (m_kind == Cubic) 247 // Should consider caching the monotonic cubics. 248 return numXRayCrossingsForCubic(xRay, m_points, ambiguous); 249 250 return xRayCrossesLine(xRay, m_points, ambiguous) ? 1 : 0; 251 } 252 253 // Performs a local triangulation of the control points in this 254 // segment. This operation only makes sense for cubic type segments. 255 // texCoords may be null when the klm coordinates have not been 256 // computed yet. 257 void triangulate(LoopBlinnLocalTriangulator::InsideEdgeComputation computeInsideEdges, 258 const LoopBlinnTextureCoords::Result* texCoords); 259 260 // Returns the number of control point triangles associated with 261 // this segment. 262 int numberOfTriangles() const 263 { 264 if (!m_triangulator) 265 return 0; 266 return m_triangulator->numberOfTriangles(); 267 } 268 269 // Fetches the given control point triangle for this segment. 270 LoopBlinnLocalTriangulator::Triangle* getTriangle(int index) 271 { 272 ASSERT(m_triangulator); 273 return m_triangulator->getTriangle(index); 274 } 275 276 // Number of vertices along the inside edge of this segment. This 277 // can be called either for line or cubic type segments. 278 int numberOfInteriorVertices() const 279 { 280 if (m_kind == Cubic) { 281 if (m_triangulator) 282 return m_triangulator->numberOfInteriorVertices(); 283 284 return 0; 285 } 286 287 return 2; 288 } 289 290 // Returns the given interior vertex, 0 <= index < numberOfInteriorVertices(). 291 FloatPoint getInteriorVertex(int index) const 292 { 293 ASSERT(index >= 0 && index < numberOfInteriorVertices()); 294 if (m_kind == Cubic) { 295 FloatPoint res; 296 if (m_triangulator) { 297 LoopBlinnLocalTriangulator::Vertex* vertex = m_triangulator->getInteriorVertex(index); 298 if (vertex) 299 res.set(vertex->xyCoordinates().x(), vertex->xyCoordinates().y()); 300 } 301 return res; 302 } 303 304 return m_points[index]; 305 } 306 307 // State to assist with curve subdivision. 308 bool markedForSubdivision() const { return m_markedForSubdivision; } 309 void setMarkedForSubdivision(bool markedForSubdivision) { m_markedForSubdivision = markedForSubdivision; } 310 311 #ifndef NDEBUG 312 // Suppport for printing Segments. 313 String toString() const 314 { 315 StringBuilder builder; 316 builder.append("[Segment kind="); 317 builder.append(kind() == Line ? "line" : "cubic"); 318 builder.append(" boundingBox="); 319 builder.append(valueToString(boundingBox())); 320 builder.append(" contour=0x"); 321 builder.append(String::format("%p", contour())); 322 builder.append(" markedForSubdivision="); 323 builder.append(markedForSubdivision() ? "true" : "false"); 324 builder.append("]"); 325 return builder.toString(); 326 } 327 #endif 328 329 private: 330 // Computes the bounding box of this Segment. 331 void computeBoundingBox() 332 { 333 switch (m_kind) { 334 case Cubic: 335 m_boundingBox.fitToPoints(m_points[0], m_points[1], m_points[2], m_points[3]); 336 break; 337 338 case Line: 339 m_boundingBox.fitToPoints(m_points[0], m_points[1]); 340 break; 341 } 342 } 343 344 PODArena* m_arena; 345 Kind m_kind; 346 FloatPoint m_points[4]; 347 Segment* m_prev; 348 Segment* m_next; 349 Contour* m_contour; 350 FloatRect m_boundingBox; 351 LoopBlinnLocalTriangulator* m_triangulator; 352 bool m_markedForSubdivision; 353 }; 354 355 //---------------------------------------------------------------------- 356 // Contour 357 // 358 359 // Describes a closed contour of the path. 360 class Contour { 361 WTF_MAKE_NONCOPYABLE(Contour); 362 public: 363 Contour() 364 { 365 m_first = &m_sentinel; 366 m_first->setNext(m_first); 367 m_first->setPrev(m_first); 368 m_isOrientedCounterClockwise = true; 369 m_boundingBoxDirty = false; 370 m_fillSide = LoopBlinnConstants::RightSide; 371 } 372 373 void add(Segment* segment) 374 { 375 if (m_first == &m_sentinel) { 376 // First element is the sentinel. Replace it with the incoming 377 // segment. 378 segment->setNext(m_first); 379 segment->setPrev(m_first); 380 m_first->setNext(segment); 381 m_first->setPrev(segment); 382 m_first = segment; 383 } else { 384 // m_first->prev() is the sentinel. 385 ASSERT(m_first->prev() == &m_sentinel); 386 Segment* last = m_sentinel.prev(); 387 last->setNext(segment); 388 segment->setPrev(last); 389 segment->setNext(&m_sentinel); 390 m_sentinel.setPrev(segment); 391 } 392 m_boundingBoxDirty = true; 393 } 394 395 // Subdivides the given segment at the given parametric value. 396 // Returns a pointer to the first of the two portions of the 397 // subdivided segment. 398 Segment* subdivide(Segment* segment, float param) 399 { 400 Segment* left = segment->subdivide(param); 401 if (m_first == segment) 402 m_first = left; 403 return left; 404 } 405 406 // Subdivides the given segment at the halfway point. Returns a 407 // pointer to the first of the two portions of the subdivided 408 // segment. 409 Segment* subdivide(Segment* segment) 410 { 411 Segment* left = segment->subdivide(); 412 if (m_first == segment) 413 m_first = left; 414 return left; 415 } 416 417 // Returns the first segment in the contour for iteration. 418 Segment* begin() const { return m_first; } 419 420 // Returns the last segment in the contour for iteration. Callers 421 // should not iterate over this segment. In other words: 422 // for (Segment* cur = contour->begin(); 423 // cur != contour->end(); 424 // cur = cur->next()) { 425 // // .. process cur ... 426 // } 427 Segment* end() 428 { 429 ASSERT(m_first->prev() == &m_sentinel); 430 return &m_sentinel; 431 } 432 433 bool isOrientedCounterClockwise() const { return m_isOrientedCounterClockwise; } 434 void setIsOrientedCounterClockwise(bool isOrientedCounterClockwise) { m_isOrientedCounterClockwise = isOrientedCounterClockwise; } 435 436 const FloatRect& boundingBox() 437 { 438 if (m_boundingBoxDirty) { 439 bool first = true; 440 for (Segment* cur = begin(); cur != end(); cur = cur->next()) { 441 if (first) 442 m_boundingBox = cur->boundingBox(); 443 else 444 m_boundingBox.unite(cur->boundingBox()); 445 first = false; 446 } 447 448 m_boundingBoxDirty = false; 449 } 450 return m_boundingBox; 451 } 452 453 // Returns which side of this contour is filled. 454 LoopBlinnConstants::FillSide fillSide() const 455 { 456 return m_fillSide; 457 } 458 459 void setFillSide(LoopBlinnConstants::FillSide fillSide) 460 { 461 m_fillSide = fillSide; 462 } 463 464 private: 465 // The start of the segment chain. The segments are kept in a 466 // circular doubly linked list for rapid access to the beginning and 467 // end. 468 Segment* m_first; 469 470 // The sentinel element at the end of the chain, needed for 471 // reasonable iteration semantics. 472 Segment m_sentinel; 473 474 bool m_isOrientedCounterClockwise; 475 476 FloatRect m_boundingBox; 477 bool m_boundingBoxDirty; 478 479 // Which side of this contour should be filled. 480 LoopBlinnConstants::FillSide m_fillSide; 481 }; 482 483 //---------------------------------------------------------------------- 484 // Segment 485 // 486 487 // Definition of Segment::triangulate(), which must come after 488 // declaration of Contour. 489 void Segment::triangulate(LoopBlinnLocalTriangulator::InsideEdgeComputation computeInsideEdges, 490 const LoopBlinnTextureCoords::Result* texCoords) 491 { 492 ASSERT(m_kind == Cubic); 493 if (!m_triangulator) 494 m_triangulator = m_arena->allocateObject<LoopBlinnLocalTriangulator>(); 495 m_triangulator->reset(); 496 for (int i = 0; i < 4; i++) { 497 LoopBlinnLocalTriangulator::Vertex* vertex = m_triangulator->getVertex(i); 498 if (texCoords) { 499 vertex->set(getPoint(i).x(), 500 getPoint(i).y(), 501 texCoords->klmCoordinates[i].x(), 502 texCoords->klmCoordinates[i].y(), 503 texCoords->klmCoordinates[i].z()); 504 } else { 505 vertex->set(getPoint(i).x(), 506 getPoint(i).y(), 507 // No texture coordinates yet 508 0, 0, 0); 509 } 510 } 511 m_triangulator->triangulate(computeInsideEdges, contour()->fillSide()); 512 } 513 514 } // namespace LoopBlinnPathProcessorImplementation 515 516 //---------------------------------------------------------------------- 517 // LoopBlinnPathProcessor 518 // 519 520 LoopBlinnPathProcessor::LoopBlinnPathProcessor() 521 : m_arena(PODArena::create()) 522 #ifndef NDEBUG 523 , m_verboseLogging(false) 524 #endif 525 { 526 } 527 528 LoopBlinnPathProcessor::LoopBlinnPathProcessor(PassRefPtr<PODArena> arena) 529 : m_arena(arena) 530 #ifndef NDEBUG 531 , m_verboseLogging(false) 532 #endif 533 { 534 } 535 536 LoopBlinnPathProcessor::~LoopBlinnPathProcessor() 537 { 538 } 539 540 void LoopBlinnPathProcessor::process(const Path& path, LoopBlinnPathCache& cache) 541 { 542 buildContours(path); 543 544 // Run plane-sweep algorithm to determine overlaps of control point 545 // curves and subdivide curves appropriately. 546 subdivideCurves(); 547 548 // Determine orientations of countours. Based on orientation and the 549 // number of curve crossings at a random point on the contour, 550 // determine whether to fill the left or right side of the contour. 551 determineSidesToFill(); 552 553 // Classify curves, compute texture coordinates and subdivide as 554 // necessary to eliminate rendering artifacts. Do the final 555 // triangulation of the curve segments, determining the path along 556 // the interior of the shape. 557 for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 558 Contour* cur = *iter; 559 for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 560 if (seg->kind() == Segment::Cubic) { 561 LoopBlinnClassifier::Result classification = LoopBlinnClassifier::classify(seg->getPoint(0), 562 seg->getPoint(1), 563 seg->getPoint(2), 564 seg->getPoint(3)); 565 #ifndef NDEBUG 566 if (m_verboseLogging) 567 LOG_ERROR("Classification: %d", (int) classification.curveType); 568 #endif 569 LoopBlinnTextureCoords::Result texCoords = 570 LoopBlinnTextureCoords::compute(classification, cur->fillSide()); 571 if (texCoords.hasRenderingArtifact) { 572 // FIXME: there is a problem where the algorithm 573 // sometimes fails to converge when splitting at the 574 // subdivision parameter value. For the time being, 575 // split halfway. 576 cur->subdivide(seg); 577 // Next iteration will handle the newly subdivided curves 578 } else { 579 if (!texCoords.isLineOrPoint) { 580 seg->triangulate(LoopBlinnLocalTriangulator::ComputeInsideEdges, &texCoords); 581 for (int i = 0; i < seg->numberOfTriangles(); i++) { 582 LoopBlinnLocalTriangulator::Triangle* triangle = seg->getTriangle(i); 583 for (int j = 0; j < 3; j++) { 584 LoopBlinnLocalTriangulator::Vertex* vert = triangle->getVertex(j); 585 cache.addVertex(vert->xyCoordinates().x(), 586 vert->xyCoordinates().y(), 587 vert->klmCoordinates().x(), 588 vert->klmCoordinates().y(), 589 vert->klmCoordinates().z()); 590 } 591 } 592 #ifdef LOOP_BLINN_PATH_CACHE_DEBUG_INTERIOR_EDGES 593 // Show the end user the interior edges as well 594 for (int i = 1; i < seg->numberOfInteriorVertices(); i++) { 595 FloatPoint vert = seg->getInteriorVertex(i); 596 // Duplicate previous vertex to be able to draw GL_LINES 597 FloatPoint prev = seg->getInteriorVertex(i - 1); 598 cache.addInteriorEdgeVertex(prev.x(), prev.y()); 599 cache.addInteriorEdgeVertex(vert.x(), vert.y()); 600 } 601 #endif // LOOP_BLINN_PATH_CACHE_DEBUG_INTERIOR_EDGES 602 } 603 } 604 } 605 } 606 } 607 608 // Run the interior paths through a tessellation algorithm 609 // supporting multiple contours. 610 tessellateInterior(cache); 611 } 612 613 void LoopBlinnPathProcessor::buildContours(const Path& path) 614 { 615 // Clear out the contours 616 m_contours.clear(); 617 #if USE(SKIA) 618 SkPath::Iter iter(*path.platformPath(), false); 619 SkPoint points[4]; 620 SkPath::Verb verb; 621 Contour* contour = 0; 622 SkPoint curPoint = { 0 }; 623 SkPoint moveToPoint = { 0 }; 624 do { 625 verb = iter.next(points); 626 if (verb != SkPath::kMove_Verb) { 627 if (!contour) { 628 contour = m_arena->allocateObject<Contour>(); 629 m_contours.append(contour); 630 } 631 } 632 switch (verb) { 633 case SkPath::kMove_Verb: { 634 contour = m_arena->allocateObject<Contour>(); 635 m_contours.append(contour); 636 curPoint = points[0]; 637 moveToPoint = points[0]; 638 #ifndef NDEBUG 639 if (m_verboseLogging) 640 LOG_ERROR("MoveTo (%f, %f)", points[0].fX, points[0].fY); 641 #endif 642 break; 643 } 644 case SkPath::kLine_Verb: { 645 Segment* segment = m_arena->allocateObject<Segment>(); 646 if (iter.isCloseLine()) { 647 segment->setup(m_arena.get(), contour, curPoint, points[1]); 648 #ifndef NDEBUG 649 if (m_verboseLogging) 650 LOG_ERROR("CloseLineTo (%f, %f), (%f, %f)", curPoint.fX, curPoint.fY, points[1].fX, points[1].fY); 651 #endif 652 contour->add(segment); 653 contour = 0; 654 } else { 655 segment->setup(m_arena.get(), contour, points[0], points[1]); 656 #ifndef NDEBUG 657 if (m_verboseLogging) 658 LOG_ERROR("LineTo (%f, %f), (%f, %f)", points[0].fX, points[0].fY, points[1].fX, points[1].fY); 659 #endif 660 contour->add(segment); 661 curPoint = points[1]; 662 } 663 break; 664 } 665 case SkPath::kQuad_Verb: { 666 // Need to degree elevate the quadratic into a cubic 667 SkPoint cubic[4]; 668 SkConvertQuadToCubic(points, cubic); 669 Segment* segment = m_arena->allocateObject<Segment>(); 670 segment->setup(m_arena.get(), contour, 671 cubic[0], cubic[1], cubic[2], cubic[3]); 672 #ifndef NDEBUG 673 if (m_verboseLogging) 674 LOG_ERROR("Quad->CubicTo (%f, %f), (%f, %f), (%f, %f), (%f, %f)", cubic[0].fX, cubic[0].fY, cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY, cubic[3].fX, cubic[3].fY); 675 #endif 676 contour->add(segment); 677 curPoint = cubic[3]; 678 break; 679 } 680 case SkPath::kCubic_Verb: { 681 Segment* segment = m_arena->allocateObject<Segment>(); 682 segment->setup(m_arena.get(), contour, points[0], points[1], points[2], points[3]); 683 #ifndef NDEBUG 684 if (m_verboseLogging) 685 LOG_ERROR("CubicTo (%f, %f), (%f, %f), (%f, %f), (%f, %f)", points[0].fX, points[0].fY, points[1].fX, points[1].fY, points[2].fX, points[2].fY, points[3].fX, points[3].fY); 686 #endif 687 contour->add(segment); 688 curPoint = points[3]; 689 break; 690 } 691 case SkPath::kClose_Verb: { 692 Segment* segment = m_arena->allocateObject<Segment>(); 693 segment->setup(m_arena.get(), contour, curPoint, moveToPoint); 694 #ifndef NDEBUG 695 if (m_verboseLogging) 696 LOG_ERROR("Close (%f, %f) -> (%f, %f)", curPoint.fX, curPoint.fY, moveToPoint.fX, moveToPoint.fY); 697 #endif 698 contour->add(segment); 699 contour = 0; 700 } 701 case SkPath::kDone_Verb: 702 break; 703 } 704 } while (verb != SkPath::kDone_Verb); 705 #else // !USE(SKIA) 706 UNUSED_PARAM(path); 707 // Must port to your platform. 708 ASSERT_NOT_REACHED(); 709 #endif 710 } 711 712 #ifndef NDEBUG 713 Vector<Segment*> LoopBlinnPathProcessor::allSegmentsOverlappingY(Contour* queryContour, float x, float y) 714 { 715 Vector<Segment*> res; 716 for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 717 Contour* cur = *iter; 718 for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 719 const FloatRect& boundingBox = seg->boundingBox(); 720 if (boundingBox.y() <= y && y <= boundingBox.maxY()) 721 res.append(seg); 722 } 723 } 724 return res; 725 } 726 #endif 727 728 // Uncomment this to debug the orientation computation. 729 // #define GPU_PATH_PROCESSOR_DEBUG_ORIENTATION 730 731 void LoopBlinnPathProcessor::determineSidesToFill() 732 { 733 // Loop and Blinn's algorithm can only easily emulate the even/odd 734 // fill rule, and only for non-intersecting curves. We can determine 735 // which side of each curve segment to fill based on its 736 // clockwise/counterclockwise orientation and how many other 737 // contours surround it. 738 739 // To optimize the query of all curve segments intersecting a 740 // horizontal line going to x=+infinity, we build up an interval 741 // tree whose keys are the y extents of the segments. 742 PODIntervalTree<float, Segment*> tree(m_arena); 743 typedef PODIntervalTree<float, Segment*>::IntervalType IntervalType; 744 745 for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 746 Contour* cur = *iter; 747 determineOrientation(cur); 748 for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 749 const FloatRect& boundingBox = seg->boundingBox(); 750 tree.add(tree.createInterval(boundingBox.y(), boundingBox.maxY(), seg)); 751 } 752 } 753 754 // Now iterate through the contours and pick a random segment (in 755 // this case we use the first) and a random point on that segment. 756 // Find all segments from other contours which intersect this one 757 // and count the number of crossings a horizontal line to 758 // x=+infinity makes with those contours. This combined with the 759 // orientation of the curve tells us which side to fill -- again, 760 // assuming an even/odd fill rule, which is all we can easily 761 // handle. 762 for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 763 Contour* cur = *iter; 764 765 bool ambiguous = true; 766 int numCrossings = 0; 767 768 // For each contour, attempt to find a point on the contour which, 769 // when we cast an XRay, does not intersect the other contours at 770 // an ambiguous point (the junction between two curves or at a 771 // tangent point). Ambiguous points make the determination of 772 // whether this contour is contained within another fragile. Note 773 // that this loop is only an approximation to the selection of a 774 // good casting point. We could as well evaluate a segment to 775 // determine a point upon it. 776 for (Segment* seg = cur->begin(); 777 ambiguous && seg != cur->end(); 778 seg = seg->next()) { 779 numCrossings = 0; 780 // We use a zero-sized vertical interval for the query. 781 Vector<IntervalType> overlaps = tree.allOverlaps(tree.createInterval(seg->getPoint(0).y(), 782 seg->getPoint(0).y(), 783 0)); 784 #if defined(GPU_PATH_PROCESSOR_DEBUG_ORIENTATION) && !defined(NDEBUG) 785 Vector<Segment*> slowOverlaps = allSegmentsOverlappingY(cur, seg->getPoint(0).x(), seg->getPoint(0).y()); 786 if (overlaps.size() != slowOverlaps.size()) { 787 LOG_ERROR("For query point (%f, %f) on contour 0x%p:", seg->getPoint(0).x(), seg->getPoint(0).y(), cur); 788 LOG_ERROR(" overlaps:"); 789 for (size_t i = 0; i < overlaps.size(); i++) 790 LOG_ERROR(" %d: %s", i+1, overlaps[i].data()->toString().ascii().data()); 791 LOG_ERROR(" slowOverlaps:"); 792 for (size_t i = 0; i < slowOverlaps.size(); i++) 793 LOG_ERROR(" %d: %s", (i+1) slowOverlaps[i]->toString()); 794 LOG_ERROR("Interval tree:"); 795 tree.dump(); 796 } 797 ASSERT(overlaps.size() == slowOverlaps.size()); 798 #endif // defined(GPU_PATH_PROCESSOR_DEBUG_ORIENTATION) && !defined(NDEBUG) 799 for (Vector<IntervalType>::iterator iter = overlaps.begin(); iter != overlaps.end(); ++iter) { 800 const IntervalType& interval = *iter; 801 Segment* querySegment = interval.data(); 802 // Ignore segments coming from the same contour. 803 if (querySegment->contour() != cur) { 804 // Only perform queries that can affect the computation. 805 const FloatRect& boundingBox = querySegment->contour()->boundingBox(); 806 if (seg->getPoint(0).x() >= boundingBox.x() 807 && seg->getPoint(0).x() <= boundingBox.maxX()) { 808 numCrossings += querySegment->numCrossingsForXRay(seg->getPoint(0), 809 ambiguous); 810 if (ambiguous) { 811 #ifndef NDEBUG 812 if (m_verboseLogging) { 813 LOG_ERROR("Ambiguous intersection query at point (%f, %f)", seg->getPoint(0).x(), seg->getPoint(0).y()); 814 LOG_ERROR("Query segment: %s", querySegment->toString().ascii().data()); 815 } 816 #endif 817 break; // Abort iteration over overlaps. 818 } 819 } 820 } 821 } 822 } // for (Segment* seg = cur->begin(); ... 823 824 cur->setFillSide((cur->isOrientedCounterClockwise() ^ (numCrossings & 1)) ? LoopBlinnConstants::LeftSide : LoopBlinnConstants::RightSide); 825 } 826 } 827 828 void LoopBlinnPathProcessor::determineOrientation(Contour* contour) 829 { 830 // Determine signed area of the polygon represented by the points 831 // along the segments. Consider this an approximation to the true 832 // orientation of the polygon; it probably won't handle 833 // self-intersecting curves correctly. 834 // 835 // There is also a pretty basic assumption here that the contour is 836 // closed. 837 float signedArea = 0; 838 for (Segment* seg = contour->begin(); 839 seg != contour->end(); 840 seg = seg->next()) { 841 int limit = (seg->kind() == Segment::Cubic) ? 4 : 2; 842 for (int i = 1; i < limit; i++) { 843 const FloatPoint& prevPoint = seg->getPoint(i - 1); 844 const FloatPoint& point = seg->getPoint(i); 845 float curArea = prevPoint.x() * point.y() - prevPoint.y() * point.x(); 846 #ifndef NDEBUG 847 if (m_verboseLogging) 848 LOG_ERROR("Adding to signed area (%f, %f) -> (%f, %f) = %f", prevPoint.x(), prevPoint.y(), point.x(), point.y(), curArea); 849 #endif 850 signedArea += curArea; 851 } 852 } 853 854 if (signedArea > 0) 855 contour->setIsOrientedCounterClockwise(true); 856 else 857 contour->setIsOrientedCounterClockwise(false); 858 } 859 860 namespace { 861 862 //---------------------------------------------------------------------- 863 // Classes and typedefs needed for curve subdivision. These can't be scoped 864 // within the subdivideCurves() method itself, because templates then fail 865 // to instantiate. 866 867 // The user data which is placed in the PODIntervalTree. 868 struct SweepData { 869 SweepData() 870 : triangle(0) 871 , segment(0) 872 { 873 } 874 875 // The triangle this interval is associated with 876 LoopBlinnLocalTriangulator::Triangle* triangle; 877 // The segment the triangle is associated with 878 Segment* segment; 879 }; 880 881 typedef PODIntervalTree<float, SweepData*> SweepTree; 882 typedef SweepTree::IntervalType SweepInterval; 883 884 // The entry / exit events which occur at the minimum and maximum x 885 // coordinates of the control point triangles' bounding boxes. 886 // 887 // Note that this class requires its copy constructor and assignment 888 // operator since it needs to be stored in a Vector. 889 class SweepEvent { 890 public: 891 SweepEvent() 892 : m_x(0) 893 , m_entry(false) 894 , m_interval(0, 0, 0) 895 { 896 } 897 898 // Initializes the SweepEvent. 899 void setup(float x, bool entry, SweepInterval interval) 900 { 901 m_x = x; 902 m_entry = entry; 903 m_interval = interval; 904 } 905 906 float x() const { return m_x; } 907 bool entry() const { return m_entry; } 908 const SweepInterval& interval() const { return m_interval; } 909 910 bool operator<(const SweepEvent& other) const 911 { 912 return m_x < other.m_x; 913 } 914 915 private: 916 float m_x; 917 bool m_entry; 918 SweepInterval m_interval; 919 }; 920 921 bool trianglesOverlap(LoopBlinnLocalTriangulator::Triangle* t0, 922 LoopBlinnLocalTriangulator::Triangle* t1) 923 { 924 return trianglesOverlap(t0->getVertex(0)->xyCoordinates(), 925 t0->getVertex(1)->xyCoordinates(), 926 t0->getVertex(2)->xyCoordinates(), 927 t1->getVertex(0)->xyCoordinates(), 928 t1->getVertex(1)->xyCoordinates(), 929 t1->getVertex(2)->xyCoordinates()); 930 } 931 932 } // anonymous namespace 933 934 void LoopBlinnPathProcessor::subdivideCurves() 935 { 936 // We need to determine all overlaps of all control point triangles 937 // (from different segments, not the same segment) and, if any 938 // exist, subdivide the associated curves. 939 // 940 // The plane-sweep algorithm determines all overlaps of a set of 941 // rectangles in the 2D plane. Our problem maps very well to this 942 // algorithm and significantly reduces the complexity compared to a 943 // naive implementation. 944 // 945 // Each bounding box of a control point triangle is converted into 946 // an "entry" event at its smallest X coordinate and an "exit" event 947 // at its largest X coordinate. Each event has an associated 948 // one-dimensional interval representing the Y span of the bounding 949 // box. We sort these events by increasing X coordinate. We then 950 // iterate through them. For each entry event we add the interval to 951 // a side interval tree, and query this tree for overlapping 952 // intervals. Any overlapping interval corresponds to an overlapping 953 // bounding box. For each exit event we remove the associated 954 // interval from the interval tree. 955 956 Vector<Segment*> curSegments; 957 Vector<Segment*> nextSegments; 958 959 // Start things off by considering all of the segments 960 for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 961 Contour* cur = *iter; 962 for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 963 if (seg->kind() == Segment::Cubic) { 964 seg->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0); 965 curSegments.append(seg); 966 } 967 } 968 } 969 970 // Subdivide curves at most this many times 971 const int MaxIterations = 5; 972 Vector<SweepInterval> overlaps; 973 974 for (int currentIteration = 0; currentIteration < MaxIterations; ++currentIteration) { 975 if (!curSegments.size()) 976 // Done 977 break; 978 979 Vector<SweepEvent> events; 980 SweepTree tree(m_arena); 981 for (Vector<Segment*>::iterator iter = curSegments.begin(); iter != curSegments.end(); ++iter) { 982 Segment* seg = *iter; 983 ASSERT(seg->kind() == Segment::Cubic); 984 for (int i = 0; i < seg->numberOfTriangles(); i++) { 985 LoopBlinnLocalTriangulator::Triangle* triangle = seg->getTriangle(i); 986 FloatRect boundingBox; 987 boundingBox.fitToPoints(triangle->getVertex(0)->xyCoordinates(), 988 triangle->getVertex(1)->xyCoordinates(), 989 triangle->getVertex(2)->xyCoordinates()); 990 // Ignore zero-width triangles to avoid issues with 991 // coincident entry and exit events for the same triangle 992 if (boundingBox.maxX() > boundingBox.x()) { 993 SweepData* data = m_arena->allocateObject<SweepData>(); 994 data->triangle = triangle; 995 data->segment = seg; 996 SweepInterval interval = tree.createInterval(boundingBox.y(), boundingBox.maxY(), data); 997 // Add entry and exit events 998 SweepEvent event; 999 event.setup(boundingBox.x(), true, interval); 1000 events.append(event); 1001 event.setup(boundingBox.maxX(), false, interval); 1002 events.append(event); 1003 } 1004 } 1005 } 1006 1007 // Sort events by increasing X coordinate 1008 std::sort(events.begin(), events.end()); 1009 #ifndef NDEBUG 1010 for (size_t ii = 1; ii < events.size(); ++ii) 1011 ASSERT(events[ii - 1].x() <= events[ii].x()); 1012 #endif 1013 1014 // Now iterate through the events 1015 for (Vector<SweepEvent>::iterator iter = events.begin(); iter != events.end(); ++iter) { 1016 SweepEvent event = *iter; 1017 if (event.entry()) { 1018 // See whether the associated segment has been subdivided yet 1019 if (!event.interval().data()->segment->markedForSubdivision()) { 1020 // Query the tree 1021 overlaps.clear(); 1022 tree.allOverlaps(event.interval(), overlaps); 1023 // Now see exactly which triangles overlap this one 1024 for (Vector<SweepInterval>::iterator iter = overlaps.begin(); iter != overlaps.end(); ++iter) { 1025 SweepInterval overlap = *iter; 1026 // Only pay attention to overlaps from a different Segment 1027 if (event.interval().data()->segment != overlap.data()->segment) { 1028 // See whether the triangles actually overlap 1029 if (trianglesOverlap(event.interval().data()->triangle, 1030 overlap.data()->triangle)) { 1031 // Actually subdivide the segments. 1032 // Each one might already have been subdivided. 1033 Segment* seg = event.interval().data()->segment; 1034 conditionallySubdivide(seg, nextSegments); 1035 seg = overlap.data()->segment; 1036 conditionallySubdivide(seg, nextSegments); 1037 } 1038 } 1039 } 1040 } 1041 // Add this interval into the tree 1042 tree.add(event.interval()); 1043 } else { 1044 // Remove this interval from the tree 1045 tree.remove(event.interval()); 1046 } 1047 } 1048 1049 curSegments.swap(nextSegments); 1050 nextSegments.clear(); 1051 } 1052 } 1053 1054 void LoopBlinnPathProcessor::conditionallySubdivide(Segment* seg, Vector<Segment*>& nextSegments) 1055 { 1056 if (!seg->markedForSubdivision()) { 1057 seg->setMarkedForSubdivision(true); 1058 Segment* next = seg->contour()->subdivide(seg); 1059 // Triangulate the newly subdivided segments. 1060 next->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0); 1061 next->next()->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0); 1062 // Add them for the next iteration. 1063 nextSegments.append(next); 1064 nextSegments.append(next->next()); 1065 } 1066 } 1067 1068 #ifndef NDEBUG 1069 void LoopBlinnPathProcessor::subdivideCurvesSlow() 1070 { 1071 // Alternate, significantly slower algorithm for curve subdivision 1072 // for use in debugging. 1073 Vector<Segment*> curSegments; 1074 Vector<Segment*> nextSegments; 1075 1076 // Start things off by considering all of the segments 1077 for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 1078 Contour* cur = *iter; 1079 for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 1080 if (seg->kind() == Segment::Cubic) { 1081 seg->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0); 1082 curSegments.append(seg); 1083 } 1084 } 1085 } 1086 1087 // Subdivide curves at most this many times 1088 const int MaxIterations = 5; 1089 1090 for (int currentIteration = 0; currentIteration < MaxIterations; ++currentIteration) { 1091 if (!curSegments.size()) 1092 // Done 1093 break; 1094 1095 for (Vector<Segment*>::iterator iter = curSegments.begin(); iter != curSegments.end(); ++iter) { 1096 Segment* seg = *iter; 1097 ASSERT(seg->kind() == Segment::Cubic); 1098 for (Vector<Segment*>::iterator iter2 = curSegments.begin(); 1099 iter2 != curSegments.end(); 1100 iter2++) { 1101 Segment* seg2 = *iter2; 1102 ASSERT(seg2->kind() == Segment::Cubic); 1103 if (seg != seg2) { 1104 for (int i = 0; i < seg->numberOfTriangles(); i++) { 1105 LoopBlinnLocalTriangulator::Triangle* triangle = seg->getTriangle(i); 1106 for (int j = 0; j < seg2->numberOfTriangles(); j++) { 1107 LoopBlinnLocalTriangulator::Triangle* triangle2 = seg2->getTriangle(j); 1108 if (trianglesOverlap(triangle, triangle2)) { 1109 conditionallySubdivide(seg, nextSegments); 1110 conditionallySubdivide(seg2, nextSegments); 1111 } 1112 } 1113 } 1114 } 1115 } 1116 } 1117 1118 curSegments.swap(nextSegments); 1119 nextSegments.clear(); 1120 } 1121 } 1122 #endif 1123 1124 namespace { 1125 1126 //---------------------------------------------------------------------- 1127 // Structures and callbacks for tessellation of the interior region of 1128 // the contours. 1129 1130 // The user data for the GLU tessellator. 1131 struct TessellationState { 1132 TessellationState(LoopBlinnPathCache& inputCache) 1133 : cache(inputCache) { } 1134 1135 LoopBlinnPathCache& cache; 1136 Vector<void*> allocatedPointers; 1137 }; 1138 1139 static void vertexCallback(void* vertexData, void* data) 1140 { 1141 TessellationState* state = static_cast<TessellationState*>(data); 1142 GLdouble* location = static_cast<GLdouble*>(vertexData); 1143 state->cache.addInteriorVertex(static_cast<float>(location[0]), 1144 static_cast<float>(location[1])); 1145 } 1146 1147 static void combineCallback(GLdouble coords[3], void* vertexData[4], 1148 GLfloat weight[4], void** outData, 1149 void* polygonData) 1150 { 1151 UNUSED_PARAM(vertexData); 1152 UNUSED_PARAM(weight); 1153 TessellationState* state = static_cast<TessellationState*>(polygonData); 1154 GLdouble* outVertex = static_cast<GLdouble*>(fastMalloc(3 * sizeof(GLdouble))); 1155 state->allocatedPointers.append(outVertex); 1156 outVertex[0] = coords[0]; 1157 outVertex[1] = coords[1]; 1158 outVertex[2] = coords[2]; 1159 *outData = outVertex; 1160 } 1161 1162 static void edgeFlagCallback(GLboolean) 1163 { 1164 // No-op just to prevent triangle strips and fans from being passed to us. 1165 // See the OpenGL Programming Guide, Chapter 11, "Tessellators and Quadrics". 1166 } 1167 1168 } // anonymous namespace 1169 1170 void LoopBlinnPathProcessor::tessellateInterior(LoopBlinnPathCache& cache) 1171 { 1172 // Because the GLU tessellator requires its input in 1173 // double-precision format, we need to make a separate copy of the 1174 // data. 1175 Vector<GLdouble> vertexData; 1176 Vector<size_t> contourEndings; 1177 // For avoiding adding coincident vertices. 1178 float curX = 0, curY = 0; 1179 for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 1180 Contour* cur = *iter; 1181 bool first = true; 1182 for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 1183 int numberOfInteriorVertices = seg->numberOfInteriorVertices(); 1184 for (int i = 0; i < numberOfInteriorVertices - 1; i++) { 1185 FloatPoint point = seg->getInteriorVertex(i); 1186 if (first) { 1187 first = false; 1188 vertexData.append(point.x()); 1189 vertexData.append(point.y()); 1190 vertexData.append(0); 1191 curX = point.x(); 1192 curY = point.y(); 1193 } else if (point.x() != curX || point.y() != curY) { 1194 vertexData.append(point.x()); 1195 vertexData.append(point.y()); 1196 vertexData.append(0); 1197 curX = point.x(); 1198 curY = point.y(); 1199 } 1200 } 1201 } 1202 contourEndings.append(vertexData.size()); 1203 } 1204 // Now that we have all of the vertex data in a stable location in 1205 // memory, call the tessellator. 1206 GLUtesselator* tess = internal_gluNewTess(); 1207 TessellationState state(cache); 1208 internal_gluTessCallback(tess, GLU_TESS_VERTEX_DATA, 1209 reinterpret_cast<GLvoid (*)()>(vertexCallback)); 1210 internal_gluTessCallback(tess, GLU_TESS_COMBINE_DATA, 1211 reinterpret_cast<GLvoid (*)()>(combineCallback)); 1212 internal_gluTessCallback(tess, GLU_TESS_EDGE_FLAG, 1213 reinterpret_cast<GLvoid (*)()>(edgeFlagCallback)); 1214 internal_gluTessBeginPolygon(tess, &state); 1215 internal_gluTessBeginContour(tess); 1216 GLdouble* base = vertexData.data(); 1217 int contourIndex = 0; 1218 for (size_t i = 0; i < vertexData.size(); i += 3) { 1219 if (i == contourEndings[contourIndex]) { 1220 internal_gluTessEndContour(tess); 1221 internal_gluTessBeginContour(tess); 1222 ++contourIndex; 1223 } 1224 internal_gluTessVertex(tess, &base[i], &base[i]); 1225 } 1226 internal_gluTessEndContour(tess); 1227 internal_gluTessEndPolygon(tess); 1228 for (size_t i = 0; i < state.allocatedPointers.size(); i++) 1229 fastFree(state.allocatedPointers[i]); 1230 internal_gluDeleteTess(tess); 1231 } 1232 1233 } // namespace WebCore 1234
