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
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 @@
op_xor = region_operator<Rect>::op_xor
};
+enum {
+ direction_LTR,
+ direction_RTL
+};
+
// ----------------------------------------------------------------------------
Region::Region() {
@@ -69,6 +74,133 @@
{
}
+/**
+ * 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