Lines Matching full:edge
37 * Stages (4) and (5) use an active edge list, which a list of all edges for which the
46 * not exact and may violate the mesh topology or active edge list ordering. We
50 * A) Intersections may cause a shortened edge to no longer be ordered with respect to its
53 * B) Intersections may cause an edge to violate the left-to-right ordering of the
54 * active edge list. This is handled by splitting the neighbour edge on the
56 * C) Shortening an edge may cause an active edge to become inactive or an inactive edge
57 * to become active. This is handled by removing or inserting the edge in the active
58 * edge list (fix_active_state()).
62 * currently uses a linked list for the active edge list, rather than a 2-3 tree as the
67 * are O(1), since we know the adjacent edge in the active edge list based on the topology.
93 struct Edge;
129 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
151 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
152 Edge* fLastEdgeAbove; // "
153 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
154 Edge* fLastEdgeBelow; // "
209 Edge* fHead;
210 Edge* fTail;
214 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
215 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
216 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
231 struct Edge {
232 Edge(Vertex* top, Vertex* bottom, int winding)
246 int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
249 Edge* fLeft; // The linked list of edges in the active edge list.
250 Edge* fRight; // "
251 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
252 Edge* fNextEdgeAbove; // "
253 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
254 Edge* fNextEdgeBelow; // "
255 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
256 Poly* fRightPoly; // The Poly to the right of this edge, if any.
257 double fDX; // The line equation for this edge, in implicit form.
275 bool intersect(const Edge& other, SkPoint* p) {
638 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) {
642 return ALLOC_NEW(Edge, (top, bottom, winding), alloc);
645 void remove_edge(Edge* edge, EdgeList* edges) {
646 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
647 SkASSERT(edge->isActive(edges));
648 remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail);
651 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
652 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
653 SkASSERT(!edge->isActive(edges));
654 Edge* next = prev ? prev->fRight : edges->fHead;
655 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &edges->fTail);
658 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
664 Edge* next = nullptr;
665 Edge* prev;
677 void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** left, Edge** right) {
678 Edge* prev = nullptr;
679 Edge* next;
681 if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRightOf(edge->fTop)) ||
682 (c.sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftOf(next->fTop)) ||
683 (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) &&
684 next->isRightOf(edge->fBottom)) ||
685 (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) &&
686 edge->isLeftOf(next->fBottom))) {
696 void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {
697 if (edge->isActive(activeEdges)) {
698 if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
699 remove_edge(edge, activeEdges);
701 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
702 Edge* left;
703 Edge* right;
704 find_enclosing_edges(edge, activeEdges, c, &left, &right);
705 insert_edge(edge, left, activeEdges);
709 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
710 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
711 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
714 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
715 Edge* prev = nullptr;
716 Edge* next;
718 if (next->isRightOf(edge->fTop)) {
723 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
724 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
727 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) {
728 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
729 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
732 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
733 Edge* prev = nullptr;
734 Edge* next;
736 if (next->isRightOf(edge->fBottom)) {
741 insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
742 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
745 void remove_edge_above(Edge* edge) {
746 LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
747 edge->fBottom->fID);
748 remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
749 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
752 void remove_edge_below(Edge* edge) {
753 LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
754 edge->fTop->fID);
755 remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
756 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
759 void erase_edge_if_zero_winding(Edge* edge, EdgeList* edges) {
760 if (edge->fWinding != 0) {
763 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
764 remove_edge_above(edge);
765 remove_edge_below(edge);
766 if (edge->isActive(edges)) {
767 remove_edge(edge, edges);
771 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
773 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
774 remove_edge_below(edge);
775 edge->fTop = v;
776 edge->recompute();
777 insert_edge_below(edge, v, c);
778 fix_active_state(edge, activeEdges, c);
779 merge_collinear_edges(edge, activeEdges, c);
782 void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
783 remove_edge_above(edge);
784 edge->fBottom = v;
785 edge->recompute();
786 insert_edge_above(edge, v, c);
787 fix_active_state(edge, activeEdges, c);
788 merge_collinear_edges(edge, activeEdges, c);
791 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {
792 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
794 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
795 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
796 other->fWinding += edge->fWinding;
798 edge->fWinding = 0;
799 erase_edge_if_zero_winding(edge, activeEdges);
800 } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
801 other->fWinding += edge->fWinding;
803 set_bottom(edge, other->fTop, activeEdges, c);
805 edge->fWinding += other->fWinding;
806 erase_edge_if_zero_winding(edge, activeEdges);
807 set_bottom(other, edge->fTop, activeEdges, c);
811 void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {
812 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
814 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
815 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
816 other->fWinding += edge->fWinding;
818 edge->fWinding = 0;
819 erase_edge_if_zero_winding(edge, activeEdges);
820 } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
821 edge->fWinding += other->fWinding;
822 erase_edge_if_zero_winding(edge, activeEdges);
823 set_top(other, edge->fBottom, activeEdges, c);
825 other->fWinding += edge->fWinding;
827 set_top(edge, other->fBottom, activeEdges, c);
831 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) {
832 if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||
833 !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
834 merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, c);
835 } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop ||
836 !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) {
837 merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, c);
839 if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom ||
840 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) {
841 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c);
842 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom ||
843 !edge->isLeftOf(edge
844 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c);
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) {
851 Vertex* top = edge->fTop;
852 Vertex* bottom = edge->fBottom;
853 if (edge->fLeft) {
854 Vertex* leftTop = edge->fLeft->fTop;
855 Vertex* leftBottom = edge->fLeft->fBottom;
856 if (c.sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(top)) {
857 split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc);
858 } else if (c.sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf(leftTop)) {
859 split_edge(edge, leftTop, activeEdges, c, alloc);
861 !edge->fLeft->isLeftOf(bottom)) {
862 split_edge(edge->fLeft, bottom, activeEdges, c, alloc);
863 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
864 split_edge(edge, leftBottom, activeEdges, c, alloc);
867 if (edge->fRight) {
868 Vertex* rightTop = edge->fRight->fTop;
869 Vertex* rightBottom = edge->fRight->fBottom;
870 if (c.sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightOf(top)) {
871 split_edge(edge->fRight, top, activeEdges, c, alloc);
872 } else if (c.sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf(rightTop)) {
873 split_edge(edge, rightTop, activeEdges, c, alloc);
875 !edge->fRight->isRightOf(bottom)) {
876 split_edge(edge->fRight, bottom, activeEdges, c, alloc);
878 !edge->isLeftOf(rightBottom)) {
879 split_edge(edge, rightBottom, activeEdges, c, alloc);
884 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& alloc) {
885 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
886 edge->fTop->fID, edge->fBottom->fID,
888 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
889 set_top(edge, v, activeEdges, c);
890 } else if (c.sweep_gt(v->fPoint, edge->fBottom->fPoint)) {
891 set_bottom(edge, v, activeEdges, c);
893 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), alloc);
895 insert_edge_above(newEdge, edge->fBottom, c);
896 set_bottom(edge, v, activeEdges, c);
897 cleanup_active_edges(edge, activeEdges, c, alloc);
906 for (Edge* edge = src->fFirstEdgeAbove; edge;) {
907 Edge* next = edge->fNextEdgeAbove;
908 set_bottom(edge, dst, nullptr, c);
909 edge = next;
911 for (Edge* edge = src->fFirstEdgeBelow; edge;) {
912 Edge* next = edge->fNextEdgeBelow;
913 set_top(edge, dst, nullptr, c);
914 edge = next;
919 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c,
922 if (!edge || !other) {
925 if (edge->intersect(*other, &p)) {
928 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) {
929 split_edge(other, edge->fTop, activeEdges, c, alloc);
930 v = edge->fTop;
931 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fPoint)) {
932 split_edge(other, edge->fBottom, activeEdges, c, alloc);
933 v = edge->fBottom;
935 split_edge(edge, other->fTop, activeEdges, c, alloc);
938 split_edge(edge, other->fBottom, activeEdges, c, alloc);
941 Vertex* nextV = edge->fTop;
966 split_edge(edge, v, activeEdges, c, alloc);
1017 Edge* edge = new_edge(v->fPrev, v, alloc, c);
1018 if (edge->fWinding > 0) {
1019 insert_edge_below(edge, v->fPrev, c);
1020 insert_edge_above(edge, v, c);
1022 insert_edge_below(edge, v, c);
1023 insert_edge_above(edge, v->fPrev, c);
1025 merge_collinear_edges(edge, nullptr, c);
1131 Edge* leftEnclosingEdge = nullptr;
1132 Edge* rightEnclosingEdge = nullptr;
1138 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = edge->fNextEdgeBelow) {
1139 if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, c, alloc)) {
1143 if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, c, alloc)) {
1159 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1162 Edge* leftEdge = leftEnclosingEdge;
1163 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1184 Edge* leftEnclosingEdge = nullptr;
1185 Edge* rightEnclosingEdge = nullptr;
1198 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1203 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1215 for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) {
1216 Edge* leftEdge = e;
1217 Edge* rightEdge = e->fNextEdgeAbove;
1262 Edge* leftEdge = v->fFirstEdgeBelow;
1265 for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge;
1280 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) {
1357 // connectivity of one Edge per Vertex (will grow for intersections).
1358 *sizeEstimate = maxPts * (3 * sizeof(Vertex) + sizeof(Edge));
