Changeset 8b1ce56 in mainline

Timestamp:

2019-11-21T13:45:43Z (5 years ago)

Author:

Jiri Svoboda <jiri@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

670cfcf

Parents:

bf22cb78

git-author:

Jiri Svoboda <jiri@…> (2019-11-20 18:45:40)

git-committer:

Jiri Svoboda <jiri@…> (2019-11-21 13:45:43)

Message:

Computing rectangle envelope

Useful for tracking changed areas, for example.

Location:

uspace/lib/gfx

Files:

• include/gfx/coord.h (modified) (1 diff)
• src/coord.c (modified) (3 diffs)
• test/coord.c (modified) (1 diff)

uspace/lib/gfx/include/gfx/coord.h

@@ -37 +37 @@
 #define _GFX_COORD_H
 
+#include <stdbool.h>
 #include <types/gfx/coord.h>
 
 extern void gfx_coord2_add(gfx_coord2_t *, gfx_coord2_t *, gfx_coord2_t *);
 extern void gfx_coord2_subtract(gfx_coord2_t *, gfx_coord2_t *, gfx_coord2_t *);
+extern void gfx_span_points_sort(gfx_coord_t, gfx_coord_t, gfx_coord_t *,
+    gfx_coord_t *);
 extern void gfx_rect_translate(gfx_coord2_t *, gfx_rect_t *, gfx_rect_t *);
+extern void gfx_rect_envelope(gfx_rect_t *, gfx_rect_t *, gfx_rect_t *);
+extern void gfx_rect_points_sort(gfx_rect_t *, gfx_rect_t *);
+extern bool gfx_rect_is_empty(gfx_rect_t *);
 
 #endif

uspace/lib/gfx/src/coord.c

@@ -35 +35 @@
 
 #include <gfx/coord.h>
+#include <macros.h>
+#include <stdbool.h>
 
 /** Add two vectors.
@@ -60 +62 @@
 }
 
+/** Sort points of a span.
+ *
+ * Sort the begin and end points so that the begin point has the lower
+ * coordinate (i.e. if needed, the span is transposed, if not, it is simply
+ * copied).
+ *
+ * @param s0 Source span start point
+ * @param s1 Source span end point
+ * @param d0 Destination span start point
+ * @param d1 Destination span end point
+ */
+void gfx_span_points_sort(gfx_coord_t s0, gfx_coord_t s1, gfx_coord_t *d0,
+    gfx_coord_t *d1)
+{
+        if (s0 <= s1) {
+                *d0 = s0;
+                *d1 = s1;
+        } else {
+                *d0 = s1 + 1;
+                *d1 = s0 + 1;
+        }
+}
+
 /** Move (translate) rectangle.
  *
@@ -72 +97 @@
 }
 
+/** Compute envelope of two rectangles.
+ *
+ * Envelope is the minimal rectangle covering all pixels of both rectangles.
+ */
+void gfx_rect_envelope(gfx_rect_t *a, gfx_rect_t *b, gfx_rect_t *dest)
+{
+        gfx_rect_t sa, sb;
+
+        if (gfx_rect_is_empty(a)) {
+                *dest = *b;
+                return;
+        }
+
+        if (gfx_rect_is_empty(b)) {
+                *dest = *a;
+                return;
+        }
+
+        /* a and b are both non-empty */
+
+        gfx_rect_points_sort(a, &sa);
+        gfx_rect_points_sort(b, &sb);
+
+        dest->p0.x = min(sa.p0.x, sb.p0.x);
+        dest->p0.y = min(sa.p0.y, sb.p0.y);
+        dest->p1.x = max(sa.p1.x, sb.p1.x);
+        dest->p1.y = max(sa.p1.y, sb.p1.y);
+}
+
+/** Sort points of a rectangle.
+ *
+ * Shuffle around coordinates of a rectangle so that p0.x < p1.x and
+ * p0.y < p0.y.
+ *
+ * @param src Source rectangle
+ * @param dest Destination (sorted) rectangle
+ */
+void gfx_rect_points_sort(gfx_rect_t *src, gfx_rect_t *dest)
+{
+        gfx_span_points_sort(src->p0.x, src->p1.x, &dest->p0.x, &dest->p1.x);
+        gfx_span_points_sort(src->p0.y, src->p1.y, &dest->p0.y, &dest->p1.y);
+}
+
+/** Determine if rectangle contains no pixels
+ *
+ * @param rect Rectangle
+ * @return @c true iff rectangle contains no pixels
+ */
+bool gfx_rect_is_empty(gfx_rect_t *rect)
+{
+        return rect->p0.x == rect->p1.x || rect->p0.y == rect->p1.y;
+}
+
 /** @}
  */

uspace/lib/gfx/test/coord.c

@@ -95 +95 @@
 }
 
