← Back to branch summary

~oem-solutions-group/unity-2d/clutter-1.0

« back to all changes in this revision

Viewing changes to clutter/cogl/cogl/cogl-atlas.c

  • Committer: Bazaar Package Importer
  • Author(s): Emilio Pozuelo Monfort
  • Date: 2010-03-21 13:27:56 UTC
  • mto: (2.1.3 experimental)
  • mto: This revision was merged to the branch mainline in revision 8.
  • Revision ID: james.westby@ubuntu.com-20100321132756-nf8yd30yxo3zzwcm
Tags: upstream-1.2.2
Import upstream version 1.2.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
clutter/cogl/cogl/cogl-atlas.c
 
1
/*
 
2
 * Cogl
 
3
 *
 
4
 * An object oriented GL/GLES Abstraction/Utility Layer
 
5
 *
 
6
 * Copyright (C) 2009 Intel Corporation.
 
7
 *
 
8
 * This library is free software; you can redistribute it and/or
 
9
 * modify it under the terms of the GNU Lesser General Public
 
10
 * License as published by the Free Software Foundation; either
 
11
 * version 2 of the License, or (at your option) any later version.
 
12
 *
 
13
 * This library is distributed in the hope that it will be useful,
 
14
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
15
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
16
 * Lesser General Public License for more details.
 
17
 *
 
18
 * You should have received a copy of the GNU Lesser General Public
 
19
 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
 
20
 *
 
21
 *
 
22
 *
 
23
 * Authors:
 
24
 *  Neil Roberts   <neil@linux.intel.com>
 
25
 */
 
26
 
 
27
#ifdef HAVE_CONFIG_H
 
28
#include "config.h"
 
29
#endif
 
30
 
 
31
#include <glib.h>
 
32
 
 
33
#include "cogl-atlas.h"
 
34
#include "cogl-debug.h"
 
35
 
 
36
/* Implements a data structure which keeps track of unused
 
37
   sub-rectangles within a larger rectangle using a binary tree
 
38
   structure. The algorithm for this is based on the description here:
 
39
 
 
40
   http://www.blackpawn.com/texts/lightmaps/default.html
 
41
*/
 
42
 
 
43
#ifdef COGL_ENABLE_DEBUG
 
44
 
 
45
/* The cairo header is only used for debugging to generate an image of
 
46
   the atlas */
 
47
#include <cairo.h>
 
48
 
 
49
static void _cogl_atlas_dump_image (CoglAtlas *atlas);
 
50
 
 
51
#endif /* COGL_ENABLE_DEBUG */
 
52
 
 
53
typedef struct _CoglAtlasNode       CoglAtlasNode;
 
54
typedef struct _CoglAtlasStackEntry CoglAtlasStackEntry;
 
55
 
 
56
typedef void (* CoglAtlasInternalForeachCb) (CoglAtlasNode *node,
 
57
                                             gpointer data);
 
58
 
 
59
typedef enum
 
60
{
 
61
  COGL_ATLAS_BRANCH,
 
62
  COGL_ATLAS_FILLED_LEAF,
 
63
  COGL_ATLAS_EMPTY_LEAF
 
64
} CoglAtlasNodeType;
 
65
 
 
66
struct _CoglAtlas
 
67
{
 
68
  CoglAtlasNode *root;
 
69
 
 
70
  unsigned int space_remaining;
 
71
  unsigned int n_rectangles;
 
72
 
 
73
  GDestroyNotify value_destroy_func;
 
74
};
 
75
 
 
76
struct _CoglAtlasNode
 
77
{
 
78
  CoglAtlasNodeType type;
 
79
 
 
80
  CoglAtlasRectangle rectangle;
 
81
 
 
82
  CoglAtlasNode *parent;
 
83
 
 
84
  union
 
85
  {
 
86
    /* Fields used when this is a branch */
 
87
    struct
 
88
    {
 
89
      CoglAtlasNode *left;
 
90
      CoglAtlasNode *right;
 
91
    } branch;
 
92
 
 
93
    /* Field used when this is a filled leaf */
 
94
    gpointer data;
 
95
  } d;
 
96
};
 
97
 
 
98
struct _CoglAtlasStackEntry
 
