Changeset 3580 for libcaca


Ignore:
Timestamp:
Jul 26, 2009, 6:20:31 PM (10 years ago)
Author:
Sam Hocevar
Message:

More complex dirty rectangle merging strategy. It's a lot slower in some
cases, but that can be fixed.

Location:
libcaca/trunk/caca
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • libcaca/trunk/caca/caca_internals.h

    r3570 r3580  
    2424#if !defined(_DOXYGEN_SKIP_ME)
    2525#   define EVENTBUF_LEN 10
    26 #   define MAX_DIRTY_COUNT 1
     26#   define MAX_DIRTY_COUNT 8
    2727#endif
    2828
     
    6464    struct
    6565    {
    66         int xmin, xmax, ymin, ymax;
     66        int xmin, ymin, xmax, ymax;
    6767    }
    68     dirty[MAX_DIRTY_COUNT];
     68    dirty[MAX_DIRTY_COUNT + 1];
    6969
    7070    /* Shortcut to the active frame information */
  • libcaca/trunk/caca/dirty.c

    r3574 r3580  
    2929#if !defined(__KERNEL__)
    3030#   include <stdio.h>
     31#   include <string.h>
    3132#endif
    3233
    3334#include "caca.h"
    3435#include "caca_internals.h"
     36
     37static void merge_new_rect(caca_canvas_t *cv, int n);
    3538
    3639/** \brief Get the number of dirty rectangles in the canvas.
     
    9194    *height = cv->dirty[r].ymax - cv->dirty[r].ymin + 1;
    9295
    93     debug("dirty #%i: %ix%i at (%i,%i)\n", r, *width, *height, *x, *y);
     96    debug("dirty #%i: %ix%i at (%i,%i)", r, *width, *height, *x, *y);
    9497
    9598    return 0;
     
    118121int caca_add_dirty_rect(caca_canvas_t *cv, int x, int y, int width, int height)
    119122{
    120     debug("new dirty: %ix%i at (%i,%i)\n", width, height, x, y);
     123    debug("new dirty: %ix%i at (%i,%i)", width, height, x, y);
    121124
    122125    /* Clip arguments to canvas */
     
    138141    }
    139142
    140     /* Add dirty rectangle to list. Current strategy: if there is room
    141      * for rectangles, just append it to the list. Otherwise, merge the
    142      * new rectangle with the first in the list. */
    143     if(cv->ndirty < MAX_DIRTY_COUNT)
    144     {
    145         cv->dirty[cv->ndirty].xmin = x;
    146         cv->dirty[cv->ndirty].xmax = x + width - 1;
    147         cv->dirty[cv->ndirty].ymin = y;
    148         cv->dirty[cv->ndirty].ymax = y + height - 1;
    149         cv->ndirty++;
    150     }
    151     else
    152     {
    153         /* FIXME We may get overlapping rectangles like this */
    154         if(x < cv->dirty[0].xmin)
    155             cv->dirty[0].xmin = x;
    156         if(x + width - 1 > cv->dirty[0].xmax)
    157             cv->dirty[0].xmax = x + width - 1;
    158         if(y < cv->dirty[0].ymin)
    159             cv->dirty[0].ymin = y;
    160         if(y + height - 1 > cv->dirty[0].ymax)
    161             cv->dirty[0].ymax = y + height - 1;
    162     }
     143    /* Add the new rectangle to the list; it works even if cv->ndirty
     144     * is MAX_DIRTY_COUNT because there's an extra cell in the array. */
     145    cv->dirty[cv->ndirty].xmin = x;
     146    cv->dirty[cv->ndirty].ymin = y;
     147    cv->dirty[cv->ndirty].xmax = x + width - 1;
     148    cv->dirty[cv->ndirty].ymax = y + height - 1;
     149    cv->ndirty++;
     150
     151    /* Try to merge the new rectangle with existing ones. This also ensures
     152     * that cv->ndirty is brought back below MAX_DIRTY_COUNT. */
     153    merge_new_rect(cv, cv->ndirty - 1);
    163154
    164155    return 0;
     
    231222 */
    232223
     224static inline int int_min(int a, int b) { return a < b ? a : b; }
     225static inline int int_max(int a, int b) { return a > b ? a : b; }
     226
     227/* Merge a newly added rectangle, if necessary. */
     228static void merge_new_rect(caca_canvas_t *cv, int n)
     229{
     230    int wasted[MAX_DIRTY_COUNT + 1];
     231    int i, sn, best, best_score;
     232
     233    best = -1;
     234    best_score = cv->width * cv->height;
     235
     236    sn = (cv->dirty[n].xmax - cv->dirty[n].xmin + 1)
     237           * (cv->dirty[n].ymax - cv->dirty[n].ymin + 1);
     238
     239    /* Check whether the new rectangle can be merged with an existing one. */
     240    for(i = 0; i < cv->ndirty; i++)
     241    {
     242        int si, sf, xmin, ymin, xmax, ymax;
     243
     244        if(i == n)
     245            continue;
     246
     247        xmin = int_min(cv->dirty[i].xmin, cv->dirty[n].xmin);
     248        ymin = int_min(cv->dirty[i].ymin, cv->dirty[n].ymin);
     249        xmax = int_max(cv->dirty[i].xmax, cv->dirty[n].xmax);
     250        ymax = int_max(cv->dirty[i].ymax, cv->dirty[n].ymax);
     251
     252        sf = (xmax - xmin + 1) * (ymax - ymin + 1);
     253
     254        /* Shortcut: if the current rectangle is inside the new rectangle,
     255         * we remove the current rectangle and continue trying merges. */
     256        if(sf == sn)
     257        {
     258            memmove(&cv->dirty[i], &cv->dirty[i + 1],
     259                    (cv->ndirty - i) * sizeof(cv->dirty[0]));
     260            cv->ndirty--;
     261
     262            if(i < n)
     263                n--;
     264            else
     265                i--;
     266
     267            continue;
     268        }
     269
     270        si = (cv->dirty[i].xmax - cv->dirty[i].xmin + 1)
     271               * (cv->dirty[i].ymax - cv->dirty[i].ymin + 1);
     272
     273        /* Shortcut: if the new rectangle is inside the current rectangle,
     274         * we get rid of the new rectangle and bail out. */
     275        if(sf == si)
     276        {
     277            cv->ndirty--;
     278            memmove(&cv->dirty[n], &cv->dirty[n + 1],
     279                    (cv->ndirty - n) * sizeof(cv->dirty[0]));
     280            return;
     281        }
     282
     283        /* We store approximately how many bytes were wasted. FIXME: this is
     284         * not an exact computation, we need to be more precise. */
     285        wasted[i] = sf - si - sn;
     286
     287        if(wasted[i] < best_score)
     288        {
     289             best = i;
     290             best_score = wasted[i];
     291        }
     292    }
     293
     294    /* FIXME: we only try to merge the current rectangle, ignoring
     295     * potentially better merges. */
     296
     297    /* If no acceptable score was found and the dirty rectangle list is
     298     * not full, we bail out. */
     299    if(best_score > 0 && cv->ndirty < MAX_DIRTY_COUNT)
     300        return;
     301
     302    /* Otherwise, merge the rectangle with the best candidate */
     303    cv->dirty[best].xmin = int_min(cv->dirty[best].xmin, cv->dirty[n].xmin);
     304    cv->dirty[best].ymin = int_min(cv->dirty[best].ymin, cv->dirty[n].ymin);
     305    cv->dirty[best].xmax = int_max(cv->dirty[best].xmax, cv->dirty[n].xmax);
     306    cv->dirty[best].ymax = int_max(cv->dirty[best].ymax, cv->dirty[n].ymax);
     307
     308    memmove(&cv->dirty[n], &cv->dirty[n + 1],
     309            (cv->ndirty - n) * sizeof(cv->dirty[0]));
     310    cv->ndirty--;
     311
     312    if(best < n)
     313        merge_new_rect(cv, best);
     314    else
     315        merge_new_rect(cv, best - 1);
     316}
     317
    233318/* Clip all dirty rectangles in case they're larger than the canvas */
    234319void _caca_clip_dirty_rect_list(caca_canvas_t *cv)
Note: See TracChangeset for help on using the changeset viewer.