+/** Sorting span with lower start and higher end point results in the same span. */
+PCUT_TEST(span_points_sort_asc)
+{
+        gfx_coord_t a, b;
+
+        gfx_span_points_sort(1, 2, &a, &b);
+        PCUT_ASSERT_EQUALS(1, a);
+        PCUT_ASSERT_EQUALS(2, b);
+}
+
+/** Sorting span with same start and end point results in the same span. */
+PCUT_TEST(span_points_sort_equal)
+{
+        gfx_coord_t a, b;
+
+        gfx_span_points_sort(1, 1, &a, &b);
+        PCUT_ASSERT_EQUALS(1, a);
+        PCUT_ASSERT_EQUALS(1, b);
+}
+
+/** Sorting span with hight start and lower end point results in transposed span. */
+PCUT_TEST(span_points_sort_decs)
+{
+        gfx_coord_t a, b;
+
+        gfx_span_points_sort(1, 0, &a, &b);
+        PCUT_ASSERT_EQUALS(1, a);
+        PCUT_ASSERT_EQUALS(2, b);
+}
+
+/** Rectangle envelope with first rectangle empty should return the second rectangle. */
+PCUT_TEST(rect_envelope_a_empty)
+{
+        gfx_rect_t a;
+        gfx_rect_t b;
+        gfx_rect_t e;
+
+        a.p0.x = 0;
+        a.p0.y = 0;
+        a.p1.x = 0;
+        a.p1.y = 0;
+
+        b.p0.x = 1;
+        b.p0.y = 2;
+        b.p1.x = 3;
+        b.p1.y = 4;
+
+        gfx_rect_envelope(&a, &b, &e);
+        PCUT_ASSERT_EQUALS(1, e.p0.x);
+        PCUT_ASSERT_EQUALS(2, e.p0.y);
+        PCUT_ASSERT_EQUALS(3, e.p1.x);
+        PCUT_ASSERT_EQUALS(4, e.p1.y);
+}
+
+/** Rectangle envelope with second rectangle empty should return the first rectangle. */
+PCUT_TEST(rect_envelope_b_empty)
+{
+        gfx_rect_t a;
+        gfx_rect_t b;
+        gfx_rect_t e;
+
+        a.p0.x = 1;
+        a.p0.y = 2;
+        a.p1.x = 3;
+        a.p1.y = 4;
+
+        b.p0.x = 0;
+        b.p0.y = 0;
+        b.p1.x = 0;
+        b.p1.y = 0;
+
+        gfx_rect_envelope(&a, &b, &e);
+        PCUT_ASSERT_EQUALS(1, e.p0.x);
+        PCUT_ASSERT_EQUALS(2, e.p0.y);
+        PCUT_ASSERT_EQUALS(3, e.p1.x);
+        PCUT_ASSERT_EQUALS(4, e.p1.y);
+}
+
+/** Rectangle envelope, a has both coordinates lower than b */
+PCUT_TEST(rect_envelope_nonempty_a_lt_b)
+{
+        gfx_rect_t a;
+        gfx_rect_t b;
+        gfx_rect_t e;
+
+        a.p0.x = 1;
+        a.p0.y = 2;
+        a.p1.x = 3;
+        a.p1.y = 4;
+
+        b.p0.x = 5;
+        b.p0.y = 6;
+        b.p1.x = 7;
+        b.p1.y = 8;
+
+        gfx_rect_envelope(&a, &b, &e);
+        PCUT_ASSERT_EQUALS(1, e.p0.x);
+        PCUT_ASSERT_EQUALS(2, e.p0.y);
+        PCUT_ASSERT_EQUALS(7, e.p1.x);
+        PCUT_ASSERT_EQUALS(8, e.p1.y);
+}
+
+/** Rectangle envelope, a has both coordinates higher than b */
+PCUT_TEST(rect_envelope_nonempty_a_gt_b)
+{
+        gfx_rect_t a;
+        gfx_rect_t b;
+        gfx_rect_t e;
+
+        a.p0.x = 5;
+        a.p0.y = 6;
+        a.p1.x = 7;
+        a.p1.y = 8;
+
+        b.p0.x = 1;
+        b.p0.y = 2;
+        b.p1.x = 3;
+        b.p1.y = 4;
+
+        gfx_rect_envelope(&a, &b, &e);
+        PCUT_ASSERT_EQUALS(1, e.p0.x);
+        PCUT_ASSERT_EQUALS(2, e.p0.y);
+        PCUT_ASSERT_EQUALS(7, e.p1.x);
+        PCUT_ASSERT_EQUALS(8, e.p1.y);
+}
+
+/** Rectangle envelope, a is inside b */
+PCUT_TEST(rect_envelope_nonempty_a_inside_b)
+{
+        gfx_rect_t a;
+        gfx_rect_t b;
+        gfx_rect_t e;
+
+        a.p0.x = 1;
+        a.p0.y = 2;
+        a.p1.x = 7;
+        a.p1.y = 8;
+
+        b.p0.x = 3;
+        b.p0.y = 4;
+        b.p1.x = 5;
+        b.p1.y = 6;
+
+        gfx_rect_envelope(&a, &b, &e);
+        PCUT_ASSERT_EQUALS(1, e.p0.x);
+        PCUT_ASSERT_EQUALS(2, e.p0.y);
+        PCUT_ASSERT_EQUALS(7, e.p1.x);
+        PCUT_ASSERT_EQUALS(8, e.p1.y);
+}
+
+/** Rectangle envelope, b is inside a*/
+PCUT_TEST(rect_envelope_nonempty_b_inside_a)
+{
+        gfx_rect_t a;
+        gfx_rect_t b;
+        gfx_rect_t e;
+
+        a.p0.x = 3;
+        a.p0.y = 4;
+        a.p1.x = 5;
+        a.p1.y = 6;
+
+        b.p0.x = 1;
+        b.p0.y = 2;
+        b.p1.x = 7;
+        b.p1.y = 8;
+
+        gfx_rect_envelope(&a, &b, &e);
+        PCUT_ASSERT_EQUALS(1, e.p0.x);
+        PCUT_ASSERT_EQUALS(2, e.p0.y);
+        PCUT_ASSERT_EQUALS(7, e.p1.x);
+        PCUT_ASSERT_EQUALS(8, e.p1.y);
+}
+
+/** Rectangle envelope, a and b cross */
+PCUT_TEST(rect_envelope_nonempty_a_crosses_b)
+{
+        gfx_rect_t a;
+        gfx_rect_t b;
+        gfx_rect_t e;
+
+        a.p0.x = 1;
+        a.p0.y = 2;
+        a.p1.x = 4;
+        a.p1.y = 3;
+
+        b.p0.x = 2;
+        b.p0.y = 1;
+        b.p1.x = 3;
+        b.p1.y = 4;
+
+        gfx_rect_envelope(&a, &b, &e);
+        PCUT_ASSERT_EQUALS(1, e.p0.x);
+        PCUT_ASSERT_EQUALS(1, e.p0.y);
+        PCUT_ASSERT_EQUALS(4, e.p1.x);
+        PCUT_ASSERT_EQUALS(4, e.p1.y);
+}
+
+/** Sort span points that are already sorted should produde indentical points */
+PCUT_TEST(rect_points_sort_sorted)
+{
+        gfx_coord_t s0, s1;
+
+        gfx_span_points_sort(1, 2, &s0, &s1);
+        PCUT_ASSERT_EQUALS(1, s0);
+        PCUT_ASSERT_EQUALS(2, s1);
+}
+
+/** Sort span points that are reversed should transpose them */
+PCUT_TEST(rect_points_sort_reversed)
+{
+        gfx_coord_t s0, s1;
+
+        gfx_span_points_sort(2, 1, &s0, &s1);
+        PCUT_ASSERT_EQUALS(2, s0);
+        PCUT_ASSERT_EQUALS(3, s1);
+}
+
+/** gfx_rect_is_empty for straight rectangle with zero columns returns true */
+PCUT_TEST(rect_is_empty_pos_x)
+{
+        gfx_rect_t rect;
+
+        rect.p0.x = 1;
+        rect.p0.y = 2;
+        rect.p1.x = 1;
+        rect.p1.y = 3;
+        PCUT_ASSERT_TRUE(gfx_rect_is_empty(&rect));
+}
+
+/** gfx_rect_is_empty for straight rectangle with zero rows returns true */
+PCUT_TEST(rect_is_empty_pos_y)
+{
+        gfx_rect_t rect;
+
+        rect.p0.x = 1;
+        rect.p0.y = 2;
+        rect.p1.x = 2;
+        rect.p1.y = 2;
+        PCUT_ASSERT_TRUE(gfx_rect_is_empty(&rect));
+}
+
+/** gfx_rect_is_empty for staright non-empty rectangle returns false */
+PCUT_TEST(rect_is_empty_neg)
+{
+        gfx_rect_t rect;
+
+        rect.p0.x = 1;
+        rect.p0.y = 2;
+        rect.p1.x = 2;
+        rect.p1.y = 3;
+        PCUT_ASSERT_FALSE(gfx_rect_is_empty(&rect));
+}
+
+/** gfx_rect_is_empty for reverse non-empty rectangle returns false */
+PCUT_TEST(rect_is_empty_reverse_neg)
+{
+        gfx_rect_t rect;
+
+        rect.p0.x = 1;
+        rect.p0.y = 2;
+        rect.p1.x = 0;
+        rect.p1.y = 1;
+        PCUT_ASSERT_FALSE(gfx_rect_is_empty(&rect));
+}
+
 PCUT_EXPORT(coord);