2 * Calculate how to pack bitmap rectangles into a larger surface
4 * Copyright 2009, 2012 Uoti Urpala
6 * This file is part of mplayer2.
8 * mplayer2 is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * mplayer2 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
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License along
19 * with mplayer2. If not, see <http://www.gnu.org/licenses/>.
24 #include <libavutil/common.h>
27 #include "bitmap_packer.h"
30 #include "sub/ass_mp.h"
31 #include "sub/dec_sub.h"
34 #define HEIGHT_SORT_BITS 4
35 static int size_index(int s
)
37 int n
= av_log2_16bit(s
);
38 return (n
<< HEIGHT_SORT_BITS
)
39 + (- 1 - (s
<< HEIGHT_SORT_BITS
>> n
) & (1 << HEIGHT_SORT_BITS
) - 1);
42 /* Pack the given rectangles into an area of size w * h.
43 * The size of each rectangle is read from in[i].x / in[i].y.
44 * The height of each rectangle must be less than 65536.
45 * 'scratch' must point to work memory for num_rects+16 ints.
46 * The packed position for rectangle number i is set in out[i].
47 * Return 0 on success, -1 if the rectangles did not fit in w*h.
49 * The rectangles are placed in rows in order approximately sorted by
50 * height (the approximate sorting is simpler than a full one would be,
51 * and allows the algorithm to work in linear time). Additionally, to
52 * reduce wasted space when there are a few tall rectangles, empty
53 * lower-right parts of rows are filled recursively when the size of
54 * rectangles in the row drops past a power-of-two threshold. So if a
55 * row starts with rectangles of size 3x50, 10x40 and 5x20 then the
56 * free rectangle with corners (13, 20)-(w, 50) is filled recursively.
58 static int pack_rectangles(struct pos
*in
, struct pos
*out
, int num_rects
,
59 int w
, int h
, int *scratch
, int *used_width
)
61 int bins
[16 << HEIGHT_SORT_BITS
];
62 int sizes
[16 << HEIGHT_SORT_BITS
] = { 0 };
63 for (int i
= 0; i
< num_rects
; i
++)
64 sizes
[size_index(in
[i
].y
)]++;
66 for (int i
= 0; i
< 16 << HEIGHT_SORT_BITS
; i
+= 1 << HEIGHT_SORT_BITS
) {
67 for (int j
= 0; j
< 1 << HEIGHT_SORT_BITS
; j
++) {
73 for (int i
= 0; i
< num_rects
; i
++)
74 scratch
[bins
[size_index(in
[i
].y
)]++] = i
;
75 for (int i
= 0; i
< 16; i
++)
76 bins
[i
] = bins
[i
<< HEIGHT_SORT_BITS
] - sizes
[i
<< HEIGHT_SORT_BITS
];
79 } stack
[16] = {{15, 0, h
}}, s
= {};
84 s
= stack
[--stackpos
];
89 while ((obj
= scratch
[bins
[s
.size
]]) >= 0) {
90 int bottom
= y
+ in
[obj
].y
;
91 if (bottom
> s
.bottom
)
93 int right
= s
.x
+ in
[obj
].x
;
97 out
[obj
] = (struct pos
){s
.x
, y
};
100 stack
[stackpos
++] = s
;
102 maxy
= FFMAX(maxy
, bottom
);
104 *used_width
= FFMAX(*used_width
, s
.x
);
109 return num_rects
? -1 : y
;
112 int packer_pack(struct bitmap_packer
*packer
)
114 if (packer
->count
== 0)
116 int w_orig
= packer
->w
, h_orig
= packer
->h
;
117 struct pos
*in
= packer
->in
;
118 int xmax
= 0, ymax
= 0;
119 for (int i
= 0; i
< packer
->count
; i
++) {
120 if (in
[i
].x
<= packer
->padding
|| in
[i
].y
<= packer
->padding
)
121 in
[i
] = (struct pos
){0, 0};
122 if (in
[i
].x
< 0 || in
[i
].x
> 65535 || in
[i
].y
< 0 || in
[i
].y
> 65535) {
123 mp_msg(MSGT_VO
, MSGL_FATAL
, "Invalid OSD / subtitle bitmap size\n");
126 xmax
= FFMAX(xmax
, in
[i
].x
);
127 ymax
= FFMAX(ymax
, in
[i
].y
);
129 xmax
= FFMAX(0, xmax
- packer
->padding
);
130 ymax
= FFMAX(0, ymax
- packer
->padding
);
131 if (xmax
> packer
->w
)
132 packer
->w
= 1 << av_log2(xmax
- 1) + 1;
133 if (ymax
> packer
->h
)
134 packer
->h
= 1 << av_log2(ymax
- 1) + 1;
137 int y
= pack_rectangles(in
, packer
->result
, packer
->count
,
138 packer
->w
+ packer
->padding
,
139 packer
->h
+ packer
->padding
,
140 packer
->scratch
, &used_width
);
142 // No padding at edges
143 packer
->used_width
= FFMIN(used_width
, packer
->w
);
144 packer
->used_height
= FFMIN(y
, packer
->h
);
145 return packer
->w
!= w_orig
|| packer
->h
!= h_orig
;
147 if (packer
->w
<= packer
->h
&& packer
->w
!= packer
->w_max
)
148 packer
->w
= FFMIN(packer
->w
* 2, packer
->w_max
);
149 else if (packer
->h
!= packer
->h_max
)
150 packer
->h
= FFMIN(packer
->h
* 2, packer
->h_max
);
159 void packer_set_size(struct bitmap_packer
*packer
, int size
)
161 packer
->count
= size
;
162 if (size
<= packer
->asize
)
164 packer
->asize
= FFMAX(packer
->asize
* 2, size
);
165 talloc_free(packer
->result
);
166 talloc_free(packer
->scratch
);
167 packer
->in
= talloc_realloc(packer
, packer
->in
, struct pos
, packer
->asize
);
168 packer
->result
= talloc_array_ptrtype(packer
, packer
->result
,
170 packer
->scratch
= talloc_array_ptrtype(packer
, packer
->scratch
,
174 static int packer_pack_from_assimg(struct bitmap_packer
*packer
,
175 struct ass_image
*imglist
)
178 struct ass_image
*img
= imglist
;
180 if (count
>= packer
->asize
)
181 packer_set_size(packer
, FFMAX(packer
->asize
* 2, 32));
182 packer
->in
[count
].x
= img
->w
;
183 packer
->in
[count
].y
= img
->h
;
187 packer
->count
= count
;
188 return packer_pack(packer
);
191 int packer_pack_from_subbitmaps(struct bitmap_packer
*packer
,
192 struct sub_bitmaps
*b
, int padding_pixels
)
196 if (b
->type
== SUBBITMAP_EMPTY
)
198 if (b
->type
== SUBBITMAP_LIBASS
)
199 return packer_pack_from_assimg(packer
, b
->imgs
);
200 packer
->padding
= padding_pixels
;
201 packer_set_size(packer
, b
->part_count
);
202 int a
= packer
->padding
;
203 for (int i
= 0; i
< b
->part_count
; i
++)
204 packer
->in
[i
] = (struct pos
){b
->parts
[i
].w
+ a
, b
->parts
[i
].h
+ a
};
205 return packer_pack(packer
);