Lines Matching refs:edge
152 // If the edge's vertices differ by many orders of magnitude, the computed line equation can have
271 // If the intersection is on any interior edge, it needs to stay fully opaque or later
276 // construction on the outer edge.
279 // Could be two connectors crossing, or a connector crossing an outer edge.
289 void GrTriangulator::EdgeList::insert(Edge* edge, Edge* prev, Edge* next) {
290 list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail);
293 void GrTriangulator::EdgeList::remove(Edge* edge) {
294 TESS_LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
295 SkASSERT(this->contains(edge));
296 list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail);
299 void GrTriangulator::MonotonePoly::addEdge(Edge* edge) {
301 SkASSERT(!edge->fUsedInRightPoly);
303 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
304 edge->fUsedInRightPoly = true;
306 SkASSERT(!edge->fUsedInLeftPoly);
308 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
309 edge->fUsedInLeftPoly = true;
628 void EdgeList::insert(Edge* edge, Edge* prev) {
629 TESS_LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
630 SkASSERT(!this->contains(edge));
632 this->insert(edge, prev, next);
658 TESS_LOG("insert edge (%g -> %g) above vertex %g\n", fTop->fID, fBottom->fID, v->fID);
676 TESS_LOG("insert edge (%g -> %g) below vertex %g\n", fTop->fID, fBottom->fID, v->fID);
689 static void remove_edge_above(Edge* edge) {
690 SkASSERT(edge->fTop && edge->fBottom);
691 TESS_LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
692 edge->fBottom->fID);
694 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
697 static void remove_edge_below(Edge* edge) {
698 SkASSERT(edge->fTop && edge->fBottom);
699 TESS_LOG("removing edge (%g -> %g) below vertex %g\n",
700 edge->fTop->fID, edge->fBottom->fID, edge->fTop->fID);
702 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
736 static void rewind_if_necessary(Edge* edge, EdgeList* activeEdges, Vertex** current,
741 Vertex* top = edge->fTop;
742 Vertex* bottom = edge->fBottom;
743 if (edge->fLeft) {
744 Vertex* leftTop = edge->fLeft->fTop;
745 Vertex* leftBottom = edge->fLeft->fBottom;
746 if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(top)) {
748 } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(leftTop)) {
751 !edge->fLeft->isLeftOf(bottom)) {
753 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
757 if (edge->fRight) {
758 Vertex* rightTop = edge->fRight->fTop;
759 Vertex* rightBottom = edge->fRight->fBottom;
760 if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(top)) {
762 } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(rightTop)) {
765 !edge->fRight->isRightOf(bottom)) {
768 !edge->isLeftOf(rightBottom)) {
774 void GrTriangulator::setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
776 remove_edge_below(edge);
778 fBreadcrumbList.append(fAlloc, edge->fTop->fPoint, edge->fBottom->fPoint, v->fPoint,
779 edge->fWinding);
781 edge->fTop = v;
782 edge->recompute();
783 edge->insertBelow(v, c);
784 rewind_if_necessary(edge, activeEdges, current, c);
785 this->mergeCollinearEdges(edge, activeEdges, current, c);
788 void GrTriangulator::setBottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
790 remove_edge_above(edge);
792 fBreadcrumbList.append(fAlloc, edge->fTop->fPoint, edge->fBottom->fPoint, v->fPoint,
793 edge->fWinding);
795 edge->fBottom = v;
796 edge->recompute();
797 edge->insertAbove(v, c);
798 rewind_if_necessary(edge, activeEdges, current, c);
799 this->mergeCollinearEdges(edge, activeEdges, current, c);
802 void GrTriangulator::mergeEdgesAbove(Edge* edge, Edge* other, EdgeList* activeEdges,
804 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
806 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
807 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
808 rewind(activeEdges, current, edge->fTop, c);
809 other->fWinding += edge->fWinding;
810 edge->disconnect();
811 edge->fTop = edge->fBottom = nullptr;
812 } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
813 rewind(activeEdges, current, edge->fTop, c);
814 other->fWinding += edge->fWinding;
815 this->setBottom(edge, other->fTop, activeEdges, current, c);
818 edge->fWinding += other->fWinding;
819 this->setBottom(other, edge->fTop, activeEdges, current, c);
823 void GrTriangulator::mergeEdgesBelow(Edge* edge, Edge* other, EdgeList* activeEdges,
825 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
827 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
828 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
829 rewind(activeEdges, current, edge->fTop, c);
830 other->fWinding += edge->fWinding;
831 edge->disconnect();
832 edge->fTop = edge->fBottom = nullptr;
833 } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
835 edge->fWinding += other->fWinding;
836 this->setTop(other, edge->fBottom, activeEdges, current, c);
838 rewind(activeEdges, current, edge->fTop, c);
839 other->fWinding += edge->fWinding;
840 this->setTop(edge, other->fBottom, activeEdges, current, c);
860 void GrTriangulator::mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current,
863 if (top_collinear(edge->fPrevEdgeAbove, edge)) {
864 this->mergeEdgesAbove(edge->fPrevEdgeAbove, edge, activeEdges, current, c);
865 } else if (top_collinear(edge, edge->fNextEdgeAbove)) {
866 this->mergeEdgesAbove(edge->fNextEdgeAbove, edge, activeEdges, current, c);
867 } else if (bottom_collinear(edge->fPrevEdgeBelow, edge)) {
868 this->mergeEdgesBelow(edge->fPrevEdgeBelow, edge, activeEdges, current, c);
869 } else if (bottom_collinear(edge, edge->fNextEdgeBelow)) {
870 this->mergeEdgesBelow(edge->fNextEdgeBelow, edge, activeEdges, current, c);
875 SkASSERT(!top_collinear(edge->fPrevEdgeAbove, edge));
876 SkASSERT(!top_collinear(edge, edge->fNextEdgeAbove));
877 SkASSERT(!bottom_collinear(edge->fPrevEdgeBelow, edge));
878 SkASSERT(!bottom_collinear(edge, edge->fNextEdgeBelow));
881 bool GrTriangulator::splitEdge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
883 if (!edge->fTop || !edge->fBottom || v == edge->fTop || v == edge->fBottom) {
886 TESS_LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
887 edge->fTop->fID, edge->fBottom->fID, v->fID, v->fPoint.fX, v->fPoint.fY);
890 int winding = edge->fWinding;
891 // Theoretically, and ideally, the edge betwee p0 and p1 is being split by v, and v is "between"
894 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
895 // Actually "v < p0 < p1": update 'edge' to be v->p1 and add v->p0. We flip the winding on
896 // the new edge so that it winds as if it were p0->v.
898 bottom = edge->fTop;
900 this->setTop(edge, v, activeEdges, current, c);
901 } else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) {
902 // Actually "p0 < p1 < v": update 'edge' to be p0->v and add p1->v. We flip the winding on
903 // the new edge so that it winds as if it were v->p1.
904 top = edge->fBottom;
907 this->setBottom(edge, v, activeEdges, current, c);
909 // The ideal case, "p0 < v < p1": update 'edge' to be p0->v and add v->p1. Original winding
912 bottom = edge->fBottom;
913 this->setBottom(edge, v, activeEdges, current, c);
915 Edge* newEdge = fAlloc->make<Edge>(top, bottom, winding, edge->fType);
960 Edge* edge = this->makeEdge(prev, next, type, c);
961 edge->insertBelow(edge->fTop, c);
962 edge->insertAbove(edge->fBottom, c);
963 edge->fWinding *= windingScale;
964 this->mergeCollinearEdges(edge, nullptr, nullptr, c);
965 return edge;
976 while (Edge* edge = src->fFirstEdgeAbove) {
977 this->setBottom(edge, dst, nullptr, nullptr, c);
979 while (Edge* edge = src->fFirstEdgeBelow) {
980 this->setTop(edge, dst, nullptr, nullptr, c);
1250 TESS_LOG(" edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding);
1253 TESS_LOG(" edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding);
1316 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
1318 leftEnclosingEdge, edge, &activeEdges, &v, mesh, c) ||
1320 edge, rightEnclosingEdge, &activeEdges, &v, mesh, c)) {