99
{
 
100
  /* The node to search */
 
101
  CoglAtlasNode *node;
 
102
  /* Index of next branch of this node to explore. Basically either 0
 
103
     to go left or 1 to go right */
 
104
  gboolean next_index;
 
105
  /* Next entry in the stack */
 
106
  CoglAtlasStackEntry *next;
 
107
};
 
108
 
 
109
static CoglAtlasNode *
 
110
_cogl_atlas_node_new (void)
 
111
{
 
112
  return g_slice_new (CoglAtlasNode);
 
113
}
 
114
 
 
115
static void
 
116
_cogl_atlas_node_free (CoglAtlasNode *node)
 
117
{
 
118
  g_slice_free (CoglAtlasNode, node);
 
119
}
 
120
 
 
121
CoglAtlas *
 
122
_cogl_atlas_new (unsigned int width,
 
123
                 unsigned int height,
 
124
                 GDestroyNotify value_destroy_func)
 
125
{
 
126
  CoglAtlas *atlas = g_new (CoglAtlas, 1);
 
127
  CoglAtlasNode *root = _cogl_atlas_node_new ();
 
128
 
 
129
  root->type = COGL_ATLAS_EMPTY_LEAF;
 
130
  root->parent = NULL;
 
131
  root->rectangle.x = 0;
 
132
  root->rectangle.y = 0;
 
133
  root->rectangle.width = width;
 
134
  root->rectangle.height = height;
 
135
 
 
136
  atlas->root = root;
 
137
  atlas->space_remaining = width * height;
 
138
  atlas->n_rectangles = 0;
 
139
  atlas->value_destroy_func = value_destroy_func;
 
140
 
 
141
  return atlas;
 
142
}
 
143
 
 
144
static CoglAtlasStackEntry *
 
145
_cogl_atlas_stack_push (CoglAtlasStackEntry *stack,
 
146
                        CoglAtlasNode *node,
 
147
                        gboolean next_index)
 
148
{
 
149
  CoglAtlasStackEntry *new_entry = g_slice_new (CoglAtlasStackEntry);
 
150
 
 
151
  new_entry->node = node;
 
152
  new_entry->next_index = next_index;
 
153
  new_entry->next = stack;
 
154
 
 
155
  return new_entry;
 
156
}
 
157
 
 
158
static CoglAtlasStackEntry *
 
159
_cogl_atlas_stack_pop (CoglAtlasStackEntry *stack)
 
160
{
 
161
  CoglAtlasStackEntry *next = stack->next;
 
162
 
 
163
  g_slice_free (CoglAtlasStackEntry, stack);
 
164
 
 
165
  return next;
 
166
}
 
167
 
 
168
static CoglAtlasNode *
 
169
_cogl_atlas_node_split_horizontally (CoglAtlasNode *node,
 
170
                                     unsigned int left_width)
 
171
{
 
172
  /* Splits the node horizontally (according to emacs' definition, not
 
173
     vim) by converting it to a branch and adding two new leaf
 
174
     nodes. The leftmost branch will have the width left_width and
 
175
     will be returned. If the node is already just the right size it
 
176
     won't do anything */
 
177
 
 
178
  CoglAtlasNode *left_node, *right_node;
 
179
 
 
180
  if (node->rectangle.width == left_width)
 
181
    return node;
 
182
 
 
183
  left_node = _cogl_atlas_node_new ();
 
184
  left_node->type = COGL_ATLAS_EMPTY_LEAF;
 
185
  left_node->parent = node;
 
186
  left_node->rectangle.x = node->rectangle.x;
 
187
  left_node->rectangle.y = node->rectangle.y;
 
188
  left_node->rectangle.width = left_width;
 
189
  left_node->rectangle.height = node->rectangle.height;
 
190
  node->d.branch.left = left_node;
 
191
 
 
192
  right_node = _cogl_atlas_node_new ();
 
193
  right_node->type = COGL_ATLAS_EMPTY_LEAF;
 
194
  right_node->parent = node;
 
195
  right_node->rectangle.x = node->rectangle.x + left_width;
 
196
  right_node->rectangle.y = node->rectangle.y;
 
197
  right_node->rectangle.width = node->rectangle.width - left_width;
 
198
  right_node->rectangle.height = node->rectangle.height;
 
199
  node->d.branch.right = right_node;
 
200
 
 
201
  node->type = COGL_ATLAS_BRANCH;
 
202
 
 
203
  return left_node;
 
204
}
 
