diff --git a/libvo/vo_vdpau.c b/libvo/vo_vdpau.c
index 034812e..3da2d14 100644
--- a/libvo/vo_vdpau.c
+++ b/libvo/vo_vdpau.c
@@ -74,6 +74,9 @@ LIBVO_EXTERN(vdpau)
         mp_msg(MSGT_VO, MSGL_WARN, "[vdpau] %s: %s\n", \
                message, vdp_get_error_string(vdp_st));
 
+/* Round up to the next power of two */
+#define ROUND_POT(x) pow(2, ceil(log(x)/log(2)))
+
 /* number of video and output surfaces */
 #define NUM_OUTPUT_SURFACES                2
 #define MAX_VIDEO_SURFACES                 50
@@ -81,8 +84,11 @@ LIBVO_EXTERN(vdpau)
 /* number of palette entries */
 #define PALETTE_SIZE 256
 
-/* Initial maximum number of EOSD surfaces */
-#define EOSD_SURFACES_INITIAL 512
+/* Initial maximum number of EOSD render targets */
+#define EOSD_TARGETS_INITIAL 512
+
+/* Size of the surfaces the EOSD bitmaps will be placed into */
+#define EOSD_SURFACE_SIZE 512
 
 /*
  * Global variable declaration - VDPAU specific
@@ -178,9 +184,9 @@ static uint32_t                           palette[PALETTE_SIZE];
 // Pool of surfaces
 struct {
     VdpBitmapSurface surface;
-    int w;
-    int h;
-    char in_use;
+    int w, h;
+    int x, y;
+    int max_y;
 } *eosd_surfaces;
 
 // List of surfaces to be rendered
@@ -192,7 +198,8 @@ struct {
 } *eosd_targets;
 
 static int eosd_render_count;
-static int eosd_surface_count;
+static int eosd_surfaces_size;
+static int eosd_targets_size;
 
 // Video equalizer
 static VdpProcamp procamp;
@@ -646,7 +653,7 @@ static void draw_eosd(void) {
 
 static void generate_eosd(mp_eosd_images_t *imgs) {
     VdpStatus vdp_st;
-    VdpRect destRect;
+    VdpRect dest_rect;
     int j, found;
     ass_image_t *img = imgs->imgs;
     ass_image_t *i;
@@ -662,54 +669,62 @@ static void generate_eosd(mp_eosd_images_t *imgs) {
     if (imgs->changed == 1)
         goto eosd_skip_upload;
 
-    for (j=0; j<eosd_surface_count; j++)
-        eosd_surfaces[j].in_use = 0;
+    for (j=0; j<eosd_surfaces_size; j++) {
+        eosd_surfaces[j].x = 0;
+        eosd_surfaces[j].y = 0;
+        eosd_surfaces[j].max_y = 0;
+    }
 
     for (i = img; i; i = i->next) {
-        // Try to reuse a suitable surface
+        // Find surface with enough free space
         found = -1;
-        for (j=0; j<eosd_surface_count; j++) {
-            if (eosd_surfaces[j].surface != VDP_INVALID_HANDLE && !eosd_surfaces[j].in_use &&
-                eosd_surfaces[j].w >= i->w && eosd_surfaces[j].h >= i->h) {
+        for (j=0; j<eosd_surfaces_size; j++)
+            if ((eosd_surfaces[j].y + i->h < eosd_surfaces[j].h && eosd_surfaces[j].x + i->w < eosd_surfaces[j].w)
+                || (eosd_surfaces[j].max_y + i->h < eosd_surfaces[j].h)){
                 found = j;
                 break;
             }
-        }
-        // None found, allocate a new surface
+        // No free space; allocate a new surface
         if (found < 0) {
-            for (j=0; j<eosd_surface_count; j++) {
-                if (!eosd_surfaces[j].in_use) {
-                    if (eosd_surfaces[j].surface != VDP_INVALID_HANDLE)
-                        vdp_bitmap_surface_destroy(eosd_surfaces[j].surface);
-                    found = j;
-                    break;
-                }
-            }
-            // Allocate new space for surface/target arrays
-            if (found < 0) {
-                j = found = eosd_surface_count;
-                eosd_surface_count = eosd_surface_count ? eosd_surface_count*2 : EOSD_SURFACES_INITIAL;
-                eosd_surfaces = realloc(eosd_surfaces, eosd_surface_count * sizeof(*eosd_surfaces));
-                eosd_targets  = realloc(eosd_targets,  eosd_surface_count * sizeof(*eosd_targets));
-                for(j=found; j<eosd_surface_count; j++) {
-                    eosd_surfaces[j].surface = VDP_INVALID_HANDLE;
-                    eosd_surfaces[j].in_use = 0;
-                }
-            }
+            found = eosd_surfaces_size;
+            eosd_surfaces = realloc(eosd_surfaces, ++eosd_surfaces_size * sizeof(*eosd_surfaces));
+            eosd_surfaces[found].w = (i->w <= EOSD_SURFACE_SIZE) ? EOSD_SURFACE_SIZE : ROUND_POT(i->w);
+            eosd_surfaces[found].h = (i->h <= EOSD_SURFACE_SIZE) ? EOSD_SURFACE_SIZE : ROUND_POT(i->h);
+            eosd_surfaces[found].x = eosd_surfaces[found].y = 0;
+            eosd_surfaces[found].max_y = 0;
+            printf("allocate %d (%dx%d)\n", found, eosd_surfaces[found].w, eosd_surfaces[found].h);
             vdp_st = vdp_bitmap_surface_create(vdp_device, VDP_RGBA_FORMAT_A8,
-                i->w, i->h, VDP_TRUE, &eosd_surfaces[found].surface);
+                eosd_surfaces[found].w, eosd_surfaces[found].h, VDP_TRUE, &eosd_surfaces[found].surface);
             CHECK_ST_WARNING("EOSD: error when creating surface")
-            eosd_surfaces[found].w = i->w;
-            eosd_surfaces[found].h = i->h;
         }
-        eosd_surfaces[found].in_use = 1;
+        // Allocate new space for targets, if needed
+        if (eosd_render_count >= eosd_targets_size) {
+            eosd_targets_size = eosd_targets_size ? eosd_targets_size*2 : EOSD_TARGETS_INITIAL;
+            eosd_targets = realloc(eosd_targets, eosd_targets_size * sizeof(*eosd_targets));
+        }
+        // Set up render target
+        if ((eosd_surfaces[found].x + i->w) > eosd_surfaces[found].w) {
+            eosd_surfaces[found].y = eosd_surfaces[found].max_y;
+            eosd_surfaces[found].x = 0;
+        }
+        dest_rect.x0 = eosd_surfaces[found].x;
+        dest_rect.y0 = eosd_surfaces[found].y;
+        dest_rect.x1 = dest_rect.x0 + i->w;
+        dest_rect.y1 = dest_rect.y0 + i->h;
+        eosd_surfaces[found].max_y = FFMAX(eosd_surfaces[found].max_y, eosd_surfaces[found].y + i->h);
+        eosd_surfaces[found].x += i->w;
+        // Render destination and color
         eosd_targets[eosd_render_count].surface = eosd_surfaces[found].surface;
-        destRect.x0 = 0;
-        destRect.y0 = 0;
-        destRect.x1 = i->w;
-        destRect.y1 = i->h;
-        vdp_st = vdp_bitmap_surface_putbits_native(eosd_targets[eosd_render_count].surface,
-            (const void *) &i->bitmap, &i->stride, &destRect);
+        eosd_targets[eosd_render_count].source.x0 = dest_rect.x0;
+        eosd_targets[eosd_render_count].source.y0 = dest_rect.y0;
+        eosd_targets[eosd_render_count].source.x1 = dest_rect.x1;
+        eosd_targets[eosd_render_count].source.y1 = dest_rect.y1;
+        eosd_targets[eosd_render_count].color.alpha = 1.0 - ((i->color >> 0) & 0xff) / 255.0;
+        eosd_targets[eosd_render_count].color.blue  = ((i->color >>  8) & 0xff) / 255.0;
+        eosd_targets[eosd_render_count].color.green = ((i->color >> 16) & 0xff) / 255.0;
+        eosd_targets[eosd_render_count].color.red   = ((i->color >> 24) & 0xff) / 255.0;
+        vdp_st = vdp_bitmap_surface_putbits_native(eosd_surfaces[found].surface,
+            (const void *) &i->bitmap, &i->stride, &dest_rect);
         CHECK_ST_WARNING("EOSD: putbits failed")
         eosd_render_count++;
     }
@@ -717,19 +732,10 @@ static void generate_eosd(mp_eosd_images_t *imgs) {
 eosd_skip_upload:
     eosd_render_count = 0;
     for (i = img; i; i = i->next) {
-        // Render dest, color, etc.
-        eosd_targets[eosd_render_count].color.alpha = 1.0 - ((i->color >> 0) & 0xff) / 255.0;
-        eosd_targets[eosd_render_count].color.blue  = ((i->color >>  8) & 0xff) / 255.0;
-        eosd_targets[eosd_render_count].color.green = ((i->color >> 16) & 0xff) / 255.0;
-        eosd_targets[eosd_render_count].color.red   = ((i->color >> 24) & 0xff) / 255.0;
         eosd_targets[eosd_render_count].dest.x0 = i->dst_x;
         eosd_targets[eosd_render_count].dest.y0 = i->dst_y;
         eosd_targets[eosd_render_count].dest.x1 = i->w + i->dst_x;
         eosd_targets[eosd_render_count].dest.y1 = i->h + i->dst_y;
-        eosd_targets[eosd_render_count].source.x0 = 0;
-        eosd_targets[eosd_render_count].source.y0 = 0;
-        eosd_targets[eosd_render_count].source.x1 = i->w;
-        eosd_targets[eosd_render_count].source.y1 = i->h;
         eosd_render_count++;
     }
 }
@@ -901,12 +907,9 @@ static void DestroyVdpauObjects(void)
         CHECK_ST_WARNING("Error when calling vdp_output_surface_destroy")
     }
 
-    for (i = 0; i<eosd_surface_count; i++) {
-        if (eosd_surfaces[i].surface != VDP_INVALID_HANDLE) {
-            vdp_st = vdp_bitmap_surface_destroy(eosd_surfaces[i].surface);
-            CHECK_ST_WARNING("Error when calling vdp_bitmap_surface_destroy")
-        }
-        eosd_surfaces[i].surface = VDP_INVALID_HANDLE;
+    for (i = 0; i<eosd_surfaces_size; i++) {
+        vdp_st = vdp_bitmap_surface_destroy(eosd_surfaces[i].surface);
+        CHECK_ST_WARNING("Error when calling vdp_bitmap_surface_destroy")
     }
 
     vdp_st = vdp_device_destroy(vdp_device);
@@ -1008,7 +1011,7 @@ static int preinit(const char *arg)
     index_data = NULL;
     index_data_size = 0;
 
-    eosd_surface_count = eosd_render_count = 0;
+    eosd_surfaces_size = eosd_targets_size = eosd_render_count = 0;
     eosd_surfaces = NULL;
     eosd_targets  = NULL;