1 /*
2 * Copyright 2011 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
8 #include "GrAAHairLinePathRenderer.h"
9
10 #include "GrContext.h"
11 #include "GrDrawState.h"
12 #include "GrDrawTargetCaps.h"
13 #include "GrProcessor.h"
14 #include "GrGpu.h"
15 #include "GrIndexBuffer.h"
16 #include "GrPathUtils.h"
17 #include "GrTBackendProcessorFactory.h"
18 #include "SkGeometry.h"
19 #include "SkStroke.h"
20 #include "SkTemplates.h"
21
22 #include "effects/GrBezierEffect.h"
23
24 namespace {
25 // quadratics are rendered as 5-sided polys in order to bound the
26 // AA stroke around the center-curve. See comments in push_quad_index_buffer and
27 // bloat_quad. Quadratics and conics share an index buffer
28 static const int kVertsPerQuad = 5;
29 static const int kIdxsPerQuad = 9;
30
31 // lines are rendered as:
32 // *______________*
33 // |\ -_______ /|
34 // | \ \ / |
35 // | *--------* |
36 // | / ______/ \ |
37 // */_-__________\*
38 // For: 6 vertices and 18 indices (for 6 triangles)
39 static const int kVertsPerLineSeg = 6;
40 static const int kIdxsPerLineSeg = 18;
41
42 static const int kNumQuadsInIdxBuffer = 256;
43 static const size_t kQuadIdxSBufize = kIdxsPerQuad *
44 sizeof(uint16_t) *
45 kNumQuadsInIdxBuffer;
46
47 static const int kNumLineSegsInIdxBuffer = 256;
48 static const size_t kLineSegIdxSBufize = kIdxsPerLineSeg *
49 sizeof(uint16_t) *
50 kNumLineSegsInIdxBuffer;
51
push_quad_index_data(GrIndexBuffer * qIdxBuffer)52 static bool push_quad_index_data(GrIndexBuffer* qIdxBuffer) {
53 uint16_t* data = (uint16_t*) qIdxBuffer->map();
54 bool tempData = NULL == data;
55 if (tempData) {
56 data = SkNEW_ARRAY(uint16_t, kNumQuadsInIdxBuffer * kIdxsPerQuad);
57 }
58 for (int i = 0; i < kNumQuadsInIdxBuffer; ++i) {
59
60 // Each quadratic is rendered as a five sided polygon. This poly bounds
61 // the quadratic's bounding triangle but has been expanded so that the
62 // 1-pixel wide area around the curve is inside the poly.
63 // If a,b,c are the original control points then the poly a0,b0,c0,c1,a1
64 // that is rendered would look like this:
65 // b0
66 // b
67 //
68 // a0 c0
69 // a c
70 // a1 c1
71 // Each is drawn as three triangles specified by these 9 indices:
72 int baseIdx = i * kIdxsPerQuad;
73 uint16_t baseVert = (uint16_t)(i * kVertsPerQuad);
74 data[0 + baseIdx] = baseVert + 0; // a0
75 data[1 + baseIdx] = baseVert + 1; // a1
76 data[2 + baseIdx] = baseVert + 2; // b0
77 data[3 + baseIdx] = baseVert + 2; // b0
78 data[4 + baseIdx] = baseVert + 4; // c1
79 data[5 + baseIdx] = baseVert + 3; // c0
80 data[6 + baseIdx] = baseVert + 1; // a1
81 data[7 + baseIdx] = baseVert + 4; // c1
82 data[8 + baseIdx] = baseVert + 2; // b0
83 }
84 if (tempData) {
85 bool ret = qIdxBuffer->updateData(data, kQuadIdxSBufize);
86 delete[] data;
87 return ret;
88 } else {
89 qIdxBuffer->unmap();
90 return true;
91 }
92 }
93
push_line_index_data(GrIndexBuffer * lIdxBuffer)94 static bool push_line_index_data(GrIndexBuffer* lIdxBuffer) {
95 uint16_t* data = (uint16_t*) lIdxBuffer->map();
96 bool tempData = NULL == data;
97 if (tempData) {
98 data = SkNEW_ARRAY(uint16_t, kNumLineSegsInIdxBuffer * kIdxsPerLineSeg);
99 }
100 for (int i = 0; i < kNumLineSegsInIdxBuffer; ++i) {
101 // Each line segment is rendered as two quads and two triangles.
102 // p0 and p1 have alpha = 1 while all other points have alpha = 0.
103 // The four external points are offset 1 pixel perpendicular to the
104 // line and half a pixel parallel to the line.
105 //
106 // p4 p5
107 // p0 p1
108 // p2 p3
109 //
110 // Each is drawn as six triangles specified by these 18 indices:
111 int baseIdx = i * kIdxsPerLineSeg;
112 uint16_t baseVert = (uint16_t)(i * kVertsPerLineSeg);
113 data[0 + baseIdx] = baseVert + 0;
114 data[1 + baseIdx] = baseVert + 1;
115 data[2 + baseIdx] = baseVert + 3;
116
117 data[3 + baseIdx] = baseVert + 0;
118 data[4 + baseIdx] = baseVert + 3;
119 data[5 + baseIdx] = baseVert + 2;
120
121 data[6 + baseIdx] = baseVert + 0;
122 data[7 + baseIdx] = baseVert + 4;
123 data[8 + baseIdx] = baseVert + 5;
124
125 data[9 + baseIdx] = baseVert + 0;
126 data[10+ baseIdx] = baseVert + 5;
127 data[11+ baseIdx] = baseVert + 1;
128
129 data[12 + baseIdx] = baseVert + 0;
130 data[13 + baseIdx] = baseVert + 2;
131 data[14 + baseIdx] = baseVert + 4;
132
133 data[15 + baseIdx] = baseVert + 1;
134 data[16 + baseIdx] = baseVert + 5;
135 data[17 + baseIdx] = baseVert + 3;
136 }
137 if (tempData) {
138 bool ret = lIdxBuffer->updateData(data, kLineSegIdxSBufize);
139 delete[] data;
140 return ret;
141 } else {
142 lIdxBuffer->unmap();
143 return true;
144 }
145 }
146 }
147
Create(GrContext * context)148 GrPathRenderer* GrAAHairLinePathRenderer::Create(GrContext* context) {
149 GrGpu* gpu = context->getGpu();
150 GrIndexBuffer* qIdxBuf = gpu->createIndexBuffer(kQuadIdxSBufize, false);
151 SkAutoTUnref<GrIndexBuffer> qIdxBuffer(qIdxBuf);
152 if (NULL == qIdxBuf || !push_quad_index_data(qIdxBuf)) {
153 return NULL;
154 }
155 GrIndexBuffer* lIdxBuf = gpu->createIndexBuffer(kLineSegIdxSBufize, false);
156 SkAutoTUnref<GrIndexBuffer> lIdxBuffer(lIdxBuf);
157 if (NULL == lIdxBuf || !push_line_index_data(lIdxBuf)) {
158 return NULL;
159 }
160 return SkNEW_ARGS(GrAAHairLinePathRenderer,
161 (context, lIdxBuf, qIdxBuf));
162 }
163
GrAAHairLinePathRenderer(const GrContext * context,const GrIndexBuffer * linesIndexBuffer,const GrIndexBuffer * quadsIndexBuffer)164 GrAAHairLinePathRenderer::GrAAHairLinePathRenderer(
165 const GrContext* context,
166 const GrIndexBuffer* linesIndexBuffer,
167 const GrIndexBuffer* quadsIndexBuffer) {
168 fLinesIndexBuffer = linesIndexBuffer;
169 linesIndexBuffer->ref();
170 fQuadsIndexBuffer = quadsIndexBuffer;
171 quadsIndexBuffer->ref();
172 }
173
~GrAAHairLinePathRenderer()174 GrAAHairLinePathRenderer::~GrAAHairLinePathRenderer() {
175 fLinesIndexBuffer->unref();
176 fQuadsIndexBuffer->unref();
177 }
178
179 namespace {
180
181 #define PREALLOC_PTARRAY(N) SkSTArray<(N),SkPoint, true>
182
183 // Takes 178th time of logf on Z600 / VC2010
get_float_exp(float x)184 int get_float_exp(float x) {
185 GR_STATIC_ASSERT(sizeof(int) == sizeof(float));
186 #ifdef SK_DEBUG
187 static bool tested;
188 if (!tested) {
189 tested = true;
190 SkASSERT(get_float_exp(0.25f) == -2);
191 SkASSERT(get_float_exp(0.3f) == -2);
192 SkASSERT(get_float_exp(0.5f) == -1);
193 SkASSERT(get_float_exp(1.f) == 0);
194 SkASSERT(get_float_exp(2.f) == 1);
195 SkASSERT(get_float_exp(2.5f) == 1);
196 SkASSERT(get_float_exp(8.f) == 3);
197 SkASSERT(get_float_exp(100.f) == 6);
198 SkASSERT(get_float_exp(1000.f) == 9);
199 SkASSERT(get_float_exp(1024.f) == 10);
200 SkASSERT(get_float_exp(3000000.f) == 21);
201 }
202 #endif
203 const int* iptr = (const int*)&x;
204 return (((*iptr) & 0x7f800000) >> 23) - 127;
205 }
206
207 // Uses the max curvature function for quads to estimate
208 // where to chop the conic. If the max curvature is not
209 // found along the curve segment it will return 1 and
210 // dst[0] is the original conic. If it returns 2 the dst[0]
211 // and dst[1] are the two new conics.
split_conic(const SkPoint src[3],SkConic dst[2],const SkScalar weight)212 int split_conic(const SkPoint src[3], SkConic dst[2], const SkScalar weight) {
213 SkScalar t = SkFindQuadMaxCurvature(src);
214 if (t == 0) {
215 if (dst) {
216 dst[0].set(src, weight);
217 }
218 return 1;
219 } else {
220 if (dst) {
221 SkConic conic;
222 conic.set(src, weight);
223 conic.chopAt(t, dst);
224 }
225 return 2;
226 }
227 }
228
229 // Calls split_conic on the entire conic and then once more on each subsection.
230 // Most cases will result in either 1 conic (chop point is not within t range)
231 // or 3 points (split once and then one subsection is split again).
chop_conic(const SkPoint src[3],SkConic dst[4],const SkScalar weight)232 int chop_conic(const SkPoint src[3], SkConic dst[4], const SkScalar weight) {
233 SkConic dstTemp[2];
234 int conicCnt = split_conic(src, dstTemp, weight);
235 if (2 == conicCnt) {
236 int conicCnt2 = split_conic(dstTemp[0].fPts, dst, dstTemp[0].fW);
237 conicCnt = conicCnt2 + split_conic(dstTemp[1].fPts, &dst[conicCnt2], dstTemp[1].fW);
238 } else {
239 dst[0] = dstTemp[0];
240 }
241 return conicCnt;
242 }
243
244 // returns 0 if quad/conic is degen or close to it
245 // in this case approx the path with lines
246 // otherwise returns 1
is_degen_quad_or_conic(const SkPoint p[3])247 int is_degen_quad_or_conic(const SkPoint p[3]) {
248 static const SkScalar gDegenerateToLineTol = SK_Scalar1;
249 static const SkScalar gDegenerateToLineTolSqd =
250 SkScalarMul(gDegenerateToLineTol, gDegenerateToLineTol);
251
252 if (p[0].distanceToSqd(p[1]) < gDegenerateToLineTolSqd ||
253 p[1].distanceToSqd(p[2]) < gDegenerateToLineTolSqd) {
254 return 1;
255 }
256
257 SkScalar dsqd = p[1].distanceToLineBetweenSqd(p[0], p[2]);
258 if (dsqd < gDegenerateToLineTolSqd) {
259 return 1;
260 }
261
262 if (p[2].distanceToLineBetweenSqd(p[1], p[0]) < gDegenerateToLineTolSqd) {
263 return 1;
264 }
265 return 0;
266 }
267
268 // we subdivide the quads to avoid huge overfill
269 // if it returns -1 then should be drawn as lines
num_quad_subdivs(const SkPoint p[3])270 int num_quad_subdivs(const SkPoint p[3]) {
271 static const SkScalar gDegenerateToLineTol = SK_Scalar1;
272 static const SkScalar gDegenerateToLineTolSqd =
273 SkScalarMul(gDegenerateToLineTol, gDegenerateToLineTol);
274
275 if (p[0].distanceToSqd(p[1]) < gDegenerateToLineTolSqd ||
276 p[1].distanceToSqd(p[2]) < gDegenerateToLineTolSqd) {
277 return -1;
278 }
279
280 SkScalar dsqd = p[1].distanceToLineBetweenSqd(p[0], p[2]);
281 if (dsqd < gDegenerateToLineTolSqd) {
282 return -1;
283 }
284
285 if (p[2].distanceToLineBetweenSqd(p[1], p[0]) < gDegenerateToLineTolSqd) {
286 return -1;
287 }
288
289 // tolerance of triangle height in pixels
290 // tuned on windows Quadro FX 380 / Z600
291 // trade off of fill vs cpu time on verts
292 // maybe different when do this using gpu (geo or tess shaders)
293 static const SkScalar gSubdivTol = 175 * SK_Scalar1;
294
295 if (dsqd <= SkScalarMul(gSubdivTol, gSubdivTol)) {
296 return 0;
297 } else {
298 static const int kMaxSub = 4;
299 // subdividing the quad reduces d by 4. so we want x = log4(d/tol)
300 // = log4(d*d/tol*tol)/2
301 // = log2(d*d/tol*tol)
302
303 // +1 since we're ignoring the mantissa contribution.
304 int log = get_float_exp(dsqd/(gSubdivTol*gSubdivTol)) + 1;
305 log = SkTMin(SkTMax(0, log), kMaxSub);
306 return log;
307 }
308 }
309
310 /**
311 * Generates the lines and quads to be rendered. Lines are always recorded in
312 * device space. We will do a device space bloat to account for the 1pixel
313 * thickness.
314 * Quads are recorded in device space unless m contains
315 * perspective, then in they are in src space. We do this because we will
316 * subdivide large quads to reduce over-fill. This subdivision has to be
317 * performed before applying the perspective matrix.
318 */
generate_lines_and_quads(const SkPath & path,const SkMatrix & m,const SkIRect & devClipBounds,GrAAHairLinePathRenderer::PtArray * lines,GrAAHairLinePathRenderer::PtArray * quads,GrAAHairLinePathRenderer::PtArray * conics,GrAAHairLinePathRenderer::IntArray * quadSubdivCnts,GrAAHairLinePathRenderer::FloatArray * conicWeights)319 int generate_lines_and_quads(const SkPath& path,
320 const SkMatrix& m,
321 const SkIRect& devClipBounds,
322 GrAAHairLinePathRenderer::PtArray* lines,
323 GrAAHairLinePathRenderer::PtArray* quads,
324 GrAAHairLinePathRenderer::PtArray* conics,
325 GrAAHairLinePathRenderer::IntArray* quadSubdivCnts,
326 GrAAHairLinePathRenderer::FloatArray* conicWeights) {
327 SkPath::Iter iter(path, false);
328
329 int totalQuadCount = 0;
330 SkRect bounds;
331 SkIRect ibounds;
332
333 bool persp = m.hasPerspective();
334
335 for (;;) {
336 SkPoint pathPts[4];
337 SkPoint devPts[4];
338 SkPath::Verb verb = iter.next(pathPts);
339 switch (verb) {
340 case SkPath::kConic_Verb: {
341 SkConic dst[4];
342 // We chop the conics to create tighter clipping to hide error
343 // that appears near max curvature of very thin conics. Thin
344 // hyperbolas with high weight still show error.
345 int conicCnt = chop_conic(pathPts, dst, iter.conicWeight());
346 for (int i = 0; i < conicCnt; ++i) {
347 SkPoint* chopPnts = dst[i].fPts;
348 m.mapPoints(devPts, chopPnts, 3);
349 bounds.setBounds(devPts, 3);
350 bounds.outset(SK_Scalar1, SK_Scalar1);
351 bounds.roundOut(&ibounds);
352 if (SkIRect::Intersects(devClipBounds, ibounds)) {
353 if (is_degen_quad_or_conic(devPts)) {
354 SkPoint* pts = lines->push_back_n(4);
355 pts[0] = devPts[0];
356 pts[1] = devPts[1];
357 pts[2] = devPts[1];
358 pts[3] = devPts[2];
359 } else {
360 // when in perspective keep conics in src space
361 SkPoint* cPts = persp ? chopPnts : devPts;
362 SkPoint* pts = conics->push_back_n(3);
363 pts[0] = cPts[0];
364 pts[1] = cPts[1];
365 pts[2] = cPts[2];
366 conicWeights->push_back() = dst[i].fW;
367 }
368 }
369 }
370 break;
371 }
372 case SkPath::kMove_Verb:
373 break;
374 case SkPath::kLine_Verb:
375 m.mapPoints(devPts, pathPts, 2);
376 bounds.setBounds(devPts, 2);
377 bounds.outset(SK_Scalar1, SK_Scalar1);
378 bounds.roundOut(&ibounds);
379 if (SkIRect::Intersects(devClipBounds, ibounds)) {
380 SkPoint* pts = lines->push_back_n(2);
381 pts[0] = devPts[0];
382 pts[1] = devPts[1];
383 }
384 break;
385 case SkPath::kQuad_Verb: {
386 SkPoint choppedPts[5];
387 // Chopping the quad helps when the quad is either degenerate or nearly degenerate.
388 // When it is degenerate it allows the approximation with lines to work since the
389 // chop point (if there is one) will be at the parabola's vertex. In the nearly
390 // degenerate the QuadUVMatrix computed for the points is almost singular which
391 // can cause rendering artifacts.
392 int n = SkChopQuadAtMaxCurvature(pathPts, choppedPts);
393 for (int i = 0; i < n; ++i) {
394 SkPoint* quadPts = choppedPts + i * 2;
395 m.mapPoints(devPts, quadPts, 3);
396 bounds.setBounds(devPts, 3);
397 bounds.outset(SK_Scalar1, SK_Scalar1);
398 bounds.roundOut(&ibounds);
399
400 if (SkIRect::Intersects(devClipBounds, ibounds)) {
401 int subdiv = num_quad_subdivs(devPts);
402 SkASSERT(subdiv >= -1);
403 if (-1 == subdiv) {
404 SkPoint* pts = lines->push_back_n(4);
405 pts[0] = devPts[0];
406 pts[1] = devPts[1];
407 pts[2] = devPts[1];
408 pts[3] = devPts[2];
409 } else {
410 // when in perspective keep quads in src space
411 SkPoint* qPts = persp ? quadPts : devPts;
412 SkPoint* pts = quads->push_back_n(3);
413 pts[0] = qPts[0];
414 pts[1] = qPts[1];
415 pts[2] = qPts[2];
416 quadSubdivCnts->push_back() = subdiv;
417 totalQuadCount += 1 << subdiv;
418 }
419 }
420 }
421 break;
422 }
423 case SkPath::kCubic_Verb:
424 m.mapPoints(devPts, pathPts, 4);
425 bounds.setBounds(devPts, 4);
426 bounds.outset(SK_Scalar1, SK_Scalar1);
427 bounds.roundOut(&ibounds);
428 if (SkIRect::Intersects(devClipBounds, ibounds)) {
429 PREALLOC_PTARRAY(32) q;
430 // we don't need a direction if we aren't constraining the subdivision
431 static const SkPath::Direction kDummyDir = SkPath::kCCW_Direction;
432 // We convert cubics to quadratics (for now).
433 // In perspective have to do conversion in src space.
434 if (persp) {
435 SkScalar tolScale =
436 GrPathUtils::scaleToleranceToSrc(SK_Scalar1, m,
437 path.getBounds());
438 GrPathUtils::convertCubicToQuads(pathPts, tolScale, false, kDummyDir, &q);
439 } else {
440 GrPathUtils::convertCubicToQuads(devPts, SK_Scalar1, false, kDummyDir, &q);
441 }
442 for (int i = 0; i < q.count(); i += 3) {
443 SkPoint* qInDevSpace;
444 // bounds has to be calculated in device space, but q is
445 // in src space when there is perspective.
446 if (persp) {
447 m.mapPoints(devPts, &q[i], 3);
448 bounds.setBounds(devPts, 3);
449 qInDevSpace = devPts;
450 } else {
451 bounds.setBounds(&q[i], 3);
452 qInDevSpace = &q[i];
453 }
454 bounds.outset(SK_Scalar1, SK_Scalar1);
455 bounds.roundOut(&ibounds);
456 if (SkIRect::Intersects(devClipBounds, ibounds)) {
457 int subdiv = num_quad_subdivs(qInDevSpace);
458 SkASSERT(subdiv >= -1);
459 if (-1 == subdiv) {
460 SkPoint* pts = lines->push_back_n(4);
461 // lines should always be in device coords
462 pts[0] = qInDevSpace[0];
463 pts[1] = qInDevSpace[1];
464 pts[2] = qInDevSpace[1];
465 pts[3] = qInDevSpace[2];
466 } else {
467 SkPoint* pts = quads->push_back_n(3);
468 // q is already in src space when there is no
469 // perspective and dev coords otherwise.
470 pts[0] = q[0 + i];
471 pts[1] = q[1 + i];
472 pts[2] = q[2 + i];
473 quadSubdivCnts->push_back() = subdiv;
474 totalQuadCount += 1 << subdiv;
475 }
476 }
477 }
478 }
479 break;
480 case SkPath::kClose_Verb:
481 break;
482 case SkPath::kDone_Verb:
483 return totalQuadCount;
484 }
485 }
486 }
487
488 struct LineVertex {
489 SkPoint fPos;
490 GrColor fCoverage;
491 };
492
493 struct BezierVertex {
494 SkPoint fPos;
495 union {
496 struct {
497 SkScalar fK;
498 SkScalar fL;
499 SkScalar fM;
500 } fConic;
501 SkVector fQuadCoord;
502 struct {
503 SkScalar fBogus[4];
504 };
505 };
506 };
507
508 GR_STATIC_ASSERT(sizeof(BezierVertex) == 3 * sizeof(SkPoint));
509
intersect_lines(const SkPoint & ptA,const SkVector & normA,const SkPoint & ptB,const SkVector & normB,SkPoint * result)510 void intersect_lines(const SkPoint& ptA, const SkVector& normA,
511 const SkPoint& ptB, const SkVector& normB,
512 SkPoint* result) {
513
514 SkScalar lineAW = -normA.dot(ptA);
515 SkScalar lineBW = -normB.dot(ptB);
516
517 SkScalar wInv = SkScalarMul(normA.fX, normB.fY) -
518 SkScalarMul(normA.fY, normB.fX);
519 wInv = SkScalarInvert(wInv);
520
521 result->fX = SkScalarMul(normA.fY, lineBW) - SkScalarMul(lineAW, normB.fY);
522 result->fX = SkScalarMul(result->fX, wInv);
523
524 result->fY = SkScalarMul(lineAW, normB.fX) - SkScalarMul(normA.fX, lineBW);
525 result->fY = SkScalarMul(result->fY, wInv);
526 }
527
set_uv_quad(const SkPoint qpts[3],BezierVertex verts[kVertsPerQuad])528 void set_uv_quad(const SkPoint qpts[3], BezierVertex verts[kVertsPerQuad]) {
529 // this should be in the src space, not dev coords, when we have perspective
530 GrPathUtils::QuadUVMatrix DevToUV(qpts);
531 DevToUV.apply<kVertsPerQuad, sizeof(BezierVertex), sizeof(SkPoint)>(verts);
532 }
533
bloat_quad(const SkPoint qpts[3],const SkMatrix * toDevice,const SkMatrix * toSrc,BezierVertex verts[kVertsPerQuad],SkRect * devBounds)534 void bloat_quad(const SkPoint qpts[3], const SkMatrix* toDevice,
535 const SkMatrix* toSrc, BezierVertex verts[kVertsPerQuad],
536 SkRect* devBounds) {
537 SkASSERT(!toDevice == !toSrc);
538 // original quad is specified by tri a,b,c
539 SkPoint a = qpts[0];
540 SkPoint b = qpts[1];
541 SkPoint c = qpts[2];
542
543 if (toDevice) {
544 toDevice->mapPoints(&a, 1);
545 toDevice->mapPoints(&b, 1);
546 toDevice->mapPoints(&c, 1);
547 }
548 // make a new poly where we replace a and c by a 1-pixel wide edges orthog
549 // to edges ab and bc:
550 //
551 // before | after
552 // | b0
553 // b |
554 // |
555 // | a0 c0
556 // a c | a1 c1
557 //
558 // edges a0->b0 and b0->c0 are parallel to original edges a->b and b->c,
559 // respectively.
560 BezierVertex& a0 = verts[0];
561 BezierVertex& a1 = verts[1];
562 BezierVertex& b0 = verts[2];
563 BezierVertex& c0 = verts[3];
564 BezierVertex& c1 = verts[4];
565
566 SkVector ab = b;
567 ab -= a;
568 SkVector ac = c;
569 ac -= a;
570 SkVector cb = b;
571 cb -= c;
572
573 // We should have already handled degenerates
574 SkASSERT(ab.length() > 0 && cb.length() > 0);
575
576 ab.normalize();
577 SkVector abN;
578 abN.setOrthog(ab, SkVector::kLeft_Side);
579 if (abN.dot(ac) > 0) {
580 abN.negate();
581 }
582
583 cb.normalize();
584 SkVector cbN;
585 cbN.setOrthog(cb, SkVector::kLeft_Side);
586 if (cbN.dot(ac) < 0) {
587 cbN.negate();
588 }
589
590 a0.fPos = a;
591 a0.fPos += abN;
592 a1.fPos = a;
593 a1.fPos -= abN;
594
595 c0.fPos = c;
596 c0.fPos += cbN;
597 c1.fPos = c;
598 c1.fPos -= cbN;
599
600 intersect_lines(a0.fPos, abN, c0.fPos, cbN, &b0.fPos);
601 devBounds->growToInclude(&verts[0].fPos, sizeof(BezierVertex), kVertsPerQuad);
602
603 if (toSrc) {
604 toSrc->mapPointsWithStride(&verts[0].fPos, sizeof(BezierVertex), kVertsPerQuad);
605 }
606 }
607
608 // Equations based off of Loop-Blinn Quadratic GPU Rendering
609 // Input Parametric:
610 // P(t) = (P0*(1-t)^2 + 2*w*P1*t*(1-t) + P2*t^2) / (1-t)^2 + 2*w*t*(1-t) + t^2)
611 // Output Implicit:
612 // f(x, y, w) = f(P) = K^2 - LM
613 // K = dot(k, P), L = dot(l, P), M = dot(m, P)
614 // k, l, m are calculated in function GrPathUtils::getConicKLM
set_conic_coeffs(const SkPoint p[3],BezierVertex verts[kVertsPerQuad],const SkScalar weight)615 void set_conic_coeffs(const SkPoint p[3], BezierVertex verts[kVertsPerQuad],
616 const SkScalar weight) {
617 SkScalar klm[9];
618
619 GrPathUtils::getConicKLM(p, weight, klm);
620
621 for (int i = 0; i < kVertsPerQuad; ++i) {
622 const SkPoint pnt = verts[i].fPos;
623 verts[i].fConic.fK = pnt.fX * klm[0] + pnt.fY * klm[1] + klm[2];
624 verts[i].fConic.fL = pnt.fX * klm[3] + pnt.fY * klm[4] + klm[5];
625 verts[i].fConic.fM = pnt.fX * klm[6] + pnt.fY * klm[7] + klm[8];
626 }
627 }
628
add_conics(const SkPoint p[3],const SkScalar weight,const SkMatrix * toDevice,const SkMatrix * toSrc,BezierVertex ** vert,SkRect * devBounds)629 void add_conics(const SkPoint p[3],
630 const SkScalar weight,
631 const SkMatrix* toDevice,
632 const SkMatrix* toSrc,
633 BezierVertex** vert,
634 SkRect* devBounds) {
635 bloat_quad(p, toDevice, toSrc, *vert, devBounds);
636 set_conic_coeffs(p, *vert, weight);
637 *vert += kVertsPerQuad;
638 }
639
add_quads(const SkPoint p[3],int subdiv,const SkMatrix * toDevice,const SkMatrix * toSrc,BezierVertex ** vert,SkRect * devBounds)640 void add_quads(const SkPoint p[3],
641 int subdiv,
642 const SkMatrix* toDevice,
643 const SkMatrix* toSrc,
644 BezierVertex** vert,
645 SkRect* devBounds) {
646 SkASSERT(subdiv >= 0);
647 if (subdiv) {
648 SkPoint newP[5];
649 SkChopQuadAtHalf(p, newP);
650 add_quads(newP + 0, subdiv-1, toDevice, toSrc, vert, devBounds);
651 add_quads(newP + 2, subdiv-1, toDevice, toSrc, vert, devBounds);
652 } else {
653 bloat_quad(p, toDevice, toSrc, *vert, devBounds);
654 set_uv_quad(p, *vert);
655 *vert += kVertsPerQuad;
656 }
657 }
658
add_line(const SkPoint p[2],const SkMatrix * toSrc,GrColor coverage,LineVertex ** vert)659 void add_line(const SkPoint p[2],
660 const SkMatrix* toSrc,
661 GrColor coverage,
662 LineVertex** vert) {
663 const SkPoint& a = p[0];
664 const SkPoint& b = p[1];
665
666 SkVector ortho, vec = b;
667 vec -= a;
668
669 if (vec.setLength(SK_ScalarHalf)) {
670 // Create a vector orthogonal to 'vec' and of unit length
671 ortho.fX = 2.0f * vec.fY;
672 ortho.fY = -2.0f * vec.fX;
673
674 (*vert)[0].fPos = a;
675 (*vert)[0].fCoverage = coverage;
676 (*vert)[1].fPos = b;
677 (*vert)[1].fCoverage = coverage;
678 (*vert)[2].fPos = a - vec + ortho;
679 (*vert)[2].fCoverage = 0;
680 (*vert)[3].fPos = b + vec + ortho;
681 (*vert)[3].fCoverage = 0;
682 (*vert)[4].fPos = a - vec - ortho;
683 (*vert)[4].fCoverage = 0;
684 (*vert)[5].fPos = b + vec - ortho;
685 (*vert)[5].fCoverage = 0;
686
687 if (toSrc) {
688 toSrc->mapPointsWithStride(&(*vert)->fPos,
689 sizeof(LineVertex),
690 kVertsPerLineSeg);
691 }
692 } else {
693 // just make it degenerate and likely offscreen
694 for (int i = 0; i < kVertsPerLineSeg; ++i) {
695 (*vert)[i].fPos.set(SK_ScalarMax, SK_ScalarMax);
696 }
697 }
698
699 *vert += kVertsPerLineSeg;
700 }
701
702 }
703
704 ///////////////////////////////////////////////////////////////////////////////
705
706 namespace {
707
708 // position + edge
709 extern const GrVertexAttrib gHairlineBezierAttribs[] = {
710 {kVec2f_GrVertexAttribType, 0, kPosition_GrVertexAttribBinding},
711 {kVec4f_GrVertexAttribType, sizeof(SkPoint), kGeometryProcessor_GrVertexAttribBinding}
712 };
713
714 // position + coverage
715 extern const GrVertexAttrib gHairlineLineAttribs[] = {
716 {kVec2f_GrVertexAttribType, 0, kPosition_GrVertexAttribBinding},
717 {kVec4ub_GrVertexAttribType, sizeof(SkPoint), kCoverage_GrVertexAttribBinding},
718 };
719
720 };
721
createLineGeom(const SkPath & path,GrDrawTarget * target,const PtArray & lines,int lineCnt,GrDrawTarget::AutoReleaseGeometry * arg,SkRect * devBounds)722 bool GrAAHairLinePathRenderer::createLineGeom(const SkPath& path,
723 GrDrawTarget* target,
724 const PtArray& lines,
725 int lineCnt,
726 GrDrawTarget::AutoReleaseGeometry* arg,
727 SkRect* devBounds) {
728 GrDrawState* drawState = target->drawState();
729
730 const SkMatrix& viewM = drawState->getViewMatrix();
731
732 int vertCnt = kVertsPerLineSeg * lineCnt;
733
734 drawState->setVertexAttribs<gHairlineLineAttribs>(SK_ARRAY_COUNT(gHairlineLineAttribs),
735 sizeof(LineVertex));
736
737 if (!arg->set(target, vertCnt, 0)) {
738 return false;
739 }
740
741 LineVertex* verts = reinterpret_cast<LineVertex*>(arg->vertices());
742
743 const SkMatrix* toSrc = NULL;
744 SkMatrix ivm;
745
746 if (viewM.hasPerspective()) {
747 if (viewM.invert(&ivm)) {
748 toSrc = &ivm;
749 }
750 }
751 devBounds->set(lines.begin(), lines.count());
752 for (int i = 0; i < lineCnt; ++i) {
753 add_line(&lines[2*i], toSrc, drawState->getCoverageColor(), &verts);
754 }
755 // All the verts computed by add_line are within sqrt(1^2 + 0.5^2) of the end points.
756 static const SkScalar kSqrtOfOneAndAQuarter = 1.118f;
757 // Add a little extra to account for vector normalization precision.
758 static const SkScalar kOutset = kSqrtOfOneAndAQuarter + SK_Scalar1 / 20;
759 devBounds->outset(kOutset, kOutset);
760
761 return true;
762 }
763
createBezierGeom(const SkPath & path,GrDrawTarget * target,const PtArray & quads,int quadCnt,const PtArray & conics,int conicCnt,const IntArray & qSubdivs,const FloatArray & cWeights,GrDrawTarget::AutoReleaseGeometry * arg,SkRect * devBounds)764 bool GrAAHairLinePathRenderer::createBezierGeom(
765 const SkPath& path,
766 GrDrawTarget* target,
767 const PtArray& quads,
768 int quadCnt,
769 const PtArray& conics,
770 int conicCnt,
771 const IntArray& qSubdivs,
772 const FloatArray& cWeights,
773 GrDrawTarget::AutoReleaseGeometry* arg,
774 SkRect* devBounds) {
775 GrDrawState* drawState = target->drawState();
776
777 const SkMatrix& viewM = drawState->getViewMatrix();
778
779 int vertCnt = kVertsPerQuad * quadCnt + kVertsPerQuad * conicCnt;
780
781 int vAttribCnt = SK_ARRAY_COUNT(gHairlineBezierAttribs);
782 target->drawState()->setVertexAttribs<gHairlineBezierAttribs>(vAttribCnt, sizeof(BezierVertex));
783
784 if (!arg->set(target, vertCnt, 0)) {
785 return false;
786 }
787
788 BezierVertex* verts = reinterpret_cast<BezierVertex*>(arg->vertices());
789
790 const SkMatrix* toDevice = NULL;
791 const SkMatrix* toSrc = NULL;
792 SkMatrix ivm;
793
794 if (viewM.hasPerspective()) {
795 if (viewM.invert(&ivm)) {
796 toDevice = &viewM;
797 toSrc = &ivm;
798 }
799 }
800
801 // Seed the dev bounds with some pts known to be inside. Each quad and conic grows the bounding
802 // box to include its vertices.
803 SkPoint seedPts[2];
804 if (quadCnt) {
805 seedPts[0] = quads[0];
806 seedPts[1] = quads[2];
807 } else if (conicCnt) {
808 seedPts[0] = conics[0];
809 seedPts[1] = conics[2];
810 }
811 if (toDevice) {
812 toDevice->mapPoints(seedPts, 2);
813 }
814 devBounds->set(seedPts[0], seedPts[1]);
815
816 int unsubdivQuadCnt = quads.count() / 3;
817 for (int i = 0; i < unsubdivQuadCnt; ++i) {
818 SkASSERT(qSubdivs[i] >= 0);
819 add_quads(&quads[3*i], qSubdivs[i], toDevice, toSrc, &verts, devBounds);
820 }
821
822 // Start Conics
823 for (int i = 0; i < conicCnt; ++i) {
824 add_conics(&conics[3*i], cWeights[i], toDevice, toSrc, &verts, devBounds);
825 }
826 return true;
827 }
828
canDrawPath(const SkPath & path,const SkStrokeRec & stroke,const GrDrawTarget * target,bool antiAlias) const829 bool GrAAHairLinePathRenderer::canDrawPath(const SkPath& path,
830 const SkStrokeRec& stroke,
831 const GrDrawTarget* target,
832 bool antiAlias) const {
833 if (!antiAlias) {
834 return false;
835 }
836
837 if (!IsStrokeHairlineOrEquivalent(stroke,
838 target->getDrawState().getViewMatrix(),
839 NULL)) {
840 return false;
841 }
842
843 if (SkPath::kLine_SegmentMask == path.getSegmentMasks() ||
844 target->caps()->shaderDerivativeSupport()) {
845 return true;
846 }
847 return false;
848 }
849
850 template <class VertexType>
check_bounds(GrDrawState * drawState,const SkRect & devBounds,void * vertices,int vCount)851 bool check_bounds(GrDrawState* drawState, const SkRect& devBounds, void* vertices, int vCount)
852 {
853 SkRect tolDevBounds = devBounds;
854 // The bounds ought to be tight, but in perspective the below code runs the verts
855 // through the view matrix to get back to dev coords, which can introduce imprecision.
856 if (drawState->getViewMatrix().hasPerspective()) {
857 tolDevBounds.outset(SK_Scalar1 / 1000, SK_Scalar1 / 1000);
858 } else {
859 // Non-persp matrices cause this path renderer to draw in device space.
860 SkASSERT(drawState->getViewMatrix().isIdentity());
861 }
862 SkRect actualBounds;
863
864 VertexType* verts = reinterpret_cast<VertexType*>(vertices);
865 bool first = true;
866 for (int i = 0; i < vCount; ++i) {
867 SkPoint pos = verts[i].fPos;
868 // This is a hack to workaround the fact that we move some degenerate segments offscreen.
869 if (SK_ScalarMax == pos.fX) {
870 continue;
871 }
872 drawState->getViewMatrix().mapPoints(&pos, 1);
873 if (first) {
874 actualBounds.set(pos.fX, pos.fY, pos.fX, pos.fY);
875 first = false;
876 } else {
877 actualBounds.growToInclude(pos.fX, pos.fY);
878 }
879 }
880 if (!first) {
881 return tolDevBounds.contains(actualBounds);
882 }
883
884 return true;
885 }
886
onDrawPath(const SkPath & path,const SkStrokeRec & stroke,GrDrawTarget * target,bool antiAlias)887 bool GrAAHairLinePathRenderer::onDrawPath(const SkPath& path,
888 const SkStrokeRec& stroke,
889 GrDrawTarget* target,
890 bool antiAlias) {
891 GrDrawState* drawState = target->drawState();
892
893 SkScalar hairlineCoverage;
894 if (IsStrokeHairlineOrEquivalent(stroke,
895 target->getDrawState().getViewMatrix(),
896 &hairlineCoverage)) {
897 uint8_t newCoverage = SkScalarRoundToInt(hairlineCoverage *
898 target->getDrawState().getCoverage());
899 target->drawState()->setCoverage(newCoverage);
900 }
901
902 SkIRect devClipBounds;
903 target->getClip()->getConservativeBounds(drawState->getRenderTarget(), &devClipBounds);
904
905 int lineCnt;
906 int quadCnt;
907 int conicCnt;
908 PREALLOC_PTARRAY(128) lines;
909 PREALLOC_PTARRAY(128) quads;
910 PREALLOC_PTARRAY(128) conics;
911 IntArray qSubdivs;
912 FloatArray cWeights;
913 quadCnt = generate_lines_and_quads(path, drawState->getViewMatrix(), devClipBounds,
914 &lines, &quads, &conics, &qSubdivs, &cWeights);
915 lineCnt = lines.count() / 2;
916 conicCnt = conics.count() / 3;
917
918 // do lines first
919 if (lineCnt) {
920 GrDrawTarget::AutoReleaseGeometry arg;
921 SkRect devBounds;
922
923 if (!this->createLineGeom(path,
924 target,
925 lines,
926 lineCnt,
927 &arg,
928 &devBounds)) {
929 return false;
930 }
931
932 GrDrawTarget::AutoStateRestore asr;
933
934 // createLineGeom transforms the geometry to device space when the matrix does not have
935 // perspective.
936 if (target->getDrawState().getViewMatrix().hasPerspective()) {
937 asr.set(target, GrDrawTarget::kPreserve_ASRInit);
938 } else if (!asr.setIdentity(target, GrDrawTarget::kPreserve_ASRInit)) {
939 return false;
940 }
941 GrDrawState* drawState = target->drawState();
942
943 // Check devBounds
944 SkASSERT(check_bounds<LineVertex>(drawState, devBounds, arg.vertices(),
945 kVertsPerLineSeg * lineCnt));
946
947 {
948 GrDrawState::AutoRestoreEffects are(drawState);
949 target->setIndexSourceToBuffer(fLinesIndexBuffer);
950 int lines = 0;
951 while (lines < lineCnt) {
952 int n = SkTMin(lineCnt - lines, kNumLineSegsInIdxBuffer);
953 target->drawIndexed(kTriangles_GrPrimitiveType,
954 kVertsPerLineSeg*lines, // startV
955 0, // startI
956 kVertsPerLineSeg*n, // vCount
957 kIdxsPerLineSeg*n, // iCount
958 &devBounds);
959 lines += n;
960 }
961 }
962 }
963
964 // then quadratics/conics
965 if (quadCnt || conicCnt) {
966 GrDrawTarget::AutoReleaseGeometry arg;
967 SkRect devBounds;
968
969 if (!this->createBezierGeom(path,
970 target,
971 quads,
972 quadCnt,
973 conics,
974 conicCnt,
975 qSubdivs,
976 cWeights,
977 &arg,
978 &devBounds)) {
979 return false;
980 }
981
982 GrDrawTarget::AutoStateRestore asr;
983
984 // createGeom transforms the geometry to device space when the matrix does not have
985 // perspective.
986 if (target->getDrawState().getViewMatrix().hasPerspective()) {
987 asr.set(target, GrDrawTarget::kPreserve_ASRInit);
988 } else if (!asr.setIdentity(target, GrDrawTarget::kPreserve_ASRInit)) {
989 return false;
990 }
991 GrDrawState* drawState = target->drawState();
992
993 // Check devBounds
994 SkASSERT(check_bounds<BezierVertex>(drawState, devBounds, arg.vertices(),
995 kVertsPerQuad * quadCnt + kVertsPerQuad * conicCnt));
996
997 if (quadCnt > 0) {
998 GrGeometryProcessor* hairQuadProcessor =
999 GrQuadEffect::Create(kHairlineAA_GrProcessorEdgeType, *target->caps());
1000 SkASSERT(hairQuadProcessor);
1001 GrDrawState::AutoRestoreEffects are(drawState);
1002 target->setIndexSourceToBuffer(fQuadsIndexBuffer);
1003 drawState->setGeometryProcessor(hairQuadProcessor)->unref();
1004 int quads = 0;
1005 while (quads < quadCnt) {
1006 int n = SkTMin(quadCnt - quads, kNumQuadsInIdxBuffer);
1007 target->drawIndexed(kTriangles_GrPrimitiveType,
1008 kVertsPerQuad*quads, // startV
1009 0, // startI
1010 kVertsPerQuad*n, // vCount
1011 kIdxsPerQuad*n, // iCount
1012 &devBounds);
1013 quads += n;
1014 }
1015 }
1016
1017 if (conicCnt > 0) {
1018 GrDrawState::AutoRestoreEffects are(drawState);
1019 GrGeometryProcessor* hairConicProcessor = GrConicEffect::Create(
1020 kHairlineAA_GrProcessorEdgeType, *target->caps());
1021 SkASSERT(hairConicProcessor);
1022 drawState->setGeometryProcessor(hairConicProcessor)->unref();
1023 int conics = 0;
1024 while (conics < conicCnt) {
1025 int n = SkTMin(conicCnt - conics, kNumQuadsInIdxBuffer);
1026 target->drawIndexed(kTriangles_GrPrimitiveType,
1027 kVertsPerQuad*(quadCnt + conics), // startV
1028 0, // startI
1029 kVertsPerQuad*n, // vCount
1030 kIdxsPerQuad*n, // iCount
1031 &devBounds);
1032 conics += n;
1033 }
1034 }
1035 }
1036
1037 target->resetIndexSource();
1038
1039 return true;
1040 }
1041