Flutter Engine
The Flutter Engine
Public Member Functions | List of all members
ActiveEdgeList Class Reference

Public Member Functions

 ActiveEdgeList (int maxEdges)
 
 ~ActiveEdgeList ()
 
bool insert (const SkPoint &p0, const SkPoint &p1, uint16_t index0, uint16_t index1)
 
bool replace (const SkPoint &p0, const SkPoint &p1, const SkPoint &p2, uint16_t index0, uint16_t index1, uint16_t index2)
 
bool remove (const SkPoint &p0, const SkPoint &p1, uint16_t index0, uint16_t index1)
 

Detailed Description

Definition at line 697 of file SkPolyUtils.cpp.

Constructor & Destructor Documentation

◆ ActiveEdgeList()

ActiveEdgeList::ActiveEdgeList ( int  maxEdges)
inline

Definition at line 699 of file SkPolyUtils.cpp.

699 {
700 fAllocation = (char*) sk_malloc_throw(sizeof(ActiveEdge)*maxEdges);
701 fCurrFree = 0;
702 fMaxFree = maxEdges;
703 }
sk_malloc_throw
static void * sk_malloc_throw(size_t size)
Definition: SkMalloc.h:67

◆ ~ActiveEdgeList()

ActiveEdgeList::~ActiveEdgeList ( )
inline

Definition at line 704 of file SkPolyUtils.cpp.

704 {
705 fTreeHead.fChild[1] = nullptr;
706 sk_free(fAllocation);
707 }
sk_free
SK_API void sk_free(void *)
Definition: SkMemory_malloc.cpp:83
ActiveEdge::fChild
ActiveEdge * fChild[2]
Definition: SkPolyUtils.cpp:691

Member Function Documentation

◆ insert()

bool ActiveEdgeList::insert ( const SkPoint &  p0,
const SkPoint &  p1,
uint16_t  index0,
uint16_t  index1 
)
inline

Definition at line 709 of file SkPolyUtils.cpp.

