mesa: implement a display list / glBitmap texture atlas

This improves the performance of applications which use glXUseXFont()
or wglUseFontBitmaps() and glCallLists() to draw bitmap text.

Basically, we collect all the glBitmap images from the display lists
and put them into a texture atlas.  To render the bitmaps for a
glCallLists() command, we render a set of textured quads where each
quad is textured with one bitmap image.  Actually, the rendering part
has to be done by the Mesa driver or Mesa/gallium state tracker.

Note that GLUT demos that use glutBitmapCharacter() don't benefit
from this.

v2, per Nicolai Hähnle:
- check the max tex rect size is at least 1024.
- add comment in dd.h that texture_rectangle is required.
- in _mesa_DeleteLists(), try to delete the atlas before the list(s)

Reviewed-by: Nicolai Hähnle <[email protected]>

5 files changed, 448 insertions, 0 deletions

diff --git a/src/mesa/main/dd.h b/src/mesa/main/dd.h
index 19ef3042548..3f5aa5db051 100644
--- a/src/mesa/main/dd.h
+++ b/src/mesa/main/dd.h
@@ -35,6 +35,7 @@
 
 #include "glheader.h"
 
+struct gl_bitmap_atlas;
 struct gl_buffer_object;
 struct gl_context;
 struct gl_display_list;
@@ -154,6 +155,14 @@ struct dd_function_table {
 		   GLint x, GLint y, GLsizei width, GLsizei height,
 		   const struct gl_pixelstore_attrib *unpack,
 		   const GLubyte *bitmap );
+
+   /**
+    * Called by display list code for optimized glCallLists/glBitmap rendering
+    * The driver must support texture rectangles of width 1024 or more.
+    */
+   void (*DrawAtlasBitmaps)(struct gl_context *ctx,
+                            const struct gl_bitmap_atlas *atlas,
+                            GLuint count, const GLubyte *ids);
    /*@}*/
 
    
diff --git a/src/mesa/main/dlist.c b/src/mesa/main/dlist.c
index 0e25efbae72..afd2d83cb59 100644
--- a/src/mesa/main/dlist.c
+++ b/src/mesa/main/dlist.c
@@ -72,6 +72,9 @@
 #include "vbo/vbo.h"
 
 
