Lines Matching defs:Edge
38 * Stages (4) and (5) use an active edge list, which a list of all edges for which the
47 * not exact and may violate the mesh topology or active edge list ordering. We
51 * A) Intersections may cause a shortened edge to no longer be ordered with respect to its
54 * B) Intersections may cause an edge to violate the left-to-right ordering of the
55 * active edge list. This is handled by splitting the neighbour edge on the
57 * C) Shortening an edge may cause an active edge to become inactive or an inactive edge
58 * to become active. This is handled by removing or inserting the edge in the active
59 * edge list (fix_active_state()).
63 * currently uses a linked list for the active edge list, rather than a 2-3 tree as the
68 * are O(1), since we know the adjacent edge in the active edge list based on the topology.
95 struct Edge;
131 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
153 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
154 Edge* fLastEdgeAbove; // "
155 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
156 Edge* fLastEdgeBelow; // "
211 Edge* fHead;
212 Edge* fTail;
216 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
217 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
218 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
233 struct Edge {
234 Edge(Vertex* top, Vertex* bottom, int winding)
248 int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
251 Edge* fLeft; // The linked list of edges in the active edge list.
252 Edge* fRight; // "
253 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
254 Edge* fNextEdgeAbove; // "
255 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
256 Edge* fNextEdgeBelow; // "
257 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
258 Poly* fRightPoly; // The Poly to the right of this edge, if any.
259 double fDX; // The line equation for this edge, in implicit form.
277 bool intersect(const Edge& other, SkPoint* p) {
637 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) {
641 return ALLOC_NEW(Edge, (top, bottom, winding), alloc);
644 void remove_edge(Edge* edge, EdgeList* edges) {
645 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
646 SkASSERT(edge->isActive(edges));
647 remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail);
650 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
651 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
652 SkASSERT(!edge->isActive(edges));
653 Edge* next = prev ? prev->fRight : edges->fHead;
654 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &edges->fTail);
657 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
663 Edge* next = NULL;
664 Edge* prev;
676 void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** left, Edge** right) {
677 Edge* prev = NULL;
678 Edge* next;
680 if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRightOf(edge->fTop)) ||
681 (c.sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftOf(next->fTop)) ||
682 (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) &&
683 next->isRightOf(edge->fBottom)) ||
684 (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) &&
685 edge->isLeftOf(next->fBottom))) {
695 void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {
696 if (edge->isActive(activeEdges)) {
697 if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
698 remove_edge(edge, activeEdges);
700 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
701 Edge* left;
702 Edge* right;
703 find_enclosing_edges(edge, activeEdges, c, &left, &right);
704 insert_edge(edge, left, activeEdges);
708 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
709 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
710 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
713 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
714 Edge* prev = NULL;
715 Edge* next;
717 if (next->isRightOf(edge->fTop)) {
722 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
723 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
726 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) {
727 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
728 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
731 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
732 Edge* prev = NULL;
733 Edge* next;
735 if (next->isRightOf(edge->fBottom)) {
740 insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
741 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
744 void remove_edge_above(Edge* edge) {
745 LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
746 edge->fBottom->fID);
747 remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
748 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
751 void remove_edge_below(Edge* edge) {
752 LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
753 edge->fTop->fID);
754 remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
755 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
758 void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) {
759 if (edge->fWinding != 0) {
762 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
763 remove_edge_above(edge);
764 remove_edge_below(edge);
765 if (edge->isActive(edges)) {
766 remove_edge(edge, edges);
770 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
772 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
773 remove_edge_below(edge);
774 edge->fTop = v;
775 edge->recompute();
776 insert_edge_below(edge, v, c);
777 fix_active_state(edge, activeEdges, c);
778 merge_collinear_edges(edge, activeEdges, c);
781 void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
782 remove_edge_above(edge);
783 edge->fBottom = v;
784 edge->recompute();
785 insert_edge_above(edge, v, c);
786 fix_active_state(edge, activeEdges, c);
787 merge_collinear_edges(edge, activeEdges, c);
790 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {
791 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
793 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
794 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
795 other->fWinding += edge->fWinding;
797 edge->fWinding = 0;
798 erase_edge_if_zero_winding(edge, activeEdges);
799 } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
800 other->fWinding += edge->fWinding;
802 set_bottom(edge, other->fTop, activeEdges, c);
804 edge->fWinding += other->fWinding;
805 erase_edge_if_zero_winding(edge, activeEdges);
806 set_bottom(other, edge->fTop, activeEdges, c);
810 void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {
811 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
813 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
814 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
815 other->fWinding += edge->fWinding;
817 edge->fWinding = 0;
818 erase_edge_if_zero_winding(edge, activeEdges);
819 } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
820 edge->fWinding += other->fWinding;
821 erase_edge_if_zero_winding(edge, activeEdges);
822 set_top(other, edge->fBottom, activeEdges, c);
824 other->fWinding += edge->fWinding;
826 set_top(edge, other->fBottom, activeEdges, c);
830 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) {
831 if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||
832 !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
833 merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, c);
834 } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop ||
835 !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) {
836 merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, c);
838 if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom ||
839 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) {
840 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c);
841 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom ||
842 !edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) {
843 merge_edges_below(edge, edge
847 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& alloc);
849 void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& alloc) {
850 Vertex* top = edge->fTop;
851 Vertex* bottom = edge->fBottom;
852 if (edge->fLeft) {
853 Vertex* leftTop = edge->fLeft->fTop;
854 Vertex* leftBottom = edge->fLeft->fBottom;
855 if (c.sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(top)) {
856 split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc);
857 } else if (c.sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf(leftTop)) {
858 split_edge(edge, leftTop, activeEdges, c, alloc);
860 !edge->fLeft->isLeftOf(bottom)) {
861 split_edge(edge->fLeft, bottom, activeEdges, c, alloc);
862 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
863 split_edge(edge, leftBottom, activeEdges, c, alloc);
866 if (edge->fRight) {
867 Vertex* rightTop = edge->fRight->fTop;
868 Vertex* rightBottom = edge->fRight->fBottom;
869 if (c.sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightOf(top)) {
870 split_edge(edge->fRight, top, activeEdges, c, alloc);
871 } else if (c.sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf(rightTop)) {
872 split_edge(edge, rightTop, activeEdges, c, alloc);
874 !edge->fRight->isRightOf(bottom)) {
875 split_edge(edge->fRight, bottom, activeEdges, c, alloc);
877 !edge->isLeftOf(rightBottom)) {
878 split_edge(edge, rightBottom, activeEdges, c, alloc);
883 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& alloc) {
884 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
885 edge->fTop->fID, edge->fBottom->fID,
887 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
888 set_top(edge, v, activeEdges, c);
889 } else if (c.sweep_gt(v->fPoint, edge->fBottom->fPoint)) {
890 set_bottom(edge, v, activeEdges, c);
892 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), alloc);
894 insert_edge_above(newEdge, edge->fBottom, c);
895 set_bottom(edge, v, activeEdges, c);
896 cleanup_active_edges(edge, activeEdges, c, alloc);
905 for (Edge* edge = src->fFirstEdgeAbove; edge;) {
906 Edge* next = edge->fNextEdgeAbove;
907 set_bottom(edge, dst, NULL, c);
908 edge = next;
910 for (Edge* edge = src->fFirstEdgeBelow; edge;) {
911 Edge* next = edge->fNextEdgeBelow;
912 set_top(edge, dst, NULL, c);
913 edge = next;
918 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c,
921 if (!edge || !other) {
924 if (edge->intersect(*other, &p)) {
927 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) {
928 split_edge(other, edge->fTop, activeEdges, c, alloc);
929 v = edge->fTop;
930 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fPoint)) {
931 split_edge(other, edge->fBottom, activeEdges, c, alloc);
932 v = edge->fBottom;
934 split_edge(edge, other->fTop, activeEdges, c, alloc);
937 split_edge(edge, other->fBottom, activeEdges, c, alloc);
940 Vertex* nextV = edge->fTop;
965 split_edge(edge, v, activeEdges, c, alloc);
1016 Edge* edge = new_edge(v->fPrev, v, alloc, c);
1017 if (edge->fWinding > 0) {
1018 insert_edge_below(edge, v->fPrev, c);
1019 insert_edge_above(edge, v, c);
1021 insert_edge_below(edge, v, c);
1022 insert_edge_above(edge, v->fPrev, c);
1024 merge_collinear_edges(edge, NULL, c);
1130 Edge* leftEnclosingEdge = NULL;
1131 Edge* rightEnclosingEdge = NULL;
1137 for (Edge* edge = v->fFirstEdgeBelow; edge != NULL; edge = edge->fNextEdgeBelow) {
1138 if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, c, alloc)) {
1142 if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, c, alloc)) {
1158 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1161 Edge* leftEdge = leftEnclosingEdge;
1162 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1183 Edge* leftEnclosingEdge = NULL;
1184 Edge* rightEnclosingEdge = NULL;
1197 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1202 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1214 for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) {
1215 Edge* leftEdge = e;
1216 Edge* rightEdge = e->fNextEdgeAbove;
1261 Edge* leftEdge = v->fFirstEdgeBelow;
1264 for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge;
1279 for (Edge* e = activeEdges.fHead; e != NULL; e = e->fRight) {
1424 // connectivity of one Edge per Vertex (will grow for intersections).
1425 SkChunkAlloc alloc(maxPts * (3 * sizeof(Vertex) + sizeof(Edge)));
