Index: uspace/lib/gfx/include/gfx/coord.h =================================================================== --- uspace/lib/gfx/include/gfx/coord.h (revision 7b882c1fb956e7997643c445ef2c7aed9e2891ff) +++ uspace/lib/gfx/include/gfx/coord.h (revision 879d7245cbdc281f61fa2ce307ec595f296867ac) @@ -37,9 +37,15 @@ #define _GFX_COORD_H +#include #include 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 Index: uspace/lib/gfx/src/coord.c =================================================================== --- uspace/lib/gfx/src/coord.c (revision 7b882c1fb956e7997643c445ef2c7aed9e2891ff) +++ uspace/lib/gfx/src/coord.c (revision 879d7245cbdc281f61fa2ce307ec595f296867ac) @@ -35,4 +35,6 @@ #include +#include +#include /** Add two vectors. @@ -60,4 +62,27 @@ } +/** 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,4 +97,57 @@ } +/** 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; +} + /** @} */ Index: uspace/lib/gfx/test/coord.c =================================================================== --- uspace/lib/gfx/test/coord.c (revision 7b882c1fb956e7997643c445ef2c7aed9e2891ff) +++ uspace/lib/gfx/test/coord.c (revision 879d7245cbdc281f61fa2ce307ec595f296867ac) @@ -95,3 +95,269 @@ } +/** 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);