SkEdgeBuilder.cpp revision 0c00f21fee3f5cfa3aa7e5d46ff94cb8cf340451
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 8909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkEdgeBuilder.h" 9909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkPath.h" 10909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkEdge.h" 11909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkEdgeClipper.h" 12909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkLineClipper.h" 13909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com#include "SkGeometry.h" 14909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 15909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comSkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {} 16909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 17909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comtemplate <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) { 18909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return static_cast<T*>(alloc.allocThrow(sizeof(T))); 19909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 20909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 21909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 22909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 23909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeBuilder::addLine(const SkPoint pts[]) { 24909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc); 25909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (edge->setLine(pts[0], pts[1], NULL, fShiftUp)) { 26909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fList.push(edge); 27909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 28909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // TODO: unallocate edge from storage... 29909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 30909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 31909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 32909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeBuilder::addQuad(const SkPoint pts[]) { 33909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkQuadraticEdge* edge = typedAllocThrow<SkQuadraticEdge>(fAlloc); 34909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (edge->setQuadratic(pts, fShiftUp)) { 35909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fList.push(edge); 36909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 37909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // TODO: unallocate edge from storage... 38909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 39909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 40909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 41909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeBuilder::addCubic(const SkPoint pts[]) { 42909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkCubicEdge* edge = typedAllocThrow<SkCubicEdge>(fAlloc); 43909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (edge->setCubic(pts, NULL, fShiftUp)) { 44909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fList.push(edge); 45909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 46909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // TODO: unallocate edge from storage... 47909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 48909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 49909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 50909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comvoid SkEdgeBuilder::addClipper(SkEdgeClipper* clipper) { 51909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint pts[4]; 52909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPath::Verb verb; 53909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 54909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com while ((verb = clipper->next(pts)) != SkPath::kDone_Verb) { 55909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com switch (verb) { 56909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kLine_Verb: 57909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addLine(pts); 58909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 59909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kQuad_Verb: 60909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addQuad(pts); 61909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 62909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kCubic_Verb: 63909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addCubic(pts); 64909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 65909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com default: 66909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 67909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 68909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 69909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 70909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 71909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com/////////////////////////////////////////////////////////////////////////////// 72909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 73909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comstatic void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) { 74909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com dst->set(SkIntToScalar(src.fLeft >> shift), 75909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkIntToScalar(src.fTop >> shift), 76909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkIntToScalar(src.fRight >> shift), 77909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkIntToScalar(src.fBottom >> shift)); 78909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 79909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 80909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comint SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip, 81909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int shiftUp) { 82909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fAlloc.reset(); 83909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fList.reset(); 84909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com fShiftUp = shiftUp; 85909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 86909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPath::Iter iter(path, true); 87909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint pts[4]; 88909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPath::Verb verb; 89909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 90909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (iclip) { 91909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkRect clip; 92909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com setShiftedClip(&clip, *iclip, shiftUp); 93909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkEdgeClipper clipper; 94909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 95909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 96909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com switch (verb) { 97909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kMove_Verb: 98909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kClose_Verb: 99909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // we ignore these, and just get the whole segment from 100909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // the corresponding line/quad/cubic verbs 101909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 102909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kLine_Verb: { 103909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint lines[SkLineClipper::kMaxPoints]; 104909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int lineCount = SkLineClipper::ClipLine(pts, clip, lines); 105909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i < lineCount; i++) { 106909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addLine(&lines[i]); 107909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 108909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 109909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 110909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kQuad_Verb: 111909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (clipper.clipQuad(pts, clip)) { 112909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addClipper(&clipper); 113909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 114909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 115909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kCubic_Verb: 116909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com if (clipper.clipCubic(pts, clip)) { 117909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addClipper(&clipper); 118909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 119909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 120909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com default: 1210c00f21fee3f5cfa3aa7e5d46ff94cb8cf340451tomhudson@google.com SkDEBUGFAIL("unexpected verb"); 122909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 123909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 124909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 125909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } else { 126909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 127909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com switch (verb) { 128909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kMove_Verb: 129909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kClose_Verb: 130909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // we ignore these, and just get the whole segment from 131909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com // the corresponding line/quad/cubic verbs 132909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 133909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kLine_Verb: 134909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addLine(pts); 135909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 136909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kQuad_Verb: { 137909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint monoX[5]; 138909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int n = SkChopQuadAtYExtrema(pts, monoX); 139909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i <= n; i++) { 140909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addQuad(&monoX[i * 2]); 141909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 142909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 143909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 144909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com case SkPath::kCubic_Verb: { 145909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com SkPoint monoY[10]; 146909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com int n = SkChopCubicAtYExtrema(pts, monoY); 147909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com for (int i = 0; i <= n; i++) { 148909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com this->addCubic(&monoY[i * 3]); 149909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 150909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 151909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 152909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com default: 1530c00f21fee3f5cfa3aa7e5d46ff94cb8cf340451tomhudson@google.com SkDEBUGFAIL("unexpected verb"); 154909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com break; 155909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 156909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 157909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com } 158909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com return fList.count(); 159909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com} 160909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 161909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 162