+#define USE_BITMAP_ATLAS 1
+
+
 
 /**
  * Other parts of Mesa (such as the VBO module) can plug into the display
@@ -606,6 +609,261 @@ void mesa_print_display_list(GLuint list);
 
 
 /**
+ * Does the given display list only contain a single glBitmap call?
+ */
+static bool
+is_bitmap_list(const struct gl_display_list *dlist)
+{
+   const Node *n = dlist->Head;
+   if (n[0].opcode == OPCODE_BITMAP) {
+      n += InstSize[OPCODE_BITMAP];
+      if (n[0].opcode == OPCODE_END_OF_LIST)
+         return true;
+   }
+   return false;
+}
+
+
+/**
+ * Is the given display list an empty list?
+ */
+static bool
+is_empty_list(const struct gl_display_list *dlist)
+{
+   const Node *n = dlist->Head;
+   return n[0].opcode == OPCODE_END_OF_LIST;
+}
+
+
+/**
+ * Delete/free a gl_bitmap_atlas.  Called during context tear-down.
+ */
+void
+_mesa_delete_bitmap_atlas(struct gl_context *ctx, struct gl_bitmap_atlas *atlas)
+{
+   if (atlas->texObj) {
+      ctx->Driver.DeleteTexture(ctx, atlas->texObj);
+   }
+   free(atlas->glyphs);
+}
+
+
+/**
+ * Lookup a gl_bitmap_atlas by listBase ID.
+ */
+static struct gl_bitmap_atlas *
+lookup_bitmap_atlas(struct gl_context *ctx, GLuint listBase)
+{
+   struct gl_bitmap_atlas *atlas;
+
+   assert(listBase > 0);
+   atlas = _mesa_HashLookup(ctx->Shared->BitmapAtlas, listBase);
+   return atlas;
+}
+
+
+/**
+ * Create new bitmap atlas and insert into hash table.
+ */
+static struct gl_bitmap_atlas *
+alloc_bitmap_atlas(struct gl_context *ctx, GLuint listBase)
+{
+   struct gl_bitmap_atlas *atlas;
+
+   assert(listBase > 0);
+   assert(_mesa_HashLookup(ctx->Shared->BitmapAtlas, listBase) == NULL);
+
+   atlas = calloc(1, sizeof(*atlas));
+   if (atlas) {
+      _mesa_HashInsert(ctx->Shared->BitmapAtlas, listBase, atlas);
+   }
+
+   return atlas;
+}
+
+
+/**
+ * Try to build a bitmap atlas.  This involves examining a sequence of
+ * display lists which contain glBitmap commands and putting the bitmap
+ * images into a texture map (the atlas).
+ * If we succeed, gl_bitmap_atlas::complete will be set to true.
+ * If we fail, gl_bitmap_atlas::incomplete will be set to true.
+ */
+static void
+build_bitmap_atlas(struct gl_context *ctx, struct gl_bitmap_atlas *atlas,
+                   GLuint listBase)
+{
+   unsigned i, row_height = 0, xpos = 0, ypos = 0;
+   GLubyte *map;
+   GLint map_stride;
+
+   assert(atlas);
+   assert(!atlas->complete);
+   assert(atlas->numBitmaps > 0);
+
+   /* We use a rectangle texture (non-normalized coords) for the atlas */
+   assert(ctx->Extensions.NV_texture_rectangle);
+   assert(ctx->Const.MaxTextureRectSize >= 1024);
+
+   atlas->texWidth = 1024;
+   atlas->texHeight = 0;  /* determined below */
+
+   atlas->glyphs = malloc(atlas->numBitmaps * sizeof(atlas->glyphs[0]));
+   if (!atlas->glyphs) {
+      /* give up */
+      atlas->incomplete = true;
+      return;
+   }
+
+   /* Loop over the display lists.  They should all contain a single glBitmap
+    * call.  If not, bail out.  Also, compute the position and sizes of each
+    * bitmap in the atlas to determine the texture atlas size.
+    */
+   for (i = 0; i < atlas->numBitmaps; i++) {
+      const struct gl_display_list *list = _mesa_lookup_list(ctx, listBase + i);
+      const Node *n;
+      struct gl_bitmap_glyph *g = &atlas->glyphs[i];
+      unsigned bitmap_width, bitmap_height;
+      float bitmap_xmove, bitmap_ymove, bitmap_xorig, bitmap_yorig;
+
+      if (!list || is_empty_list(list)) {
+         /* stop here */
+         atlas->numBitmaps = i;
+         break;
+      }
+
+      if (!is_bitmap_list(list)) {
+         /* This list does not contain exactly one glBitmap command. Give up. */
+         atlas->incomplete = true;
+         return;
+      }
+
+      /* get bitmap info from the display list command */
+      n = list->Head;
+      assert(n[0].opcode == OPCODE_BITMAP);
+      bitmap_width = n[1].i;
+      bitmap_height = n[2].i;
+      bitmap_xorig = n[3].f;
+      bitmap_yorig = n[4].f;
+      bitmap_xmove = n[5].f;
+      bitmap_ymove = n[6].f;
+
+      if (xpos + bitmap_width > atlas->texWidth) {
+         /* advance to the next row of the texture */
+         xpos = 0;
+         ypos += row_height;
+         row_height = 0;
+      }
+
+      /* save the bitmap's position in the atlas */
+      g->x = xpos;
+      g->y = ypos;
+      g->w = bitmap_width;
+      g->h = bitmap_height;
+      g->xorig = bitmap_xorig;
+      g->yorig = bitmap_yorig;
+      g->xmove = bitmap_xmove;
+      g->ymove = bitmap_ymove;
+
+      xpos += bitmap_width;
+
+      /* keep track of tallest bitmap in the row */
+      row_height = MAX2(row_height, bitmap_height);
+   }
+
+   /* Now we know the texture height */
+   atlas->texHeight = ypos + row_height;
+
+   if (atlas->texHeight == 0) {
+      /* no glyphs found, give up */
+      goto fail;
+   }
+   else if (atlas->texHeight > ctx->Const.MaxTextureRectSize) {
+      /* too large, give up */
+      goto fail;
+   }
+
+   /* Create atlas texture (texture ID is irrelevant) */
+   atlas->texObj = ctx->Driver.NewTextureObject(ctx, 999, GL_TEXTURE_RECTANGLE);
+   if (!atlas->texObj) {
+      goto out_of_memory;
+   }
+
+   atlas->texObj->Sampler.MinFilter = GL_NEAREST;
+   atlas->texObj->Sampler.MagFilter = GL_NEAREST;
+   atlas->texObj->MaxLevel = 0;
+   atlas->texObj->Immutable = GL_TRUE;
+
+   atlas->texImage = _mesa_get_tex_image(ctx, atlas->texObj,
+                                         GL_TEXTURE_RECTANGLE, 0);
+   if (!atlas->texImage) {
+      goto out_of_memory;
+   }
+
+   _mesa_init_teximage_fields(ctx, atlas->texImage,
+                              atlas->texWidth, atlas->texHeight, 1, 0,
+                              GL_ALPHA, MESA_FORMAT_A_UNORM8);
+
+   /* alloc image storage */
+   if (!ctx->Driver.AllocTextureImageBuffer(ctx, atlas->texImage)) {
+      goto out_of_memory;
+   }
+
+   /* map teximage, load with bitmap glyphs */
+   ctx->Driver.MapTextureImage(ctx, atlas->texImage, 0,
+                               0, 0, atlas->texWidth, atlas->texHeight,
+                               GL_MAP_WRITE_BIT, &map, &map_stride);
+   if (!map) {
+      goto out_of_memory;
+   }
+
+   /* Background/clear pixels are 0xff, foreground/set pixels are 0x0 */
+   memset(map, 0xff, map_stride * atlas->texHeight);
+
+   for (i = 0; i < atlas->numBitmaps; i++) {
+      const struct gl_display_list *list = _mesa_lookup_list(ctx, listBase + i);
+      const Node *n = list->Head;
+
+      assert(n[0].opcode == OPCODE_BITMAP ||
+             n[0].opcode == OPCODE_END_OF_LIST);
+
+      if (n[0].opcode == OPCODE_BITMAP) {
+         unsigned bitmap_width = n[1].i;
+         unsigned bitmap_height = n[2].i;
+         unsigned xpos = atlas->glyphs[i].x;
+         unsigned ypos = atlas->glyphs[i].y;
+         const void *bitmap_image = get_pointer(&n[7]);
+
+         assert(atlas->glyphs[i].w == bitmap_width);
+         assert(atlas->glyphs[i].h == bitmap_height);
+
+         /* put the bitmap image into the texture image */
+         _mesa_expand_bitmap(bitmap_width, bitmap_height,
+                             &ctx->DefaultPacking, bitmap_image,
+                             map + map_stride * ypos + xpos, /* dest addr */
+                             map_stride, 0x0);
+      }
+   }
+
+   ctx->Driver.UnmapTextureImage(ctx, atlas->texImage, 0);
+
+   atlas->complete = true;
+
+   return;
+
+out_of_memory:
+   _mesa_error(ctx, GL_OUT_OF_MEMORY, "Display list bitmap atlas");
+fail:
+   if (atlas->texObj) {
+      ctx->Driver.DeleteTexture(ctx, atlas->texObj);
+   }
+   free(atlas->glyphs);
+   atlas->glyphs = NULL;
+   atlas->incomplete = true;
+}
+
+
+/**
  * Allocate a gl_display_list object with an initial block of storage.
  * \param count  how many display list nodes/tokens to allocate
  */
