code.vuplus.com Git - vuplus_webkit/blob - Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp

   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