Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset 8b1ce56 in mainline


Ignore:
Timestamp:
2019-11-21T13:45:43Z (12 months ago)
Author:
Jiri Svoboda <jiri@…>
Branches:
master
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:
3 edited

Legend:

Unmodified
Added
Removed
  • uspace/lib/gfx/include/gfx/coord.h

    rbf22cb78 r8b1ce56  
    3737#define _GFX_COORD_H
    3838
     39#include <stdbool.h>
    3940#include <types/gfx/coord.h>
    4041
    4142extern void gfx_coord2_add(gfx_coord2_t *, gfx_coord2_t *, gfx_coord2_t *);
    4243extern void gfx_coord2_subtract(gfx_coord2_t *, gfx_coord2_t *, gfx_coord2_t *);
     44extern void gfx_span_points_sort(gfx_coord_t, gfx_coord_t, gfx_coord_t *,
     45    gfx_coord_t *);
    4346extern void gfx_rect_translate(gfx_coord2_t *, gfx_rect_t *, gfx_rect_t *);
     47extern void gfx_rect_envelope(gfx_rect_t *, gfx_rect_t *, gfx_rect_t *);
     48extern void gfx_rect_points_sort(gfx_rect_t *, gfx_rect_t *);
     49extern bool gfx_rect_is_empty(gfx_rect_t *);
    4450
    4551#endif
  • uspace/lib/gfx/src/coord.c

    rbf22cb78 r8b1ce56  
    3535
    3636#include <gfx/coord.h>
     37#include <macros.h>
     38#include <stdbool.h>
    3739
    3840/** Add two vectors.
     
    6062}
    6163
     64/** Sort points of a span.
     65 *
     66 * Sort the begin and end points so that the begin point has the lower
     67 * coordinate (i.e. if needed, the span is transposed, if not, it is simply
     68 * copied).
     69 *
     70 * @param s0 Source span start point
     71 * @param s1 Source span end point
     72 * @param d0 Destination span start point
     73 * @param d1 Destination span end point
     74 */
     75void gfx_span_points_sort(gfx_coord_t s0, gfx_coord_t s1, gfx_coord_t *d0,
     76    gfx_coord_t *d1)
     77{
     78        if (s0 <= s1) {
     79                *d0 = s0;
     80                *d1 = s1;
     81        } else {
     82                *d0 = s1 + 1;
     83                *d1 = s0 + 1;
     84        }
     85}
     86
    6287/** Move (translate) rectangle.
    6388 *
     
    7297}
    7398
     99/** Compute envelope of two rectangles.
     100 *
     101 * Envelope is the minimal rectangle covering all pixels of both rectangles.
     102 */
     103void gfx_rect_envelope(gfx_rect_t *a, gfx_rect_t *b, gfx_rect_t *dest)
     104{
     105        gfx_rect_t sa, sb;
     106
     107        if (gfx_rect_is_empty(a)) {
     108                *dest = *b;
     109                return;
     110        }
     111
     112        if (gfx_rect_is_empty(b)) {
     113                *dest = *a;
     114                return;
     115        }
     116
     117        /* a and b are both non-empty */
     118
     119        gfx_rect_points_sort(a, &sa);
     120        gfx_rect_points_sort(b, &sb);
     121
     122        dest->p0.x = min(sa.p0.x, sb.p0.x);
     123        dest->p0.y = min(sa.p0.y, sb.p0.y);
     124        dest->p1.x = max(sa.p1.x, sb.p1.x);
     125        dest->p1.y = max(sa.p1.y, sb.p1.y);
     126}
     127
     128/** Sort points of a rectangle.
     129 *
     130 * Shuffle around coordinates of a rectangle so that p0.x < p1.x and
     131 * p0.y < p0.y.
     132 *
     133 * @param src Source rectangle
     134 * @param dest Destination (sorted) rectangle
     135 */
     136void gfx_rect_points_sort(gfx_rect_t *src, gfx_rect_t *dest)
     137{
     138        gfx_span_points_sort(src->p0.x, src->p1.x, &dest->p0.x, &dest->p1.x);
     139        gfx_span_points_sort(src->p0.y, src->p1.y, &dest->p0.y, &dest->p1.y);
     140}
     141
     142/** Determine if rectangle contains no pixels
     143 *
     144 * @param rect Rectangle
     145 * @return @c true iff rectangle contains no pixels
     146 */
     147bool gfx_rect_is_empty(gfx_rect_t *rect)
     148{
     149        return rect->p0.x == rect->p1.x || rect->p0.y == rect->p1.y;
     150}
     151
    74152/** @}
    75153 */
  • uspace/lib/gfx/test/coord.c

    rbf22cb78 r8b1ce56  
    9595}
    9696
     97/** Sorting span with lower start and higher end point results in the same span. */
     98PCUT_TEST(span_points_sort_asc)
     99{
     100        gfx_coord_t a, b;
     101
     102        gfx_span_points_sort(1, 2, &a, &b);
     103        PCUT_ASSERT_EQUALS(1, a);
     104        PCUT_ASSERT_EQUALS(2, b);
     105}
     106
     107/** Sorting span with same start and end point results in the same span. */
     108PCUT_TEST(span_points_sort_equal)
     109{
     110        gfx_coord_t a, b;
     111
     112        gfx_span_points_sort(1, 1, &a, &b);
     113        PCUT_ASSERT_EQUALS(1, a);
     114        PCUT_ASSERT_EQUALS(1, b);
     115}
     116
     117/** Sorting span with hight start and lower end point results in transposed span. */
     118PCUT_TEST(span_points_sort_decs)
     119{
     120        gfx_coord_t a, b;
     121
     122        gfx_span_points_sort(1, 0, &a, &b);
     123        PCUT_ASSERT_EQUALS(1, a);
     124        PCUT_ASSERT_EQUALS(2, b);
     125}
     126
     127/** Rectangle envelope with first rectangle empty should return the second rectangle. */
     128PCUT_TEST(rect_envelope_a_empty)
     129{
     130        gfx_rect_t a;
     131        gfx_rect_t b;
     132        gfx_rect_t e;
     133
     134        a.p0.x = 0;
     135        a.p0.y = 0;
     136        a.p1.x = 0;
     137        a.p1.y = 0;
     138
     139        b.p0.x = 1;
     140        b.p0.y = 2;
     141        b.p1.x = 3;
     142        b.p1.y = 4;
     143
     144        gfx_rect_envelope(&a, &b, &e);
     145        PCUT_ASSERT_EQUALS(1, e.p0.x);
     146        PCUT_ASSERT_EQUALS(2, e.p0.y);
     147        PCUT_ASSERT_EQUALS(3, e.p1.x);
     148        PCUT_ASSERT_EQUALS(4, e.p1.y);
     149}
     150
     151/** Rectangle envelope with second rectangle empty should return the first rectangle. */
     152PCUT_TEST(rect_envelope_b_empty)
     153{
     154        gfx_rect_t a;
     155        gfx_rect_t b;
     156        gfx_rect_t e;
     157
     158        a.p0.x = 1;
     159        a.p0.y = 2;
     160        a.p1.x = 3;
     161        a.p1.y = 4;
     162
     163        b.p0.x = 0;
     164        b.p0.y = 0;
     165        b.p1.x = 0;
     166        b.p1.y = 0;
     167
     168        gfx_rect_envelope(&a, &b, &e);
     169        PCUT_ASSERT_EQUALS(1, e.p0.x);
     170        PCUT_ASSERT_EQUALS(2, e.p0.y);
     171        PCUT_ASSERT_EQUALS(3, e.p1.x);
     172        PCUT_ASSERT_EQUALS(4, e.p1.y);
     173}
     174
     175/** Rectangle envelope, a has both coordinates lower than b */
     176PCUT_TEST(rect_envelope_nonempty_a_lt_b)
     177{
     178        gfx_rect_t a;
     179        gfx_rect_t b;
     180        gfx_rect_t e;
     181
     182        a.p0.x = 1;
     183        a.p0.y = 2;
     184        a.p1.x = 3;
     185        a.p1.y = 4;
     186
     187        b.p0.x = 5;
     188        b.p0.y = 6;
     189        b.p1.x = 7;
     190        b.p1.y = 8;
     191
     192        gfx_rect_envelope(&a, &b, &e);
     193        PCUT_ASSERT_EQUALS(1, e.p0.x);
     194        PCUT_ASSERT_EQUALS(2, e.p0.y);
     195        PCUT_ASSERT_EQUALS(7, e.p1.x);
     196        PCUT_ASSERT_EQUALS(8, e.p1.y);
     197}
     198
     199/** Rectangle envelope, a has both coordinates higher than b */
     200PCUT_TEST(rect_envelope_nonempty_a_gt_b)
     201{
     202        gfx_rect_t a;
     203        gfx_rect_t b;
     204        gfx_rect_t e;
     205
     206        a.p0.x = 5;
     207        a.p0.y = 6;
     208        a.p1.x = 7;
     209        a.p1.y = 8;
     210
     211        b.p0.x = 1;
     212        b.p0.y = 2;
     213        b.p1.x = 3;
     214        b.p1.y = 4;
     215
     216        gfx_rect_envelope(&a, &b, &e);
     217        PCUT_ASSERT_EQUALS(1, e.p0.x);
     218        PCUT_ASSERT_EQUALS(2, e.p0.y);
     219        PCUT_ASSERT_EQUALS(7, e.p1.x);
     220        PCUT_ASSERT_EQUALS(8, e.p1.y);
     221}
     222
     223/** Rectangle envelope, a is inside b */
     224PCUT_TEST(rect_envelope_nonempty_a_inside_b)
     225{
     226        gfx_rect_t a;
     227        gfx_rect_t b;
     228        gfx_rect_t e;
     229
     230        a.p0.x = 1;
     231        a.p0.y = 2;
     232        a.p1.x = 7;
     233        a.p1.y = 8;
     234
     235        b.p0.x = 3;
     236        b.p0.y = 4;
     237        b.p1.x = 5;
     238        b.p1.y = 6;
     239
     240        gfx_rect_envelope(&a, &b, &e);
     241        PCUT_ASSERT_EQUALS(1, e.p0.x);
     242        PCUT_ASSERT_EQUALS(2, e.p0.y);
     243        PCUT_ASSERT_EQUALS(7, e.p1.x);
     244        PCUT_ASSERT_EQUALS(8, e.p1.y);
     245}
     246
     247/** Rectangle envelope, b is inside a*/
     248PCUT_TEST(rect_envelope_nonempty_b_inside_a)
     249{
     250        gfx_rect_t a;
     251        gfx_rect_t b;
     252        gfx_rect_t e;
     253
     254        a.p0.x = 3;
     255        a.p0.y = 4;
     256        a.p1.x = 5;
     257        a.p1.y = 6;
     258
     259        b.p0.x = 1;
     260        b.p0.y = 2;
     261        b.p1.x = 7;
     262        b.p1.y = 8;
     263
     264        gfx_rect_envelope(&a, &b, &e);
     265        PCUT_ASSERT_EQUALS(1, e.p0.x);
     266        PCUT_ASSERT_EQUALS(2, e.p0.y);
     267        PCUT_ASSERT_EQUALS(7, e.p1.x);
     268        PCUT_ASSERT_EQUALS(8, e.p1.y);
     269}
     270
     271/** Rectangle envelope, a and b cross */
     272PCUT_TEST(rect_envelope_nonempty_a_crosses_b)
     273{
     274        gfx_rect_t a;
     275        gfx_rect_t b;
     276        gfx_rect_t e;
     277
     278        a.p0.x = 1;
     279        a.p0.y = 2;
     280        a.p1.x = 4;
     281        a.p1.y = 3;
     282
     283        b.p0.x = 2;
     284        b.p0.y = 1;
     285        b.p1.x = 3;
     286        b.p1.y = 4;
     287
     288        gfx_rect_envelope(&a, &b, &e);
     289        PCUT_ASSERT_EQUALS(1, e.p0.x);
     290        PCUT_ASSERT_EQUALS(1, e.p0.y);
     291        PCUT_ASSERT_EQUALS(4, e.p1.x);
     292        PCUT_ASSERT_EQUALS(4, e.p1.y);
     293}
     294
     295/** Sort span points that are already sorted should produde indentical points */
     296PCUT_TEST(rect_points_sort_sorted)
     297{
     298        gfx_coord_t s0, s1;
     299
     300        gfx_span_points_sort(1, 2, &s0, &s1);
     301        PCUT_ASSERT_EQUALS(1, s0);
     302        PCUT_ASSERT_EQUALS(2, s1);
     303}
     304
     305/** Sort span points that are reversed should transpose them */
     306PCUT_TEST(rect_points_sort_reversed)
     307{
     308        gfx_coord_t s0, s1;
     309
     310        gfx_span_points_sort(2, 1, &s0, &s1);
     311        PCUT_ASSERT_EQUALS(2, s0);
     312        PCUT_ASSERT_EQUALS(3, s1);
     313}
     314
     315/** gfx_rect_is_empty for straight rectangle with zero columns returns true */
     316PCUT_TEST(rect_is_empty_pos_x)
     317{
     318        gfx_rect_t rect;
     319
     320        rect.p0.x = 1;
     321        rect.p0.y = 2;
     322        rect.p1.x = 1;
     323        rect.p1.y = 3;
     324        PCUT_ASSERT_TRUE(gfx_rect_is_empty(&rect));
     325}
     326
     327/** gfx_rect_is_empty for straight rectangle with zero rows returns true */
     328PCUT_TEST(rect_is_empty_pos_y)
     329{
     330        gfx_rect_t rect;
     331
     332        rect.p0.x = 1;
     333        rect.p0.y = 2;
     334        rect.p1.x = 2;
     335        rect.p1.y = 2;
     336        PCUT_ASSERT_TRUE(gfx_rect_is_empty(&rect));
     337}
     338
     339/** gfx_rect_is_empty for staright non-empty rectangle returns false */
     340PCUT_TEST(rect_is_empty_neg)
     341{
     342        gfx_rect_t rect;
     343
     344        rect.p0.x = 1;
     345        rect.p0.y = 2;
     346        rect.p1.x = 2;
     347        rect.p1.y = 3;
     348        PCUT_ASSERT_FALSE(gfx_rect_is_empty(&rect));
     349}
     350
     351/** gfx_rect_is_empty for reverse non-empty rectangle returns false */
     352PCUT_TEST(rect_is_empty_reverse_neg)
     353{
     354        gfx_rect_t rect;
     355
     356        rect.p0.x = 1;
     357        rect.p0.y = 2;
     358        rect.p1.x = 0;
     359        rect.p1.y = 1;
     360        PCUT_ASSERT_FALSE(gfx_rect_is_empty(&rect));
     361}
     362
    97363PCUT_EXPORT(coord);
Note: See TracChangeset for help on using the changeset viewer.