GrAAConvexTessellator.cpp 41 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104
  1. /*
  2. * Copyright 2015 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "include/core/SkCanvas.h"
  8. #include "include/core/SkPath.h"
  9. #include "include/core/SkPoint.h"
  10. #include "include/core/SkString.h"
  11. #include "src/gpu/geometry/GrPathUtils.h"
  12. #include "src/gpu/ops/GrAAConvexTessellator.h"
  13. // Next steps:
  14. // add an interactive sample app slide
  15. // add debug check that all points are suitably far apart
  16. // test more degenerate cases
  17. // The tolerance for fusing vertices and eliminating colinear lines (It is in device space).
  18. static const SkScalar kClose = (SK_Scalar1 / 16);
  19. static const SkScalar kCloseSqd = kClose * kClose;
  20. // tesselation tolerance values, in device space pixels
  21. static const SkScalar kQuadTolerance = 0.2f;
  22. static const SkScalar kCubicTolerance = 0.2f;
  23. static const SkScalar kConicTolerance = 0.25f;
  24. // dot product below which we use a round cap between curve segments
  25. static const SkScalar kRoundCapThreshold = 0.8f;
  26. // dot product above which we consider two adjacent curves to be part of the "same" curve
  27. static const SkScalar kCurveConnectionThreshold = 0.8f;
  28. static bool intersect(const SkPoint& p0, const SkPoint& n0,
  29. const SkPoint& p1, const SkPoint& n1,
  30. SkScalar* t) {
  31. const SkPoint v = p1 - p0;
  32. SkScalar perpDot = n0.fX * n1.fY - n0.fY * n1.fX;
  33. if (SkScalarNearlyZero(perpDot)) {
  34. return false;
  35. }
  36. *t = (v.fX * n1.fY - v.fY * n1.fX) / perpDot;
  37. SkASSERT(SkScalarIsFinite(*t));
  38. return true;
  39. }
  40. // This is a special case version of intersect where we have the vector
  41. // perpendicular to the second line rather than the vector parallel to it.
  42. static SkScalar perp_intersect(const SkPoint& p0, const SkPoint& n0,
  43. const SkPoint& p1, const SkPoint& perp) {
  44. const SkPoint v = p1 - p0;
  45. SkScalar perpDot = n0.dot(perp);
  46. return v.dot(perp) / perpDot;
  47. }
  48. static bool duplicate_pt(const SkPoint& p0, const SkPoint& p1) {
  49. SkScalar distSq = SkPointPriv::DistanceToSqd(p0, p1);
  50. return distSq < kCloseSqd;
  51. }
  52. static bool points_are_colinear_and_b_is_middle(const SkPoint& a, const SkPoint& b,
  53. const SkPoint& c) {
  54. // 'area' is twice the area of the triangle with corners a, b, and c.
  55. SkScalar area = a.fX * (b.fY - c.fY) + b.fX * (c.fY - a.fY) + c.fX * (a.fY - b.fY);
  56. if (SkScalarAbs(area) >= 2 * kCloseSqd) {
  57. return false;
  58. }
  59. return (a - b).dot(b - c) >= 0;
  60. }
  61. int GrAAConvexTessellator::addPt(const SkPoint& pt,
  62. SkScalar depth,
  63. SkScalar coverage,
  64. bool movable,
  65. CurveState curve) {
  66. SkASSERT(pt.isFinite());
  67. this->validate();
  68. int index = fPts.count();
  69. *fPts.push() = pt;
  70. *fCoverages.push() = coverage;
  71. *fMovable.push() = movable;
  72. *fCurveState.push() = curve;
  73. this->validate();
  74. return index;
  75. }
  76. void GrAAConvexTessellator::popLastPt() {
  77. this->validate();
  78. fPts.pop();
  79. fCoverages.pop();
  80. fMovable.pop();
  81. fCurveState.pop();
  82. this->validate();
  83. }
  84. void GrAAConvexTessellator::popFirstPtShuffle() {
  85. this->validate();
  86. fPts.removeShuffle(0);
  87. fCoverages.removeShuffle(0);
  88. fMovable.removeShuffle(0);
  89. fCurveState.removeShuffle(0);
  90. this->validate();
  91. }
  92. void GrAAConvexTessellator::updatePt(int index,
  93. const SkPoint& pt,
  94. SkScalar depth,
  95. SkScalar coverage) {
  96. this->validate();
  97. SkASSERT(fMovable[index]);
  98. fPts[index] = pt;
  99. fCoverages[index] = coverage;
  100. }
  101. void GrAAConvexTessellator::addTri(int i0, int i1, int i2) {
  102. if (i0 == i1 || i1 == i2 || i2 == i0) {
  103. return;
  104. }
  105. *fIndices.push() = i0;
  106. *fIndices.push() = i1;
  107. *fIndices.push() = i2;
  108. }
  109. void GrAAConvexTessellator::rewind() {
  110. fPts.rewind();
  111. fCoverages.rewind();
  112. fMovable.rewind();
  113. fIndices.rewind();
  114. fNorms.rewind();
  115. fCurveState.rewind();
  116. fInitialRing.rewind();
  117. fCandidateVerts.rewind();
  118. #if GR_AA_CONVEX_TESSELLATOR_VIZ
  119. fRings.rewind(); // TODO: leak in this case!
  120. #else
  121. fRings[0].rewind();
  122. fRings[1].rewind();
  123. #endif
  124. }
  125. void GrAAConvexTessellator::computeNormals() {
  126. auto normalToVector = [this](SkVector v) {
  127. SkVector n = SkPointPriv::MakeOrthog(v, fSide);
  128. SkAssertResult(n.normalize());
  129. SkASSERT(SkScalarNearlyEqual(1.0f, n.length()));
  130. return n;
  131. };
  132. // Check the cross product of the final trio
  133. fNorms.append(fPts.count());
  134. fNorms[0] = fPts[1] - fPts[0];
  135. fNorms.top() = fPts[0] - fPts.top();
  136. SkScalar cross = SkPoint::CrossProduct(fNorms[0], fNorms.top());
  137. fSide = (cross > 0.0f) ? SkPointPriv::kRight_Side : SkPointPriv::kLeft_Side;
  138. fNorms[0] = normalToVector(fNorms[0]);
  139. for (int cur = 1; cur < fNorms.count() - 1; ++cur) {
  140. fNorms[cur] = normalToVector(fPts[cur + 1] - fPts[cur]);
  141. }
  142. fNorms.top() = normalToVector(fNorms.top());
  143. }
  144. void GrAAConvexTessellator::computeBisectors() {
  145. fBisectors.setCount(fNorms.count());
  146. int prev = fBisectors.count() - 1;
  147. for (int cur = 0; cur < fBisectors.count(); prev = cur, ++cur) {
  148. fBisectors[cur] = fNorms[cur] + fNorms[prev];
  149. if (!fBisectors[cur].normalize()) {
  150. fBisectors[cur] = SkPointPriv::MakeOrthog(fNorms[cur], (SkPointPriv::Side)-fSide) +
  151. SkPointPriv::MakeOrthog(fNorms[prev], fSide);
  152. SkAssertResult(fBisectors[cur].normalize());
  153. } else {
  154. fBisectors[cur].negate(); // make the bisector face in
  155. }
  156. if (fCurveState[prev] == kIndeterminate_CurveState) {
  157. if (fCurveState[cur] == kSharp_CurveState) {
  158. fCurveState[prev] = kSharp_CurveState;
  159. } else {
  160. if (SkScalarAbs(fNorms[cur].dot(fNorms[prev])) > kCurveConnectionThreshold) {
  161. fCurveState[prev] = kCurve_CurveState;
  162. fCurveState[cur] = kCurve_CurveState;
  163. } else {
  164. fCurveState[prev] = kSharp_CurveState;
  165. fCurveState[cur] = kSharp_CurveState;
  166. }
  167. }
  168. }
  169. SkASSERT(SkScalarNearlyEqual(1.0f, fBisectors[cur].length()));
  170. }
  171. }
  172. // Create as many rings as we need to (up to a predefined limit) to reach the specified target
  173. // depth. If we are in fill mode, the final ring will automatically be fanned.
  174. bool GrAAConvexTessellator::createInsetRings(Ring& previousRing, SkScalar initialDepth,
  175. SkScalar initialCoverage, SkScalar targetDepth,
  176. SkScalar targetCoverage, Ring** finalRing) {
  177. static const int kMaxNumRings = 8;
  178. if (previousRing.numPts() < 3) {
  179. return false;
  180. }
  181. Ring* currentRing = &previousRing;
  182. int i;
  183. for (i = 0; i < kMaxNumRings; ++i) {
  184. Ring* nextRing = this->getNextRing(currentRing);
  185. SkASSERT(nextRing != currentRing);
  186. bool done = this->createInsetRing(*currentRing, nextRing, initialDepth, initialCoverage,
  187. targetDepth, targetCoverage, i == 0);
  188. currentRing = nextRing;
  189. if (done) {
  190. break;
  191. }
  192. currentRing->init(*this);
  193. }
  194. if (kMaxNumRings == i) {
  195. // Bail if we've exceeded the amount of time we want to throw at this.
  196. this->terminate(*currentRing);
  197. return false;
  198. }
  199. bool done = currentRing->numPts() >= 3;
  200. if (done) {
  201. currentRing->init(*this);
  202. }
  203. *finalRing = currentRing;
  204. return done;
  205. }
  206. // The general idea here is to, conceptually, start with the original polygon and slide
  207. // the vertices along the bisectors until the first intersection. At that
  208. // point two of the edges collapse and the process repeats on the new polygon.
  209. // The polygon state is captured in the Ring class while the GrAAConvexTessellator
  210. // controls the iteration. The CandidateVerts holds the formative points for the
  211. // next ring.
  212. bool GrAAConvexTessellator::tessellate(const SkMatrix& m, const SkPath& path) {
  213. if (!this->extractFromPath(m, path)) {
  214. return false;
  215. }
  216. SkScalar coverage = 1.0f;
  217. SkScalar scaleFactor = 0.0f;
  218. if (SkStrokeRec::kStrokeAndFill_Style == fStyle) {
  219. SkASSERT(m.isSimilarity());
  220. scaleFactor = m.getMaxScale(); // x and y scale are the same
  221. SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth;
  222. Ring outerStrokeAndAARing;
  223. this->createOuterRing(fInitialRing,
  224. effectiveStrokeWidth / 2 + kAntialiasingRadius, 0.0,
  225. &outerStrokeAndAARing);
  226. // discard all the triangles added between the originating ring and the new outer ring
  227. fIndices.rewind();
  228. outerStrokeAndAARing.init(*this);
  229. outerStrokeAndAARing.makeOriginalRing();
  230. // Add the outer stroke ring's normals to the originating ring's normals
  231. // so it can also act as an originating ring
  232. fNorms.setCount(fNorms.count() + outerStrokeAndAARing.numPts());
  233. for (int i = 0; i < outerStrokeAndAARing.numPts(); ++i) {
  234. SkASSERT(outerStrokeAndAARing.index(i) < fNorms.count());
  235. fNorms[outerStrokeAndAARing.index(i)] = outerStrokeAndAARing.norm(i);
  236. }
  237. // the bisectors are only needed for the computation of the outer ring
  238. fBisectors.rewind();
  239. Ring* insetAARing;
  240. this->createInsetRings(outerStrokeAndAARing,
  241. 0.0f, 0.0f, 2*kAntialiasingRadius, 1.0f,
  242. &insetAARing);
  243. SkDEBUGCODE(this->validate();)
  244. return true;
  245. }
  246. if (SkStrokeRec::kStroke_Style == fStyle) {
  247. SkASSERT(fStrokeWidth >= 0.0f);
  248. SkASSERT(m.isSimilarity());
  249. scaleFactor = m.getMaxScale(); // x and y scale are the same
  250. SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth;
  251. Ring outerStrokeRing;
  252. this->createOuterRing(fInitialRing, effectiveStrokeWidth / 2 - kAntialiasingRadius,
  253. coverage, &outerStrokeRing);
  254. outerStrokeRing.init(*this);
  255. Ring outerAARing;
  256. this->createOuterRing(outerStrokeRing, kAntialiasingRadius * 2, 0.0f, &outerAARing);
  257. } else {
  258. Ring outerAARing;
  259. this->createOuterRing(fInitialRing, kAntialiasingRadius, 0.0f, &outerAARing);
  260. }
  261. // the bisectors are only needed for the computation of the outer ring
  262. fBisectors.rewind();
  263. if (SkStrokeRec::kStroke_Style == fStyle && fInitialRing.numPts() > 2) {
  264. SkASSERT(fStrokeWidth >= 0.0f);
  265. SkScalar effectiveStrokeWidth = scaleFactor * fStrokeWidth;
  266. Ring* insetStrokeRing;
  267. SkScalar strokeDepth = effectiveStrokeWidth / 2 - kAntialiasingRadius;
  268. if (this->createInsetRings(fInitialRing, 0.0f, coverage, strokeDepth, coverage,
  269. &insetStrokeRing)) {
  270. Ring* insetAARing;
  271. this->createInsetRings(*insetStrokeRing, strokeDepth, coverage, strokeDepth +
  272. kAntialiasingRadius * 2, 0.0f, &insetAARing);
  273. }
  274. } else {
  275. Ring* insetAARing;
  276. this->createInsetRings(fInitialRing, 0.0f, 0.5f, kAntialiasingRadius, 1.0f, &insetAARing);
  277. }
  278. SkDEBUGCODE(this->validate();)
  279. return true;
  280. }
  281. SkScalar GrAAConvexTessellator::computeDepthFromEdge(int edgeIdx, const SkPoint& p) const {
  282. SkASSERT(edgeIdx < fNorms.count());
  283. SkPoint v = p - fPts[edgeIdx];
  284. SkScalar depth = -fNorms[edgeIdx].dot(v);
  285. return depth;
  286. }
  287. // Find a point that is 'desiredDepth' away from the 'edgeIdx'-th edge and lies
  288. // along the 'bisector' from the 'startIdx'-th point.
  289. bool GrAAConvexTessellator::computePtAlongBisector(int startIdx,
  290. const SkVector& bisector,
  291. int edgeIdx,
  292. SkScalar desiredDepth,
  293. SkPoint* result) const {
  294. const SkPoint& norm = fNorms[edgeIdx];
  295. // First find the point where the edge and the bisector intersect
  296. SkPoint newP;
  297. SkScalar t = perp_intersect(fPts[startIdx], bisector, fPts[edgeIdx], norm);
  298. if (SkScalarNearlyEqual(t, 0.0f)) {
  299. // the start point was one of the original ring points
  300. SkASSERT(startIdx < fPts.count());
  301. newP = fPts[startIdx];
  302. } else if (t < 0.0f) {
  303. newP = bisector;
  304. newP.scale(t);
  305. newP += fPts[startIdx];
  306. } else {
  307. return false;
  308. }
  309. // Then offset along the bisector from that point the correct distance
  310. SkScalar dot = bisector.dot(norm);
  311. t = -desiredDepth / dot;
  312. *result = bisector;
  313. result->scale(t);
  314. *result += newP;
  315. return true;
  316. }
  317. bool GrAAConvexTessellator::extractFromPath(const SkMatrix& m, const SkPath& path) {
  318. SkASSERT(SkPath::kConvex_Convexity == path.getConvexity());
  319. SkRect bounds = path.getBounds();
  320. m.mapRect(&bounds);
  321. if (!bounds.isFinite()) {
  322. // We could do something smarter here like clip the path based on the bounds of the dst.
  323. // We'd have to be careful about strokes to ensure we don't draw something wrong.
  324. return false;
  325. }
  326. // Outer ring: 3*numPts
  327. // Middle ring: numPts
  328. // Presumptive inner ring: numPts
  329. this->reservePts(5*path.countPoints());
  330. // Outer ring: 12*numPts
  331. // Middle ring: 0
  332. // Presumptive inner ring: 6*numPts + 6
  333. fIndices.setReserve(18*path.countPoints() + 6);
  334. // TODO: is there a faster way to extract the points from the path? Perhaps
  335. // get all the points via a new entry point, transform them all in bulk
  336. // and then walk them to find duplicates?
  337. SkPath::Iter iter(path, true);
  338. SkPoint pts[4];
  339. SkPath::Verb verb;
  340. while ((verb = iter.next(pts, true, true)) != SkPath::kDone_Verb) {
  341. switch (verb) {
  342. case SkPath::kLine_Verb:
  343. this->lineTo(m, pts[1], kSharp_CurveState);
  344. break;
  345. case SkPath::kQuad_Verb:
  346. this->quadTo(m, pts);
  347. break;
  348. case SkPath::kCubic_Verb:
  349. this->cubicTo(m, pts);
  350. break;
  351. case SkPath::kConic_Verb:
  352. this->conicTo(m, pts, iter.conicWeight());
  353. break;
  354. case SkPath::kMove_Verb:
  355. case SkPath::kClose_Verb:
  356. case SkPath::kDone_Verb:
  357. break;
  358. }
  359. }
  360. if (this->numPts() < 2) {
  361. return false;
  362. }
  363. // check if last point is a duplicate of the first point. If so, remove it.
  364. if (duplicate_pt(fPts[this->numPts()-1], fPts[0])) {
  365. this->popLastPt();
  366. }
  367. // Remove any lingering colinear points where the path wraps around
  368. bool noRemovalsToDo = false;
  369. while (!noRemovalsToDo && this->numPts() >= 3) {
  370. if (points_are_colinear_and_b_is_middle(fPts[fPts.count() - 2], fPts.top(), fPts[0])) {
  371. this->popLastPt();
  372. } else if (points_are_colinear_and_b_is_middle(fPts.top(), fPts[0], fPts[1])) {
  373. this->popFirstPtShuffle();
  374. } else {
  375. noRemovalsToDo = true;
  376. }
  377. }
  378. // Compute the normals and bisectors.
  379. SkASSERT(fNorms.empty());
  380. if (this->numPts() >= 3) {
  381. this->computeNormals();
  382. this->computeBisectors();
  383. } else if (this->numPts() == 2) {
  384. // We've got two points, so we're degenerate.
  385. if (fStyle == SkStrokeRec::kFill_Style) {
  386. // it's a fill, so we don't need to worry about degenerate paths
  387. return false;
  388. }
  389. // For stroking, we still need to process the degenerate path, so fix it up
  390. fSide = SkPointPriv::kLeft_Side;
  391. fNorms.append(2);
  392. fNorms[0] = SkPointPriv::MakeOrthog(fPts[1] - fPts[0], fSide);
  393. fNorms[0].normalize();
  394. fNorms[1] = -fNorms[0];
  395. SkASSERT(SkScalarNearlyEqual(1.0f, fNorms[0].length()));
  396. // we won't actually use the bisectors, so just push zeroes
  397. fBisectors.push_back(SkPoint::Make(0.0, 0.0));
  398. fBisectors.push_back(SkPoint::Make(0.0, 0.0));
  399. } else {
  400. return false;
  401. }
  402. fCandidateVerts.setReserve(this->numPts());
  403. fInitialRing.setReserve(this->numPts());
  404. for (int i = 0; i < this->numPts(); ++i) {
  405. fInitialRing.addIdx(i, i);
  406. }
  407. fInitialRing.init(fNorms, fBisectors);
  408. this->validate();
  409. return true;
  410. }
  411. GrAAConvexTessellator::Ring* GrAAConvexTessellator::getNextRing(Ring* lastRing) {
  412. #if GR_AA_CONVEX_TESSELLATOR_VIZ
  413. Ring* ring = *fRings.push() = new Ring;
  414. ring->setReserve(fInitialRing.numPts());
  415. ring->rewind();
  416. return ring;
  417. #else
  418. // Flip flop back and forth between fRings[0] & fRings[1]
  419. int nextRing = (lastRing == &fRings[0]) ? 1 : 0;
  420. fRings[nextRing].setReserve(fInitialRing.numPts());
  421. fRings[nextRing].rewind();
  422. return &fRings[nextRing];
  423. #endif
  424. }
  425. void GrAAConvexTessellator::fanRing(const Ring& ring) {
  426. // fan out from point 0
  427. int startIdx = ring.index(0);
  428. for (int cur = ring.numPts() - 2; cur >= 0; --cur) {
  429. this->addTri(startIdx, ring.index(cur), ring.index(cur + 1));
  430. }
  431. }
  432. void GrAAConvexTessellator::createOuterRing(const Ring& previousRing, SkScalar outset,
  433. SkScalar coverage, Ring* nextRing) {
  434. const int numPts = previousRing.numPts();
  435. if (numPts == 0) {
  436. return;
  437. }
  438. int prev = numPts - 1;
  439. int lastPerpIdx = -1, firstPerpIdx = -1;
  440. const SkScalar outsetSq = outset * outset;
  441. SkScalar miterLimitSq = outset * fMiterLimit;
  442. miterLimitSq = miterLimitSq * miterLimitSq;
  443. for (int cur = 0; cur < numPts; ++cur) {
  444. int originalIdx = previousRing.index(cur);
  445. // For each vertex of the original polygon we add at least two points to the
  446. // outset polygon - one extending perpendicular to each impinging edge. Connecting these
  447. // two points yields a bevel join. We need one additional point for a mitered join, and
  448. // a round join requires one or more points depending upon curvature.
  449. // The perpendicular point for the last edge
  450. SkPoint normal1 = previousRing.norm(prev);
  451. SkPoint perp1 = normal1;
  452. perp1.scale(outset);
  453. perp1 += this->point(originalIdx);
  454. // The perpendicular point for the next edge.
  455. SkPoint normal2 = previousRing.norm(cur);
  456. SkPoint perp2 = normal2;
  457. perp2.scale(outset);
  458. perp2 += fPts[originalIdx];
  459. CurveState curve = fCurveState[originalIdx];
  460. // We know it isn't a duplicate of the prior point (since it and this
  461. // one are just perpendicular offsets from the non-merged polygon points)
  462. int perp1Idx = this->addPt(perp1, -outset, coverage, false, curve);
  463. nextRing->addIdx(perp1Idx, originalIdx);
  464. int perp2Idx;
  465. // For very shallow angles all the corner points could fuse.
  466. if (duplicate_pt(perp2, this->point(perp1Idx))) {
  467. perp2Idx = perp1Idx;
  468. } else {
  469. perp2Idx = this->addPt(perp2, -outset, coverage, false, curve);
  470. }
  471. if (perp2Idx != perp1Idx) {
  472. if (curve == kCurve_CurveState) {
  473. // bevel or round depending upon curvature
  474. SkScalar dotProd = normal1.dot(normal2);
  475. if (dotProd < kRoundCapThreshold) {
  476. // Currently we "round" by creating a single extra point, which produces
  477. // good results for common cases. For thick strokes with high curvature, we will
  478. // need to add more points; for the time being we simply fall back to software
  479. // rendering for thick strokes.
  480. SkPoint miter = previousRing.bisector(cur);
  481. miter.setLength(-outset);
  482. miter += fPts[originalIdx];
  483. // For very shallow angles all the corner points could fuse
  484. if (!duplicate_pt(miter, this->point(perp1Idx))) {
  485. int miterIdx;
  486. miterIdx = this->addPt(miter, -outset, coverage, false, kSharp_CurveState);
  487. nextRing->addIdx(miterIdx, originalIdx);
  488. // The two triangles for the corner
  489. this->addTri(originalIdx, perp1Idx, miterIdx);
  490. this->addTri(originalIdx, miterIdx, perp2Idx);
  491. }
  492. } else {
  493. this->addTri(originalIdx, perp1Idx, perp2Idx);
  494. }
  495. } else {
  496. switch (fJoin) {
  497. case SkPaint::Join::kMiter_Join: {
  498. // The bisector outset point
  499. SkPoint miter = previousRing.bisector(cur);
  500. SkScalar dotProd = normal1.dot(normal2);
  501. // The max is because this could go slightly negative if precision causes
  502. // us to become slightly concave.
  503. SkScalar sinHalfAngleSq = SkTMax(SkScalarHalf(SK_Scalar1 + dotProd), 0.f);
  504. SkScalar lengthSq = sk_ieee_float_divide(outsetSq, sinHalfAngleSq);
  505. if (lengthSq > miterLimitSq) {
  506. // just bevel it
  507. this->addTri(originalIdx, perp1Idx, perp2Idx);
  508. break;
  509. }
  510. miter.setLength(-SkScalarSqrt(lengthSq));
  511. miter += fPts[originalIdx];
  512. // For very shallow angles all the corner points could fuse
  513. if (!duplicate_pt(miter, this->point(perp1Idx))) {
  514. int miterIdx;
  515. miterIdx = this->addPt(miter, -outset, coverage, false,
  516. kSharp_CurveState);
  517. nextRing->addIdx(miterIdx, originalIdx);
  518. // The two triangles for the corner
  519. this->addTri(originalIdx, perp1Idx, miterIdx);
  520. this->addTri(originalIdx, miterIdx, perp2Idx);
  521. } else {
  522. // ignore the miter point as it's so close to perp1/perp2 and simply
  523. // bevel.
  524. this->addTri(originalIdx, perp1Idx, perp2Idx);
  525. }
  526. break;
  527. }
  528. case SkPaint::Join::kBevel_Join:
  529. this->addTri(originalIdx, perp1Idx, perp2Idx);
  530. break;
  531. default:
  532. // kRound_Join is unsupported for now. GrAALinearizingConvexPathRenderer is
  533. // only willing to draw mitered or beveled, so we should never get here.
  534. SkASSERT(false);
  535. }
  536. }
  537. nextRing->addIdx(perp2Idx, originalIdx);
  538. }
  539. if (0 == cur) {
  540. // Store the index of the first perpendicular point to finish up
  541. firstPerpIdx = perp1Idx;
  542. SkASSERT(-1 == lastPerpIdx);
  543. } else {
  544. // The triangles for the previous edge
  545. int prevIdx = previousRing.index(prev);
  546. this->addTri(prevIdx, perp1Idx, originalIdx);
  547. this->addTri(prevIdx, lastPerpIdx, perp1Idx);
  548. }
  549. // Track the last perpendicular outset point so we can construct the
  550. // trailing edge triangles.
  551. lastPerpIdx = perp2Idx;
  552. prev = cur;
  553. }
  554. // pick up the final edge rect
  555. int lastIdx = previousRing.index(numPts - 1);
  556. this->addTri(lastIdx, firstPerpIdx, previousRing.index(0));
  557. this->addTri(lastIdx, lastPerpIdx, firstPerpIdx);
  558. this->validate();
  559. }
  560. // Something went wrong in the creation of the next ring. If we're filling the shape, just go ahead
  561. // and fan it.
  562. void GrAAConvexTessellator::terminate(const Ring& ring) {
  563. if (fStyle != SkStrokeRec::kStroke_Style && ring.numPts() > 0) {
  564. this->fanRing(ring);
  565. }
  566. }
  567. static SkScalar compute_coverage(SkScalar depth, SkScalar initialDepth, SkScalar initialCoverage,
  568. SkScalar targetDepth, SkScalar targetCoverage) {
  569. if (SkScalarNearlyEqual(initialDepth, targetDepth)) {
  570. return targetCoverage;
  571. }
  572. SkScalar result = (depth - initialDepth) / (targetDepth - initialDepth) *
  573. (targetCoverage - initialCoverage) + initialCoverage;
  574. return SkScalarClampMax(result, 1.0f);
  575. }
  576. // return true when processing is complete
  577. bool GrAAConvexTessellator::createInsetRing(const Ring& lastRing, Ring* nextRing,
  578. SkScalar initialDepth, SkScalar initialCoverage,
  579. SkScalar targetDepth, SkScalar targetCoverage,
  580. bool forceNew) {
  581. bool done = false;
  582. fCandidateVerts.rewind();
  583. // Loop through all the points in the ring and find the intersection with the smallest depth
  584. SkScalar minDist = SK_ScalarMax, minT = 0.0f;
  585. int minEdgeIdx = -1;
  586. for (int cur = 0; cur < lastRing.numPts(); ++cur) {
  587. int next = (cur + 1) % lastRing.numPts();
  588. SkScalar t;
  589. bool result = intersect(this->point(lastRing.index(cur)), lastRing.bisector(cur),
  590. this->point(lastRing.index(next)), lastRing.bisector(next),
  591. &t);
  592. // The bisectors may be parallel (!result) or the previous ring may have become slightly
  593. // concave due to accumulated error (t <= 0).
  594. if (!result || t <= 0) {
  595. continue;
  596. }
  597. SkScalar dist = -t * lastRing.norm(cur).dot(lastRing.bisector(cur));
  598. if (minDist > dist) {
  599. minDist = dist;
  600. minT = t;
  601. minEdgeIdx = cur;
  602. }
  603. }
  604. if (minEdgeIdx == -1) {
  605. return false;
  606. }
  607. SkPoint newPt = lastRing.bisector(minEdgeIdx);
  608. newPt.scale(minT);
  609. newPt += this->point(lastRing.index(minEdgeIdx));
  610. SkScalar depth = this->computeDepthFromEdge(lastRing.origEdgeID(minEdgeIdx), newPt);
  611. if (depth >= targetDepth) {
  612. // None of the bisectors intersect before reaching the desired depth.
  613. // Just step them all to the desired depth
  614. depth = targetDepth;
  615. done = true;
  616. }
  617. // 'dst' stores where each point in the last ring maps to/transforms into
  618. // in the next ring.
  619. SkTDArray<int> dst;
  620. dst.setCount(lastRing.numPts());
  621. // Create the first point (who compares with no one)
  622. if (!this->computePtAlongBisector(lastRing.index(0),
  623. lastRing.bisector(0),
  624. lastRing.origEdgeID(0),
  625. depth, &newPt)) {
  626. this->terminate(lastRing);
  627. return true;
  628. }
  629. dst[0] = fCandidateVerts.addNewPt(newPt,
  630. lastRing.index(0), lastRing.origEdgeID(0),
  631. !this->movable(lastRing.index(0)));
  632. // Handle the middle points (who only compare with the prior point)
  633. for (int cur = 1; cur < lastRing.numPts()-1; ++cur) {
  634. if (!this->computePtAlongBisector(lastRing.index(cur),
  635. lastRing.bisector(cur),
  636. lastRing.origEdgeID(cur),
  637. depth, &newPt)) {
  638. this->terminate(lastRing);
  639. return true;
  640. }
  641. if (!duplicate_pt(newPt, fCandidateVerts.lastPoint())) {
  642. dst[cur] = fCandidateVerts.addNewPt(newPt,
  643. lastRing.index(cur), lastRing.origEdgeID(cur),
  644. !this->movable(lastRing.index(cur)));
  645. } else {
  646. dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur));
  647. }
  648. }
  649. // Check on the last point (handling the wrap around)
  650. int cur = lastRing.numPts()-1;
  651. if (!this->computePtAlongBisector(lastRing.index(cur),
  652. lastRing.bisector(cur),
  653. lastRing.origEdgeID(cur),
  654. depth, &newPt)) {
  655. this->terminate(lastRing);
  656. return true;
  657. }
  658. bool dupPrev = duplicate_pt(newPt, fCandidateVerts.lastPoint());
  659. bool dupNext = duplicate_pt(newPt, fCandidateVerts.firstPoint());
  660. if (!dupPrev && !dupNext) {
  661. dst[cur] = fCandidateVerts.addNewPt(newPt,
  662. lastRing.index(cur), lastRing.origEdgeID(cur),
  663. !this->movable(lastRing.index(cur)));
  664. } else if (dupPrev && !dupNext) {
  665. dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur));
  666. } else if (!dupPrev && dupNext) {
  667. dst[cur] = fCandidateVerts.fuseWithNext();
  668. } else {
  669. bool dupPrevVsNext = duplicate_pt(fCandidateVerts.firstPoint(), fCandidateVerts.lastPoint());
  670. if (!dupPrevVsNext) {
  671. dst[cur] = fCandidateVerts.fuseWithPrior(lastRing.origEdgeID(cur));
  672. } else {
  673. const int fused = fCandidateVerts.fuseWithBoth();
  674. dst[cur] = fused;
  675. const int targetIdx = dst[cur - 1];
  676. for (int i = cur - 1; i >= 0 && dst[i] == targetIdx; i--) {
  677. dst[i] = fused;
  678. }
  679. }
  680. }
  681. // Fold the new ring's points into the global pool
  682. for (int i = 0; i < fCandidateVerts.numPts(); ++i) {
  683. int newIdx;
  684. if (fCandidateVerts.needsToBeNew(i) || forceNew) {
  685. // if the originating index is still valid then this point wasn't
  686. // fused (and is thus movable)
  687. SkScalar coverage = compute_coverage(depth, initialDepth, initialCoverage,
  688. targetDepth, targetCoverage);
  689. newIdx = this->addPt(fCandidateVerts.point(i), depth, coverage,
  690. fCandidateVerts.originatingIdx(i) != -1, kSharp_CurveState);
  691. } else {
  692. SkASSERT(fCandidateVerts.originatingIdx(i) != -1);
  693. this->updatePt(fCandidateVerts.originatingIdx(i), fCandidateVerts.point(i), depth,
  694. targetCoverage);
  695. newIdx = fCandidateVerts.originatingIdx(i);
  696. }
  697. nextRing->addIdx(newIdx, fCandidateVerts.origEdge(i));
  698. }
  699. // 'dst' currently has indices into the ring. Remap these to be indices
  700. // into the global pool since the triangulation operates in that space.
  701. for (int i = 0; i < dst.count(); ++i) {
  702. dst[i] = nextRing->index(dst[i]);
  703. }
  704. for (int i = 0; i < lastRing.numPts(); ++i) {
  705. int next = (i + 1) % lastRing.numPts();
  706. this->addTri(lastRing.index(i), lastRing.index(next), dst[next]);
  707. this->addTri(lastRing.index(i), dst[next], dst[i]);
  708. }
  709. if (done && fStyle != SkStrokeRec::kStroke_Style) {
  710. // fill or stroke-and-fill
  711. this->fanRing(*nextRing);
  712. }
  713. if (nextRing->numPts() < 3) {
  714. done = true;
  715. }
  716. return done;
  717. }
  718. void GrAAConvexTessellator::validate() const {
  719. SkASSERT(fPts.count() == fMovable.count());
  720. SkASSERT(fPts.count() == fCoverages.count());
  721. SkASSERT(fPts.count() == fCurveState.count());
  722. SkASSERT(0 == (fIndices.count() % 3));
  723. SkASSERT(!fBisectors.count() || fBisectors.count() == fNorms.count());
  724. }
  725. //////////////////////////////////////////////////////////////////////////////
  726. void GrAAConvexTessellator::Ring::init(const GrAAConvexTessellator& tess) {
  727. this->computeNormals(tess);
  728. this->computeBisectors(tess);
  729. }
  730. void GrAAConvexTessellator::Ring::init(const SkTDArray<SkVector>& norms,
  731. const SkTDArray<SkVector>& bisectors) {
  732. for (int i = 0; i < fPts.count(); ++i) {
  733. fPts[i].fNorm = norms[i];
  734. fPts[i].fBisector = bisectors[i];
  735. }
  736. }
  737. // Compute the outward facing normal at each vertex.
  738. void GrAAConvexTessellator::Ring::computeNormals(const GrAAConvexTessellator& tess) {
  739. for (int cur = 0; cur < fPts.count(); ++cur) {
  740. int next = (cur + 1) % fPts.count();
  741. fPts[cur].fNorm = tess.point(fPts[next].fIndex) - tess.point(fPts[cur].fIndex);
  742. SkPoint::Normalize(&fPts[cur].fNorm);
  743. fPts[cur].fNorm = SkPointPriv::MakeOrthog(fPts[cur].fNorm, tess.side());
  744. }
  745. }
  746. void GrAAConvexTessellator::Ring::computeBisectors(const GrAAConvexTessellator& tess) {
  747. int prev = fPts.count() - 1;
  748. for (int cur = 0; cur < fPts.count(); prev = cur, ++cur) {
  749. fPts[cur].fBisector = fPts[cur].fNorm + fPts[prev].fNorm;
  750. if (!fPts[cur].fBisector.normalize()) {
  751. fPts[cur].fBisector =
  752. SkPointPriv::MakeOrthog(fPts[cur].fNorm, (SkPointPriv::Side)-tess.side()) +
  753. SkPointPriv::MakeOrthog(fPts[prev].fNorm, tess.side());
  754. SkAssertResult(fPts[cur].fBisector.normalize());
  755. } else {
  756. fPts[cur].fBisector.negate(); // make the bisector face in
  757. }
  758. }
  759. }
  760. //////////////////////////////////////////////////////////////////////////////
  761. #ifdef SK_DEBUG
  762. // Is this ring convex?
  763. bool GrAAConvexTessellator::Ring::isConvex(const GrAAConvexTessellator& tess) const {
  764. if (fPts.count() < 3) {
  765. return true;
  766. }
  767. SkPoint prev = tess.point(fPts[0].fIndex) - tess.point(fPts.top().fIndex);
  768. SkPoint cur = tess.point(fPts[1].fIndex) - tess.point(fPts[0].fIndex);
  769. SkScalar minDot = prev.fX * cur.fY - prev.fY * cur.fX;
  770. SkScalar maxDot = minDot;
  771. prev = cur;
  772. for (int i = 1; i < fPts.count(); ++i) {
  773. int next = (i + 1) % fPts.count();
  774. cur = tess.point(fPts[next].fIndex) - tess.point(fPts[i].fIndex);
  775. SkScalar dot = prev.fX * cur.fY - prev.fY * cur.fX;
  776. minDot = SkMinScalar(minDot, dot);
  777. maxDot = SkMaxScalar(maxDot, dot);
  778. prev = cur;
  779. }
  780. if (SkScalarNearlyEqual(maxDot, 0.0f, 0.005f)) {
  781. maxDot = 0;
  782. }
  783. if (SkScalarNearlyEqual(minDot, 0.0f, 0.005f)) {
  784. minDot = 0;
  785. }
  786. return (maxDot >= 0.0f) == (minDot >= 0.0f);
  787. }
  788. #endif
  789. void GrAAConvexTessellator::lineTo(const SkPoint& p, CurveState curve) {
  790. if (this->numPts() > 0 && duplicate_pt(p, this->lastPoint())) {
  791. return;
  792. }
  793. if (this->numPts() >= 2 &&
  794. points_are_colinear_and_b_is_middle(fPts[fPts.count() - 2], fPts.top(), p)) {
  795. // The old last point is on the line from the second to last to the new point
  796. this->popLastPt();
  797. // double-check that the new last point is not a duplicate of the new point. In an ideal
  798. // world this wouldn't be necessary (since it's only possible for non-convex paths), but
  799. // floating point precision issues mean it can actually happen on paths that were
  800. // determined to be convex.
  801. if (duplicate_pt(p, this->lastPoint())) {
  802. return;
  803. }
  804. }
  805. SkScalar initialRingCoverage = (SkStrokeRec::kFill_Style == fStyle) ? 0.5f : 1.0f;
  806. this->addPt(p, 0.0f, initialRingCoverage, false, curve);
  807. }
  808. void GrAAConvexTessellator::lineTo(const SkMatrix& m, SkPoint p, CurveState curve) {
  809. m.mapPoints(&p, 1);
  810. this->lineTo(p, curve);
  811. }
  812. void GrAAConvexTessellator::quadTo(const SkPoint pts[3]) {
  813. int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
  814. fPointBuffer.setCount(maxCount);
  815. SkPoint* target = fPointBuffer.begin();
  816. int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
  817. kQuadTolerance, &target, maxCount);
  818. fPointBuffer.setCount(count);
  819. for (int i = 0; i < count - 1; i++) {
  820. this->lineTo(fPointBuffer[i], kCurve_CurveState);
  821. }
  822. this->lineTo(fPointBuffer[count - 1], kIndeterminate_CurveState);
  823. }
  824. void GrAAConvexTessellator::quadTo(const SkMatrix& m, SkPoint pts[3]) {
  825. m.mapPoints(pts, 3);
  826. this->quadTo(pts);
  827. }
  828. void GrAAConvexTessellator::cubicTo(const SkMatrix& m, SkPoint pts[4]) {
  829. m.mapPoints(pts, 4);
  830. int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
  831. fPointBuffer.setCount(maxCount);
  832. SkPoint* target = fPointBuffer.begin();
  833. int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
  834. kCubicTolerance, &target, maxCount);
  835. fPointBuffer.setCount(count);
  836. for (int i = 0; i < count - 1; i++) {
  837. this->lineTo(fPointBuffer[i], kCurve_CurveState);
  838. }
  839. this->lineTo(fPointBuffer[count - 1], kIndeterminate_CurveState);
  840. }
  841. // include down here to avoid compilation errors caused by "-" overload in SkGeometry.h
  842. #include "src/core/SkGeometry.h"
  843. void GrAAConvexTessellator::conicTo(const SkMatrix& m, SkPoint pts[3], SkScalar w) {
  844. m.mapPoints(pts, 3);
  845. SkAutoConicToQuads quadder;
  846. const SkPoint* quads = quadder.computeQuads(pts, w, kConicTolerance);
  847. SkPoint lastPoint = *(quads++);
  848. int count = quadder.countQuads();
  849. for (int i = 0; i < count; ++i) {
  850. SkPoint quadPts[3];
  851. quadPts[0] = lastPoint;
  852. quadPts[1] = quads[0];
  853. quadPts[2] = i == count - 1 ? pts[2] : quads[1];
  854. this->quadTo(quadPts);
  855. lastPoint = quadPts[2];
  856. quads += 2;
  857. }
  858. }
  859. //////////////////////////////////////////////////////////////////////////////
  860. #if GR_AA_CONVEX_TESSELLATOR_VIZ
  861. static const SkScalar kPointRadius = 0.02f;
  862. static const SkScalar kArrowStrokeWidth = 0.0f;
  863. static const SkScalar kArrowLength = 0.2f;
  864. static const SkScalar kEdgeTextSize = 0.1f;
  865. static const SkScalar kPointTextSize = 0.02f;
  866. static void draw_point(SkCanvas* canvas, const SkPoint& p, SkScalar paramValue, bool stroke) {
  867. SkPaint paint;
  868. SkASSERT(paramValue <= 1.0f);
  869. int gs = int(255*paramValue);
  870. paint.setARGB(255, gs, gs, gs);
  871. canvas->drawCircle(p.fX, p.fY, kPointRadius, paint);
  872. if (stroke) {
  873. SkPaint stroke;
  874. stroke.setColor(SK_ColorYELLOW);
  875. stroke.setStyle(SkPaint::kStroke_Style);
  876. stroke.setStrokeWidth(kPointRadius/3.0f);
  877. canvas->drawCircle(p.fX, p.fY, kPointRadius, stroke);
  878. }
  879. }
  880. static void draw_line(SkCanvas* canvas, const SkPoint& p0, const SkPoint& p1, SkColor color) {
  881. SkPaint p;
  882. p.setColor(color);
  883. canvas->drawLine(p0.fX, p0.fY, p1.fX, p1.fY, p);
  884. }
  885. static void draw_arrow(SkCanvas*canvas, const SkPoint& p, const SkPoint &n,
  886. SkScalar len, SkColor color) {
  887. SkPaint paint;
  888. paint.setColor(color);
  889. paint.setStrokeWidth(kArrowStrokeWidth);
  890. paint.setStyle(SkPaint::kStroke_Style);
  891. canvas->drawLine(p.fX, p.fY,
  892. p.fX + len * n.fX, p.fY + len * n.fY,
  893. paint);
  894. }
  895. void GrAAConvexTessellator::Ring::draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const {
  896. SkPaint paint;
  897. paint.setTextSize(kEdgeTextSize);
  898. for (int cur = 0; cur < fPts.count(); ++cur) {
  899. int next = (cur + 1) % fPts.count();
  900. draw_line(canvas,
  901. tess.point(fPts[cur].fIndex),
  902. tess.point(fPts[next].fIndex),
  903. SK_ColorGREEN);
  904. SkPoint mid = tess.point(fPts[cur].fIndex) + tess.point(fPts[next].fIndex);
  905. mid.scale(0.5f);
  906. if (fPts.count()) {
  907. draw_arrow(canvas, mid, fPts[cur].fNorm, kArrowLength, SK_ColorRED);
  908. mid.fX += (kArrowLength/2) * fPts[cur].fNorm.fX;
  909. mid.fY += (kArrowLength/2) * fPts[cur].fNorm.fY;
  910. }
  911. SkString num;
  912. num.printf("%d", this->origEdgeID(cur));
  913. canvas->drawString(num, mid.fX, mid.fY, paint);
  914. if (fPts.count()) {
  915. draw_arrow(canvas, tess.point(fPts[cur].fIndex), fPts[cur].fBisector,
  916. kArrowLength, SK_ColorBLUE);
  917. }
  918. }
  919. }
  920. void GrAAConvexTessellator::draw(SkCanvas* canvas) const {
  921. for (int i = 0; i < fIndices.count(); i += 3) {
  922. SkASSERT(fIndices[i] < this->numPts()) ;
  923. SkASSERT(fIndices[i+1] < this->numPts()) ;
  924. SkASSERT(fIndices[i+2] < this->numPts()) ;
  925. draw_line(canvas,
  926. this->point(this->fIndices[i]), this->point(this->fIndices[i+1]),
  927. SK_ColorBLACK);
  928. draw_line(canvas,
  929. this->point(this->fIndices[i+1]), this->point(this->fIndices[i+2]),
  930. SK_ColorBLACK);
  931. draw_line(canvas,
  932. this->point(this->fIndices[i+2]), this->point(this->fIndices[i]),
  933. SK_ColorBLACK);
  934. }
  935. fInitialRing.draw(canvas, *this);
  936. for (int i = 0; i < fRings.count(); ++i) {
  937. fRings[i]->draw(canvas, *this);
  938. }
  939. for (int i = 0; i < this->numPts(); ++i) {
  940. draw_point(canvas,
  941. this->point(i), 0.5f + (this->depth(i)/(2 * kAntialiasingRadius)),
  942. !this->movable(i));
  943. SkPaint paint;
  944. paint.setTextSize(kPointTextSize);
  945. if (this->depth(i) <= -kAntialiasingRadius) {
  946. paint.setColor(SK_ColorWHITE);
  947. }
  948. SkString num;
  949. num.printf("%d", i);
  950. canvas->drawString(num,
  951. this->point(i).fX, this->point(i).fY+(kPointRadius/2.0f),
  952. paint);
  953. }
  954. }
  955. #endif