1 /*
2 * Copyright 2012 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 "GrStrokePathRenderer.h"
9
10 #include "GrDrawTarget.h"
11 #include "SkPath.h"
12 #include "SkStrokeRec.h"
13
is_clockwise(const SkVector & before,const SkVector & after)14 static bool is_clockwise(const SkVector& before, const SkVector& after) {
15 return before.cross(after) > 0;
16 }
17
18 enum IntersectionType {
19 kNone_IntersectionType,
20 kIn_IntersectionType,
21 kOut_IntersectionType
22 };
23
intersection(const SkPoint & p1,const SkPoint & p2,const SkPoint & p3,const SkPoint & p4,SkPoint & res)24 static IntersectionType intersection(const SkPoint& p1, const SkPoint& p2,
25 const SkPoint& p3, const SkPoint& p4,
26 SkPoint& res) {
27 // Store the values for fast access and easy
28 // equations-to-code conversion
29 SkScalar x1 = p1.x(), x2 = p2.x(), x3 = p3.x(), x4 = p4.x();
30 SkScalar y1 = p1.y(), y2 = p2.y(), y3 = p3.y(), y4 = p4.y();
31
32 SkScalar d = SkScalarMul(x1 - x2, y3 - y4) - SkScalarMul(y1 - y2, x3 - x4);
33 // If d is zero, there is no intersection
34 if (SkScalarNearlyZero(d)) {
35 return kNone_IntersectionType;
36 }
37
38 // Get the x and y
39 SkScalar pre = SkScalarMul(x1, y2) - SkScalarMul(y1, x2),
40 post = SkScalarMul(x3, y4) - SkScalarMul(y3, x4);
41 // Compute the point of intersection
42 res.set((SkScalarMul(pre, x3 - x4) - SkScalarMul(x1 - x2, post) / d,
43 (SkScalarMul(pre, y3 - y4) - SkScalarMul(y1 - y2, post) / d);
44
45 // Check if the x and y coordinates are within both lines
46 return (res.x() < GrMin(x1, x2) || res.x() > GrMax(x1, x2) ||
47 res.x() < GrMin(x3, x4) || res.x() > GrMax(x3, x4) ||
48 res.y() < GrMin(y1, y2) || res.y() > GrMax(y1, y2) ||
49 res.y() < GrMin(y3, y4) || res.y() > GrMax(y3, y4)) ?
50 kOut_IntersectionType : kIn_IntersectionType;
51 }
52
53 GrStrokePathRenderer::GrStrokePathRenderer() {
54 }
55
56 bool GrStrokePathRenderer::canDrawPath(const SkPath& path,
57 const SkStrokeRec& stroke,
58 const GrDrawTarget* target,
59 bool antiAlias) const {
60 // FIXME : put the proper condition once GrDrawTarget::isOpaque is implemented
61 const bool isOpaque = true; // target->isOpaque();
62
63 // FIXME : remove this requirement once we have AA circles and implement the
64 // circle joins/caps appropriately in the ::onDrawPath() function.
65 const bool requiresAACircle = (stroke.getCap() == SkPaint::kRound_Cap) ||
66 (stroke.getJoin() == SkPaint::kRound_Join);
67
68 // Indices being stored in uint16, we don't want to overflow the indices capacity
69 static const int maxVBSize = 1 << 16;
70 const int maxNbVerts = (path.countPoints() + 1) * 5;
71
72 // Check that the path contains no curved lines, only straight lines
73 static const uint32_t unsupportedMask = SkPath::kQuad_SegmentMask | SkPath::kCubic_SegmentMask;
74
75 // Must not be filled nor hairline nor semi-transparent
76 // Note : May require a check to path.isConvex() if AA is supported
77 return ((stroke.getStyle() == SkStrokeRec::kStroke_Style) && (maxNbVerts < maxVBSize) &&
78 !path.isInverseFillType() && isOpaque && !requiresAACircle && !antiAlias &&
79 ((path.getSegmentMasks() & unsupportedMask) == 0));
80 }
81
82 bool GrStrokePathRenderer::onDrawPath(const SkPath& origPath,
83 const SkStrokeRec& stroke,
84 GrDrawTarget* target,
85 bool antiAlias) {
86 if (origPath.isEmpty()) {
87 return true;
88 }
89
90 SkScalar width = stroke.getWidth();
91 if (width <= 0) {
92 return false;
93 }
94
95 // Get the join type
96 SkPaint::Join join = stroke.getJoin();
97 SkScalar miterLimit = stroke.getMiter();
98 SkScalar sqMiterLimit = SkScalarMul(miterLimit, miterLimit);
99 if ((join == SkPaint::kMiter_Join) && (miterLimit <= SK_Scalar1)) {
100 // If the miter limit is small, treat it as a bevel join
101 join = SkPaint::kBevel_Join;
102 }
103 const bool isMiter = (join == SkPaint::kMiter_Join);
104 const bool isBevel = (join == SkPaint::kBevel_Join);
105 SkScalar invMiterLimit = isMiter ? SK_Scalar1 / miterLimit : 0;
106 SkScalar invMiterLimitSq = SkScalarMul(invMiterLimit, invMiterLimit);
107
108 // Allocate vertices
109 const int nbQuads = origPath.countPoints() + 1; // Could be "-1" if path is not closed
110 const int extraVerts = isMiter || isBevel ? 1 : 0;
111 const int maxVertexCount = nbQuads * (4 + extraVerts);
112 const int maxIndexCount = nbQuads * (6 + extraVerts * 3); // Each extra vert adds a triangle
113 target->drawState()->setDefaultVertexAttribs();
114 GrDrawTarget::AutoReleaseGeometry arg(target, maxVertexCount, maxIndexCount);
115 if (!arg.succeeded()) {
116 return false;
117 }
118 SkPoint* verts = reinterpret_cast<SkPoint*>(arg.vertices());
119 uint16_t* idxs = reinterpret_cast<uint16_t*>(arg.indices());
120 int vCount = 0, iCount = 0;
121
122 // Transform the path into a list of triangles
123 SkPath::Iter iter(origPath, false);
124 SkPoint pts[4];
125 const SkScalar radius = SkScalarMul(width, 0.5f);
126 SkPoint *firstPt = verts, *lastPt = NULL;
127 SkVector firstDir, dir;
128 firstDir.set(0, 0);
129 dir.set(0, 0);
130 bool isOpen = true;
131 for(SkPath::Verb v = iter.next(pts); v != SkPath::kDone_Verb; v = iter.next(pts)) {
132 switch(v) {
133 case SkPath::kMove_Verb:
134 // This will already be handled as pts[0] of the 1st line
135 break;
136 case SkPath::kClose_Verb:
137 isOpen = (lastPt == NULL);
138 break;
139 case SkPath::kLine_Verb:
140 {
141 SkVector v0 = dir;
142 dir = pts[1] - pts[0];
143 if (dir.setLength(radius)) {
144 SkVector dirT;
145 dirT.set(dir.fY, -dir.fX); // Get perpendicular direction
146 SkPoint l1a = pts[0]+dirT, l1b = pts[1]+dirT,
147 l2a = pts[0]-dirT, l2b = pts[1]-dirT;
148 SkPoint miterPt[2];
149 bool useMiterPoint = false;
150 int idx0(-1), idx1(-1);
151 if (NULL == lastPt) {
152 firstDir = dir;
153 } else {
154 SkVector v1 = dir;
155 if (v0.normalize() && v1.normalize()) {
156 SkScalar dotProd = v0.dot(v1);
157 // No need for bevel or miter join if the angle
158 // is either 0 or 180 degrees
159 if (!SkScalarNearlyZero(dotProd + SK_Scalar1) &&
160 !SkScalarNearlyZero(dotProd - SK_Scalar1)) {
161 bool ccw = !is_clockwise(v0, v1);
162 int offset = ccw ? 1 : 0;
163 idx0 = vCount-2+offset;
164 idx1 = vCount+offset;
165 const SkPoint* pt0 = &(lastPt[offset]);
166 const SkPoint* pt1 = ccw ? &l2a : &l1a;
167 switch(join) {
168 case SkPaint::kMiter_Join:
169 {
170 // *Note : Logic is from MiterJoiner
171
172 // FIXME : Special case if we have a right angle ?
173 // if (SkScalarNearlyZero(dotProd)) {...}
174
175 SkScalar sinHalfAngleSq =
176 SkScalarHalf(SK_Scalar1 + dotProd);
177 if (sinHalfAngleSq >= invMiterLimitSq) {
178 // Find the miter point (or points if it is further
179 // than the miter limit)
180 const SkPoint pt2 = *pt0+v0, pt3 = *pt1+v1;
181 if (intersection(*pt0, pt2, *pt1, pt3, miterPt[0]) !=
182 kNone_IntersectionType) {
183 SkPoint miterPt0 = miterPt[0] - *pt0;
184 SkPoint miterPt1 = miterPt[0] - *pt1;
185 SkScalar sqDist0 = miterPt0.dot(miterPt0);
186 SkScalar sqDist1 = miterPt1.dot(miterPt1);
187 const SkScalar rSq = radius*radius / sinHalfAngleSq;
188 const SkScalar sqRLimit =
189 SkScalarMul(sqMiterLimit, rSq);
190 if (sqDist0 > sqRLimit || sqDist1 > sqRLimit) {
191 if (sqDist1 > sqRLimit) {
192 v1.setLength(SkScalarSqrt(sqRLimit));
193 miterPt[1] = *pt1+v1;
194 } else {
195 miterPt[1] = miterPt[0];
196 }
197 if (sqDist0 > sqRLimit) {
198 v0.setLength(SkScalarSqrt(sqRLimit));
199 miterPt[0] = *pt0+v0;
200 }
201 } else {
202 miterPt[1] = miterPt[0];
203 }
204 useMiterPoint = true;
205 }
206 }
207 if (useMiterPoint && (miterPt[1] == miterPt[0])) {
208 break;
209 }
210 }
211 default:
212 case SkPaint::kBevel_Join:
213 {
214 // Note : This currently causes some overdraw where both
215 // lines initially intersect. We'd need to add
216 // another line intersection check here if the
217 // overdraw becomes an issue instead of using the
218 // current point directly.
219
220 // Add center point
221 *verts++ = pts[0]; // Use current point directly
222 // This idx is passed the current point so increment it
223 ++idx1;
224 // Add center triangle
225 *idxs++ = idx0;
226 *idxs++ = vCount;
227 *idxs++ = idx1;
228 vCount++;
229 iCount += 3;
230 }
231 break;
232 }
233 }
234 }
235 }
236 *verts++ = l1a;
237 *verts++ = l2a;
238 lastPt = verts;
239 *verts++ = l1b;
240 *verts++ = l2b;
241
242 if (useMiterPoint && (idx0 >= 0) && (idx1 >= 0)) {
243 firstPt[idx0] = miterPt[0];
244 firstPt[idx1] = miterPt[1];
245 }
246
247 // 1st triangle
248 *idxs++ = vCount+0;
249 *idxs++ = vCount+2;
250 *idxs++ = vCount+1;
251 // 2nd triangle
252 *idxs++ = vCount+1;
253 *idxs++ = vCount+2;
254 *idxs++ = vCount+3;
255
256 vCount += 4;
257 iCount += 6;
258 }
259 }
260 break;
261 case SkPath::kQuad_Verb:
262 case SkPath::kCubic_Verb:
263 SkDEBUGFAIL("Curves not supported!");
264 default:
265 // Unhandled cases
266 SkASSERT(false);
267 }
268 }
269
270 if (isOpen) {
271 // Add caps
272 switch (stroke.getCap()) {
273 case SkPaint::kSquare_Cap:
274 firstPt[0] -= firstDir;
275 firstPt[1] -= firstDir;
276 lastPt [0] += dir;
277 lastPt [1] += dir;
278 break;
279 case SkPaint::kRound_Cap:
280 SkDEBUGFAIL("Round caps not supported!");
281 default: // No cap
282 break;
283 }
284 }
285
286 SkASSERT(vCount <= maxVertexCount);
287 SkASSERT(iCount <= maxIndexCount);
288
289 if (vCount > 0) {
290 target->drawIndexed(kTriangles_GrPrimitiveType,
291 0, // start vertex
292 0, // start index
293 vCount,
294 iCount);
295 }
296
297 return true;
298 }
299