@@ -856,6 +1114,30 @@ _mesa_delete_list(struct gl_context *ctx, struct gl_display_list *dlist)
 
 
 /**
+ * Called by _mesa_HashWalk() to check if a display list which is being
+ * deleted belongs to a bitmap texture atlas.
+ */
+static void
+check_atlas_for_deleted_list(GLuint atlas_id, void *data, void *userData)
+{
+   struct gl_bitmap_atlas *atlas = (struct gl_bitmap_atlas *) data;
+   GLuint list_id = *((GLuint *) userData);  /* the list being deleted */
+
+   /* See if the list_id falls in the range contained in this texture atlas */
+   if (atlas->complete &&
+       list_id >= atlas_id &&
+       list_id < atlas_id + atlas->numBitmaps) {
+      /* Mark the atlas as incomplete so it doesn't get used.  But don't
+       * delete it yet since we don't want to try to recreate it in the next
+       * glCallLists.
+       */
+      atlas->complete = false;
+      atlas->incomplete = true;
+   }
+}
+
+
+/**
  * Destroy a display list and remove from hash table.
  * \param list - display list number
  */
@@ -871,6 +1153,16 @@ destroy_list(struct gl_context *ctx, GLuint list)
    if (!dlist)
       return;
 
+   if (is_bitmap_list(dlist)) {
+      /* If we're destroying a simple glBitmap display list, there's a
+       * chance that we're destroying a bitmap image that's in a texture
+       * atlas.  Examine all atlases to see if that's the case.  There's
+       * usually few (if any) atlases so this isn't expensive.
+       */
+      _mesa_HashWalk(ctx->Shared->BitmapAtlas,
+                     check_atlas_for_deleted_list, &list);
+   }
+
    _mesa_delete_list(ctx, dlist);
    _mesa_HashRemove(ctx->Shared->DisplayList, list);
 }
