1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 7909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkEdgeBuilder.h" 8909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkPath.h" 9909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkEdge.h" 1038911a7cb53474575e1cd1cb545902b50ee00889liyuqian#include "SkAnalyticEdge.h" 11909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkEdgeClipper.h" 12909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkLineClipper.h" 13909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkGeometry.h" 14909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 15909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 16909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 172b46f3eff9cebe900080a1c56d2d542df7377a27Mike KleinSkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) { 182b46f3eff9cebe900080a1c56d2d542df7377a27Mike Klein fEdgeList = nullptr; 192b46f3eff9cebe900080a1c56d2d542df7377a27Mike Klein} 20c8d640b1788822a8697816b645c327383a1d1f20reed@google.com 21afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclarkSkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical(const SkEdge* edge, SkEdge* last) { 22afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (last->fCurveCount || last->fDX || edge->fX != last->fX) { 23afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kNo_Combine; 24afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 25afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (edge->fWinding == last->fWinding) { 26afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (edge->fLastY + 1 == last->fFirstY) { 27afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fFirstY = edge->fFirstY; 28afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kPartial_Combine; 29afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 30afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (edge->fFirstY == last->fLastY + 1) { 31afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fLastY = edge->fLastY; 32afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kPartial_Combine; 33afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 34afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kNo_Combine; 35afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 36afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (edge->fFirstY == last->fFirstY) { 37afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (edge->fLastY == last->fLastY) { 38afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kTotal_Combine; 39afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 40afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (edge->fLastY < last->fLastY) { 41afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fFirstY = edge->fLastY + 1; 42afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kPartial_Combine; 43afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 44afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fFirstY = last->fLastY + 1; 45afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fLastY = edge->fLastY; 46afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fWinding = edge->fWinding; 47afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kPartial_Combine; 48afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 49afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (edge->fLastY == last->fLastY) { 50afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (edge->fFirstY > last->fFirstY) { 51afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fLastY = edge->fFirstY - 1; 52afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kPartial_Combine; 53afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 54afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fLastY = last->fFirstY - 1; 55afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fFirstY = edge->fFirstY; 56afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark last->fWinding = edge->fWinding; 57afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kPartial_Combine; 58afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 59afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return kNo_Combine; 60afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark} 61afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark 62451ceba3544fa1ff810378f1e9a47c7d20f48a9fliyuqianstatic inline bool approximatelyEqual(SkFixed a, SkFixed b) { 63451ceba3544fa1ff810378f1e9a47c7d20f48a9fliyuqian return SkAbs32(a - b) < 0x100; 64451ceba3544fa1ff810378f1e9a47c7d20f48a9fliyuqian} 65451ceba3544fa1ff810378f1e9a47c7d20f48a9fliyuqian 6638911a7cb53474575e1cd1cb545902b50ee00889liyuqianSkEdgeBuilder::Combine SkEdgeBuilder::CombineVertical( 6738911a7cb53474575e1cd1cb545902b50ee00889liyuqian const SkAnalyticEdge* edge, SkAnalyticEdge* last) { 6838911a7cb53474575e1cd1cb545902b50ee00889liyuqian SkASSERT(fAnalyticAA); 6938911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (last->fCurveCount || last->fDX || edge->fX != last->fX) { 7038911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kNo_Combine; 7138911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 7238911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->fWinding == last->fWinding) { 7338911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->fLowerY == last->fUpperY) { 7438911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fUpperY = edge->fUpperY; 7538911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fY = last->fUpperY; 7638911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kPartial_Combine; 7738911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 78451ceba3544fa1ff810378f1e9a47c7d20f48a9fliyuqian if (approximatelyEqual(edge->fUpperY, last->fLowerY)) { 7938911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fLowerY = edge->fLowerY; 8038911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kPartial_Combine; 8138911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 8238911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kNo_Combine; 8338911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 84451ceba3544fa1ff810378f1e9a47c7d20f48a9fliyuqian if (approximatelyEqual(edge->fUpperY, last->fUpperY)) { 85451ceba3544fa1ff810378f1e9a47c7d20f48a9fliyuqian if (approximatelyEqual(edge->fLowerY, last->fLowerY)) { 8638911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kTotal_Combine; 8738911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 8838911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->fLowerY < last->fLowerY) { 8938911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fUpperY = edge->fLowerY; 9038911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fY = last->fUpperY; 9138911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kPartial_Combine; 9238911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 9338911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fUpperY = last->fLowerY; 9438911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fY = last->fUpperY; 9538911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fLowerY = edge->fLowerY; 9638911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fWinding = edge->fWinding; 9738911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kPartial_Combine; 9838911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 99451ceba3544fa1ff810378f1e9a47c7d20f48a9fliyuqian if (approximatelyEqual(edge->fLowerY, last->fLowerY)) { 10038911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->fUpperY > last->fUpperY) { 10138911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fLowerY = edge->fUpperY; 10238911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kPartial_Combine; 10338911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 10438911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fLowerY = last->fUpperY; 10538911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fUpperY = edge->fUpperY; 10638911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fY = last->fUpperY; 10738911a7cb53474575e1cd1cb545902b50ee00889liyuqian last->fWinding = edge->fWinding; 10838911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kPartial_Combine; 10938911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 11038911a7cb53474575e1cd1cb545902b50ee00889liyuqian return kNo_Combine; 11138911a7cb53474575e1cd1cb545902b50ee00889liyuqian} 11238911a7cb53474575e1cd1cb545902b50ee00889liyuqian 11338911a7cb53474575e1cd1cb545902b50ee00889liyuqianbool SkEdgeBuilder::vertical_line(const SkEdge* edge) { 11438911a7cb53474575e1cd1cb545902b50ee00889liyuqian return !edge->fDX && !edge->fCurveCount; 11538911a7cb53474575e1cd1cb545902b50ee00889liyuqian} 11638911a7cb53474575e1cd1cb545902b50ee00889liyuqian 11738911a7cb53474575e1cd1cb545902b50ee00889liyuqianbool SkEdgeBuilder::vertical_line(const SkAnalyticEdge* edge) { 11838911a7cb53474575e1cd1cb545902b50ee00889liyuqian SkASSERT(fAnalyticAA); 119afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark return !edge->fDX && !edge->fCurveCount; 120afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark} 121afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark 122909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeBuilder::addLine(const SkPoint pts[]) { 12338911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (fAnalyticAA) { 1244b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby SkAnalyticEdge* edge = fAlloc.make<SkAnalyticEdge>(); 12538911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->setLine(pts[0], pts[1])) { 12638911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (vertical_line(edge) && fList.count()) { 12738911a7cb53474575e1cd1cb545902b50ee00889liyuqian Combine combine = CombineVertical(edge, (SkAnalyticEdge*)*(fList.end() - 1)); 12838911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (kNo_Combine != combine) { 12938911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (kTotal_Combine == combine) { 13038911a7cb53474575e1cd1cb545902b50ee00889liyuqian fList.pop(); 13138911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 13238911a7cb53474575e1cd1cb545902b50ee00889liyuqian goto unallocate_analytic_edge; 133afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 134afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 13538911a7cb53474575e1cd1cb545902b50ee00889liyuqian fList.push(edge); 13638911a7cb53474575e1cd1cb545902b50ee00889liyuqian } else { 13738911a7cb53474575e1cd1cb545902b50ee00889liyuqianunallocate_analytic_edge: 13838911a7cb53474575e1cd1cb545902b50ee00889liyuqian ; 13938911a7cb53474575e1cd1cb545902b50ee00889liyuqian // TODO: unallocate edge from storage... 140afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 141909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 1424b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby SkEdge* edge = fAlloc.make<SkEdge>(); 14338911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->setLine(pts[0], pts[1], fShiftUp)) { 14438911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (vertical_line(edge) && fList.count()) { 14538911a7cb53474575e1cd1cb545902b50ee00889liyuqian Combine combine = CombineVertical(edge, (SkEdge*)*(fList.end() - 1)); 14638911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (kNo_Combine != combine) { 14738911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (kTotal_Combine == combine) { 14838911a7cb53474575e1cd1cb545902b50ee00889liyuqian fList.pop(); 14938911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 15038911a7cb53474575e1cd1cb545902b50ee00889liyuqian goto unallocate_edge; 15138911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 15238911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 15338911a7cb53474575e1cd1cb545902b50ee00889liyuqian fList.push(edge); 15438911a7cb53474575e1cd1cb545902b50ee00889liyuqian } else { 155afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclarkunallocate_edge: 15638911a7cb53474575e1cd1cb545902b50ee00889liyuqian ; 15738911a7cb53474575e1cd1cb545902b50ee00889liyuqian // TODO: unallocate edge from storage... 15838911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 159909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 160909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 161909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 162909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeBuilder::addQuad(const SkPoint pts[]) { 16338911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (fAnalyticAA) { 1644b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby SkAnalyticQuadraticEdge* edge = fAlloc.make<SkAnalyticQuadraticEdge>(); 16538911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->setQuadratic(pts)) { 16638911a7cb53474575e1cd1cb545902b50ee00889liyuqian fList.push(edge); 16738911a7cb53474575e1cd1cb545902b50ee00889liyuqian } else { 16838911a7cb53474575e1cd1cb545902b50ee00889liyuqian // TODO: unallocate edge from storage... 16938911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 170909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 1714b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby SkQuadraticEdge* edge = fAlloc.make<SkQuadraticEdge>(); 17238911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->setQuadratic(pts, fShiftUp)) { 17338911a7cb53474575e1cd1cb545902b50ee00889liyuqian fList.push(edge); 17438911a7cb53474575e1cd1cb545902b50ee00889liyuqian } else { 17538911a7cb53474575e1cd1cb545902b50ee00889liyuqian // TODO: unallocate edge from storage... 17638911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 177909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 178909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 179909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 180909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeBuilder::addCubic(const SkPoint pts[]) { 18138911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (fAnalyticAA) { 1824b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby SkAnalyticCubicEdge* edge = fAlloc.make<SkAnalyticCubicEdge>(); 18338911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->setCubic(pts)) { 18438911a7cb53474575e1cd1cb545902b50ee00889liyuqian fList.push(edge); 18538911a7cb53474575e1cd1cb545902b50ee00889liyuqian } else { 18638911a7cb53474575e1cd1cb545902b50ee00889liyuqian // TODO: unallocate edge from storage... 18738911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 188909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 1894b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby SkCubicEdge* edge = fAlloc.make<SkCubicEdge>(); 19038911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (edge->setCubic(pts, fShiftUp)) { 19138911a7cb53474575e1cd1cb545902b50ee00889liyuqian fList.push(edge); 19238911a7cb53474575e1cd1cb545902b50ee00889liyuqian } else { 19338911a7cb53474575e1cd1cb545902b50ee00889liyuqian // TODO: unallocate edge from storage... 19438911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 195909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 196909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 197909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 198909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) { 199909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint pts[4]; 200909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPath::Verb verb; 201909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 202909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) { 203909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com switch (verb) { 204909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kLine_Verb: 205909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addLine(pts); 206909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 207909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kQuad_Verb: 208909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addQuad(pts); 209909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 210909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kCubic_Verb: 211909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addCubic(pts); 212909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 213909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com default: 214909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 215909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 216909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 217909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 218909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 219909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 220909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 221909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) { 222909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com dst->set(SkIntToScalar(src.fLeft >> shift), 223909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkIntToScalar(src.fTop >> shift), 224909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkIntToScalar(src.fRight >> shift), 225909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkIntToScalar(src.fBottom >> shift)); 226909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 227909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 228afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclarkSkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkEdge* edge, SkEdge** edgePtr) { 22938911a7cb53474575e1cd1cb545902b50ee00889liyuqian return !vertical_line(edge) || edgePtr <= (SkEdge**)fEdgeList ? kNo_Combine : 23038911a7cb53474575e1cd1cb545902b50ee00889liyuqian CombineVertical(edge, edgePtr[-1]); 23138911a7cb53474575e1cd1cb545902b50ee00889liyuqian} 23238911a7cb53474575e1cd1cb545902b50ee00889liyuqian 23338911a7cb53474575e1cd1cb545902b50ee00889liyuqianSkEdgeBuilder::Combine SkEdgeBuilder::checkVertical(const SkAnalyticEdge* edge, 23438911a7cb53474575e1cd1cb545902b50ee00889liyuqian SkAnalyticEdge** edgePtr) { 23538911a7cb53474575e1cd1cb545902b50ee00889liyuqian SkASSERT(fAnalyticAA); 23638911a7cb53474575e1cd1cb545902b50ee00889liyuqian return !vertical_line(edge) || edgePtr <= (SkAnalyticEdge**)fEdgeList ? kNo_Combine : 237afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark CombineVertical(edge, edgePtr[-1]); 238afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark} 239afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark 24001d3319b67b1ad404006a0026803efc1573f4570reedint SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip, int shiftUp, 24131223e0cb74f47f63b094520a9830c525b72fe87reed bool canCullToTheRight) { 242c8d640b1788822a8697816b645c327383a1d1f20reed@google.com SkPath::Iter iter(path, true); 243c8d640b1788822a8697816b645c327383a1d1f20reed@google.com SkPoint pts[4]; 244c8d640b1788822a8697816b645c327383a1d1f20reed@google.com SkPath::Verb verb; 245fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 246c8d640b1788822a8697816b645c327383a1d1f20reed@google.com int maxEdgeCount = path.countPoints(); 247c8d640b1788822a8697816b645c327383a1d1f20reed@google.com if (iclip) { 248c8d640b1788822a8697816b645c327383a1d1f20reed@google.com // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since 249c8d640b1788822a8697816b645c327383a1d1f20reed@google.com // we turn portions that are clipped out on the left/right into vertical 250c8d640b1788822a8697816b645c327383a1d1f20reed@google.com // segments. 251c8d640b1788822a8697816b645c327383a1d1f20reed@google.com maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments; 252c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 2534b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby 25438911a7cb53474575e1cd1cb545902b50ee00889liyuqian size_t edgeSize = fAnalyticAA ? sizeof(SkAnalyticEdge) : sizeof(SkEdge); 2554b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby char* edge = fAnalyticAA ? (char*)fAlloc.makeArrayDefault<SkAnalyticEdge>(maxEdgeCount) 2564b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby : (char*)fAlloc.makeArrayDefault<SkEdge>(maxEdgeCount); 257c8d640b1788822a8697816b645c327383a1d1f20reed@google.com 2584b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby SkDEBUGCODE(char* edgeStart = edge); 2594b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby char** edgePtr = fAlloc.makeArrayDefault<char*>(maxEdgeCount); 26038911a7cb53474575e1cd1cb545902b50ee00889liyuqian fEdgeList = (void**)edgePtr; 261c8d640b1788822a8697816b645c327383a1d1f20reed@google.com 262c8d640b1788822a8697816b645c327383a1d1f20reed@google.com if (iclip) { 263c8d640b1788822a8697816b645c327383a1d1f20reed@google.com SkRect clip; 264c8d640b1788822a8697816b645c327383a1d1f20reed@google.com setShiftedClip(&clip, *iclip, shiftUp); 265fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 266c8d640b1788822a8697816b645c327383a1d1f20reed@google.com while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 267c8d640b1788822a8697816b645c327383a1d1f20reed@google.com switch (verb) { 268c8d640b1788822a8697816b645c327383a1d1f20reed@google.com case SkPath::kMove_Verb: 269c8d640b1788822a8697816b645c327383a1d1f20reed@google.com case SkPath::kClose_Verb: 270c8d640b1788822a8697816b645c327383a1d1f20reed@google.com // we ignore these, and just get the whole segment from 271c8d640b1788822a8697816b645c327383a1d1f20reed@google.com // the corresponding line/quad/cubic verbs 272c8d640b1788822a8697816b645c327383a1d1f20reed@google.com break; 273c8d640b1788822a8697816b645c327383a1d1f20reed@google.com case SkPath::kLine_Verb: { 274c8d640b1788822a8697816b645c327383a1d1f20reed@google.com SkPoint lines[SkLineClipper::kMaxPoints]; 27531223e0cb74f47f63b094520a9830c525b72fe87reed int lineCount = SkLineClipper::ClipLine(pts, clip, lines, canCullToTheRight); 276c8d640b1788822a8697816b645c327383a1d1f20reed@google.com SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments); 277c8d640b1788822a8697816b645c327383a1d1f20reed@google.com for (int i = 0; i < lineCount; i++) { 27838911a7cb53474575e1cd1cb545902b50ee00889liyuqian bool setLineResult = fAnalyticAA ? 27938911a7cb53474575e1cd1cb545902b50ee00889liyuqian ((SkAnalyticEdge*)edge)->setLine(lines[i], lines[i + 1]) : 28038911a7cb53474575e1cd1cb545902b50ee00889liyuqian ((SkEdge*)edge)->setLine(lines[i], lines[i + 1], shiftUp); 28138911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (setLineResult) { 28238911a7cb53474575e1cd1cb545902b50ee00889liyuqian Combine combine = fAnalyticAA ? 28338911a7cb53474575e1cd1cb545902b50ee00889liyuqian checkVertical((SkAnalyticEdge*)edge, (SkAnalyticEdge**)edgePtr) : 28438911a7cb53474575e1cd1cb545902b50ee00889liyuqian checkVertical((SkEdge*)edge, (SkEdge**)edgePtr); 285afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (kNo_Combine == combine) { 28638911a7cb53474575e1cd1cb545902b50ee00889liyuqian *edgePtr++ = edge; 28738911a7cb53474575e1cd1cb545902b50ee00889liyuqian edge += edgeSize; 288afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } else if (kTotal_Combine == combine) { 289afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark --edgePtr; 290afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 291c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 292c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 293c8d640b1788822a8697816b645c327383a1d1f20reed@google.com break; 294c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 295c8d640b1788822a8697816b645c327383a1d1f20reed@google.com default: 296c8d640b1788822a8697816b645c327383a1d1f20reed@google.com SkDEBUGFAIL("unexpected verb"); 297c8d640b1788822a8697816b645c327383a1d1f20reed@google.com break; 298c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 299c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 300c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } else { 301c8d640b1788822a8697816b645c327383a1d1f20reed@google.com while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 302c8d640b1788822a8697816b645c327383a1d1f20reed@google.com switch (verb) { 303c8d640b1788822a8697816b645c327383a1d1f20reed@google.com case SkPath::kMove_Verb: 304c8d640b1788822a8697816b645c327383a1d1f20reed@google.com case SkPath::kClose_Verb: 305c8d640b1788822a8697816b645c327383a1d1f20reed@google.com // we ignore these, and just get the whole segment from 306c8d640b1788822a8697816b645c327383a1d1f20reed@google.com // the corresponding line/quad/cubic verbs 307c8d640b1788822a8697816b645c327383a1d1f20reed@google.com break; 30838911a7cb53474575e1cd1cb545902b50ee00889liyuqian case SkPath::kLine_Verb: { 30938911a7cb53474575e1cd1cb545902b50ee00889liyuqian bool setLineResult = fAnalyticAA ? 31038911a7cb53474575e1cd1cb545902b50ee00889liyuqian ((SkAnalyticEdge*)edge)->setLine(pts[0], pts[1]) : 31138911a7cb53474575e1cd1cb545902b50ee00889liyuqian ((SkEdge*)edge)->setLine(pts[0], pts[1], shiftUp); 31238911a7cb53474575e1cd1cb545902b50ee00889liyuqian if (setLineResult) { 31338911a7cb53474575e1cd1cb545902b50ee00889liyuqian Combine combine = fAnalyticAA ? 31438911a7cb53474575e1cd1cb545902b50ee00889liyuqian checkVertical((SkAnalyticEdge*)edge, (SkAnalyticEdge**)edgePtr) : 31538911a7cb53474575e1cd1cb545902b50ee00889liyuqian checkVertical((SkEdge*)edge, (SkEdge**)edgePtr); 316afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark if (kNo_Combine == combine) { 31738911a7cb53474575e1cd1cb545902b50ee00889liyuqian *edgePtr++ = edge; 31838911a7cb53474575e1cd1cb545902b50ee00889liyuqian edge += edgeSize; 319afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } else if (kTotal_Combine == combine) { 320afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark --edgePtr; 321afd25f703d9bbc9cd80b03b63b30abd14db4911dcaryclark } 322c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 323c8d640b1788822a8697816b645c327383a1d1f20reed@google.com break; 32438911a7cb53474575e1cd1cb545902b50ee00889liyuqian } 325c8d640b1788822a8697816b645c327383a1d1f20reed@google.com default: 326c8d640b1788822a8697816b645c327383a1d1f20reed@google.com SkDEBUGFAIL("unexpected verb"); 327c8d640b1788822a8697816b645c327383a1d1f20reed@google.com break; 328c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 329c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 330c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 3314b1b04d8ecb3dd8c67d9e1724e7a1898a51dbf32Herb Derby SkASSERT((size_t)(edge - edgeStart) <= maxEdgeCount * edgeSize); 33238911a7cb53474575e1cd1cb545902b50ee00889liyuqian SkASSERT(edgePtr - (char**)fEdgeList <= maxEdgeCount); 33338911a7cb53474575e1cd1cb545902b50ee00889liyuqian return SkToInt(edgePtr - (char**)fEdgeList); 334c8d640b1788822a8697816b645c327383a1d1f20reed@google.com} 335c8d640b1788822a8697816b645c327383a1d1f20reed@google.com 336277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic void handle_quad(SkEdgeBuilder* builder, const SkPoint pts[3]) { 337277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com SkPoint monoX[5]; 338277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com int n = SkChopQuadAtYExtrema(pts, monoX); 339277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com for (int i = 0; i <= n; i++) { 340277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com builder->addQuad(&monoX[i * 2]); 341277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com } 342277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com} 343277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 34401d3319b67b1ad404006a0026803efc1573f4570reedint SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, int shiftUp, 34538911a7cb53474575e1cd1cb545902b50ee00889liyuqian bool canCullToTheRight, bool analyticAA) { 346909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fAlloc.reset(); 347909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fList.reset(); 348909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fShiftUp = shiftUp; 34938911a7cb53474575e1cd1cb545902b50ee00889liyuqian fAnalyticAA = analyticAA; 350909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 351c8d640b1788822a8697816b645c327383a1d1f20reed@google.com if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) { 35231223e0cb74f47f63b094520a9830c525b72fe87reed return this->buildPoly(path, iclip, shiftUp, canCullToTheRight); 353c8d640b1788822a8697816b645c327383a1d1f20reed@google.com } 354c8d640b1788822a8697816b645c327383a1d1f20reed@google.com 355220f926d9d4b38a9018c922c095847bbd261f583reed SkAutoConicToQuads quadder; 3563f4e045b4f8b97d189162d17c85b8410e083a3afreed const SkScalar conicTol = SK_Scalar1 / 4; 357220f926d9d4b38a9018c922c095847bbd261f583reed 358909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPath::Iter iter(path, true); 359909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint pts[4]; 360909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPath::Verb verb; 361909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 362909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (iclip) { 363909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkRect clip; 364909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com setShiftedClip(&clip, *iclip, shiftUp); 36531223e0cb74f47f63b094520a9830c525b72fe87reed SkEdgeClipper clipper(canCullToTheRight); 366909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 3674a3b714d73e585a3985d614600c6b79d5c8b1f1ereed@google.com while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 368909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com switch (verb) { 369909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kMove_Verb: 370909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kClose_Verb: 371909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // we ignore these, and just get the whole segment from 372909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // the corresponding line/quad/cubic verbs 373909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 3745baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed case SkPath::kLine_Verb: 3755baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed if (clipper.clipLine(pts[0], pts[1], clip)) { 3765baafa8ff1b7e2fa0bd0c3d3733f47656fcc6277Mike Reed this->addClipper(&clipper); 377909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 378909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 379909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kQuad_Verb: 380909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (clipper.clipQuad(pts, clip)) { 381909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addClipper(&clipper); 382909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 383909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 384277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com case SkPath::kConic_Verb: { 385220f926d9d4b38a9018c922c095847bbd261f583reed const SkPoint* quadPts = quadder.computeQuads( 386220f926d9d4b38a9018c922c095847bbd261f583reed pts, iter.conicWeight(), conicTol); 387220f926d9d4b38a9018c922c095847bbd261f583reed for (int i = 0; i < quadder.countQuads(); ++i) { 388220f926d9d4b38a9018c922c095847bbd261f583reed if (clipper.clipQuad(quadPts, clip)) { 389277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com this->addClipper(&clipper); 390277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com } 391220f926d9d4b38a9018c922c095847bbd261f583reed quadPts += 2; 392277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com } 393277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com } break; 394909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kCubic_Verb: 395909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (clipper.clipCubic(pts, clip)) { 396909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addClipper(&clipper); 397909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 398909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 399909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com default: 4000c00f21fee3f5cfa3aa7e5d46ff94cb8cf340451tomhudson@google.com SkDEBUGFAIL("unexpected verb"); 401909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 402909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 403909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 404909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 4054a3b714d73e585a3985d614600c6b79d5c8b1f1ereed@google.com while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 406909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com switch (verb) { 407909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kMove_Verb: 408909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kClose_Verb: 409909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // we ignore these, and just get the whole segment from 410909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // the corresponding line/quad/cubic verbs 411909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 412909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kLine_Verb: 413909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addLine(pts); 414909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 415909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kQuad_Verb: { 416277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com handle_quad(this, pts); 417909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 418909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 419277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com case SkPath::kConic_Verb: { 420220f926d9d4b38a9018c922c095847bbd261f583reed const SkPoint* quadPts = quadder.computeQuads( 421220f926d9d4b38a9018c922c095847bbd261f583reed pts, iter.conicWeight(), conicTol); 422220f926d9d4b38a9018c922c095847bbd261f583reed for (int i = 0; i < quadder.countQuads(); ++i) { 423220f926d9d4b38a9018c922c095847bbd261f583reed handle_quad(this, quadPts); 424220f926d9d4b38a9018c922c095847bbd261f583reed quadPts += 2; 425277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com } 426277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com } break; 427909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kCubic_Verb: { 428909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint monoY[10]; 429909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int n = SkChopCubicAtYExtrema(pts, monoY); 430909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i <= n; i++) { 431909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addCubic(&monoY[i * 3]); 432909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 433909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 434909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 435909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com default: 4360c00f21fee3f5cfa3aa7e5d46ff94cb8cf340451tomhudson@google.com SkDEBUGFAIL("unexpected verb"); 437909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 438909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 439909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 440909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 441c8d640b1788822a8697816b645c327383a1d1f20reed@google.com fEdgeList = fList.begin(); 442909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return fList.count(); 443909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 444