Add createTJunctionFreeRegion

T-junction free regions are useful for rendering regions with various
geometric transformations, and the Region's span-ordered, sorted rect
list supports T-junction free storage without modification.

This approach creates a T-junction free region by splitting each
rectangle that is part of a vertical T-junction. This approach is two
pass (up and down) so that divisions can trickle up/down to other
adjacent spans.

Change-Id: Ifcf5e6fe0034c96b00ef09a4433b2b0fce8f4300

6 files changed, 315 insertions, 86 deletions

diff --git a/include/ui/Region.h b/include/ui/Region.h
index 43a4450..ffcd429 100644
--- a/include/ui/Region.h
+++ b/include/ui/Region.h
@@ -39,7 +39,9 @@ public:
                         Region(const Region& rhs);
     explicit            Region(const Rect& rhs);
                         ~Region();
-                        
+
+    static  Region      createTJunctionFreeRegion(const Region& r);
+
         Region& operator = (const Region& rhs);
 
     inline  bool        isEmpty() const     { return getBounds().isEmpty(); }
diff --git a/libs/ui/Region.cpp b/libs/ui/Region.cpp
index 932ef68..1a613f8 100644
--- a/libs/ui/Region.cpp
+++ b/libs/ui/Region.cpp
@@ -47,6 +47,11 @@ enum {
     op_xor  = region_operator<Rect>::op_xor
 };
 