@@ -8895,6 +9187,18 @@ _mesa_DeleteLists(GLuint list, GLsizei range)
       _mesa_error(ctx, GL_INVALID_VALUE, "glDeleteLists");
       return;
    }
+
+   if (range > 1) {
+      /* We may be deleting a set of bitmap lists.  See if there's a
+       * bitmap atlas to free.
+       */
+      struct gl_bitmap_atlas *atlas = lookup_bitmap_atlas(ctx, list);
+      if (atlas) {
+         _mesa_delete_bitmap_atlas(ctx, atlas);
+         _mesa_HashRemove(ctx->Shared->BitmapAtlas, list);
+      }
+   }
+
    for (i = list; i < list + range; i++) {
       destroy_list(ctx, i);
    }
@@ -8936,6 +9240,24 @@ _mesa_GenLists(GLsizei range)
       }
    }
 
+   if (USE_BITMAP_ATLAS &&
+       range > 16 &&
+       ctx->Driver.DrawAtlasBitmaps) {
+      /* "range > 16" is a rough heuristic to guess when glGenLists might be
+       * used to allocate display lists for glXUseXFont or wglUseFontBitmaps.
+       * Create the empty atlas now.
+       */
+      struct gl_bitmap_atlas *atlas = lookup_bitmap_atlas(ctx, base);
+      if (!atlas) {
+         atlas = alloc_bitmap_atlas(ctx, base);
+      }
+      if (atlas) {
+         /* Atlas _should_ be new/empty now, but clobbering is OK */
+         assert(atlas->numBitmaps == 0);
+         atlas->numBitmaps = range;
+      }
+   }
+
    mtx_unlock(&ctx->Shared->Mutex);
 
    return base;
@@ -9085,6 +9407,65 @@ _mesa_CallList(GLuint list)
 
 
 /**
+ * Try to execute a glCallLists() command where the display lists contain
+ * glBitmap commands with a texture atlas.
+ * \return true for success, false otherwise
+ */
+static bool
+render_bitmap_atlas(struct gl_context *ctx, GLsizei n, GLenum type,
+                    const void *lists)
+{
+   struct gl_bitmap_atlas *atlas;
+   int i;
+
+   if (!USE_BITMAP_ATLAS ||
+       !ctx->Current.RasterPosValid ||
+       ctx->List.ListBase == 0 ||
+       type != GL_UNSIGNED_BYTE ||
+       !ctx->Driver.DrawAtlasBitmaps) {
+      /* unsupported */
+      return false;
+   }
+
+   atlas = lookup_bitmap_atlas(ctx, ctx->List.ListBase);
+
+   if (!atlas) {
+      /* Even if glGenLists wasn't called, we can still try to create
+       * the atlas now.
+       */
+      atlas = alloc_bitmap_atlas(ctx, ctx->List.ListBase);
+   }
+
+   if (atlas && !atlas->complete && !atlas->incomplete) {
+      /* Try to build the bitmap atlas now.
+       * If the atlas was created in glGenLists, we'll have recorded the
+       * number of lists (bitmaps).  Otherwise, take a guess at 256.
+       */
+      if (atlas->numBitmaps == 0)
+         atlas->numBitmaps = 256;
+      build_bitmap_atlas(ctx, atlas, ctx->List.ListBase);
+   }
+
+   if (!atlas || !atlas->complete) {
+      return false;
+   }
+
+   /* check that all display list IDs are in the atlas */
+   for (i = 0; i < n; i++) {
+      const GLubyte *ids = (const GLubyte *) lists;
+
+      if (ids[i] >= atlas->numBitmaps) {
+         return false;
+      }
+   }
+
+   ctx->Driver.DrawAtlasBitmaps(ctx, atlas, n, (const GLubyte *) lists);
+
+   return true;
+}
+
+
+/**
  * Execute glCallLists:  call multiple display lists.
  */
 void GLAPIENTRY
@@ -9123,6 +9504,10 @@ _mesa_CallLists(GLsizei n, GLenum type, const GLvoid * lists)
       return;
    }
 
+   if (render_bitmap_atlas(ctx, n, type, lists)) {
+      return;
+   }
+
    /* Save the CompileFlag status, turn it off, execute display list,
     * and restore the CompileFlag.
     */