709 {
710 SkVector v = p1 - p0;
711 if (!v.isFinite()) {
712 return false;
713 }
714 // empty tree case -- easy
715 if (!fTreeHead.fChild[1]) {
716 ActiveEdge* root = fTreeHead.fChild[1] = this->allocate(p0, v, index0, index1);
717 SkASSERT(root);
718 if (!root) {
719 return false;
720 }
721 root->fRed = false;
722 return true;
723 }
724
725 // set up helpers
726 ActiveEdge* top = &fTreeHead;
727 ActiveEdge *grandparent = nullptr;
728 ActiveEdge *parent = nullptr;
729 ActiveEdge *curr = top->fChild[1];
730 int dir = 0;
731 int last = 0; // ?
732 // predecessor and successor, for intersection check
733 ActiveEdge* pred = nullptr;
734 ActiveEdge* succ = nullptr;
735
736 // search down the tree
737 while (true) {
738 if (!curr) {
739 // check for intersection with predecessor and successor
740 if ((pred && pred->intersect(p0, v, index0, index1)) ||
741 (succ && succ->intersect(p0, v, index0, index1))) {
742 return false;
743 }
744 // insert new node at bottom
745 parent->fChild[dir] = curr = this->allocate(p0, v, index0, index1);
746 SkASSERT(curr);
747 if (!curr) {
748 return false;
749 }
750 curr->fAbove = pred;
751 curr->fBelow = succ;
752 if (pred) {
753 if (pred->fSegment.fP0 == curr->fSegment.fP0 &&
754 pred->fSegment.fV == curr->fSegment.fV) {
755 return false;
756 }
757 pred->fBelow = curr;
758 }
759 if (succ) {
760 if (succ->fSegment.fP0 == curr->fSegment.fP0 &&
761 succ->fSegment.fV == curr->fSegment.fV) {
762 return false;
763 }
764 succ->fAbove = curr;
765 }
766 if (IsRed(parent)) {
767 int dir2 = (top->fChild[1] == grandparent);
768 if (curr == parent->fChild[last]) {
769 top->fChild[dir2] = SingleRotation(grandparent, !last);
770 } else {
771 top->fChild[dir2] = DoubleRotation(grandparent, !last);
772 }
773 }
774 break;
775 } else if (IsRed(curr->fChild[0]) && IsRed(curr->fChild[1])) {
776 // color flip
777 curr->fRed = true;
778 curr->fChild[0]->fRed = false;
779 curr->fChild[1]->fRed = false;
780 if (IsRed(parent)) {
781 int dir2 = (top->fChild[1] == grandparent);
782 if (curr == parent->fChild[last]) {
783 top->fChild[dir2] = SingleRotation(grandparent, !last);
784 } else {
785 top->fChild[dir2] = DoubleRotation(grandparent, !last);
786 }
787 }
788 }
789
790 last = dir;
791 int side;
792 // check to see if segment is above or below
793 if (curr->fIndex0 == index0) {
794 side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
795 } else {
796 side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
797 }
798 if (0 == side) {
799 return false;
800 }
801 dir = (side < 0);
802
803 if (0 == dir) {
804 succ = curr;
805 } else {
806 pred = curr;
807 }
808
809 // update helpers
810 if (grandparent) {
811 top = grandparent;
812 }
813 grandparent = parent;
814 parent = curr;
815 curr = curr->fChild[dir];
816 }
817
818 // update root and make it black
819 fTreeHead.fChild[1]->fRed = false;
820
821 SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
822
823 return true;
824 }
SkASSERT
#define SkASSERT(cond)
Definition: SkAssert.h:116
side
static int side(double x)
Definition: SkOpCubicHull.cpp:45
compute_side
static int compute_side(const SkPoint &p0, const SkVector &v, const SkPoint &p)
Definition: SkPolyUtils.cpp:46
SkDEBUGCODE
SkDEBUGCODE(SK_SPI) SkThreadID SkGetThreadID()
flutter::dir
DEF_SWITCHES_START aot vmservice shared library Name of the *so containing AOT compiled Dart assets for launching the service isolate vm snapshot The VM snapshot data that will be memory mapped as read only SnapshotAssetPath must be present isolate snapshot The isolate snapshot data that will be memory mapped as read only SnapshotAssetPath must be present cache dir Path to the cache directory This is different from the persistent_cache_path in embedder which is used for Skia shader cache icu native lib Path to the library file that exports the ICU data vm service The hostname IP address on which the Dart VM Service should be served If not defaults to or::depending on whether ipv6 is specified vm service A custom Dart VM Service port The default is to pick a randomly available open port disable vm Disable the Dart VM Service The Dart VM Service is never available in release mode disable vm service Disable mDNS Dart VM Service publication Bind to the IPv6 localhost address for the Dart VM Service Ignored if vm service host is set endless trace Enable an endless trace buffer The default is a ring buffer This is useful when very old events need to viewed For during application launch Memory usage will continue to grow indefinitely however Start app with an specific route defined on the framework flutter assets dir
Definition: switches.h:145
scale_cpu.root
string root
Definition: scale_cpu.py:20
ActiveEdge::fAbove
ActiveEdge * fAbove
Definition: SkPolyUtils.cpp:692
ActiveEdge::fBelow
ActiveEdge * fBelow
Definition: SkPolyUtils.cpp:693
ActiveEdge::intersect
bool intersect(const SkPoint &q0, const SkVector &w, uint16_t index0, uint16_t index1) const
Definition: SkPolyUtils.cpp:634
ActiveEdge::fIndex0
uint16_t fIndex0
Definition: SkPolyUtils.cpp:689
ActiveEdge::fRed
int32_t fRed
Definition: SkPolyUtils.cpp:694
ActiveEdge::fSegment
OffsetSegment fSegment
Definition: SkPolyUtils.cpp:688
SkPoint::isFinite
bool isFinite() const
Definition: SkPoint_impl.h:412

◆ remove()

bool ActiveEdgeList::remove ( const SkPoint &  p0,
const SkPoint &  p1,
uint16_t  index0,
uint16_t  index1 
)
inline

Definition at line 886 of file SkPolyUtils.cpp.