205
 
 
206
static CoglAtlasNode *
 
207
_cogl_atlas_node_split_vertically (CoglAtlasNode *node,
 
208
                                   unsigned int top_height)
 
209
{
 
210
  /* Splits the node vertically (according to emacs' definition, not
 
211
     vim) by converting it to a branch and adding two new leaf
 
212
     nodes. The topmost branch will have the height top_height and
 
213
     will be returned. If the node is already just the right size it
 
214
     won't do anything */
 
215
 
 
216
  CoglAtlasNode *top_node, *bottom_node;
 
217
 
 
218
  if (node->rectangle.height == top_height)
 
219
    return node;
 
220
 
 
221
  top_node = _cogl_atlas_node_new ();
 
222
  top_node->type = COGL_ATLAS_EMPTY_LEAF;
 
223
  top_node->parent = node;
 
224
  top_node->rectangle.x = node->rectangle.x;
 
225
  top_node->rectangle.y = node->rectangle.y;
 
226
  top_node->rectangle.width = node->rectangle.width;
 
227
  top_node->rectangle.height = top_height;
 
228
  node->d.branch.left = top_node;
 
229
 
 
230
  bottom_node = _cogl_atlas_node_new ();
 
231
  bottom_node->type = COGL_ATLAS_EMPTY_LEAF;
 
232
  bottom_node->parent = node;
 
233
  bottom_node->rectangle.x = node->rectangle.x;
 
234
  bottom_node->rectangle.y = node->rectangle.y + top_height;
 
235
  bottom_node->rectangle.width = node->rectangle.width;
 
236
  bottom_node->rectangle.height = node->rectangle.height - top_height;
 
237
  node->d.branch.right = bottom_node;
 
238
 
 
239
  node->type = COGL_ATLAS_BRANCH;
 
240
 
 
241
  return top_node;
 
242
}
 
243
 
 
244
gboolean
 
245
_cogl_atlas_add_rectangle (CoglAtlas *atlas,
 
246
                           unsigned int width,
 
247
                           unsigned int height,
 
248
                           gpointer data,
 
249
                           CoglAtlasRectangle *rectangle)
 
