From c1af9d57a343d9d782f9de4c6e31002c674769e1 Mon Sep 17 00:00:00 2001 From: bruvzg <7645683+bruvzg@users.noreply.github.com> Date: Tue, 18 Oct 2022 10:10:24 +0300 Subject: Improve font glyph cache packing shelf best height fit heuristic. --- doc/classes/FontFile.xml | 4 +- doc/classes/TextServer.xml | 4 +- modules/text_server_adv/text_server_adv.cpp | 115 ++++++++++----------------- modules/text_server_adv/text_server_adv.h | 86 ++++++++++++++++++--- modules/text_server_fb/text_server_fb.cpp | 116 ++++++++++------------------ modules/text_server_fb/text_server_fb.h | 86 ++++++++++++++++++--- 6 files changed, 236 insertions(+), 175 deletions(-) diff --git a/doc/classes/FontFile.xml b/doc/classes/FontFile.xml index df378d9d2f..dac822ae2f 100644 --- a/doc/classes/FontFile.xml +++ b/doc/classes/FontFile.xml @@ -262,7 +262,7 @@ - Returns a copy of the array containing the first free pixel in the each column of texture. Should be the same size as texture width or empty. + Returns a copy of the array containing glyph packing data. @@ -522,7 +522,7 @@ - Sets array containing the first free pixel in the each column of texture. Should be the same size as texture width or empty (for the fonts without dynamic glyph generation support). + Sets array containing glyph packing data. diff --git a/doc/classes/TextServer.xml b/doc/classes/TextServer.xml index 2512c563c5..0b822a4fe9 100644 --- a/doc/classes/TextServer.xml +++ b/doc/classes/TextServer.xml @@ -413,7 +413,7 @@ - Returns array containing the first free pixel in the each column of texture. Should be the same size as texture width or empty. + Returns array containing glyph packing data. @@ -824,7 +824,7 @@ - Sets array containing the first free pixel in the each column of texture. Should be the same size as texture width or empty. + Sets array containing glyph packing data. diff --git a/modules/text_server_adv/text_server_adv.cpp b/modules/text_server_adv/text_server_adv.cpp index 0929d3a2b0..dba94dfda2 100644 --- a/modules/text_server_adv/text_server_adv.cpp +++ b/modules/text_server_adv/text_server_adv.cpp @@ -788,58 +788,27 @@ String TextServerAdvanced::_tag_to_name(int64_t p_tag) const { _FORCE_INLINE_ TextServerAdvanced::FontTexturePosition TextServerAdvanced::find_texture_pos_for_glyph(FontForSizeAdvanced *p_data, int p_color_size, Image::Format p_image_format, int p_width, int p_height, bool p_msdf) const { FontTexturePosition ret; - ret.index = -1; int mw = p_width; int mh = p_height; - for (int i = 0; i < p_data->textures.size(); i++) { - const FontTexture &ct = p_data->textures[i]; - - if (p_image_format != ct.format) { - continue; - } - - if (mw > ct.texture_w || mh > ct.texture_h) { // Too big for this texture. + ShelfPackTexture *ct = p_data->textures.ptrw(); + for (int32_t i = 0; i < p_data->textures.size(); i++) { + if (p_image_format != ct[i].format) { continue; } - - if (ct.offsets.size() < ct.texture_w) { + if (mw > ct[i].texture_w || mh > ct[i].texture_h) { // Too big for this texture. continue; } - ret.y = 0x7fffffff; - ret.x = 0; - const int *ct_offsets_ptr = ct.offsets.ptr(); - - for (int j = 0; j < ct.texture_w - mw; j++) { - int max_y = 0; - for (int k = j; k < j + mw; k++) { - int y = ct_offsets_ptr[k]; - if (y > max_y) { - max_y = y; - } - } - - if (max_y < ret.y) { - ret.y = max_y; - ret.x = j; - } - } - - if (ret.y == 0x7fffffff || ret.y + mh > ct.texture_h) { - continue; // Fail, could not fit it here. + ret = ct[i].pack_rect(i, mh, mw); + if (ret.index != -1) { + break; } - - ret.index = i; - break; } if (ret.index == -1) { // Could not find texture to fit, create one. - ret.x = 0; - ret.y = 0; - int texsize = MAX(p_data->size.x * p_data->oversampling * 8, 256); #ifdef GDEXTENSION @@ -867,12 +836,9 @@ _FORCE_INLINE_ TextServerAdvanced::FontTexturePosition TextServerAdvanced::find_ #endif } - FontTexture tex; - tex.texture_w = texsize; - tex.texture_h = texsize; + ShelfPackTexture tex = ShelfPackTexture(texsize, texsize); tex.format = p_image_format; tex.imgdata.resize(texsize * texsize * p_color_size); - { // Zero texture. uint8_t *w = tex.imgdata.ptrw(); @@ -895,14 +861,10 @@ _FORCE_INLINE_ TextServerAdvanced::FontTexturePosition TextServerAdvanced::find_ ERR_FAIL_V(ret); } } - tex.offsets.resize(texsize); - int32_t *offw = tex.offsets.ptrw(); - for (int i = 0; i < texsize; i++) { // Zero offsets. - offw[i] = 0; - } - p_data->textures.push_back(tex); - ret.index = p_data->textures.size() - 1; + + int32_t idx = p_data->textures.size() - 1; + ret = p_data->textures.write[idx].pack_rect(idx, mh, mw); } return ret; @@ -1036,7 +998,7 @@ _FORCE_INLINE_ TextServerAdvanced::FontGlyph TextServerAdvanced::rasterize_msdf( FontTexturePosition tex_pos = find_texture_pos_for_glyph(p_data, 4, Image::FORMAT_RGBA8, mw, mh, true); ERR_FAIL_COND_V(tex_pos.index < 0, FontGlyph()); - FontTexture &tex = p_data->textures.write[tex_pos.index]; + ShelfPackTexture &tex = p_data->textures.write[tex_pos.index]; edgeColoringSimple(shape, 3.0); // Max. angle. msdfgen::Bitmap image(w, h); // Texture size. @@ -1079,12 +1041,6 @@ _FORCE_INLINE_ TextServerAdvanced::FontGlyph TextServerAdvanced::rasterize_msdf( tex.dirty = true; - // Update height array. - int32_t *offw = tex.offsets.ptrw(); - for (int k = tex_pos.x; k < tex_pos.x + mw; k++) { - offw[k] = tex_pos.y + mh; - } - chr.texture_idx = tex_pos.index; chr.uv_rect = Rect2(tex_pos.x + p_rect_margin, tex_pos.y + p_rect_margin, w + p_rect_margin * 2, h + p_rect_margin * 2); @@ -1132,8 +1088,7 @@ _FORCE_INLINE_ TextServerAdvanced::FontGlyph TextServerAdvanced::rasterize_bitma ERR_FAIL_COND_V(tex_pos.index < 0, FontGlyph()); // Fit character in char texture. - - FontTexture &tex = p_data->textures.write[tex_pos.index]; + ShelfPackTexture &tex = p_data->textures.write[tex_pos.index]; { uint8_t *wr = tex.imgdata.ptrw(); @@ -1198,12 +1153,6 @@ _FORCE_INLINE_ TextServerAdvanced::FontGlyph TextServerAdvanced::rasterize_bitma tex.dirty = true; - // Update height array. - int32_t *offw = tex.offsets.ptrw(); - for (int k = tex_pos.x; k < tex_pos.x + mw; k++) { - offw[k] = tex_pos.y + mh; - } - FontGlyph chr; chr.advance = advance * p_data->scale / p_data->oversampling; chr.texture_idx = tex_pos.index; @@ -2492,7 +2441,7 @@ void TextServerAdvanced::_font_set_texture_image(const RID &p_font_rid, const Ve fd->cache[size]->textures.resize(p_texture_index + 1); } - FontTexture &tex = fd->cache[size]->textures.write[p_texture_index]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[p_texture_index]; tex.imgdata = p_image->get_data(); tex.texture_w = p_image->get_width(); @@ -2517,11 +2466,12 @@ Ref TextServerAdvanced::_font_get_texture_image(const RID &p_font_rid, co ERR_FAIL_COND_V(!_ensure_cache_for_size(fd, size), Ref()); ERR_FAIL_INDEX_V(p_texture_index, fd->cache[size]->textures.size(), Ref()); - const FontTexture &tex = fd->cache[size]->textures[p_texture_index]; + const ShelfPackTexture &tex = fd->cache[size]->textures[p_texture_index]; return Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); } -void TextServerAdvanced::_font_set_texture_offsets(const RID &p_font_rid, const Vector2i &p_size, int64_t p_texture_index, const PackedInt32Array &p_offset) { +void TextServerAdvanced::_font_set_texture_offsets(const RID &p_font_rid, const Vector2i &p_size, int64_t p_texture_index, const PackedInt32Array &p_offsets) { + ERR_FAIL_COND(p_offsets.size() % 4 != 0); FontAdvanced *fd = font_owner.get_or_null(p_font_rid); ERR_FAIL_COND(!fd); @@ -2533,8 +2483,11 @@ void TextServerAdvanced::_font_set_texture_offsets(const RID &p_font_rid, const fd->cache[size]->textures.resize(p_texture_index + 1); } - FontTexture &tex = fd->cache[size]->textures.write[p_texture_index]; - tex.offsets = p_offset; + ShelfPackTexture &tex = fd->cache[size]->textures.write[p_texture_index]; + tex.shelves.clear(); + for (int32_t i = 0; i < p_offsets.size(); i += 4) { + tex.shelves.push_back(Shelf(p_offsets[i], p_offsets[i + 1], p_offsets[i + 2], p_offsets[i + 3])); + } } PackedInt32Array TextServerAdvanced::_font_get_texture_offsets(const RID &p_font_rid, const Vector2i &p_size, int64_t p_texture_index) const { @@ -2546,8 +2499,20 @@ PackedInt32Array TextServerAdvanced::_font_get_texture_offsets(const RID &p_font ERR_FAIL_COND_V(!_ensure_cache_for_size(fd, size), PackedInt32Array()); ERR_FAIL_INDEX_V(p_texture_index, fd->cache[size]->textures.size(), PackedInt32Array()); - const FontTexture &tex = fd->cache[size]->textures[p_texture_index]; - return tex.offsets; + const ShelfPackTexture &tex = fd->cache[size]->textures[p_texture_index]; + PackedInt32Array ret; + ret.resize(tex.shelves.size() * 4); + + int32_t *wr = ret.ptrw(); + int32_t i = 0; + for (const Shelf &E : tex.shelves) { + wr[i * 4] = E.x; + wr[i * 4 + 1] = E.y; + wr[i * 4 + 2] = E.w; + wr[i * 4 + 3] = E.h; + i++; + } + return ret; } PackedInt32Array TextServerAdvanced::_font_get_glyph_list(const RID &p_font_rid, const Vector2i &p_size) const { @@ -2851,7 +2816,7 @@ RID TextServerAdvanced::_font_get_glyph_texture_rid(const RID &p_font_rid, const if (RenderingServer::get_singleton() != nullptr) { if (gl[p_glyph | mod].texture_idx != -1) { if (fd->cache[size]->textures[gl[p_glyph | mod].texture_idx].dirty) { - FontTexture &tex = fd->cache[size]->textures.write[gl[p_glyph | mod].texture_idx]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[gl[p_glyph | mod].texture_idx]; Ref img = Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); if (fd->mipmaps) { img->generate_mipmaps(); @@ -2897,7 +2862,7 @@ Size2 TextServerAdvanced::_font_get_glyph_texture_size(const RID &p_font_rid, co if (RenderingServer::get_singleton() != nullptr) { if (gl[p_glyph | mod].texture_idx != -1) { if (fd->cache[size]->textures[gl[p_glyph | mod].texture_idx].dirty) { - FontTexture &tex = fd->cache[size]->textures.write[gl[p_glyph | mod].texture_idx]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[gl[p_glyph | mod].texture_idx]; Ref img = Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); if (fd->mipmaps) { img->generate_mipmaps(); @@ -3242,7 +3207,7 @@ void TextServerAdvanced::_font_draw_glyph(const RID &p_font_rid, const RID &p_ca #endif if (RenderingServer::get_singleton() != nullptr) { if (fd->cache[size]->textures[gl.texture_idx].dirty) { - FontTexture &tex = fd->cache[size]->textures.write[gl.texture_idx]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[gl.texture_idx]; Ref img = Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); if (fd->mipmaps) { img->generate_mipmaps(); @@ -3332,7 +3297,7 @@ void TextServerAdvanced::_font_draw_glyph_outline(const RID &p_font_rid, const R #endif if (RenderingServer::get_singleton() != nullptr) { if (fd->cache[size]->textures[gl.texture_idx].dirty) { - FontTexture &tex = fd->cache[size]->textures.write[gl.texture_idx]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[gl.texture_idx]; Ref img = Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); if (fd->mipmaps) { img->generate_mipmaps(); diff --git a/modules/text_server_adv/text_server_adv.h b/modules/text_server_adv/text_server_adv.h index fb5075e835..37292e017e 100644 --- a/modules/text_server_adv/text_server_adv.h +++ b/modules/text_server_adv/text_server_adv.h @@ -168,20 +168,86 @@ class TextServerAdvanced : public TextServerExtension { const int rect_range = 1; - struct FontTexture { + struct FontTexturePosition { + int32_t index = -1; + int32_t x = 0; + int32_t y = 0; + + FontTexturePosition() {} + FontTexturePosition(int32_t p_id, int32_t p_x, int32_t p_y) : + index(p_id), x(p_x), y(p_y) {} + }; + + struct Shelf { + int32_t x = 0; + int32_t y = 0; + int32_t w = 0; + int32_t h = 0; + + FontTexturePosition alloc_shelf(int32_t p_id, int32_t p_w, int32_t p_h) { + if (p_w > w || p_h > h) { + return FontTexturePosition(-1, 0, 0); + } + int32_t xx = x; + x += p_w; + w -= p_w; + return FontTexturePosition(p_id, xx, y); + } + + Shelf() {} + Shelf(int32_t p_x, int32_t p_y, int32_t p_w, int32_t p_h) : + x(p_x), y(p_y), w(p_w), h(p_h) {} + }; + + struct ShelfPackTexture { + int32_t texture_w = 1024; + int32_t texture_h = 1024; + Image::Format format; PackedByteArray imgdata; - int texture_w = 0; - int texture_h = 0; - PackedInt32Array offsets; Ref texture; bool dirty = true; - }; - struct FontTexturePosition { - int index = 0; - int x = 0; - int y = 0; + List shelves; + + FontTexturePosition pack_rect(int32_t p_id, int32_t p_h, int32_t p_w) { + int32_t y = 0; + int32_t waste = 0; + Shelf *best_shelf = nullptr; + int32_t best_waste = std::numeric_limits::max(); + + for (Shelf &E : shelves) { + y += E.h; + if (p_w > E.w) { + continue; + } + if (p_h == E.h) { + return E.alloc_shelf(p_id, p_w, p_h); + } + if (p_h > E.h) { + continue; + } + if (p_h < E.h) { + waste = (E.h - p_h) * p_w; + if (waste < best_waste) { + best_waste = waste; + best_shelf = &E; + } + } + } + if (best_shelf) { + return best_shelf->alloc_shelf(p_id, p_w, p_h); + } + if (p_h <= (texture_h - y) && p_w <= texture_w) { + List::Element *E = shelves.push_back(Shelf(0, y, texture_w, p_h)); + return E->get().alloc_shelf(p_id, p_w, p_h); + } + return FontTexturePosition(-1, 0, 0); + } + + ShelfPackTexture() {} + ShelfPackTexture(int32_t p_w, int32_t p_h) : + texture_w(p_w), texture_h(p_h) {} }; struct FontGlyph { @@ -202,7 +268,7 @@ class TextServerAdvanced : public TextServerExtension { Vector2i size; - Vector textures; + Vector textures; HashMap glyph_map; HashMap kerning_map; hb_font_t *hb_handle = nullptr; diff --git a/modules/text_server_fb/text_server_fb.cpp b/modules/text_server_fb/text_server_fb.cpp index 4a46e17868..9e532ec52a 100644 --- a/modules/text_server_fb/text_server_fb.cpp +++ b/modules/text_server_fb/text_server_fb.cpp @@ -211,59 +211,27 @@ String TextServerFallback::_tag_to_name(int64_t p_tag) const { _FORCE_INLINE_ TextServerFallback::FontTexturePosition TextServerFallback::find_texture_pos_for_glyph(FontForSizeFallback *p_data, int p_color_size, Image::Format p_image_format, int p_width, int p_height, bool p_msdf) const { FontTexturePosition ret; - ret.index = -1; int mw = p_width; int mh = p_height; - for (int i = 0; i < p_data->textures.size(); i++) { - const FontTexture &ct = p_data->textures[i]; - - if (p_image_format != ct.format) { + ShelfPackTexture *ct = p_data->textures.ptrw(); + for (int32_t i = 0; i < p_data->textures.size(); i++) { + if (p_image_format != ct[i].format) { continue; } - - if (mw > ct.texture_w || mh > ct.texture_h) { // Too big for this texture. + if (mw > ct[i].texture_w || mh > ct[i].texture_h) { // Too big for this texture. continue; } - if (ct.offsets.size() < ct.texture_w) { - continue; + ret = ct[i].pack_rect(i, mh, mw); + if (ret.index != -1) { + break; } - - ret.y = 0x7fffffff; - ret.x = 0; - const int *ct_offsets_ptr = ct.offsets.ptr(); - - for (int j = 0; j < ct.texture_w - mw; j++) { - int max_y = 0; - - for (int k = j; k < j + mw; k++) { - int y = ct_offsets_ptr[k]; - if (y > max_y) { - max_y = y; - } - } - - if (max_y < ret.y) { - ret.y = max_y; - ret.x = j; - } - } - - if (ret.y == 0x7fffffff || ret.y + mh > ct.texture_h) { - continue; // Fail, could not fit it here. - } - - ret.index = i; - break; } if (ret.index == -1) { // Could not find texture to fit, create one. - ret.x = 0; - ret.y = 0; - int texsize = MAX(p_data->size.x * p_data->oversampling * 8, 256); #ifdef GDEXTENSION @@ -292,12 +260,9 @@ _FORCE_INLINE_ TextServerFallback::FontTexturePosition TextServerFallback::find_ #endif } - FontTexture tex; - tex.texture_w = texsize; - tex.texture_h = texsize; + ShelfPackTexture tex = ShelfPackTexture(texsize, texsize); tex.format = p_image_format; tex.imgdata.resize(texsize * texsize * p_color_size); - { // Zero texture. uint8_t *w = tex.imgdata.ptrw(); @@ -320,14 +285,10 @@ _FORCE_INLINE_ TextServerFallback::FontTexturePosition TextServerFallback::find_ ERR_FAIL_V(ret); } } - tex.offsets.resize(texsize); - int32_t *offw = tex.offsets.ptrw(); - for (int i = 0; i < texsize; i++) { // Zero offsets. - offw[i] = 0; - } - p_data->textures.push_back(tex); - ret.index = p_data->textures.size() - 1; + + int32_t idx = p_data->textures.size() - 1; + ret = p_data->textures.write[idx].pack_rect(idx, mh, mw); } return ret; @@ -461,7 +422,7 @@ _FORCE_INLINE_ TextServerFallback::FontGlyph TextServerFallback::rasterize_msdf( FontTexturePosition tex_pos = find_texture_pos_for_glyph(p_data, 4, Image::FORMAT_RGBA8, mw, mh, true); ERR_FAIL_COND_V(tex_pos.index < 0, FontGlyph()); - FontTexture &tex = p_data->textures.write[tex_pos.index]; + ShelfPackTexture &tex = p_data->textures.write[tex_pos.index]; edgeColoringSimple(shape, 3.0); // Max. angle. msdfgen::Bitmap image(w, h); // Texture size. @@ -504,12 +465,6 @@ _FORCE_INLINE_ TextServerFallback::FontGlyph TextServerFallback::rasterize_msdf( tex.dirty = true; - // Update height array. - int32_t *offw = tex.offsets.ptrw(); - for (int k = tex_pos.x; k < tex_pos.x + mw; k++) { - offw[k] = tex_pos.y + mh; - } - chr.texture_idx = tex_pos.index; chr.uv_rect = Rect2(tex_pos.x + p_rect_margin, tex_pos.y + p_rect_margin, w + p_rect_margin * 2, h + p_rect_margin * 2); @@ -556,8 +511,7 @@ _FORCE_INLINE_ TextServerFallback::FontGlyph TextServerFallback::rasterize_bitma ERR_FAIL_COND_V(tex_pos.index < 0, FontGlyph()); // Fit character in char texture. - - FontTexture &tex = p_data->textures.write[tex_pos.index]; + ShelfPackTexture &tex = p_data->textures.write[tex_pos.index]; { uint8_t *wr = tex.imgdata.ptrw(); @@ -622,12 +576,6 @@ _FORCE_INLINE_ TextServerFallback::FontGlyph TextServerFallback::rasterize_bitma tex.dirty = true; - // Update height array. - int32_t *offw = tex.offsets.ptrw(); - for (int k = tex_pos.x; k < tex_pos.x + mw; k++) { - offw[k] = tex_pos.y + mh; - } - FontGlyph chr; chr.advance = advance * p_data->scale / p_data->oversampling; chr.texture_idx = tex_pos.index; @@ -1587,7 +1535,7 @@ void TextServerFallback::_font_set_texture_image(const RID &p_font_rid, const Ve fd->cache[size]->textures.resize(p_texture_index + 1); } - FontTexture &tex = fd->cache[size]->textures.write[p_texture_index]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[p_texture_index]; tex.imgdata = p_image->get_data(); tex.texture_w = p_image->get_width(); @@ -1612,11 +1560,12 @@ Ref TextServerFallback::_font_get_texture_image(const RID &p_font_rid, co ERR_FAIL_COND_V(!_ensure_cache_for_size(fd, size), Ref()); ERR_FAIL_INDEX_V(p_texture_index, fd->cache[size]->textures.size(), Ref()); - const FontTexture &tex = fd->cache[size]->textures[p_texture_index]; + const ShelfPackTexture &tex = fd->cache[size]->textures[p_texture_index]; return Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); } -void TextServerFallback::_font_set_texture_offsets(const RID &p_font_rid, const Vector2i &p_size, int64_t p_texture_index, const PackedInt32Array &p_offset) { +void TextServerFallback::_font_set_texture_offsets(const RID &p_font_rid, const Vector2i &p_size, int64_t p_texture_index, const PackedInt32Array &p_offsets) { + ERR_FAIL_COND(p_offsets.size() % 4 != 0); FontFallback *fd = font_owner.get_or_null(p_font_rid); ERR_FAIL_COND(!fd); @@ -1628,8 +1577,11 @@ void TextServerFallback::_font_set_texture_offsets(const RID &p_font_rid, const fd->cache[size]->textures.resize(p_texture_index + 1); } - FontTexture &tex = fd->cache[size]->textures.write[p_texture_index]; - tex.offsets = p_offset; + ShelfPackTexture &tex = fd->cache[size]->textures.write[p_texture_index]; + tex.shelves.clear(); + for (int32_t i = 0; i < p_offsets.size(); i += 4) { + tex.shelves.push_back(Shelf(p_offsets[i], p_offsets[i + 1], p_offsets[i + 2], p_offsets[i + 3])); + } } PackedInt32Array TextServerFallback::_font_get_texture_offsets(const RID &p_font_rid, const Vector2i &p_size, int64_t p_texture_index) const { @@ -1641,8 +1593,20 @@ PackedInt32Array TextServerFallback::_font_get_texture_offsets(const RID &p_font ERR_FAIL_COND_V(!_ensure_cache_for_size(fd, size), PackedInt32Array()); ERR_FAIL_INDEX_V(p_texture_index, fd->cache[size]->textures.size(), PackedInt32Array()); - const FontTexture &tex = fd->cache[size]->textures[p_texture_index]; - return tex.offsets; + const ShelfPackTexture &tex = fd->cache[size]->textures[p_texture_index]; + PackedInt32Array ret; + ret.resize(tex.shelves.size() * 4); + + int32_t *wr = ret.ptrw(); + int32_t i = 0; + for (const Shelf &E : tex.shelves) { + wr[i * 4] = E.x; + wr[i * 4 + 1] = E.y; + wr[i * 4 + 2] = E.w; + wr[i * 4 + 3] = E.h; + i++; + } + return ret; } PackedInt32Array TextServerFallback::_font_get_glyph_list(const RID &p_font_rid, const Vector2i &p_size) const { @@ -1932,7 +1896,7 @@ RID TextServerFallback::_font_get_glyph_texture_rid(const RID &p_font_rid, const if (RenderingServer::get_singleton() != nullptr) { if (gl[p_glyph | mod].texture_idx != -1) { if (fd->cache[size]->textures[gl[p_glyph | mod].texture_idx].dirty) { - FontTexture &tex = fd->cache[size]->textures.write[gl[p_glyph | mod].texture_idx]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[gl[p_glyph | mod].texture_idx]; Ref img = Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); if (fd->mipmaps) { img->generate_mipmaps(); @@ -1978,7 +1942,7 @@ Size2 TextServerFallback::_font_get_glyph_texture_size(const RID &p_font_rid, co if (RenderingServer::get_singleton() != nullptr) { if (gl[p_glyph | mod].texture_idx != -1) { if (fd->cache[size]->textures[gl[p_glyph | mod].texture_idx].dirty) { - FontTexture &tex = fd->cache[size]->textures.write[gl[p_glyph | mod].texture_idx]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[gl[p_glyph | mod].texture_idx]; Ref img = Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); if (fd->mipmaps) { img->generate_mipmaps(); @@ -2305,7 +2269,7 @@ void TextServerFallback::_font_draw_glyph(const RID &p_font_rid, const RID &p_ca #endif if (RenderingServer::get_singleton() != nullptr) { if (fd->cache[size]->textures[gl.texture_idx].dirty) { - FontTexture &tex = fd->cache[size]->textures.write[gl.texture_idx]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[gl.texture_idx]; Ref img = Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); if (fd->mipmaps) { img->generate_mipmaps(); @@ -2395,7 +2359,7 @@ void TextServerFallback::_font_draw_glyph_outline(const RID &p_font_rid, const R #endif if (RenderingServer::get_singleton() != nullptr) { if (fd->cache[size]->textures[gl.texture_idx].dirty) { - FontTexture &tex = fd->cache[size]->textures.write[gl.texture_idx]; + ShelfPackTexture &tex = fd->cache[size]->textures.write[gl.texture_idx]; Ref img = Image::create_from_data(tex.texture_w, tex.texture_h, false, tex.format, tex.imgdata); if (fd->mipmaps) { img->generate_mipmaps(); diff --git a/modules/text_server_fb/text_server_fb.h b/modules/text_server_fb/text_server_fb.h index 4aeec4f452..151ae13904 100644 --- a/modules/text_server_fb/text_server_fb.h +++ b/modules/text_server_fb/text_server_fb.h @@ -127,20 +127,86 @@ class TextServerFallback : public TextServerExtension { const int rect_range = 1; - struct FontTexture { + struct FontTexturePosition { + int32_t index = -1; + int32_t x = 0; + int32_t y = 0; + + FontTexturePosition() {} + FontTexturePosition(int32_t p_id, int32_t p_x, int32_t p_y) : + index(p_id), x(p_x), y(p_y) {} + }; + + struct Shelf { + int32_t x = 0; + int32_t y = 0; + int32_t w = 0; + int32_t h = 0; + + FontTexturePosition alloc_shelf(int32_t p_id, int32_t p_w, int32_t p_h) { + if (p_w > w || p_h > h) { + return FontTexturePosition(-1, 0, 0); + } + int32_t xx = x; + x += p_w; + w -= p_w; + return FontTexturePosition(p_id, xx, y); + } + + Shelf() {} + Shelf(int32_t p_x, int32_t p_y, int32_t p_w, int32_t p_h) : + x(p_x), y(p_y), w(p_w), h(p_h) {} + }; + + struct ShelfPackTexture { + int32_t texture_w = 1024; + int32_t texture_h = 1024; + Image::Format format; PackedByteArray imgdata; - int texture_w = 0; - int texture_h = 0; - PackedInt32Array offsets; Ref texture; bool dirty = true; - }; - struct FontTexturePosition { - int index = 0; - int x = 0; - int y = 0; + List shelves; + + FontTexturePosition pack_rect(int32_t p_id, int32_t p_h, int32_t p_w) { + int32_t y = 0; + int32_t waste = 0; + Shelf *best_shelf = nullptr; + int32_t best_waste = std::numeric_limits::max(); + + for (Shelf &E : shelves) { + y += E.h; + if (p_w > E.w) { + continue; + } + if (p_h == E.h) { + return E.alloc_shelf(p_id, p_w, p_h); + } + if (p_h > E.h) { + continue; + } + if (p_h < E.h) { + waste = (E.h - p_h) * p_w; + if (waste < best_waste) { + best_waste = waste; + best_shelf = &E; + } + } + } + if (best_shelf) { + return best_shelf->alloc_shelf(p_id, p_w, p_h); + } + if (p_h <= (texture_h - y) && p_w <= texture_w) { + List::Element *E = shelves.push_back(Shelf(0, y, texture_w, p_h)); + return E->get().alloc_shelf(p_id, p_w, p_h); + } + return FontTexturePosition(-1, 0, 0); + } + + ShelfPackTexture() {} + ShelfPackTexture(int32_t p_w, int32_t p_h) : + texture_w(p_w), texture_h(p_h) {} }; struct FontGlyph { @@ -161,7 +227,7 @@ class TextServerFallback : public TextServerExtension { Vector2i size; - Vector textures; + Vector textures; HashMap glyph_map; HashMap kerning_map; -- cgit v1.2.3