+enum {
+    direction_LTR,
+    direction_RTL
+};
+
 // ----------------------------------------------------------------------------
 
 Region::Region() {
@@ -69,6 +74,133 @@ Region::~Region()
 {
 }
 
+/**
+ * Copy rects from the src vector into the dst vector, resolving vertical T-Junctions along the way
+ *
+ * First pass through, divideSpanRTL will be set because the 'previous span' (indexing into the dst
+ * vector) will be reversed. Each rectangle in the original list, starting from the bottom, will be
+ * compared with the span directly below, and subdivided as needed to resolve T-junctions.
+ *
+ * The resulting temporary vector will be a completely reversed copy of the original, without any
+ * bottom-up T-junctions.
+ *
+ * Second pass through, divideSpanRTL will be false since the previous span will index into the
+ * final, correctly ordered region buffer. Each rectangle will be compared with the span directly
+ * above it, and subdivided to resolve any remaining T-junctions.
+ */
+static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end,
+        Vector<Rect>& dst, int spanDirection) {
+    dst.clear();
+
+    const Rect* current = end - 1;
+    int lastTop = current->top;
+
+    // add first span immediately
+    do {
+        dst.add(*current);
+        current--;
+    } while (current->top == lastTop && current >= begin);
+
+    unsigned int beginLastSpan = -1;
+    unsigned int endLastSpan = -1;
+    int top = -1;
+    int bottom = -1;
+
+    // for all other spans, split if a t-junction exists in the span directly above
+    while (current >= begin) {
+        if (current->top != (current + 1)->top) {
+            // new span
+            if ((spanDirection == direction_RTL && current->bottom != (current + 1)->top) ||
+                    (spanDirection == direction_LTR && current->top != (current + 1)->bottom)) {
+                // previous span not directly adjacent, don't check for T junctions
+                beginLastSpan = INT_MAX;
+            } else {
+                beginLastSpan = endLastSpan + 1;
+            }
+            endLastSpan = dst.size() - 1;
+
+            top = current->top;
+            bottom = current->bottom;
+        }
+        int left = current->left;
+        int right = current->right;
+
+        for (unsigned int prevIndex = beginLastSpan; prevIndex <= endLastSpan; prevIndex++) {
+            const Rect* prev = &dst[prevIndex];
+            if (spanDirection == direction_RTL) {
+                // iterating over previous span RTL, quit if it's too far left
+                if (prev->right <= left) break;
+
+                if (prev->right > left && prev->right < right) {
+                    dst.add(Rect(prev->right, top, right, bottom));
+                    right = prev->right;
+                }
+
+                if (prev->left > left && prev->left < right) {
+                    dst.add(Rect(prev->left, top, right, bottom));
+                    right = prev->left;
+                }
+
+                // if an entry in the previous span is too far right, nothing further left in the
+                // current span will need it
+                if (prev->left >= right) {
+                    beginLastSpan = prevIndex;
+                }
+            } else {
+                // iterating over previous span LTR, quit if it's too far right
+                if (prev->left >= right) break;
+
+                if (prev->left > left && prev->left < right) {
+                    dst.add(Rect(left, top, prev->left, bottom));
+                    left = prev->left;
+                }
+
+                if (prev->right > left && prev->right < right) {
+                    dst.add(Rect(left, top, prev->right, bottom));
+                    left = prev->right;
+                }
+                // if an entry in the previous span is too far left, nothing further right in the
+                // current span will need it
+                if (prev->right <= left) {
+                    beginLastSpan = prevIndex;
+                }
+            }
+        }
+
+        if (left < right) {
+            dst.add(Rect(left, top, right, bottom));
+        }
+
+        current--;
+    }
+}
+
+/**
+ * Creates a new region with the same data as the argument, but divides rectangles as necessary to
+ * remove T-Junctions
+ *
+ * Note: the output will not necessarily be a very efficient representation of the region, since it
+ * may be that a triangle-based approach would generate significantly simpler geometry
+ */
+Region Region::createTJunctionFreeRegion(const Region& r) {
+    if (r.isEmpty()) return r;
+    if (r.isRect()) return r;
+
+    Vector<Rect> reversed;
+    reverseRectsResolvingJunctions(r.begin(), r.end(), reversed, direction_RTL);
+
+    Region outputRegion;
+    reverseRectsResolvingJunctions(reversed.begin(), reversed.end(),
+            outputRegion.mStorage, direction_LTR);
+    outputRegion.mStorage.add(r.getBounds()); // to make region valid, mStorage must end with bounds
+
+#if VALIDATE_REGIONS
+    validate(outputRegion, "T-Junction free region");
+#endif
+
+    return outputRegion;
+}
+
 Region& Region::operator = (const Region& rhs)
 {
 #if VALIDATE_REGIONS
diff --git a/libs/ui/tests/Android.mk b/libs/ui/tests/Android.mk
index 50cad36..8b8e1d8 100644
--- a/libs/ui/tests/Android.mk
+++ b/libs/ui/tests/Android.mk
@@ -1,4 +1,28 @@
 # Build the unit tests.
+LOCAL_PATH := $(call my-dir)
+include $(CLEAR_VARS)
+
+# Build the unit tests.
+test_src_files := \
+    Region_test.cpp
+
+shared_libraries := \
+    libui
+
+static_libraries := \
+    libgtest \
+    libgtest_main
+
+$(foreach file,$(test_src_files), \
+    $(eval include $(CLEAR_VARS)) \
+    $(eval LOCAL_SHARED_LIBRARIES := $(shared_libraries)) \
+    $(eval LOCAL_STATIC_LIBRARIES := $(static_libraries)) \
+    $(eval LOCAL_SRC_FILES := $(file)) \
+    $(eval LOCAL_MODULE := $(notdir $(file:%.cpp=%))) \
+    $(eval include $(BUILD_NATIVE_TEST)) \
+)
+
+# Build the unit tests.
 LOCAL_PATH:= $(call my-dir)
 include $(CLEAR_VARS)
 
diff --git a/libs/ui/tests/Region_test.cpp b/libs/ui/tests/Region_test.cpp
new file mode 100644
index 0000000..b104a46
--- /dev/null
+++ b/libs/ui/tests/Region_test.cpp
@@ -0,0 +1,156 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define LOG_TAG "RegionTest"
+
+#include <stdlib.h>
+#include <ui/Region.h>
+#include <ui/Rect.h>
+#include <gtest/gtest.h>
+
+namespace android {
+
+class RegionTest : public testing::Test {
+protected:
+    void checkVertTJunction(const Rect* lhs, const Rect* rhs) {
+        EXPECT_FALSE((rhs->right > lhs->left && rhs->right < lhs->right) ||
+                (rhs->left > lhs->left && rhs->left < lhs->right));
+    }
+
+    void verifyNoTJunctions(const Region& r) {
+        for (const Rect* current = r.begin(); current < r.end(); current++) {
+            for (const Rect* other = current - 1; other >= r.begin(); other--) {
+                if (other->bottom < current->top) break;
+                if (other->bottom != current->top) continue;
+                checkVertTJunction(current, other);
+            }
+            for (const Rect* other = current + 1; other < r.end(); other++) {
+                if (other->top > current->bottom) break;
+                if (other->top != current->bottom) continue;
+                checkVertTJunction(current, other);
+            }
+        }
+    }
+
+    void checkTJunctionFreeFromRegion(const Region& original, int expectedCount = -1) {
+        Region modified = Region::createTJunctionFreeRegion(original);
+        verifyNoTJunctions(modified);
+        if (expectedCount != -1) {
+            EXPECT_EQ(modified.end() - modified.begin(), expectedCount);
+        }
+        EXPECT_TRUE((original ^ modified).isEmpty());
+    }
+};
+
+TEST_F(RegionTest, MinimalDivision_TJunction) {
+    Region r;
+     // | x |
+     // |xxx|
+    r.clear();
+    r.orSelf(Rect(1, 0, 2, 1));
+    r.orSelf(Rect(0, 1, 3, 2));
+    checkTJunctionFreeFromRegion(r, 4);
+
+     // | x |
+     // |   |
+     // |xxx|
+    r.clear();
+    r.orSelf(Rect(1, 0, 2, 1));
+    r.orSelf(Rect(0, 2, 3, 3));
+    checkTJunctionFreeFromRegion(r, 2);
+}
+
+TEST_F(RegionTest, Trivial_TJunction) {
+    Region r;
+    checkTJunctionFreeFromRegion(r);
+
+    r.orSelf(Rect(100, 100, 500, 500));
+    checkTJunctionFreeFromRegion(r);
+}
+
+TEST_F(RegionTest, Simple_TJunction) {
+    Region r;
+     // | x  |
+     // |xxxx|
+     // |xxxx|
+     // |xxxx|
+    r.clear();
+    r.orSelf(Rect(1, 0, 2, 1));
+    r.orSelf(Rect(0, 1, 3, 3));
+    checkTJunctionFreeFromRegion(r);
+
+     // | x |
+     // |xx |
+     // |xxx|
+    r.clear();
+    r.orSelf(Rect(2,0,4,2));
+    r.orSelf(Rect(0,2,4,4));
+    r.orSelf(Rect(0,4,6,6));
+    checkTJunctionFreeFromRegion(r);
+
+     // |x x|
+     // |xxx|
+     // |x x|
+    r.clear();
+    r.orSelf(Rect(0,0,2,6));
+    r.orSelf(Rect(4,0,6,6));
+    r.orSelf(Rect(0,2,6,4));
+    checkTJunctionFreeFromRegion(r);
+
+     // |xxx|
+     // | x |
+     // | x |
+    r.clear();
+    r.orSelf(Rect(0,0,6,2));
+    r.orSelf(Rect(2,2,4,6));
+    checkTJunctionFreeFromRegion(r);
+}
+
+TEST_F(RegionTest, Bigger_TJunction) {
+    Region r;
+     // |xxxx   |
+     // | xxxx  |
+     // |  xxxx |
+     // |   xxxx|
+    for (int i = 0; i < 4; i++) {
+        r.orSelf(Rect(i,i,i+4,i+1));
+    }
+    checkTJunctionFreeFromRegion(r, 16);
+}
+
+#define ITER_MAX 1000
+#define X_MAX 8
+#define Y_MAX 8
+
+TEST_F(RegionTest, Random_TJunction) {
+    Region r;
+    srandom(12345);
+
+    for (int iter = 0; iter < ITER_MAX; iter++) {
+        r.clear();
+        for (int i = 0; i < X_MAX; i++) {
+            for (int j = 0; j < Y_MAX; j++) {
+                if (random() % 2) {
+                    r.orSelf(Rect(i, j, i + 1, j + 1));
+                }
+            }
+        }
+        checkTJunctionFreeFromRegion(r);
+    }
+}
+
+}; // namespace android
+
diff --git a/libs/ui/tests/region/Android.mk b/libs/ui/tests/region/Android.mk
deleted file mode 100644
index 6cc4a5a..0000000
--- a/libs/ui/tests/region/Android.mk
+++ /dev/null
@@ -1,16 +0,0 @@
-LOCAL_PATH:= $(call my-dir)
-include $(CLEAR_VARS)
-
-LOCAL_SRC_FILES:= \
-	region.cpp
-
-LOCAL_SHARED_LIBRARIES := \
-	libcutils \
-	libutils \
-    libui
-
-LOCAL_MODULE:= test-region
-
-LOCAL_MODULE_TAGS := tests
-
-include $(BUILD_EXECUTABLE)
diff --git a/libs/ui/tests/region/region.cpp b/libs/ui/tests/region/region.cpp
deleted file mode 100644
index 6347294..0000000
--- a/libs/ui/tests/region/region.cpp
+++ /dev/null
@@ -1,69 +0,0 @@
-/*
- * Copyright (C) 2009 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#define LOG_TAG "Region"
-
-#include <stdio.h>
-#include <utils/Debug.h>
-#include <ui/Rect.h>
-#include <ui/Region.h>
-
-using namespace android;
-
-int main()
-{
-    Region empty;
-    Region reg0( Rect(  0, 0,  100, 100 ) );
-    Region reg1 = reg0;
-    Region reg2, reg3;
-
-    Region reg4 = empty | reg1;
-    Region reg5 = reg1 | empty;
-
-    reg4.dump("reg4");
-    reg5.dump("reg5");
-    
-    reg0.dump("reg0");
-    reg1.dump("reg1");
-
-    reg0 = reg0 | reg0.translate(150, 0);
-    reg0.dump("reg0");
-    reg1.dump("reg1");
-
-    reg0 = reg0 | reg0.translate(300, 0);
-    reg0.dump("reg0");
-    reg1.dump("reg1");
-
-    //reg2 = reg0 | reg0.translate(0, 100);
-    //reg0.dump("reg0");
-    //reg1.dump("reg1");
-    //reg2.dump("reg2");
-
-    //reg3 = reg0 | reg0.translate(0, 150);
-    //reg0.dump("reg0");
-    //reg1.dump("reg1");
-    //reg2.dump("reg2");
-    //reg3.dump("reg3");
-
-    ALOGD("---");
-    reg2 = reg0 | reg0.translate(100, 0);
-    reg0.dump("reg0");
-    reg1.dump("reg1");
-    reg2.dump("reg2");
-    
-    return 0;
-}
-