250
{
 
251
  /* Stack of nodes to search in */
 
252
  CoglAtlasStackEntry *node_stack;
 
253
  CoglAtlasNode *found_node = NULL;
 
254
 
 
255
  /* Zero-sized rectangles break the algorithm for removing rectangles
 
256
     so we'll disallow them */
 
257
  g_return_val_if_fail (width > 0 && height > 0, FALSE);
 
258
 
 
259
  /* Start with the root node */
 
260
  node_stack = _cogl_atlas_stack_push (NULL, atlas->root, FALSE);
 
261
 
 
262
  /* Depth-first search for an empty node that is big enough */
 
263
  while (node_stack)
 
264
    {
 
265
      /* Pop an entry off the stack */
 
266
      CoglAtlasNode *node = node_stack->node;
 
267
      int next_index = node_stack->next_index;
 
268
      node_stack = _cogl_atlas_stack_pop (node_stack);
 
269
 
 
270
      /* Regardless of the type of the node, there's no point
 
271
         descending any further if the new rectangle won't fit within
 
272
         it */
 
273
      if (node->rectangle.width >= width &&
 
274
          node->rectangle.height >= height)
 
275
        {
 
276
          if (node->type == COGL_ATLAS_EMPTY_LEAF)
 
277
            {
 
278
              /* We've found a node we can use */
 
279
              found_node = node;
 
280
              break;
 
281
            }
 
282
          else if (node->type == COGL_ATLAS_BRANCH)
 
283
            {
 
284
              if (next_index)
 
285
                /* Try the right branch */
 
286
                node_stack = _cogl_atlas_stack_push (node_stack,
 
287
                                                     node->d.branch.right,
 
288
                                                     0);
 
289
              else
 
290
                {
 
291
                  /* Make sure we remember to try the right branch once
 
292
                     we've finished descending the left branch */
 
293
                  node_stack = _cogl_atlas_stack_push (node_stack,
 
294
                                                       node,
 
295
                                                       1);
 
296
                  /* Try the left branch */
 
297
                  node_stack = _cogl_atlas_stack_push (node_stack,
 
298
                                                       node->d.branch.left,
 
299
                                                       0);
 
300
                }
 
301
            }
 
302
        }
 
303
    }
 
304
 
 
305
  /* Free the stack */
 
306
  while (node_stack)
 
307
    node_stack = _cogl_atlas_stack_pop (node_stack);
 
308
 
 
309
  if (found_node)
 
310
    {
 
311
      /* Split according to whichever axis will leave us with the
 
312
         largest space */
 
313
      if (found_node->rectangle.width - width >
 
314
          found_node->rectangle.height - height)
 
315
        {
 
316
          found_node = _cogl_atlas_node_split_horizontally (found_node, width);
 
317
          found_node = _cogl_atlas_node_split_vertically (found_node, height);
 
318
        }
 
319
      else
 
320
        {
 
321
          found_node = _cogl_atlas_node_split_vertically (found_node, height);
 
322
          found_node = _cogl_atlas_node_split_horizontally (found_node, width);
 
323
        }
 
324
 
 
325
      found_node->type = COGL_ATLAS_FILLED_LEAF;
 
326
      found_node->d.data = data;
 
327
      if (rectangle)
 
328
        *rectangle = found_node->rectangle;
 
329
 
 
330
      /* Record how much empty space is remaining after this rectangle
 
331
         is added */
 
332
      g_assert (width * height <= atlas->space_remaining);
 
333
      atlas->space_remaining -= width * height;
 
334
      atlas->n_rectangles++;
 
335
 
 
336
#ifdef COGL_ENABLE_DEBUG
 
337
      if (G_UNLIKELY (cogl_debug_flags & COGL_DEBUG_DUMP_ATLAS_IMAGE))
 
338
        _cogl_atlas_dump_image (atlas);
 
339
#endif
 
340
 
 
341
      return TRUE;
 
342
    }
 
343
  else
 
344
    return FALSE;
 
345
}
 
346
 
 
347
void
 
348
_cogl_atlas_remove_rectangle (CoglAtlas *atlas,
 
349
                              const CoglAtlasRectangle *rectangle)
 
350
{
 
351
  CoglAtlasNode *node = atlas->root;
 
352
 
 
353
  /* We can do a binary-chop down the search tree to find the rectangle */
 
354
  while (node->type == COGL_ATLAS_BRANCH)
 
355
    {
 
356
      CoglAtlasNode *left_node = node->d.branch.left;
 
357
 
 
358
      /* If and only if the rectangle is in the left node then the x,y
 
359
         position of the rectangle will be within the node's
 
360
         rectangle */
 
361
      if (rectangle->x < left_node->rectangle.x + left_node->rectangle.width &&
 
362
          rectangle->y < left_node->rectangle.y + left_node->rectangle.height)
 
363
        /* Go left */
 
364
        node = left_node;
 
365
      else
 
366
        /* Go right */
 
367
        node = node->d.branch.right;
 
368
    }
 
369
 
 
370
  /* Make sure we found the right node */
 
371
  if (node->type != COGL_ATLAS_FILLED_LEAF ||
 
372
      node->rectangle.x != rectangle->x ||
 
373
      node->rectangle.y != rectangle->y ||
 
374
      node->rectangle.width != rectangle->width ||
 
375
      node->rectangle.height != rectangle->height)
 
376
    /* This should only happen if someone tried to remove a rectangle
 
377
       that was not in the atlas so something has gone wrong */
 
378
    g_return_if_reached ();
 
379
  else
 
380
    {
 
381
      /* Convert the node back to an empty node */
 
382
      if (atlas->value_destroy_func)
 
383
        atlas->value_destroy_func (node->d.data);
 
384
      node->type = COGL_ATLAS_EMPTY_LEAF;
 
385
 
 
386
      /* Walk back up the tree combining branch nodes that have two
 
387
         empty leaves back into a single empty leaf */
 
388
      for (node = node->parent; node; node = node->parent)
 
389
        {
 
390
          /* This node is a parent so it should always be a branch */
 
391
          g_assert (node->type == COGL_ATLAS_BRANCH);
 
392
 
 
393
          if (node->d.branch.left->type == COGL_ATLAS_EMPTY_LEAF &&
 
394
              node->d.branch.right->type == COGL_ATLAS_EMPTY_LEAF)
 
395
            {
 
396
              _cogl_atlas_node_free (node->d.branch.left);
 
397
              _cogl_atlas_node_free (node->d.branch.right);
 
398
              node->type = COGL_ATLAS_EMPTY_LEAF;
 
399
            }
 
400
          else
 
401
            break;
 
402
        }
 
403
 
 
404
      /* There is now more free space and one less rectangle */
 
405
      atlas->space_remaining += rectangle->width * rectangle->height;
 
406
      g_assert (atlas->n_rectangles > 0);
 
407
      atlas->n_rectangles--;
 
408
    }
 
409
 
 
410
#ifdef COGL_ENABLE_DEBUG
 
411
  if (G_UNLIKELY (cogl_debug_flags & COGL_DEBUG_DUMP_ATLAS_IMAGE))
 
412
    _cogl_atlas_dump_image (atlas);
 
413
#endif
 
414
}
 
