645 void remove_edge(Edge* edge, EdgeList* edges) {  in remove_edge()  argument
646     LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);  in remove_edge()
647     SkASSERT(edge->isActive(edges));  in remove_edge()
648     remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail);  in remove_edge()
651 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {  in insert_edge()  argument
652     LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);  in insert_edge()
653     SkASSERT(!edge->isActive(edges));  in insert_edge()
655     insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &edges->fTail);  in insert_edge()
677 void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** left, Edge** right) {  in find_enclosing_edges()  argument
681         if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRightOf(edge->fTop)) ||  in find_enclosing_edges()
682             (c.sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftOf(next->fTop)) ||  in find_enclosing_edges()
683             (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) &&  in find_enclosing_edges()
684              next->isRightOf(edge->fBottom)) ||  in find_enclosing_edges()
685             (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) &&  in find_enclosing_edges()
686              edge->isLeftOf(next->fBottom))) {  in find_enclosing_edges()
696 void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {  in fix_active_state()  argument
697     if (edge->isActive(activeEdges)) {  in fix_active_state()
698         if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {  in fix_active_state()
699             remove_edge(edge, activeEdges);  in fix_active_state()
701     } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {  in fix_active_state()
704         find_enclosing_edges(edge, activeEdges, c, &left, &right);  in fix_active_state()
705         insert_edge(edge, left, activeEdges);  in fix_active_state()
709 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {  in insert_edge_above()  argument
710     if (edge->fTop->fPoint == edge->fBottom->fPoint ||  in insert_edge_above()
711         c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {  in insert_edge_above()
714     LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);  in insert_edge_above()
718         if (next->isRightOf(edge->fTop)) {  in insert_edge_above()
724         edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);  in insert_edge_above()
727 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) {  in insert_edge_below()  argument
728     if (edge->fTop->fPoint == edge->fBottom->fPoint ||  in insert_edge_below()
729         c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {  in insert_edge_below()
732     LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);  in insert_edge_below()
736         if (next->isRightOf(edge->fBottom)) {  in insert_edge_below()
742         edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);  in insert_edge_below()
745 void remove_edge_above(Edge* edge) {  in remove_edge_above()  argument
746     LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,  in remove_edge_above()
747         edge->fBottom->fID);  in remove_edge_above()
749         edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);  in remove_edge_above()
752 void remove_edge_below(Edge* edge) {  in remove_edge_below()  argument
753     LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID,  in remove_edge_below()
754         edge->fTop->fID);  in remove_edge_below()
756         edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);  in remove_edge_below()
759 void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) {  in erase_edge_if_zero_winding()  argument
760     if (edge->fWinding != 0) {  in erase_edge_if_zero_winding()
763     LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);  in erase_edge_if_zero_winding()
764     remove_edge_above(edge);  in erase_edge_if_zero_winding()
765     remove_edge_below(edge);  in erase_edge_if_zero_winding()
766     if (edge->isActive(edges)) {  in erase_edge_if_zero_winding()
767         remove_edge(edge, edges);  in erase_edge_if_zero_winding()
771 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
773 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {  in set_top()  argument
774     remove_edge_below(edge);  in set_top()
775     edge->fTop = v;  in set_top()
776     edge->recompute();  in set_top()
777     insert_edge_below(edge, v, c);  in set_top()
778     fix_active_state(edge, activeEdges, c);  in set_top()
779     merge_collinear_edges(edge, activeEdges, c);  in set_top()
782 void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {  in set_bottom()  argument
783     remove_edge_above(edge);  in set_bottom()
784     edge->fBottom = v;  in set_bottom()
785     edge->recompute();  in set_bottom()
786     insert_edge_above(edge, v, c);  in set_bottom()
787     fix_active_state(edge, activeEdges, c);  in set_bottom()
788     merge_collinear_edges(edge, activeEdges, c);  in set_bottom()
791 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {  in merge_edges_above()  argument
792     if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {  in merge_edges_above()
794             edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,  in merge_edges_above()
795             edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);  in merge_edges_above()
796         other->fWinding += edge->fWinding;  in merge_edges_above()
798         edge->fWinding = 0;  in merge_edges_above()
799         erase_edge_if_zero_winding(edge, activeEdges);  in merge_edges_above()
800     } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {  in merge_edges_above()
801         other->fWinding += edge->fWinding;  in merge_edges_above()
803         set_bottom(edge, other->fTop, activeEdges, c);  in merge_edges_above()
805         edge->fWinding += other->fWinding;  in merge_edges_above()
806         erase_edge_if_zero_winding(edge, activeEdges);  in merge_edges_above()
807         set_bottom(other, edge->fTop, activeEdges, c);  in merge_edges_above()
811 void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {  in merge_edges_below()  argument
812     if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {  in merge_edges_below()
814             edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,  in merge_edges_below()
815             edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);  in merge_edges_below()
816         other->fWinding += edge->fWinding;  in merge_edges_below()
818         edge->fWinding = 0;  in merge_edges_below()
819         erase_edge_if_zero_winding(edge, activeEdges);  in merge_edges_below()
820     } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {  in merge_edges_below()
821         edge->fWinding += other->fWinding;  in merge_edges_below()
822         erase_edge_if_zero_winding(edge, activeEdges);  in merge_edges_below()
823         set_top(other, edge->fBottom, activeEdges, c);  in merge_edges_below()
825         other->fWinding += edge->fWinding;  in merge_edges_below()
827         set_top(edge, other->fBottom, activeEdges, c);  in merge_edges_below()
831 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) {  in merge_collinear_edges()  argument
832     if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||  in merge_collinear_edges()
833                                  !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {  in merge_collinear_edges()
834         merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, c);  in merge_collinear_edges()
835     } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop ||  in merge_collinear_edges()
836                                         !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) {  in merge_collinear_edges()
837         merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, c);  in merge_collinear_edges()
839     if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom ||  in merge_collinear_edges()
840                                  !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) {  in merge_collinear_edges()
841         merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c);  in merge_collinear_edges()
842     } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom ||  in merge_collinear_edges()
843                                         !edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) {  in merge_collinear_edges()
844         merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c);  in merge_collinear_edges()
848 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& alloc);
850 void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& alloc) {  in cleanup_active_edges()  argument
851     Vertex* top = edge->fTop;  in cleanup_active_edges()
852     Vertex* bottom = edge->fBottom;  in cleanup_active_edges()
853     if (edge->fLeft) {  in cleanup_active_edges()
854         Vertex* leftTop = edge->fLeft->fTop;  in cleanup_active_edges()
855         Vertex* leftBottom = edge->fLeft->fBottom;  in cleanup_active_edges()
856         if (c.sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(top)) {  in cleanup_active_edges()
857             split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc);  in cleanup_active_edges()
858         } else if (c.sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf(leftTop)) {  in cleanup_active_edges()
859             split_edge(edge, leftTop, activeEdges, c, alloc);  in cleanup_active_edges()
861                    !edge->fLeft->isLeftOf(bottom)) {  in cleanup_active_edges()
862             split_edge(edge->fLeft, bottom, activeEdges, c, alloc);  in cleanup_active_edges()
863         } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {  in cleanup_active_edges()
864             split_edge(edge, leftBottom, activeEdges, c, alloc);  in cleanup_active_edges()
867     if (edge->fRight) {  in cleanup_active_edges()
868         Vertex* rightTop = edge->fRight->fTop;  in cleanup_active_edges()
869         Vertex* rightBottom = edge->fRight->fBottom;  in cleanup_active_edges()
870         if (c.sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightOf(top)) {  in cleanup_active_edges()
871             split_edge(edge->fRight, top, activeEdges, c, alloc);  in cleanup_active_edges()
872         } else if (c.sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf(rightTop)) {  in cleanup_active_edges()
873             split_edge(edge, rightTop, activeEdges, c, alloc);  in cleanup_active_edges()
875                    !edge->fRight->isRightOf(bottom)) {  in cleanup_active_edges()
876             split_edge(edge->fRight, bottom, activeEdges, c, alloc);  in cleanup_active_edges()
878                    !edge->isLeftOf(rightBottom)) {  in cleanup_active_edges()
879             split_edge(edge, rightBottom, activeEdges, c, alloc);  in cleanup_active_edges()
884 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& alloc) {  in split_edge()  argument
886         edge->fTop->fID, edge->fBottom->fID,  in split_edge()
888     if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {  in split_edge()
889         set_top(edge, v, activeEdges, c);  in split_edge()
890     } else if (c.sweep_gt(v->fPoint, edge->fBottom->fPoint)) {  in split_edge()
891         set_bottom(edge, v, activeEdges, c);  in split_edge()
893         Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), alloc);  in split_edge()
895         insert_edge_above(newEdge, edge->fBottom, c);  in split_edge()
896         set_bottom(edge, v, activeEdges, c);  in split_edge()
897         cleanup_active_edges(edge, activeEdges, c, alloc);  in split_edge()
906     for (Edge* edge = src->fFirstEdgeAbove; edge;) {  in merge_vertices()  local
907         Edge* next = edge->fNextEdgeAbove;  in merge_vertices()
908         set_bottom(edge, dst, nullptr, c);  in merge_vertices()
909         edge = next;  in merge_vertices()
911     for (Edge* edge = src->fFirstEdgeBelow; edge;) {  in merge_vertices()  local
912         Edge* next = edge->fNextEdgeBelow;  in merge_vertices()
913         set_top(edge, dst, nullptr, c);  in merge_vertices()
914         edge = next;  in merge_vertices()
919 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c,  in check_for_intersection()  argument
922     if (!edge || !other) {  in check_for_intersection()
925     if (edge->intersect(*other, &p)) {  in check_for_intersection()
928         if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) {  in check_for_intersection()
929             split_edge(other, edge->fTop, activeEdges, c, alloc);  in check_for_intersection()
930             v = edge->fTop;  in check_for_intersection()
931         } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fPoint)) {  in check_for_intersection()
932             split_edge(other, edge->fBottom, activeEdges, c, alloc);  in check_for_intersection()
933             v = edge->fBottom;  in check_for_intersection()
935             split_edge(edge, other->fTop, activeEdges, c, alloc);  in check_for_intersection()
938             split_edge(edge, other->fBottom, activeEdges, c, alloc);  in check_for_intersection()
941             Vertex* nextV = edge->fTop;  in check_for_intersection()
966             split_edge(edge, v, activeEdges, c, alloc);  in check_for_intersection()
1017             Edge* edge = new_edge(v->fPrev, v, alloc, c);  in build_edges()  local
1018             if (edge->fWinding > 0) {  in build_edges()
1019                 insert_edge_below(edge, v->fPrev, c);  in build_edges()
1020                 insert_edge_above(edge, v, c);  in build_edges()
1022                 insert_edge_below(edge, v, c);  in build_edges()
1023                 insert_edge_above(edge, v->fPrev, c);  in build_edges()
1025             merge_collinear_edges(edge, nullptr, c);  in build_edges()
1138 …              for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = edge->fNextEdgeBelow) {  in simplify()  local
1139                     if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, c, alloc)) {  in simplify()
1143                     if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, c, alloc)) {  in simplify()