source: libcaca/trunk/caca/dirty.c @ 3580

Last change on this file since 3580 was 3580, checked in by Sam Hocevar, 11 years ago

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

  • Property svn:keywords set to Id
File size: 10.4 KB
Line 
1/*
2 *  libcaca       Colour ASCII-Art library
3 *  Copyright (c) 2002-2009 Sam Hocevar <sam@hocevar.net>
4 *                All Rights Reserved
5 *
6 *  $Id: dirty.c 3580 2009-07-26 16:20:31Z sam $
7 *
8 *  This library is free software. It comes without any warranty, to
9 *  the extent permitted by applicable law. You can redistribute it
10 *  and/or modify it under the terms of the Do What The Fuck You Want
11 *  To Public License, Version 2, as published by Sam Hocevar. See
12 *  http://sam.zoy.org/wtfpl/COPYING for more details.
13 */
14
15/*
16 *  This file contains the dirty rectangle handling functions.
17 *
18 *
19 *  About dirty rectangles:
20 *
21 *  * Dirty rectangles MUST NOT be larger than the canvas. If the user
22 *  provides a large rectangle through caca_add_dirty_rect(), or if the
23 *  canvas changes size to become smaller, all dirty rectangles MUST
24 *  immediately be clipped to the canvas size.
25 */
26
27#include "config.h"
28
29#if !defined(__KERNEL__)
30#   include <stdio.h>
31#   include <string.h>
32#endif
33
34#include "caca.h"
35#include "caca_internals.h"
36
37static void merge_new_rect(caca_canvas_t *cv, int n);
38
39/** \brief Get the number of dirty rectangles in the canvas.
40 *
41 *  Get the number of dirty rectangles in a canvas. Dirty rectangles are
42 *  areas that contain cells that have changed since the last reset.
43 *
44 *  The dirty rectangles are used internally by display drivers to optimise
45 *  rendering by avoiding to redraw the whole screen. Once the display driver
46 *  has rendered the canvas, it resets the dirty rectangle list.
47 *
48 *  Dirty rectangles are guaranteed not to overlap.
49 *
50 *  This function never fails.
51 *
52 *  \param cv A libcaca canvas.
53 *  \return The number of dirty rectangles in the given canvas.
54 */
55int caca_get_dirty_rect_count(caca_canvas_t *cv)
56{
57    return cv->ndirty;
58}
59
60/** \brief Get a canvas's dirty rectangle.
61 *
62 *  Get the canvas's given dirty rectangle coordinates. The index must be
63 *  within the dirty rectangle count. See caca_get_dirty_rect_count()
64 *  for how to compute this count.
65 *
66 *  If an error occurs, no coordinates are written in the pointer arguments,
67 *  -1 is returned and \b errno is set accordingly:
68 *  - \c EINVAL Specified rectangle index is out of bounds.
69 *
70 *  \param cv A libcaca canvas.
71 *  \param r The requested rectangle index.
72 *  \param x A pointer to an integer where the leftmost edge of the
73 *           dirty rectangle will be stored.
74 *  \param y A pointer to an integer where the topmost edge of the
75 *           dirty rectangle will be stored.
76 *  \param width A pointer to an integer where the width of the
77 *               dirty rectangle will be stored.
78 *  \param height A pointer to an integer where the height of the
79 *                dirty rectangle will be stored.
80 *  \return 0 in case of success, -1 if an error occurred.
81 */
82int caca_get_dirty_rect(caca_canvas_t *cv, int r,
83                        int *x, int *y, int *width, int *height)
84{
85    if(r < 0 || r >= cv->ndirty)
86    {
87        seterrno(EINVAL);
88        return -1;
89    }
90
91    *x = cv->dirty[r].xmin;
92    *y = cv->dirty[r].ymin;
93    *width = cv->dirty[r].xmax - cv->dirty[r].xmin + 1;
94    *height = cv->dirty[r].ymax - cv->dirty[r].ymin + 1;
95
96    debug("dirty #%i: %ix%i at (%i,%i)", r, *width, *height, *x, *y);
97
98    return 0;
99}
100
101/** \brief Add an area to the canvas's dirty rectangle list.
102 *
103 *  Add an invalidating zone to the canvas's dirty rectangle list. For more
104 *  information about the dirty rectangles, see caca_get_dirty_rect().
105 *
106 *  This function may be useful to force refresh of a given zone of the
107 *  canvas even if the dirty rectangle tracking indicates that it is
108 *  unchanged. This may happen if the canvas contents were somewhat
109 *  directly modified.
110 *
111 *  If an error occurs, -1 is returned and \b errno is set accordingly:
112 *  - \c EINVAL Specified rectangle coordinates are out of bounds.
113 *
114 *  \param cv A libcaca canvas.
115 *  \param x The leftmost edge of the additional dirty rectangle.
116 *  \param y The topmost edge of the additional dirty rectangle.
117 *  \param width The width of the additional dirty rectangle.
118 *  \param height The height of the additional dirty rectangle.
119 *  \return 0 in case of success, -1 if an error occurred.
120 */
121int caca_add_dirty_rect(caca_canvas_t *cv, int x, int y, int width, int height)
122{
123    debug("new dirty: %ix%i at (%i,%i)", width, height, x, y);
124
125    /* Clip arguments to canvas */
126    if(x < 0) { width += x; x = 0; }
127
128    if(x + width > cv->width)
129        width = cv->width - x;
130
131    if(y < 0) { height += y; y = 0; }
132
133    if(y + height > cv->height)
134        height = cv->height - y;
135
136    /* Ignore empty and out-of-canvas rectangles */
137    if(width <= 0 || height <= 0)
138    {
139        seterrno(EINVAL);
140        return -1;
141    }
142
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);
154
155    return 0;
156}
157
158/** \brief Remove an area from the dirty rectangle list.
159 *
160 *  Mark a cell area in the canvas as not dirty. For more information about
161 *  the dirty rectangles, see caca_get_dirty_rect().
162 *
163 *  Values such that \b xmin > \b xmax or \b ymin > \b ymax indicate that
164 *  the dirty rectangle is empty. They will be silently ignored.
165 *
166 *  If an error occurs, -1 is returned and \b errno is set accordingly:
167 *  - \c EINVAL Specified rectangle coordinates are out of bounds.
168 *
169 *  \param cv A libcaca canvas.
170 *  \param x The leftmost edge of the clean rectangle.
171 *  \param y The topmost edge of the clean rectangle.
172 *  \param width The width of the clean rectangle.
173 *  \param height The height of the clean rectangle.
174 *  \return 0 in case of success, -1 if an error occurred.
175 */
176int caca_remove_dirty_rect(caca_canvas_t *cv, int x, int y,
177                           int width, int height)
178{
179    /* Clip arguments to canvas size */
180    if(x < 0) { width += x; x = 0; }
181
182    if(x + width > cv->width)
183        width = cv->width - x;
184
185    if(y < 0) { height += y; y = 0; }
186
187    if(y + height > cv->height)
188        height = cv->height - y;
189
190    /* Ignore empty and out-of-canvas rectangles */
191    if(width <= 0 || height <= 0)
192    {
193        seterrno(EINVAL);
194        return -1;
195    }
196
197    /* FIXME: implement this function. It's OK to have it do nothing,
198     * since we take a conservative approach in dirty rectangle handling,
199     * but we ought to help the rendering eventually. */
200
201    return 0;
202}
203
204/** \brief Clear a canvas's dirty rectangle list.
205 *
206 *  Empty the canvas's dirty rectangle list.
207 *
208 *  This function never fails.
209 *
210 *  \param cv A libcaca canvas.
211 *  \return This function always returns 0.
212 */
213int caca_clear_dirty_rect_list(caca_canvas_t *cv)
214{
215    cv->ndirty = 0;
216
217    return 0;
218}
219
220/*
221 * XXX: the following functions are local.
222 */
223
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
318/* Clip all dirty rectangles in case they're larger than the canvas */
319void _caca_clip_dirty_rect_list(caca_canvas_t *cv)
320{
321    int i;
322
323    for(i = 0; i < cv->ndirty; i++)
324    {
325        if(cv->dirty[i].xmin < 0)
326            cv->dirty[i].xmin = 0;
327
328        if(cv->dirty[i].ymin < 0)
329            cv->dirty[i].ymin = 0;
330
331        if(cv->dirty[i].xmax >= cv->width)
332            cv->dirty[i].xmax = cv->width - 1;
333
334        if(cv->dirty[i].ymax >= cv->height)
335            cv->dirty[i].ymax = cv->height - 1;
336    }
337}
338
Note: See TracBrowser for help on using the repository browser.