OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "GrTessellator.h" | 8 #include "GrTessellator.h" |
9 | 9 |
10 #include "GrDefaultGeoProcFactory.h" | 10 #include "GrDefaultGeoProcFactory.h" |
(...skipping 242 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
253 } | 253 } |
254 }; | 254 }; |
255 | 255 |
256 // Round to nearest quarter-pixel. This is used for screenspace tessellation. | 256 // Round to nearest quarter-pixel. This is used for screenspace tessellation. |
257 | 257 |
258 inline void round(SkPoint* p) { | 258 inline void round(SkPoint* p) { |
259 p->fX = SkScalarRoundToScalar(p->fX * SkFloatToScalar(4.0f)) * SkFloatToScal
ar(0.25f); | 259 p->fX = SkScalarRoundToScalar(p->fX * SkFloatToScalar(4.0f)) * SkFloatToScal
ar(0.25f); |
260 p->fY = SkScalarRoundToScalar(p->fY * SkFloatToScalar(4.0f)) * SkFloatToScal
ar(0.25f); | 260 p->fY = SkScalarRoundToScalar(p->fY * SkFloatToScalar(4.0f)) * SkFloatToScal
ar(0.25f); |
261 } | 261 } |
262 | 262 |
| 263 // A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x
, y) on the line. |
| 264 struct Line { |
| 265 Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {} |
| 266 Line(const SkPoint& p, const SkPoint& q) |
| 267 : fA(static_cast<double>(q.fY) - p.fY) // a = dY |
| 268 , fB(static_cast<double>(p.fX) - q.fX) // b = -dX |
| 269 , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p) |
| 270 static_cast<double>(p.fX) * q.fY) {} |
| 271 double dist(const SkPoint& p) const { |
| 272 return fA * p.fX + fB * p.fY + fC; |
| 273 } |
| 274 double magSq() const { |
| 275 return fA * fA + fB * fB; |
| 276 } |
| 277 |
| 278 // Compute the intersection of two (infinite) Lines. |
| 279 bool intersect(const Line& other, SkPoint* point) { |
| 280 double denom = fA * other.fB - fB * other.fA; |
| 281 if (denom == 0.0) { |
| 282 return false; |
| 283 } |
| 284 double scale = 1.0f / denom; |
| 285 point->fX = SkDoubleToScalar((fB * other.fC - other.fB * fC) * scale); |
| 286 point->fY = SkDoubleToScalar((other.fA * fC - fA * other.fC) * scale); |
| 287 round(point); |
| 288 return true; |
| 289 } |
| 290 double fA, fB, fC; |
| 291 }; |
| 292 |
263 /** | 293 /** |
264 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of
"edges above" and | 294 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of
"edges above" and |
265 * "edge below" a vertex as well as for the active edge list is handled by isLef
tOf()/isRightOf(). | 295 * "edge below" a vertex as well as for the active edge list is handled by isLef
tOf()/isRightOf(). |
266 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b
ecause floating | 296 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b
ecause floating |
267 * point). For speed, that case is only tested by the callers which require it (
e.g., | 297 * point). For speed, that case is only tested by the callers which require it (
e.g., |
268 * cleanup_active_edges()). Edges also handle checking for intersection with oth
er edges. | 298 * cleanup_active_edges()). Edges also handle checking for intersection with oth
er edges. |
269 * Currently, this converts the edges to the parametric form, in order to avoid
doing a division | 299 * Currently, this converts the edges to the parametric form, in order to avoid
doing a division |
270 * until an intersection has been confirmed. This is slightly slower in the "fou
nd" case, but | 300 * until an intersection has been confirmed. This is slightly slower in the "fou
nd" case, but |
271 * a lot faster in the "not found" case. | 301 * a lot faster in the "not found" case. |
272 * | 302 * |
(...skipping 16 matching lines...) Expand all Loading... |
289 , fNextEdgeAbove(nullptr) | 319 , fNextEdgeAbove(nullptr) |
290 , fPrevEdgeBelow(nullptr) | 320 , fPrevEdgeBelow(nullptr) |
291 , fNextEdgeBelow(nullptr) | 321 , fNextEdgeBelow(nullptr) |
292 , fLeftPoly(nullptr) | 322 , fLeftPoly(nullptr) |
293 , fRightPoly(nullptr) | 323 , fRightPoly(nullptr) |
294 , fLeftPolyPrev(nullptr) | 324 , fLeftPolyPrev(nullptr) |
295 , fLeftPolyNext(nullptr) | 325 , fLeftPolyNext(nullptr) |
296 , fRightPolyPrev(nullptr) | 326 , fRightPolyPrev(nullptr) |
297 , fRightPolyNext(nullptr) | 327 , fRightPolyNext(nullptr) |
298 , fUsedInLeftPoly(false) | 328 , fUsedInLeftPoly(false) |
299 , fUsedInRightPoly(false) { | 329 , fUsedInRightPoly(false) |
300 recompute(); | 330 , fLine(top, bottom) { |
301 } | 331 } |
302 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar
d. | 332 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar
d. |
303 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt
). | 333 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt
). |
304 Vertex* fBottom; // The bottom vertex in vertex-sort-order. | 334 Vertex* fBottom; // The bottom vertex in vertex-sort-order. |
305 Edge* fLeft; // The linked list of edges in the active edge l
ist. | 335 Edge* fLeft; // The linked list of edges in the active edge l
ist. |
306 Edge* fRight; // " | 336 Edge* fRight; // " |
307 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex
's "edges above". | 337 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex
's "edges above". |
308 Edge* fNextEdgeAbove; // " | 338 Edge* fNextEdgeAbove; // " |
309 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's
"edges below". | 339 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's
"edges below". |
310 Edge* fNextEdgeBelow; // " | 340 Edge* fNextEdgeBelow; // " |
311 Poly* fLeftPoly; // The Poly to the left of this edge, if any. | 341 Poly* fLeftPoly; // The Poly to the left of this edge, if any. |
312 Poly* fRightPoly; // The Poly to the right of this edge, if any. | 342 Poly* fRightPoly; // The Poly to the right of this edge, if any. |
313 Edge* fLeftPolyPrev; | 343 Edge* fLeftPolyPrev; |
314 Edge* fLeftPolyNext; | 344 Edge* fLeftPolyNext; |
315 Edge* fRightPolyPrev; | 345 Edge* fRightPolyPrev; |
316 Edge* fRightPolyNext; | 346 Edge* fRightPolyNext; |
317 bool fUsedInLeftPoly; | 347 bool fUsedInLeftPoly; |
318 bool fUsedInRightPoly; | 348 bool fUsedInRightPoly; |
319 double fDX; // The line equation for this edge, in implicit
form. | 349 Line fLine; |
320 double fDY; // fDY * x + fDX * y + fC = 0, for point (x, y)
on the line. | |
321 double fC; | |
322 double dist(const SkPoint& p) const { | 350 double dist(const SkPoint& p) const { |
323 return fDY * p.fX - fDX * p.fY + fC; | 351 return fLine.dist(p); |
324 } | 352 } |
325 bool isRightOf(Vertex* v) const { | 353 bool isRightOf(Vertex* v) const { |
326 return dist(v->fPoint) < 0.0; | 354 return fLine.dist(v->fPoint) < 0.0; |
327 } | 355 } |
328 bool isLeftOf(Vertex* v) const { | 356 bool isLeftOf(Vertex* v) const { |
329 return dist(v->fPoint) > 0.0; | 357 return fLine.dist(v->fPoint) > 0.0; |
330 } | 358 } |
331 void recompute() { | 359 void recompute() { |
332 fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX; | 360 fLine = Line(fTop, fBottom); |
333 fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY; | |
334 fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX - | |
335 static_cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY; | |
336 } | 361 } |
337 bool intersect(const Edge& other, SkPoint* p) { | 362 bool intersect(const Edge& other, SkPoint* p) { |
338 LOG("intersecting %g -> %g with %g -> %g\n", | 363 LOG("intersecting %g -> %g with %g -> %g\n", |
339 fTop->fID, fBottom->fID, | 364 fTop->fID, fBottom->fID, |
340 other.fTop->fID, other.fBottom->fID); | 365 other.fTop->fID, other.fBottom->fID); |
341 if (fTop == other.fTop || fBottom == other.fBottom) { | 366 if (fTop == other.fTop || fBottom == other.fBottom) { |
342 return false; | 367 return false; |
343 } | 368 } |
344 double denom = fDX * other.fDY - fDY * other.fDX; | 369 double denom = fLine.fA * other.fLine.fB - fLine.fB * other.fLine.fA; |
345 if (denom == 0.0) { | 370 if (denom == 0.0) { |
346 return false; | 371 return false; |
347 } | 372 } |
348 double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX
; | 373 double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX
; |
349 double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY
; | 374 double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY
; |
350 double sNumer = dy * other.fDX - dx * other.fDY; | 375 double sNumer = -dy * other.fLine.fB - dx * other.fLine.fA; |
351 double tNumer = dy * fDX - dx * fDY; | 376 double tNumer = -dy * fLine.fB - dx * fLine.fA; |
352 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early. | 377 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early. |
353 // This saves us doing the divide below unless absolutely necessary. | 378 // This saves us doing the divide below unless absolutely necessary. |
354 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNu
mer > denom) | 379 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNu
mer > denom) |
355 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNu
mer < denom)) { | 380 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNu
mer < denom)) { |
356 return false; | 381 return false; |
357 } | 382 } |
358 double s = sNumer / denom; | 383 double s = sNumer / denom; |
359 SkASSERT(s >= 0.0 && s <= 1.0); | 384 SkASSERT(s >= 0.0 && s <= 1.0); |
360 p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX); | 385 p->fX = SkDoubleToScalar(fTop->fPoint.fX - s * fLine.fB); |
361 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY); | 386 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fLine.fA); |
362 return true; | 387 return true; |
363 } | 388 } |
364 }; | 389 }; |
365 | 390 |
366 struct EdgeList { | 391 struct EdgeList { |
367 EdgeList() : fHead(nullptr), fTail(nullptr), fNext(nullptr), fCount(0) {} | 392 EdgeList() : fHead(nullptr), fTail(nullptr), fNext(nullptr), fCount(0) {} |
368 Edge* fHead; | 393 Edge* fHead; |
369 Edge* fTail; | 394 Edge* fTail; |
370 EdgeList* fNext; | 395 EdgeList* fNext; |
371 int fCount; | 396 int fCount; |
(...skipping 1044 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1416 if (!is_boundary_edge(e, fillType)) { | 1441 if (!is_boundary_edge(e, fillType)) { |
1417 remove_edge_above(e); | 1442 remove_edge_above(e); |
1418 remove_edge_below(e); | 1443 remove_edge_below(e); |
1419 } | 1444 } |
1420 e = next; | 1445 e = next; |
1421 } | 1446 } |
1422 } | 1447 } |
1423 return vertices; | 1448 return vertices; |
1424 } | 1449 } |
1425 | 1450 |
1426 // This is different from Edge::intersect, in that it intersects lines, not line
segments. | |
1427 bool intersect(const Edge& a, const Edge& b, SkPoint* point) { | |
1428 double denom = a.fDX * b.fDY - a.fDY * b.fDX; | |
1429 if (denom == 0.0) { | |
1430 return false; | |
1431 } | |
1432 double scale = 1.0f / denom; | |
1433 point->fX = SkDoubleToScalar((b.fDX * a.fC - a.fDX * b.fC) * scale); | |
1434 point->fY = SkDoubleToScalar((b.fDY * a.fC - a.fDY * b.fC) * scale); | |
1435 round(point); | |
1436 return true; | |
1437 } | |
1438 | |
1439 void get_edge_normal(const Edge* e, SkVector* normal) { | 1451 void get_edge_normal(const Edge* e, SkVector* normal) { |
1440 normal->setNormalize(SkDoubleToScalar(e->fDX) * e->fWinding, | 1452 normal->setNormalize(SkDoubleToScalar(-e->fLine.fB) * e->fWinding, |
1441 SkDoubleToScalar(e->fDY) * e->fWinding); | 1453 SkDoubleToScalar(e->fLine.fA) * e->fWinding); |
1442 } | 1454 } |
1443 | 1455 |
1444 // Stage 5c: detect and remove "pointy" vertices whose edge normals point in opp
osite directions | 1456 // Stage 5c: detect and remove "pointy" vertices whose edge normals point in opp
osite directions |
1445 // and whose adjacent vertices are less than a quarter pixel from an edge. These
are guaranteed to | 1457 // and whose adjacent vertices are less than a quarter pixel from an edge. These
are guaranteed to |
1446 // invert on stroking. | 1458 // invert on stroking. |
1447 | 1459 |
1448 void simplify_boundary(EdgeList* boundary, Comparator& c, SkChunkAlloc& alloc) { | 1460 void simplify_boundary(EdgeList* boundary, Comparator& c, SkChunkAlloc& alloc) { |
1449 Edge* prevEdge = boundary->fTail; | 1461 Edge* prevEdge = boundary->fTail; |
1450 SkVector prevNormal; | 1462 SkVector prevNormal; |
1451 get_edge_normal(prevEdge, &prevNormal); | 1463 get_edge_normal(prevEdge, &prevNormal); |
1452 for (Edge* e = boundary->fHead; e != nullptr;) { | 1464 for (Edge* e = boundary->fHead; e != nullptr;) { |
1453 Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBot
tom; | 1465 Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBot
tom; |
1454 Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop; | 1466 Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop; |
1455 double dist = e->dist(prev->fPoint); | 1467 double dist = e->dist(prev->fPoint); |
1456 SkVector normal; | 1468 SkVector normal; |
1457 get_edge_normal(e, &normal); | 1469 get_edge_normal(e, &normal); |
1458 float denom = 0.25f * static_cast<float>(e->fDX * e->fDX + e->fDY * e->f
DY); | 1470 float denom = 0.25f * static_cast<float>(e->fLine.magSq()); |
1459 if (prevNormal.dot(normal) < 0.0 && (dist * dist) <= denom) { | 1471 if (prevNormal.dot(normal) < 0.0 && (dist * dist) <= denom) { |
1460 Edge* join = new_edge(prev, next, alloc, c); | 1472 Edge* join = new_edge(prev, next, alloc, c); |
1461 insert_edge(join, e, boundary); | 1473 insert_edge(join, e, boundary); |
1462 remove_edge(prevEdge, boundary); | 1474 remove_edge(prevEdge, boundary); |
1463 remove_edge(e, boundary); | 1475 remove_edge(e, boundary); |
1464 if (join->fLeft && join->fRight) { | 1476 if (join->fLeft && join->fRight) { |
1465 prevEdge = join->fLeft; | 1477 prevEdge = join->fLeft; |
1466 e = join; | 1478 e = join; |
1467 } else { | 1479 } else { |
1468 prevEdge = boundary->fTail; | 1480 prevEdge = boundary->fTail; |
1469 e = boundary->fHead; // join->fLeft ? join->fLeft : join; | 1481 e = boundary->fHead; // join->fLeft ? join->fLeft : join; |
1470 } | 1482 } |
1471 get_edge_normal(prevEdge, &prevNormal); | 1483 get_edge_normal(prevEdge, &prevNormal); |
1472 } else { | 1484 } else { |
1473 prevEdge = e; | 1485 prevEdge = e; |
1474 prevNormal = normal; | 1486 prevNormal = normal; |
1475 e = e->fRight; | 1487 e = e->fRight; |
1476 } | 1488 } |
1477 } | 1489 } |
1478 } | 1490 } |
1479 | 1491 |
1480 // Stage 5d: Displace edges by half a pixel inward and outward along their norma
ls. Intersect to | 1492 // Stage 5d: Displace edges by half a pixel inward and outward along their norma
ls. Intersect to |
1481 // find new vertices, and set zero alpha on the exterior and one alpha on the in
terior. Build a | 1493 // find new vertices, and set zero alpha on the exterior and one alpha on the in
terior. Build a |
1482 // new antialiased mesh from those vertices. | 1494 // new antialiased mesh from those vertices. |
1483 | 1495 |
1484 void boundary_to_aa_mesh(EdgeList* boundary, VertexList* mesh, Comparator& c, Sk
ChunkAlloc& alloc) { | 1496 void boundary_to_aa_mesh(EdgeList* boundary, VertexList* mesh, Comparator& c, Sk
ChunkAlloc& alloc) { |
1485 EdgeList outerContour; | 1497 EdgeList outerContour; |
1486 Edge* prevEdge = boundary->fTail; | 1498 Edge* prevEdge = boundary->fTail; |
1487 float radius = 0.5f; | 1499 float radius = 0.5f; |
1488 double offset = radius * sqrt(prevEdge->fDX * prevEdge->fDX + prevEdge->fDY
* prevEdge->fDY) | 1500 double offset = radius * sqrt(prevEdge->fLine.magSq()) * prevEdge->fWinding; |
1489 * prevEdge->fWinding; | 1501 Line prevInner(prevEdge->fTop, prevEdge->fBottom); |
1490 Edge prevInner(prevEdge->fTop, prevEdge->fBottom, prevEdge->fWinding); | |
1491 prevInner.fC -= offset; | 1502 prevInner.fC -= offset; |
1492 Edge prevOuter(prevEdge->fTop, prevEdge->fBottom, prevEdge->fWinding); | 1503 Line prevOuter(prevEdge->fTop, prevEdge->fBottom); |
1493 prevOuter.fC += offset; | 1504 prevOuter.fC += offset; |
1494 VertexList innerVertices; | 1505 VertexList innerVertices; |
1495 VertexList outerVertices; | 1506 VertexList outerVertices; |
1496 SkScalar innerCount = SK_Scalar1, outerCount = SK_Scalar1; | 1507 SkScalar innerCount = SK_Scalar1, outerCount = SK_Scalar1; |
1497 for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) { | 1508 for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) { |
1498 double offset = radius * sqrt(e->fDX * e->fDX + e->fDY * e->fDY) * e->fW
inding; | 1509 double offset = radius * sqrt(e->fLine.magSq()) * e->fWinding; |
1499 Edge inner(e->fTop, e->fBottom, e->fWinding); | 1510 Line inner(e->fTop, e->fBottom); |
1500 inner.fC -= offset; | 1511 inner.fC -= offset; |
1501 Edge outer(e->fTop, e->fBottom, e->fWinding); | 1512 Line outer(e->fTop, e->fBottom); |
1502 outer.fC += offset; | 1513 outer.fC += offset; |
1503 SkPoint innerPoint, outerPoint; | 1514 SkPoint innerPoint, outerPoint; |
1504 if (intersect(prevInner, inner, &innerPoint) && | 1515 if (prevInner.intersect(inner, &innerPoint) && |
1505 intersect(prevOuter, outer, &outerPoint)) { | 1516 prevOuter.intersect(outer, &outerPoint)) { |
1506 Vertex* innerVertex = ALLOC_NEW(Vertex, (innerPoint, 255), alloc); | 1517 Vertex* innerVertex = ALLOC_NEW(Vertex, (innerPoint, 255), alloc); |
1507 Vertex* outerVertex = ALLOC_NEW(Vertex, (outerPoint, 0), alloc); | 1518 Vertex* outerVertex = ALLOC_NEW(Vertex, (outerPoint, 0), alloc); |
1508 if (innerVertices.fTail && outerVertices.fTail) { | 1519 if (innerVertices.fTail && outerVertices.fTail) { |
1509 Edge innerEdge(innerVertices.fTail, innerVertex, 1); | 1520 Edge innerEdge(innerVertices.fTail, innerVertex, 1); |
1510 Edge outerEdge(outerVertices.fTail, outerVertex, 1); | 1521 Edge outerEdge(outerVertices.fTail, outerVertex, 1); |
1511 SkVector innerNormal; | 1522 SkVector innerNormal; |
1512 get_edge_normal(&innerEdge, &innerNormal); | 1523 get_edge_normal(&innerEdge, &innerNormal); |
1513 SkVector outerNormal; | 1524 SkVector outerNormal; |
1514 get_edge_normal(&outerEdge, &outerNormal); | 1525 get_edge_normal(&outerEdge, &outerNormal); |
1515 SkVector normal; | 1526 SkVector normal; |
(...skipping 288 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1804 } | 1815 } |
1805 } | 1816 } |
1806 int actualCount = static_cast<int>(vertsEnd - *verts); | 1817 int actualCount = static_cast<int>(vertsEnd - *verts); |
1807 SkASSERT(actualCount <= count); | 1818 SkASSERT(actualCount <= count); |
1808 SkASSERT(pointsEnd - points == actualCount); | 1819 SkASSERT(pointsEnd - points == actualCount); |
1809 delete[] points; | 1820 delete[] points; |
1810 return actualCount; | 1821 return actualCount; |
1811 } | 1822 } |
1812 | 1823 |
1813 } // namespace | 1824 } // namespace |
OLD | NEW |