415
 
 
416
unsigned int
 
417
_cogl_atlas_get_width (CoglAtlas *atlas)
 
418
{
 
419
  return atlas->root->rectangle.width;
 
420
}
 
421
 
 
422
unsigned int
 
423
_cogl_atlas_get_height (CoglAtlas *atlas)
 
424
{
 
425
  return atlas->root->rectangle.height;
 
426
}
 
427
 
 
428
unsigned int
 
429
_cogl_atlas_get_remaining_space (CoglAtlas *atlas)
 
430
{
 
431
  return atlas->space_remaining;
 
432
}
 
433
 
 
434
unsigned int
 
435
_cogl_atlas_get_n_rectangles (CoglAtlas *atlas)
 
436
{
 
437
  return atlas->n_rectangles;
 
438
}
 
439
 
 
440
static void
 
441
_cogl_atlas_internal_foreach (CoglAtlas *atlas,
 
442
                              CoglAtlasInternalForeachCb callback,
 
443
                              gpointer data)
 
444
{
 
445
  /* Stack of nodes to search in */
 
446
  CoglAtlasStackEntry *node_stack;
 
447
 
 
448
  /* Start with the root node */
 
449
  node_stack = _cogl_atlas_stack_push (NULL, atlas->root, 0);
 
450
 
 
451
  /* Iterate all nodes depth-first */
 
452
  while (node_stack)
 
453
    {
 
454
      CoglAtlasNode *node = node_stack->node;
 
455
 
 
456
      switch (node->type)
 
457
        {
 
458
        case COGL_ATLAS_BRANCH:
 
459
          if (node_stack->next_index == 0)
 
460
            {
 
461
              /* Next time we come back to this node, go to the right */
 
462
              node_stack->next_index = 1;
 
463
 
 
464
              /* Explore the left branch next */
 
465
              node_stack = _cogl_atlas_stack_push (node_stack,
 
466
                                                  node->d.branch.left,
 
467
                                                  0);
 
468
            }
 
469
          else if (node_stack->next_index == 1)
 
470
            {
 
471
              /* Next time we come back to this node, stop processing it */
 
472
              node_stack->next_index = 2;
 
473
 
 
474
              /* Explore the right branch next */
 
475
              node_stack = _cogl_atlas_stack_push (node_stack,
 
476
                                                  node->d.branch.right,
 
477
                                                  0);
 
478
            }
 
479
          else
 
480
            {
 
481
              /* We're finished with this node so we can call the callback */
 
482
              callback (node, data);
 
483
              node_stack = _cogl_atlas_stack_pop (node_stack);
 
484
            }
 
485
          break;
 
486
 
 
487
        default:
 
488
          /* Some sort of leaf node, just call the callback */
 
489
          callback (node, data);
 
490
          node_stack = _cogl_atlas_stack_pop (node_stack);
 
491
          break;
 
492
        }
 
493
    }
 
494
 
 
495
  /* The stack should now be empty */
 
496
  g_assert (node_stack == NULL);
 
497
}
 
498
 
 
499
typedef struct _CoglAtlasForeachClosure
 
