12fc2651226baac27029e38c9d6ef883fa32084dbSteve Block/* 22fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * Copyright (C) 2011 Google Inc. All rights reserved. 32fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * 42fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * Redistribution and use in source and binary forms, with or without 52fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * modification, are permitted provided that the following conditions 62fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * are met: 72fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * 82fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * 1. Redistributions of source code must retain the above copyright 92fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * notice, this list of conditions and the following disclaimer. 102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * 2. Redistributions in binary form must reproduce the above copyright 112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * notice, this list of conditions and the following disclaimer in the 122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * documentation and/or other materials provided with the distribution. 132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * 142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block */ 252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "config.h" 272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "LoopBlinnPathProcessor.h" 292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "FloatPoint.h" 312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "FloatRect.h" 322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "LoopBlinnClassifier.h" 332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "LoopBlinnConstants.h" 342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "LoopBlinnLocalTriangulator.h" 352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "LoopBlinnMathUtils.h" 362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "LoopBlinnPathCache.h" 372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "LoopBlinnTextureCoords.h" 382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "PODArena.h" 392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "PODIntervalTree.h" 402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "Path.h" 412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "internal_glu.h" 422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <algorithm> 432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <wtf/Assertions.h> 442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include <wtf/FastMalloc.h> 452bde8e466a4451c7319e3a072d118917957d6554Steve Block#include <wtf/UnusedParam.h> 462bde8e466a4451c7319e3a072d118917957d6554Steve Block 472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4881bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#if USE(SKIA) 492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "SkGeometry.h" 502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "SkPath.h" 512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#include "SkScalar.h" 522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#else 532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Must port to your platform. 542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 562fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocknamespace WebCore { 572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 582fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockusing LoopBlinnMathUtils::XRay; 592fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockusing LoopBlinnMathUtils::chopCubicAt; 602fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockusing LoopBlinnMathUtils::numXRayCrossingsForCubic; 612fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockusing LoopBlinnMathUtils::trianglesOverlap; 622fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockusing LoopBlinnMathUtils::xRayCrossesLine; 632fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockusing LoopBlinnPathProcessorImplementation::Contour; 642fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockusing LoopBlinnPathProcessorImplementation::Segment; 652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 662fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocknamespace { 672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 692fc2651226baac27029e38c9d6ef883fa32084dbSteve BlockString valueToString(const FloatRect& arg) 702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block StringBuilder builder; 722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append("[FloatRect x="); 732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(String::number(arg.x())); 742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(" y="); 752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(String::number(arg.y())); 762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(" maxX="); 772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(String::number(arg.maxX())); 782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(" maxY="); 792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(String::number(arg.maxY())); 802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append("]"); 812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return builder.toString(); 822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 852fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockstruct SweepData; 862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} // anonymous namespace 882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 892fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocknamespace LoopBlinnPathProcessorImplementation { 902fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockclass Segment; 912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Routines needed to print the types of IntervalNodes we instantiate 952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// in this file. 962fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocktemplate <> 972fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockstruct ValueToString<float> { 982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block static String string(const float& value) 992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 1002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return String::number(value); 1012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 1022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 1032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1042fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocktemplate <> 1052fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockstruct ValueToString<SweepData*> { 1062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block static String string(SweepData* const& value) 1072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 1082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return String::format("0x%p", value); 1092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 1102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 1112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1122fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocktemplate <> 1132fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockstruct ValueToString<LoopBlinnPathProcessorImplementation::Segment*> { 1142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block static String string(LoopBlinnPathProcessorImplementation::Segment* const& value) 1152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 1162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return String::format("0x%p", value); 1172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 1182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 1192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 1202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1212fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocknamespace LoopBlinnPathProcessorImplementation { 1222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block//---------------------------------------------------------------------- 1242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Segment 1252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// 1262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Describes a segment of the path: either a cubic or a line segment. 1282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// These are stored in a doubly linked list to speed up curve 1292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// subdivision, which occurs due to either rendering artifacts in the 1302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// loop case or due to overlapping triangles. 1312fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockclass Segment { 1322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block WTF_MAKE_NONCOPYABLE(Segment); 1332fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockpublic: 1342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block enum Kind { 1352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Cubic, 1362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Line 1372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block }; 1382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // No-argument constructor allows construction by the PODArena class. 1402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment() 1412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block : m_arena(0) 1422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_kind(Cubic) 1432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_prev(0) 1442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_next(0) 1452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_contour(0) 1462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_triangulator(0) 1472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_markedForSubdivision(false) 1482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 1492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 1502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Initializer for cubic curve segments. 1522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void setup(PODArena* arena, 1532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* contour, 1542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint cp0, 1552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint cp1, 1562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint cp2, 1572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint cp3) 1582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 1592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_arena = arena; 1602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_contour = contour; 1612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_kind = Cubic; 1622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_points[0] = cp0; 1632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_points[1] = cp1; 1642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_points[2] = cp2; 1652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_points[3] = cp3; 1662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block computeBoundingBox(); 1672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 1682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Initializer for line segments. 1702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void setup(PODArena* arena, 1712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* contour, 1722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint p0, 1732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint p1) 1742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 1752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_arena = arena; 1762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_contour = contour; 1772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_kind = Line; 1782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_points[0] = p0; 1792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_points[1] = p1; 1802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block computeBoundingBox(); 1812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 1822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Kind kind() const { return m_kind; } 1842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Returns the i'th control point, 0 <= i < 4. 1862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const FloatPoint& getPoint(int i) 1872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 1882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(i >= 0 && i < 4); 1892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_points[i]; 1902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 1912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* next() const { return m_next; } 1932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* prev() const { return m_prev; } 1942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void setNext(Segment* next) { m_next = next; } 1962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void setPrev(Segment* prev) { m_prev = prev; } 1972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 1982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // The contour this segment belongs to. 1992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* contour() const { return m_contour; } 2002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Subdivides the current segment at the given parameter value (0 <= 2022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // t <= 1) and replaces it with the two newly created Segments in 2032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // the linked list, if possible. Returns a pointer to the leftmost 2042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Segment. 2052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* subdivide(float param) 2062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 2072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint dst[7]; 2082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block chopCubicAt(m_points, dst, param); 2092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* left = m_arena->allocateObject<Segment>(); 2102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* right = m_arena->allocateObject<Segment>(); 2112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block left->setup(m_arena, m_contour, dst[0], dst[1], dst[2], dst[3]); 2122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block right->setup(m_arena, m_contour, dst[3], dst[4], dst[5], dst[6]); 2132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block left->setNext(right); 2142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block right->setPrev(left); 2152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Try to set up a link between "this->prev()" and "left". 2162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (prev()) { 2172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block left->setPrev(prev()); 2182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block prev()->setNext(left); 2192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 2202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Try to set up a link between "this->next()" and "right". 2212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* n = next(); 2222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (n) { 2232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block right->setNext(n); 2242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block n->setPrev(right); 2252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 2262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Set up a link between "this" and "left"; this is only to 2272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // provide a certain amount of continuity during forward iteration. 2282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block setNext(left); 2292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return left; 2302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 2312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Subdivides the current segment at the halfway point and replaces 2332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // it with the two newly created Segments in the linked list, if 2342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // possible. Returns a pointer to the leftmost Segment. 2352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* subdivide() { return subdivide(0.5f); } 2362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const FloatRect& boundingBox() const { return m_boundingBox; } 2382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Computes the number of times a query line starting at the given 2402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // point and extending to x=+infinity crosses this segment. Outgoing 2412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // "ambiguous" argument indicates whether the query intersected an 2422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // endpoint or tangent point of the segment, indicating that another 2432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // query point is preferred. 2442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int numCrossingsForXRay(const XRay& xRay, bool& ambiguous) const 2452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 2462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_kind == Cubic) 2472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Should consider caching the monotonic cubics. 2482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return numXRayCrossingsForCubic(xRay, m_points, ambiguous); 2492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return xRayCrossesLine(xRay, m_points, ambiguous) ? 1 : 0; 2512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 2522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Performs a local triangulation of the control points in this 2542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // segment. This operation only makes sense for cubic type segments. 2552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // texCoords may be null when the klm coordinates have not been 2562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // computed yet. 2572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void triangulate(LoopBlinnLocalTriangulator::InsideEdgeComputation computeInsideEdges, 2582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const LoopBlinnTextureCoords::Result* texCoords); 2592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Returns the number of control point triangles associated with 2612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // this segment. 2622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int numberOfTriangles() const 2632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 2642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!m_triangulator) 2652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return 0; 2662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_triangulator->numberOfTriangles(); 2672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 2682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Fetches the given control point triangle for this segment. 2702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Triangle* getTriangle(int index) 2712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 2722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(m_triangulator); 2732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_triangulator->getTriangle(index); 2742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 2752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Number of vertices along the inside edge of this segment. This 2772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // can be called either for line or cubic type segments. 2782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int numberOfInteriorVertices() const 2792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 2802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_kind == Cubic) { 2812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_triangulator) 2822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_triangulator->numberOfInteriorVertices(); 2832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return 0; 2852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 2862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return 2; 2882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 2892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 2902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Returns the given interior vertex, 0 <= index < numberOfInteriorVertices(). 2912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint getInteriorVertex(int index) const 2922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 2932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(index >= 0 && index < numberOfInteriorVertices()); 2942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_kind == Cubic) { 2952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint res; 2962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_triangulator) { 2972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Vertex* vertex = m_triangulator->getInteriorVertex(index); 2982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (vertex) 2992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block res.set(vertex->xyCoordinates().x(), vertex->xyCoordinates().y()); 3002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 3012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return res; 3022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 3032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_points[index]; 3052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 3062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // State to assist with curve subdivision. 3082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool markedForSubdivision() const { return m_markedForSubdivision; } 3092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void setMarkedForSubdivision(bool markedForSubdivision) { m_markedForSubdivision = markedForSubdivision; } 3102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 3122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Suppport for printing Segments. 3132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block String toString() const 3142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 3152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block StringBuilder builder; 3162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append("[Segment kind="); 3172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(kind() == Line ? "line" : "cubic"); 3182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(" boundingBox="); 3192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(valueToString(boundingBox())); 3202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(" contour=0x"); 3212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(String::format("%p", contour())); 3222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(" markedForSubdivision="); 3232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append(markedForSubdivision() ? "true" : "false"); 3242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block builder.append("]"); 3252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return builder.toString(); 3262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 3272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 3282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block private: 3302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Computes the bounding box of this Segment. 3312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void computeBoundingBox() 3322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 3332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block switch (m_kind) { 3342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block case Cubic: 3352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_boundingBox.fitToPoints(m_points[0], m_points[1], m_points[2], m_points[3]); 3362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; 3372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block case Line: 3392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_boundingBox.fitToPoints(m_points[0], m_points[1]); 3402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; 3412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 3422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 3432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block PODArena* m_arena; 3452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Kind m_kind; 3462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint m_points[4]; 3472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* m_prev; 3482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* m_next; 3492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* m_contour; 3502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatRect m_boundingBox; 3512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator* m_triangulator; 3522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool m_markedForSubdivision; 3532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 3542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block//---------------------------------------------------------------------- 3562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Contour 3572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// 3582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Describes a closed contour of the path. 3602fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockclass Contour { 3612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block WTF_MAKE_NONCOPYABLE(Contour); 3622fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockpublic: 3632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour() 3642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 3652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_first = &m_sentinel; 3662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_first->setNext(m_first); 3672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_first->setPrev(m_first); 3682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_isOrientedCounterClockwise = true; 3692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_boundingBoxDirty = false; 3702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_fillSide = LoopBlinnConstants::RightSide; 3712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 3722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void add(Segment* segment) 3742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 3752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_first == &m_sentinel) { 3762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // First element is the sentinel. Replace it with the incoming 3772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // segment. 3782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block segment->setNext(m_first); 3792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block segment->setPrev(m_first); 3802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_first->setNext(segment); 3812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_first->setPrev(segment); 3822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_first = segment; 3832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } else { 3842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // m_first->prev() is the sentinel. 3852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(m_first->prev() == &m_sentinel); 3862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* last = m_sentinel.prev(); 3872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block last->setNext(segment); 3882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block segment->setPrev(last); 3892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block segment->setNext(&m_sentinel); 3902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_sentinel.setPrev(segment); 3912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 3922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_boundingBoxDirty = true; 3932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 3942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 3952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Subdivides the given segment at the given parametric value. 3962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Returns a pointer to the first of the two portions of the 3972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // subdivided segment. 3982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* subdivide(Segment* segment, float param) 3992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 4002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* left = segment->subdivide(param); 4012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_first == segment) 4022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_first = left; 4032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return left; 4042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 4052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Subdivides the given segment at the halfway point. Returns a 4072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // pointer to the first of the two portions of the subdivided 4082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // segment. 4092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* subdivide(Segment* segment) 4102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 4112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* left = segment->subdivide(); 4122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_first == segment) 4132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_first = left; 4142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return left; 4152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 4162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Returns the first segment in the contour for iteration. 4182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* begin() const { return m_first; } 4192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Returns the last segment in the contour for iteration. Callers 4212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // should not iterate over this segment. In other words: 4222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // for (Segment* cur = contour->begin(); 4232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // cur != contour->end(); 4242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // cur = cur->next()) { 4252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // // .. process cur ... 4262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // } 4272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* end() 4282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 4292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(m_first->prev() == &m_sentinel); 4302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return &m_sentinel; 4312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 4322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool isOrientedCounterClockwise() const { return m_isOrientedCounterClockwise; } 4342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void setIsOrientedCounterClockwise(bool isOrientedCounterClockwise) { m_isOrientedCounterClockwise = isOrientedCounterClockwise; } 4352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const FloatRect& boundingBox() 4372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 4382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_boundingBoxDirty) { 4392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool first = true; 4402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Segment* cur = begin(); cur != end(); cur = cur->next()) { 4412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (first) 4422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_boundingBox = cur->boundingBox(); 4432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block else 4442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_boundingBox.unite(cur->boundingBox()); 4452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block first = false; 4462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 4472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_boundingBoxDirty = false; 4492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 4502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_boundingBox; 4512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 4522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Returns which side of this contour is filled. 4542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnConstants::FillSide fillSide() const 4552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 4562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_fillSide; 4572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 4582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void setFillSide(LoopBlinnConstants::FillSide fillSide) 4602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 4612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_fillSide = fillSide; 4622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 4632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4642fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockprivate: 4652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // The start of the segment chain. The segments are kept in a 4662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // circular doubly linked list for rapid access to the beginning and 4672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // end. 4682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* m_first; 4692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // The sentinel element at the end of the chain, needed for 4712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // reasonable iteration semantics. 4722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment m_sentinel; 4732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool m_isOrientedCounterClockwise; 4752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatRect m_boundingBox; 4772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool m_boundingBoxDirty; 4782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Which side of this contour should be filled. 4802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnConstants::FillSide m_fillSide; 4812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 4822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block//---------------------------------------------------------------------- 4842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Segment 4852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// 4862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 4872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Definition of Segment::triangulate(), which must come after 4882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// declaration of Contour. 4892fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid Segment::triangulate(LoopBlinnLocalTriangulator::InsideEdgeComputation computeInsideEdges, 4902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const LoopBlinnTextureCoords::Result* texCoords) 4912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 4922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(m_kind == Cubic); 4932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!m_triangulator) 4942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_triangulator = m_arena->allocateObject<LoopBlinnLocalTriangulator>(); 4952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_triangulator->reset(); 4962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int i = 0; i < 4; i++) { 4972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Vertex* vertex = m_triangulator->getVertex(i); 4982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (texCoords) { 4992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vertex->set(getPoint(i).x(), 5002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block getPoint(i).y(), 5012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block texCoords->klmCoordinates[i].x(), 5022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block texCoords->klmCoordinates[i].y(), 5032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block texCoords->klmCoordinates[i].z()); 5042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } else { 5052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vertex->set(getPoint(i).x(), 5062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block getPoint(i).y(), 5072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // No texture coordinates yet 5082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 0, 0, 0); 5092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 5102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 5112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_triangulator->triangulate(computeInsideEdges, contour()->fillSide()); 5122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 5132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 5142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} // namespace LoopBlinnPathProcessorImplementation 5152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 5162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block//---------------------------------------------------------------------- 5172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// LoopBlinnPathProcessor 5182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// 5192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 5202fc2651226baac27029e38c9d6ef883fa32084dbSteve BlockLoopBlinnPathProcessor::LoopBlinnPathProcessor() 5212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block : m_arena(PODArena::create()) 5222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 5232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_verboseLogging(false) 5242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 5252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 5262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 5272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 5282fc2651226baac27029e38c9d6ef883fa32084dbSteve BlockLoopBlinnPathProcessor::LoopBlinnPathProcessor(PassRefPtr<PODArena> arena) 5292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block : m_arena(arena) 5302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 5312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_verboseLogging(false) 5322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 5332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 5342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 5352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 5362fc2651226baac27029e38c9d6ef883fa32084dbSteve BlockLoopBlinnPathProcessor::~LoopBlinnPathProcessor() 5372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 5382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 5392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 5402fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid LoopBlinnPathProcessor::process(const Path& path, LoopBlinnPathCache& cache) 5412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 5422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block buildContours(path); 5432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 5442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Run plane-sweep algorithm to determine overlaps of control point 5452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // curves and subdivide curves appropriately. 5462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block subdivideCurves(); 5472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 5482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Determine orientations of countours. Based on orientation and the 5492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // number of curve crossings at a random point on the contour, 5502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // determine whether to fill the left or right side of the contour. 5512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block determineSidesToFill(); 5522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 5532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Classify curves, compute texture coordinates and subdivide as 5542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // necessary to eliminate rendering artifacts. Do the final 5552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // triangulation of the curve segments, determining the path along 5562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // the interior of the shape. 5572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 5582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* cur = *iter; 5592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 5602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (seg->kind() == Segment::Cubic) { 5612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnClassifier::Result classification = LoopBlinnClassifier::classify(seg->getPoint(0), 5622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg->getPoint(1), 5632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg->getPoint(2), 5642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg->getPoint(3)); 5652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 5662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_verboseLogging) 5672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("Classification: %d", (int) classification.curveType); 5682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 5692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnTextureCoords::Result texCoords = 5702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnTextureCoords::compute(classification, cur->fillSide()); 5712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (texCoords.hasRenderingArtifact) { 5722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // FIXME: there is a problem where the algorithm 5732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // sometimes fails to converge when splitting at the 5742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // subdivision parameter value. For the time being, 5752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // split halfway. 5762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block cur->subdivide(seg); 5772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Next iteration will handle the newly subdivided curves 5782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } else { 5792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!texCoords.isLineOrPoint) { 5802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg->triangulate(LoopBlinnLocalTriangulator::ComputeInsideEdges, &texCoords); 5812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int i = 0; i < seg->numberOfTriangles(); i++) { 5822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Triangle* triangle = seg->getTriangle(i); 5832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int j = 0; j < 3; j++) { 5842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Vertex* vert = triangle->getVertex(j); 5852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block cache.addVertex(vert->xyCoordinates().x(), 5862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vert->xyCoordinates().y(), 5872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vert->klmCoordinates().x(), 5882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vert->klmCoordinates().y(), 5892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vert->klmCoordinates().z()); 5902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 5912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 5922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifdef LOOP_BLINN_PATH_CACHE_DEBUG_INTERIOR_EDGES 5932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Show the end user the interior edges as well 5942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int i = 1; i < seg->numberOfInteriorVertices(); i++) { 5952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint vert = seg->getInteriorVertex(i); 5962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Duplicate previous vertex to be able to draw GL_LINES 5972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint prev = seg->getInteriorVertex(i - 1); 5982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block cache.addInteriorEdgeVertex(prev.x(), prev.y()); 5992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block cache.addInteriorEdgeVertex(vert.x(), vert.y()); 6002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif // LOOP_BLINN_PATH_CACHE_DEBUG_INTERIOR_EDGES 6022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 6082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Run the interior paths through a tessellation algorithm 6092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // supporting multiple contours. 6102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block tessellateInterior(cache); 6112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 6122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 6132fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid LoopBlinnPathProcessor::buildContours(const Path& path) 6142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 6152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Clear out the contours 6162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_contours.clear(); 61781bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#if USE(SKIA) 6182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SkPath::Iter iter(*path.platformPath(), false); 6192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SkPoint points[4]; 6202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SkPath::Verb verb; 6212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* contour = 0; 6222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SkPoint curPoint = { 0 }; 6232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SkPoint moveToPoint = { 0 }; 6242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block do { 6252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block verb = iter.next(points); 6262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (verb != SkPath::kMove_Verb) { 6272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!contour) { 6282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour = m_arena->allocateObject<Contour>(); 6292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_contours.append(contour); 6302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block switch (verb) { 6332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block case SkPath::kMove_Verb: { 6342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour = m_arena->allocateObject<Contour>(); 6352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_contours.append(contour); 6362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curPoint = points[0]; 6372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block moveToPoint = points[0]; 6382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 6392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_verboseLogging) 6402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("MoveTo (%f, %f)", points[0].fX, points[0].fY); 6412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 6422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; 6432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block case SkPath::kLine_Verb: { 6452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* segment = m_arena->allocateObject<Segment>(); 6462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (iter.isCloseLine()) { 6472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block segment->setup(m_arena.get(), contour, curPoint, points[1]); 6482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 6492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_verboseLogging) 6502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("CloseLineTo (%f, %f), (%f, %f)", curPoint.fX, curPoint.fY, points[1].fX, points[1].fY); 6512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 6522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour->add(segment); 6532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour = 0; 6542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } else { 6552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block segment->setup(m_arena.get(), contour, points[0], points[1]); 6562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 6572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_verboseLogging) 6582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("LineTo (%f, %f), (%f, %f)", points[0].fX, points[0].fY, points[1].fX, points[1].fY); 6592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 6602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour->add(segment); 6612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curPoint = points[1]; 6622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; 6642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block case SkPath::kQuad_Verb: { 6662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Need to degree elevate the quadratic into a cubic 6672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SkPoint cubic[4]; 6682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SkConvertQuadToCubic(points, cubic); 6692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* segment = m_arena->allocateObject<Segment>(); 6702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block segment->setup(m_arena.get(), contour, 6712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block cubic[0], cubic[1], cubic[2], cubic[3]); 6722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 6732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_verboseLogging) 6742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 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); 6752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 6762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour->add(segment); 6772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curPoint = cubic[3]; 6782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; 6792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block case SkPath::kCubic_Verb: { 6812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* segment = m_arena->allocateObject<Segment>(); 6822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block segment->setup(m_arena.get(), contour, points[0], points[1], points[2], points[3]); 6832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 6842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_verboseLogging) 6852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 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); 6862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 6872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour->add(segment); 6882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curPoint = points[3]; 6892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; 6902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 6912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block case SkPath::kClose_Verb: { 6922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* segment = m_arena->allocateObject<Segment>(); 6932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block segment->setup(m_arena.get(), contour, curPoint, moveToPoint); 6942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 6952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_verboseLogging) 6962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("Close (%f, %f) -> (%f, %f)", curPoint.fX, curPoint.fY, moveToPoint.fX, moveToPoint.fY); 6972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 6982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour->add(segment); 6992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour = 0; 7002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 7012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block case SkPath::kDone_Verb: 7022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; 7032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 7042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } while (verb != SkPath::kDone_Verb); 70581bc750723a18f21cd17d1b173cd2a4dda9cea6eBen Murdoch#else // !USE(SKIA) 7062bde8e466a4451c7319e3a072d118917957d6554Steve Block UNUSED_PARAM(path); 7072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Must port to your platform. 7082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT_NOT_REACHED(); 7092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 7102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 7112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 7122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 7132fc2651226baac27029e38c9d6ef883fa32084dbSteve BlockVector<Segment*> LoopBlinnPathProcessor::allSegmentsOverlappingY(Contour* queryContour, float x, float y) 7142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 7152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<Segment*> res; 7162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 7172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* cur = *iter; 7182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 7192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const FloatRect& boundingBox = seg->boundingBox(); 7202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (boundingBox.y() <= y && y <= boundingBox.maxY()) 7212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block res.append(seg); 7222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 7232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 7242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return res; 7252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 7262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 7272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 7282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Uncomment this to debug the orientation computation. 7292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// #define GPU_PATH_PROCESSOR_DEBUG_ORIENTATION 7302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 7312fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid LoopBlinnPathProcessor::determineSidesToFill() 7322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 7332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Loop and Blinn's algorithm can only easily emulate the even/odd 7342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // fill rule, and only for non-intersecting curves. We can determine 7352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // which side of each curve segment to fill based on its 7362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // clockwise/counterclockwise orientation and how many other 7372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // contours surround it. 7382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 7392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // To optimize the query of all curve segments intersecting a 7402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // horizontal line going to x=+infinity, we build up an interval 7412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // tree whose keys are the y extents of the segments. 7422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block PODIntervalTree<float, Segment*> tree(m_arena); 7432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block typedef PODIntervalTree<float, Segment*>::IntervalType IntervalType; 7442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 7452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 7462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* cur = *iter; 7472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block determineOrientation(cur); 7482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 7492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const FloatRect& boundingBox = seg->boundingBox(); 7502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block tree.add(tree.createInterval(boundingBox.y(), boundingBox.maxY(), seg)); 7512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 7522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 7532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 7542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Now iterate through the contours and pick a random segment (in 7552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // this case we use the first) and a random point on that segment. 7562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Find all segments from other contours which intersect this one 7572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // and count the number of crossings a horizontal line to 7582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // x=+infinity makes with those contours. This combined with the 7592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // orientation of the curve tells us which side to fill -- again, 7602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // assuming an even/odd fill rule, which is all we can easily 7612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // handle. 7622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 7632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* cur = *iter; 7642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 7652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool ambiguous = true; 7662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int numCrossings = 0; 7672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 7682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // For each contour, attempt to find a point on the contour which, 7692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // when we cast an XRay, does not intersect the other contours at 7702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // an ambiguous point (the junction between two curves or at a 7712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // tangent point). Ambiguous points make the determination of 7722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // whether this contour is contained within another fragile. Note 7732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // that this loop is only an approximation to the selection of a 7742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // good casting point. We could as well evaluate a segment to 7752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // determine a point upon it. 7762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Segment* seg = cur->begin(); 7772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ambiguous && seg != cur->end(); 7782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg = seg->next()) { 7792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block numCrossings = 0; 7802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // We use a zero-sized vertical interval for the query. 7812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<IntervalType> overlaps = tree.allOverlaps(tree.createInterval(seg->getPoint(0).y(), 7822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg->getPoint(0).y(), 7832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 0)); 7842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#if defined(GPU_PATH_PROCESSOR_DEBUG_ORIENTATION) && !defined(NDEBUG) 7852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<Segment*> slowOverlaps = allSegmentsOverlappingY(cur, seg->getPoint(0).x(), seg->getPoint(0).y()); 7862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (overlaps.size() != slowOverlaps.size()) { 7872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("For query point (%f, %f) on contour 0x%p:", seg->getPoint(0).x(), seg->getPoint(0).y(), cur); 7882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR(" overlaps:"); 7892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (size_t i = 0; i < overlaps.size(); i++) 7902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR(" %d: %s", i+1, overlaps[i].data()->toString().ascii().data()); 7912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR(" slowOverlaps:"); 7922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (size_t i = 0; i < slowOverlaps.size(); i++) 7932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR(" %d: %s", (i+1) slowOverlaps[i]->toString()); 7942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("Interval tree:"); 7952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block tree.dump(); 7962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 7972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(overlaps.size() == slowOverlaps.size()); 7982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif // defined(GPU_PATH_PROCESSOR_DEBUG_ORIENTATION) && !defined(NDEBUG) 7992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<IntervalType>::iterator iter = overlaps.begin(); iter != overlaps.end(); ++iter) { 8002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const IntervalType& interval = *iter; 8012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* querySegment = interval.data(); 8022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Ignore segments coming from the same contour. 8032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (querySegment->contour() != cur) { 8042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Only perform queries that can affect the computation. 8052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const FloatRect& boundingBox = querySegment->contour()->boundingBox(); 8062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (seg->getPoint(0).x() >= boundingBox.x() 8072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block && seg->getPoint(0).x() <= boundingBox.maxX()) { 8082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block numCrossings += querySegment->numCrossingsForXRay(seg->getPoint(0), 8092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ambiguous); 8102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (ambiguous) { 8112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 8122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_verboseLogging) { 8132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("Ambiguous intersection query at point (%f, %f)", seg->getPoint(0).x(), seg->getPoint(0).y()); 8142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("Query segment: %s", querySegment->toString().ascii().data()); 8152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 8172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; // Abort iteration over overlaps. 8182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } // for (Segment* seg = cur->begin(); ... 8232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block cur->setFillSide((cur->isOrientedCounterClockwise() ^ (numCrossings & 1)) ? LoopBlinnConstants::LeftSide : LoopBlinnConstants::RightSide); 8252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 8272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8282fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid LoopBlinnPathProcessor::determineOrientation(Contour* contour) 8292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 8302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Determine signed area of the polygon represented by the points 8312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // along the segments. Consider this an approximation to the true 8322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // orientation of the polygon; it probably won't handle 8332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // self-intersecting curves correctly. 8342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // 8352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // There is also a pretty basic assumption here that the contour is 8362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // closed. 8372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block float signedArea = 0; 8382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Segment* seg = contour->begin(); 8392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg != contour->end(); 8402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg = seg->next()) { 8412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int limit = (seg->kind() == Segment::Cubic) ? 4 : 2; 8422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int i = 1; i < limit; i++) { 8432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const FloatPoint& prevPoint = seg->getPoint(i - 1); 8442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const FloatPoint& point = seg->getPoint(i); 8452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block float curArea = prevPoint.x() * point.y() - prevPoint.y() * point.x(); 8462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 8472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (m_verboseLogging) 8482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LOG_ERROR("Adding to signed area (%f, %f) -> (%f, %f) = %f", prevPoint.x(), prevPoint.y(), point.x(), point.y(), curArea); 8492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 8502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block signedArea += curArea; 8512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (signedArea > 0) 8552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour->setIsOrientedCounterClockwise(true); 8562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block else 8572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contour->setIsOrientedCounterClockwise(false); 8582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 8592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8602fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocknamespace { 8612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block//---------------------------------------------------------------------- 8632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Classes and typedefs needed for curve subdivision. These can't be scoped 8642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// within the subdivideCurves() method itself, because templates then fail 8652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// to instantiate. 8662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// The user data which is placed in the PODIntervalTree. 8682fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockstruct SweepData { 8692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SweepData() 8702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block : triangle(0) 8712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , segment(0) 8722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 8732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // The triangle this interval is associated with 8762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Triangle* triangle; 8772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // The segment the triangle is associated with 8782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* segment; 8792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 8802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8812fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocktypedef PODIntervalTree<float, SweepData*> SweepTree; 8822fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocktypedef SweepTree::IntervalType SweepInterval; 8832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// The entry / exit events which occur at the minimum and maximum x 8852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// coordinates of the control point triangles' bounding boxes. 8862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// 8872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Note that this class requires its copy constructor and assignment 8882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// operator since it needs to be stored in a Vector. 8892fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockclass SweepEvent { 8902fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockpublic: 8912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SweepEvent() 8922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block : m_x(0) 8932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_entry(false) 8942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block , m_interval(0, 0, 0) 8952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 8962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 8972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 8982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Initializes the SweepEvent. 8992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void setup(float x, bool entry, SweepInterval interval) 9002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 9012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_x = x; 9022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_entry = entry; 9032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block m_interval = interval; 9042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 9052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block float x() const { return m_x; } 9072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool entry() const { return m_entry; } 9082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const SweepInterval& interval() const { return m_interval; } 9092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool operator<(const SweepEvent& other) const 9112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block { 9122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return m_x < other.m_x; 9132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 9142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9152fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockprivate: 9162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block float m_x; 9172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool m_entry; 9182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SweepInterval m_interval; 9192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 9202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9212fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockbool trianglesOverlap(LoopBlinnLocalTriangulator::Triangle* t0, 9222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Triangle* t1) 9232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 9242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block return trianglesOverlap(t0->getVertex(0)->xyCoordinates(), 9252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block t0->getVertex(1)->xyCoordinates(), 9262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block t0->getVertex(2)->xyCoordinates(), 9272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block t1->getVertex(0)->xyCoordinates(), 9282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block t1->getVertex(1)->xyCoordinates(), 9292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block t1->getVertex(2)->xyCoordinates()); 9302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 9312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} // anonymous namespace 9332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9342fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid LoopBlinnPathProcessor::subdivideCurves() 9352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 9362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // We need to determine all overlaps of all control point triangles 9372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // (from different segments, not the same segment) and, if any 9382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // exist, subdivide the associated curves. 9392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // 9402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // The plane-sweep algorithm determines all overlaps of a set of 9412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // rectangles in the 2D plane. Our problem maps very well to this 9422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // algorithm and significantly reduces the complexity compared to a 9432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // naive implementation. 9442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // 9452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Each bounding box of a control point triangle is converted into 9462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // an "entry" event at its smallest X coordinate and an "exit" event 9472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // at its largest X coordinate. Each event has an associated 9482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // one-dimensional interval representing the Y span of the bounding 9492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // box. We sort these events by increasing X coordinate. We then 9502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // iterate through them. For each entry event we add the interval to 9512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // a side interval tree, and query this tree for overlapping 9522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // intervals. Any overlapping interval corresponds to an overlapping 9532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // bounding box. For each exit event we remove the associated 9542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // interval from the interval tree. 9552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<Segment*> curSegments; 9572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<Segment*> nextSegments; 9582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Start things off by considering all of the segments 9602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 9612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* cur = *iter; 9622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 9632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (seg->kind() == Segment::Cubic) { 9642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0); 9652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curSegments.append(seg); 9662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 9672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 9682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 9692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Subdivide curves at most this many times 9712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const int MaxIterations = 5; 9722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<SweepInterval> overlaps; 9732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int currentIteration = 0; currentIteration < MaxIterations; ++currentIteration) { 9752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!curSegments.size()) 9762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Done 9772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; 9782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 9792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<SweepEvent> events; 9802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SweepTree tree(m_arena); 9812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Segment*>::iterator iter = curSegments.begin(); iter != curSegments.end(); ++iter) { 9822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* seg = *iter; 9832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(seg->kind() == Segment::Cubic); 9842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int i = 0; i < seg->numberOfTriangles(); i++) { 9852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Triangle* triangle = seg->getTriangle(i); 9862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatRect boundingBox; 9872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block boundingBox.fitToPoints(triangle->getVertex(0)->xyCoordinates(), 9882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block triangle->getVertex(1)->xyCoordinates(), 9892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block triangle->getVertex(2)->xyCoordinates()); 9902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Ignore zero-width triangles to avoid issues with 9912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // coincident entry and exit events for the same triangle 9922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (boundingBox.maxX() > boundingBox.x()) { 9932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SweepData* data = m_arena->allocateObject<SweepData>(); 9942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block data->triangle = triangle; 9952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block data->segment = seg; 9962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SweepInterval interval = tree.createInterval(boundingBox.y(), boundingBox.maxY(), data); 9972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Add entry and exit events 9982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SweepEvent event; 9992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block event.setup(boundingBox.x(), true, interval); 10002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block events.append(event); 10012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block event.setup(boundingBox.maxX(), false, interval); 10022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block events.append(event); 10032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 10072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Sort events by increasing X coordinate 10082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block std::sort(events.begin(), events.end()); 10092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 10102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (size_t ii = 1; ii < events.size(); ++ii) 10112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(events[ii - 1].x() <= events[ii].x()); 10122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 10132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 10142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Now iterate through the events 10152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<SweepEvent>::iterator iter = events.begin(); iter != events.end(); ++iter) { 10162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SweepEvent event = *iter; 10172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (event.entry()) { 10182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // See whether the associated segment has been subdivided yet 10192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!event.interval().data()->segment->markedForSubdivision()) { 10202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Query the tree 10212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block overlaps.clear(); 10222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block tree.allOverlaps(event.interval(), overlaps); 10232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Now see exactly which triangles overlap this one 10242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<SweepInterval>::iterator iter = overlaps.begin(); iter != overlaps.end(); ++iter) { 10252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block SweepInterval overlap = *iter; 10262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Only pay attention to overlaps from a different Segment 10272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (event.interval().data()->segment != overlap.data()->segment) { 10282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // See whether the triangles actually overlap 10292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (trianglesOverlap(event.interval().data()->triangle, 10302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block overlap.data()->triangle)) { 10312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Actually subdivide the segments. 10322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Each one might already have been subdivided. 10332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* seg = event.interval().data()->segment; 10342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block conditionallySubdivide(seg, nextSegments); 10352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg = overlap.data()->segment; 10362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block conditionallySubdivide(seg, nextSegments); 10372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10392fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Add this interval into the tree 10422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block tree.add(event.interval()); 10432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } else { 10442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Remove this interval from the tree 10452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block tree.remove(event.interval()); 10462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10472fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 10492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curSegments.swap(nextSegments); 10502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block nextSegments.clear(); 10512fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10522fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 10532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 10542fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid LoopBlinnPathProcessor::conditionallySubdivide(Segment* seg, Vector<Segment*>& nextSegments) 10552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 10562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!seg->markedForSubdivision()) { 10572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg->setMarkedForSubdivision(true); 10582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* next = seg->contour()->subdivide(seg); 10592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Triangulate the newly subdivided segments. 10602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block next->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0); 10612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block next->next()->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0); 10622fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Add them for the next iteration. 10632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block nextSegments.append(next); 10642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block nextSegments.append(next->next()); 10652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 10672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 10682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#ifndef NDEBUG 10692fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid LoopBlinnPathProcessor::subdivideCurvesSlow() 10702fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 10712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Alternate, significantly slower algorithm for curve subdivision 10722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // for use in debugging. 10732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<Segment*> curSegments; 10742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<Segment*> nextSegments; 10752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 10762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Start things off by considering all of the segments 10772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 10782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* cur = *iter; 10792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 10802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (seg->kind() == Segment::Cubic) { 10812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block seg->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0); 10822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curSegments.append(seg); 10832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 10862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 10872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Subdivide curves at most this many times 10882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block const int MaxIterations = 5; 10892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 10902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int currentIteration = 0; currentIteration < MaxIterations; ++currentIteration) { 10912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (!curSegments.size()) 10922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Done 10932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block break; 10942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 10952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Segment*>::iterator iter = curSegments.begin(); iter != curSegments.end(); ++iter) { 10962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* seg = *iter; 10972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(seg->kind() == Segment::Cubic); 10982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Segment*>::iterator iter2 = curSegments.begin(); 10992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block iter2 != curSegments.end(); 11002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block iter2++) { 11012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Segment* seg2 = *iter2; 11022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ASSERT(seg2->kind() == Segment::Cubic); 11032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (seg != seg2) { 11042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int i = 0; i < seg->numberOfTriangles(); i++) { 11052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Triangle* triangle = seg->getTriangle(i); 11062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int j = 0; j < seg2->numberOfTriangles(); j++) { 11072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnLocalTriangulator::Triangle* triangle2 = seg2->getTriangle(j); 11082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (trianglesOverlap(triangle, triangle2)) { 11092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block conditionallySubdivide(seg, nextSegments); 11102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block conditionallySubdivide(seg2, nextSegments); 11112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 11122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 11132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 11142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 11152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 11162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 11172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curSegments.swap(nextSegments); 11192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block nextSegments.clear(); 11202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 11212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 11222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block#endif 11232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11242fc2651226baac27029e38c9d6ef883fa32084dbSteve Blocknamespace { 11252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block//---------------------------------------------------------------------- 11272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// Structures and callbacks for tessellation of the interior region of 11282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// the contours. 11292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block// The user data for the GLU tessellator. 11312fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockstruct TessellationState { 11322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block TessellationState(LoopBlinnPathCache& inputCache) 11332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block : cache(inputCache) { } 11342fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11352fc2651226baac27029e38c9d6ef883fa32084dbSteve Block LoopBlinnPathCache& cache; 11362fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<void*> allocatedPointers; 11372fc2651226baac27029e38c9d6ef883fa32084dbSteve Block}; 11382fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11392fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockstatic void vertexCallback(void* vertexData, void* data) 11402fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 11412fc2651226baac27029e38c9d6ef883fa32084dbSteve Block TessellationState* state = static_cast<TessellationState*>(data); 11422fc2651226baac27029e38c9d6ef883fa32084dbSteve Block GLdouble* location = static_cast<GLdouble*>(vertexData); 11432fc2651226baac27029e38c9d6ef883fa32084dbSteve Block state->cache.addInteriorVertex(static_cast<float>(location[0]), 11442fc2651226baac27029e38c9d6ef883fa32084dbSteve Block static_cast<float>(location[1])); 11452fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 11462fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11472fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockstatic void combineCallback(GLdouble coords[3], void* vertexData[4], 11482fc2651226baac27029e38c9d6ef883fa32084dbSteve Block GLfloat weight[4], void** outData, 11492fc2651226baac27029e38c9d6ef883fa32084dbSteve Block void* polygonData) 11502fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 11512bde8e466a4451c7319e3a072d118917957d6554Steve Block UNUSED_PARAM(vertexData); 11522bde8e466a4451c7319e3a072d118917957d6554Steve Block UNUSED_PARAM(weight); 11532fc2651226baac27029e38c9d6ef883fa32084dbSteve Block TessellationState* state = static_cast<TessellationState*>(polygonData); 11542fc2651226baac27029e38c9d6ef883fa32084dbSteve Block GLdouble* outVertex = static_cast<GLdouble*>(fastMalloc(3 * sizeof(GLdouble))); 11552fc2651226baac27029e38c9d6ef883fa32084dbSteve Block state->allocatedPointers.append(outVertex); 11562fc2651226baac27029e38c9d6ef883fa32084dbSteve Block outVertex[0] = coords[0]; 11572fc2651226baac27029e38c9d6ef883fa32084dbSteve Block outVertex[1] = coords[1]; 11582fc2651226baac27029e38c9d6ef883fa32084dbSteve Block outVertex[2] = coords[2]; 11592fc2651226baac27029e38c9d6ef883fa32084dbSteve Block *outData = outVertex; 11602fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 11612fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11622fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockstatic void edgeFlagCallback(GLboolean) 11632fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 11642fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // No-op just to prevent triangle strips and fans from being passed to us. 11652fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // See the OpenGL Programming Guide, Chapter 11, "Tessellators and Quadrics". 11662fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 11672fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11682fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} // anonymous namespace 11692fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 11702fc2651226baac27029e38c9d6ef883fa32084dbSteve Blockvoid LoopBlinnPathProcessor::tessellateInterior(LoopBlinnPathCache& cache) 11712fc2651226baac27029e38c9d6ef883fa32084dbSteve Block{ 11722fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Because the GLU tessellator requires its input in 11732fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // double-precision format, we need to make a separate copy of the 11742fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // data. 11752fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<GLdouble> vertexData; 11762fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Vector<size_t> contourEndings; 11772fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // For avoiding adding coincident vertices. 11782fc2651226baac27029e38c9d6ef883fa32084dbSteve Block float curX = 0, curY = 0; 11792fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) { 11802fc2651226baac27029e38c9d6ef883fa32084dbSteve Block Contour* cur = *iter; 11812fc2651226baac27029e38c9d6ef883fa32084dbSteve Block bool first = true; 11822fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { 11832fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int numberOfInteriorVertices = seg->numberOfInteriorVertices(); 11842fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (int i = 0; i < numberOfInteriorVertices - 1; i++) { 11852fc2651226baac27029e38c9d6ef883fa32084dbSteve Block FloatPoint point = seg->getInteriorVertex(i); 11862fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (first) { 11872fc2651226baac27029e38c9d6ef883fa32084dbSteve Block first = false; 11882fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vertexData.append(point.x()); 11892fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vertexData.append(point.y()); 11902fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vertexData.append(0); 11912fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curX = point.x(); 11922fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curY = point.y(); 11932fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } else if (point.x() != curX || point.y() != curY) { 11942fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vertexData.append(point.x()); 11952fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vertexData.append(point.y()); 11962fc2651226baac27029e38c9d6ef883fa32084dbSteve Block vertexData.append(0); 11972fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curX = point.x(); 11982fc2651226baac27029e38c9d6ef883fa32084dbSteve Block curY = point.y(); 11992fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 12002fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 12012fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 12022fc2651226baac27029e38c9d6ef883fa32084dbSteve Block contourEndings.append(vertexData.size()); 12032fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 12042fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // Now that we have all of the vertex data in a stable location in 12052fc2651226baac27029e38c9d6ef883fa32084dbSteve Block // memory, call the tessellator. 12062fc2651226baac27029e38c9d6ef883fa32084dbSteve Block GLUtesselator* tess = internal_gluNewTess(); 12072fc2651226baac27029e38c9d6ef883fa32084dbSteve Block TessellationState state(cache); 12082fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessCallback(tess, GLU_TESS_VERTEX_DATA, 12092fc2651226baac27029e38c9d6ef883fa32084dbSteve Block reinterpret_cast<GLvoid (*)()>(vertexCallback)); 12102fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessCallback(tess, GLU_TESS_COMBINE_DATA, 12112fc2651226baac27029e38c9d6ef883fa32084dbSteve Block reinterpret_cast<GLvoid (*)()>(combineCallback)); 12122fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessCallback(tess, GLU_TESS_EDGE_FLAG, 12132fc2651226baac27029e38c9d6ef883fa32084dbSteve Block reinterpret_cast<GLvoid (*)()>(edgeFlagCallback)); 12142fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessBeginPolygon(tess, &state); 12152fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessBeginContour(tess); 12162fc2651226baac27029e38c9d6ef883fa32084dbSteve Block GLdouble* base = vertexData.data(); 12172fc2651226baac27029e38c9d6ef883fa32084dbSteve Block int contourIndex = 0; 12182fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (size_t i = 0; i < vertexData.size(); i += 3) { 12192fc2651226baac27029e38c9d6ef883fa32084dbSteve Block if (i == contourEndings[contourIndex]) { 12202fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessEndContour(tess); 12212fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessBeginContour(tess); 12222fc2651226baac27029e38c9d6ef883fa32084dbSteve Block ++contourIndex; 12232fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 12242fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessVertex(tess, &base[i], &base[i]); 12252fc2651226baac27029e38c9d6ef883fa32084dbSteve Block } 12262fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessEndContour(tess); 12272fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluTessEndPolygon(tess); 12282fc2651226baac27029e38c9d6ef883fa32084dbSteve Block for (size_t i = 0; i < state.allocatedPointers.size(); i++) 12292fc2651226baac27029e38c9d6ef883fa32084dbSteve Block fastFree(state.allocatedPointers[i]); 12302fc2651226baac27029e38c9d6ef883fa32084dbSteve Block internal_gluDeleteTess(tess); 12312fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} 12322fc2651226baac27029e38c9d6ef883fa32084dbSteve Block 12332fc2651226baac27029e38c9d6ef883fa32084dbSteve Block} // namespace WebCore 1234