diff --git a/src/mesa/main/dlist.h b/src/mesa/main/dlist.h
index 7a23208ba5a..22b696f50c1 100644
--- a/src/mesa/main/dlist.h
+++ b/src/mesa/main/dlist.h
@@ -36,6 +36,44 @@
 #include "main/mtypes.h"
 
 
+/**
+ * Describes the location and size of a glBitmap image in a texture atlas.
+ */
+struct gl_bitmap_glyph
+{
+   unsigned short x, y, w, h;  /**< position and size in the texture */
+   float xorig, yorig;         /**< bitmap origin */
+   float xmove, ymove;         /**< rasterpos move */
+};
+
+
+/**
+ * Describes a set of glBitmap display lists which live in a texture atlas.
+ * The idea is when we see a code sequence of glListBase(b), glCallLists(n)
+ * we're probably drawing bitmap font glyphs.  We try to put all the bitmap
+ * glyphs into one texture map then render the glCallLists as a textured
+ * quadstrip.
+ */
+struct gl_bitmap_atlas
+{
+   bool complete;     /**< Is the atlas ready to use? */
+   bool incomplete;   /**< Did we fail to construct this atlas? */
+
+   unsigned numBitmaps;
+   unsigned texWidth, texHeight;
+   struct gl_texture_object *texObj;
+   struct gl_texture_image *texImage;
+
+   unsigned glyphHeight;
+
+   struct gl_bitmap_glyph *glyphs;
+};
+
+void
+_mesa_delete_bitmap_atlas(struct gl_context *ctx,
+                          struct gl_bitmap_atlas *atlas);
+
+
 GLboolean GLAPIENTRY
 _mesa_IsList(GLuint list);
 
diff --git a/src/mesa/main/mtypes.h b/src/mesa/main/mtypes.h
index e85bd0d45ab..e5f2da0b3c4 100644
--- a/src/mesa/main/mtypes.h
+++ b/src/mesa/main/mtypes.h
@@ -3046,6 +3046,7 @@ struct gl_shared_state
    mtx_t Mutex;		   /**< for thread safety */
    GLint RefCount;			   /**< Reference count */
    struct _mesa_HashTable *DisplayList;	   /**< Display lists hash table */
+   struct _mesa_HashTable *BitmapAtlas;    /**< For optimized glBitmap text */
    struct _mesa_HashTable *TexObjects;	   /**< Texture objects hash table */
 
    /** Default texture objects (shared by all texture units) */
diff --git a/src/mesa/main/shared.c b/src/mesa/main/shared.c
index b9f7bb65fb6..49e5f028045 100644
--- a/src/mesa/main/shared.c
+++ b/src/mesa/main/shared.c
@@ -65,6 +65,7 @@ _mesa_alloc_shared_state(struct gl_context *ctx)
    mtx_init(&shared->Mutex, mtx_plain);
 
    shared->DisplayList = _mesa_NewHashTable();
+   shared->BitmapAtlas = _mesa_NewHashTable();
    shared->TexObjects = _mesa_NewHashTable();
    shared->Programs = _mesa_NewHashTable();
 
@@ -144,6 +145,18 @@ delete_displaylist_cb(GLuint id, void *data, void *userData)
 
 
 /**
+ * Callback for deleting a bitmap atlas.  Called by _mesa_HashDeleteAll().
+ */
+static void
+delete_bitmap_atlas_cb(GLuint id, void *data, void *userData)
+{
+   struct gl_bitmap_atlas *atlas = (struct gl_bitmap_atlas *) data;
+   struct gl_context *ctx = (struct gl_context *) userData;
+   _mesa_delete_bitmap_atlas(ctx, atlas);
+}
+
+
+/**
  * Callback for deleting a texture object.  Called by _mesa_HashDeleteAll().
  */
 static void
@@ -309,6 +322,8 @@ free_shared_state(struct gl_context *ctx, struct gl_shared_state *shared)
     */
    _mesa_HashDeleteAll(shared->DisplayList, delete_displaylist_cb, ctx);
    _mesa_DeleteHashTable(shared->DisplayList);
+   _mesa_HashDeleteAll(shared->BitmapAtlas, delete_bitmap_atlas_cb, ctx);
+   _mesa_DeleteHashTable(shared->BitmapAtlas);
 
    _mesa_HashWalk(shared->ShaderObjects, free_shader_program_data_cb, ctx);
    _mesa_HashDeleteAll(shared->ShaderObjects, delete_shader_cb, ctx);