500
{
 
501
  CoglAtlasCallback callback;
 
502
  gpointer data;
 
503
} CoglAtlasForeachClosure;
 
504
 
 
505
static void
 
506
_cogl_atlas_foreach_cb (CoglAtlasNode *node, gpointer data)
 
507
{
 
508
  CoglAtlasForeachClosure *closure = data;
 
509
 
 
510
  if (node->type == COGL_ATLAS_FILLED_LEAF)
 
511
    closure->callback (&node->rectangle, node->d.data, closure->data);
 
512
}
 
513
 
 
514
void
 
515
_cogl_atlas_foreach (CoglAtlas *atlas,
 
516
                     CoglAtlasCallback callback,
 
517
                     gpointer data)
 
518
{
 
519
  CoglAtlasForeachClosure closure;
 
520
 
 
521
  closure.callback = callback;
 
522
  closure.data = data;
 
523
 
 
524
  _cogl_atlas_internal_foreach (atlas, _cogl_atlas_foreach_cb, &closure);
 
525
}
 
526
 
 
527
static void
 
528
_cogl_atlas_free_cb (CoglAtlasNode *node, gpointer data)
 
529
{
 
530
  CoglAtlas *atlas = data;
 
531
 
 
532
  if (node->type == COGL_ATLAS_FILLED_LEAF && atlas->value_destroy_func)
 
533
    atlas->value_destroy_func (node->d.data);
 
534
 
 
535
  _cogl_atlas_node_free (node);
 
536
}
 
537
 
 
538
void
 
539
_cogl_atlas_free (CoglAtlas *atlas)
 
540
{
 
541
  _cogl_atlas_internal_foreach (atlas, _cogl_atlas_free_cb, atlas);
 
542
  g_free (atlas);
 
543
}
 
544
 
 
545
#ifdef COGL_ENABLE_DEBUG
 
546
 
 
547
static void
 
548
_cogl_atlas_dump_image_cb (CoglAtlasNode *node, gpointer data)
 
549
{
 
550
  cairo_t *cr = data;
 
551
 
 
552
  if (node->type == COGL_ATLAS_FILLED_LEAF ||
 
553
      node->type == COGL_ATLAS_EMPTY_LEAF)
 
554
    {
 
555
      /* Fill the rectangle using a different colour depending on
 
556
         whether the rectangle is used */
 
557
      if (node->type == COGL_ATLAS_FILLED_LEAF)
 
558
        cairo_set_source_rgb (cr, 0.0, 0.0, 1.0);
 
559
      else
 
560
        cairo_set_source_rgb (cr, 0.0, 0.0, 0.0);
 
561
 
 
562
      cairo_rectangle (cr,
 
563
                       node->rectangle.x,
 
564
                       node->rectangle.y,
 
565
                       node->rectangle.width,
 
566
                       node->rectangle.height);
 
567
 
 
568
      cairo_fill_preserve (cr);
 
569
 
 
570
      /* Draw a white outline around the rectangle */
 
571
      cairo_set_source_rgb (cr, 1.0, 1.0, 1.0);
 
572
      cairo_stroke (cr);
 
573
    }
 
574
}
 
575
 
 
576
static void
 
577
_cogl_atlas_dump_image (CoglAtlas *atlas)
 
578
{
 
579
  /* This dumps a png to help visualize the atlas. Each leaf rectangle
 
580
     is drawn with a white outline. Unused leaves are filled in black
 
581
     and used leaves are blue */
 
582
 
 
583
  cairo_surface_t *surface =
 
584
    cairo_image_surface_create (CAIRO_FORMAT_RGB24,
 
585
                                _cogl_atlas_get_width (atlas),
 
586
                                _cogl_atlas_get_height (atlas));
 
587
  cairo_t *cr = cairo_create (surface);
 
588
 
 
589
  _cogl_atlas_internal_foreach (atlas, _cogl_atlas_dump_image_cb, cr);
 
590
 
 
591
  cairo_destroy (cr);
 
592
 
 
593
  cairo_surface_write_to_png (surface, "cogl-atlas-dump.png");
 
594
 
 
595
  cairo_surface_destroy (surface);
 
596
}
 
597
 
 
598
#endif /* COGL_ENABLE_DEBUG */