886 {
887 if (!fTreeHead.fChild[1]) {
888 return false;
889 }
890
891 ActiveEdge* curr = &fTreeHead;
892 ActiveEdge* parent = nullptr;
893 ActiveEdge* grandparent = nullptr;
894 ActiveEdge* found = nullptr;
895 int dir = 1;
896
897 // search and push a red node down
898 while (curr->fChild[dir] != nullptr) {
899 int last = dir;
900
901 // update helpers
902 grandparent = parent;
903 parent = curr;
904 curr = curr->fChild[dir];
905 // save found node
906 if (curr->equals(index0, index1)) {
907 found = curr;
908 dir = 0;
909 } else {
910 // check to see if segment is above or below
911 int side;
912 if (curr->fIndex1 == index1) {
913 side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
914 } else {
915 side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
916 }
917 if (0 == side) {
918 return false;
919 }
920 dir = (side < 0);
921 }
922
923 // push the red node down
924 if (!IsRed(curr) && !IsRed(curr->fChild[dir])) {
925 if (IsRed(curr->fChild[!dir])) {
926 parent = parent->fChild[last] = SingleRotation(curr, dir);
927 } else {
928 ActiveEdge *s = parent->fChild[!last];
929
930 if (s != nullptr) {
931 if (!IsRed(s->fChild[!last]) && !IsRed(s->fChild[last])) {
932 // color flip
933 parent->fRed = false;
934 s->fRed = true;
935 curr->fRed = true;
936 } else {
937 int dir2 = (grandparent->fChild[1] == parent);
938
939 if (IsRed(s->fChild[last])) {
940 grandparent->fChild[dir2] = DoubleRotation(parent, last);
941 } else if (IsRed(s->fChild[!last])) {
942 grandparent->fChild[dir2] = SingleRotation(parent, last);
943 }
944
945 // ensure correct coloring
946 curr->fRed = grandparent->fChild[dir2]->fRed = true;
947 grandparent->fChild[dir2]->fChild[0]->fRed = false;
948 grandparent->fChild[dir2]->fChild[1]->fRed = false;
949 }
950 }
951 }
952 }
953 }
954
955 // replace and remove if found
956 if (found) {
957 ActiveEdge* pred = found->fAbove;
958 ActiveEdge* succ = found->fBelow;
959 if ((pred && pred->intersect(found)) || (succ && succ->intersect(found))) {
960 return false;
961 }
962 if (found != curr) {
963 found->fSegment = curr->fSegment;
964 found->fIndex0 = curr->fIndex0;
965 found->fIndex1 = curr->fIndex1;
966 found->fAbove = curr->fAbove;
967 pred = found->fAbove;
968 // we don't need to set found->fBelow here
969 } else {
970 if (succ) {
971 succ->fAbove = pred;
972 }
973 }
974 if (pred) {
975 pred->fBelow = curr->fBelow;
976 }
977 parent->fChild[parent->fChild[1] == curr] = curr->fChild[!curr->fChild[0]];
978
979 // no need to delete
980 curr->fAbove = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
981 curr->fBelow = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
982 if (fTreeHead.fChild[1]) {
983 fTreeHead.fChild[1]->fRed = false;
984 }
985 }
986
987 // update root and make it black
988 if (fTreeHead.fChild[1]) {
989 fTreeHead.fChild[1]->fRed = false;
990 }
991
992 SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
993
994 return true;
995 }
s
struct MyStruct s
ActiveEdge::fIndex1
uint16_t fIndex1
Definition: SkPolyUtils.cpp:690
ActiveEdge::equals
bool equals(uint16_t index0, uint16_t index1) const
Definition: SkPolyUtils.cpp:684

◆ replace()

bool ActiveEdgeList::replace ( const SkPoint &  p0,
const SkPoint &  p1,
const SkPoint &  p2,
uint16_t  index0,
uint16_t  index1,
uint16_t  index2 
)
inline

Definition at line 827 of file SkPolyUtils.cpp.

828 {
829 if (!fTreeHead.fChild[1]) {
830 return false;
831 }
832
833 SkVector v = p2 - p1;
834 ActiveEdge* curr = &fTreeHead;
835 ActiveEdge* found = nullptr;
836 int dir = 1;
837
838 // search
839 while (curr->fChild[dir] != nullptr) {
840 // update helpers
841 curr = curr->fChild[dir];
842 // save found node
843 if (curr->equals(index0, index1)) {
844 found = curr;
845 break;
846 } else {
847 // check to see if segment is above or below
848 int side;
849 if (curr->fIndex1 == index1) {
850 side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
851 } else {
852 side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
853 }
854 if (0 == side) {
855 return false;
856 }
857 dir = (side < 0);
858 }
859 }
860
861 if (!found) {
862 return false;
863 }
864
865 // replace if found
866 ActiveEdge* pred = found->fAbove;
867 ActiveEdge* succ = found->fBelow;
868 // check deletion and insert intersection cases
869 if (pred && (pred->intersect(found) || pred->intersect(p1, v, index1, index2))) {
870 return false;
871 }
872 if (succ && (succ->intersect(found) || succ->intersect(p1, v, index1, index2))) {
873 return false;
874 }
875 found->fSegment.fP0 = p1;
876 found->fSegment.fV = v;
877 found->fIndex0 = index1;
878 found->fIndex1 = index2;
879 // above and below should stay the same
880
881 SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
882
883 return true;
884 }
The documentation for this class was generated from the following file:
Generated on Sun Jun 23 2024 21:57:51 for Flutter Engine by doxygen 1.9.4