1 // Copyright (C) 2002-2012 Nikolaus Gebhardt
2 // This file is part of the "Irrlicht Engine".
3 // For conditions of distribution and use, see copyright notice in irrlicht.h
4 
5 #ifndef __GLYPH_LAYOUT_H_INCLUDED__
6 #define __GLYPH_LAYOUT_H_INCLUDED__
7 
8 #include "irrTypes.h"
9 #include "dimension2d.h"
10 
11 #include <algorithm>
12 #include <numeric>
13 #include <vector>
14 
15 namespace irr
16 {
17 namespace gui
18 {
19 
20 enum GlyphLayoutFlag
21 {
22 GLF_RTL_LINE = 1, /* This line from this glyph is RTL. */
23 GLF_RTL_CHAR = 2, /* This character(s) from this glyph is RTL. */
24 GLF_BREAKABLE = 4, /* This glyph is breakable when line breaking. */
25 GLF_QUICK_DRAW = 8, /* This glyph is not created by libraqm, which get x_advance_x directly from font. */
26 GLF_NEWLINE = 16, /* This glyph will start a newline. */
27 GLF_COLORED = 32 /* This glyph is a colored one (for example emoji). */
28 };
29 
30 enum GlyphLayoutDraw
31 {
32 GLD_NONE = 0, /* Default flag. */
33 GLD_MARKED = 1, /* This glyph will be drawn with background marked for marked text. */
34 GLD_COMPOSING = 2 /* This glyph will be drawn with underline (for example composing text). */
35 };
36 
37 //! GlyphLayout copied from libraqm.
38 struct GlyphLayout
39 {
40 u32 index;
41 s32 x_advance;
42 //s32 y_advance; we don't use y_advance atm
43 s32 x_offset;
44 s32 y_offset;
45 /* Above variable is same for raqm_glyph_t */
46 // If some characters share the same glyph
47 std::vector<s32> cluster;
48 std::vector<u8> draw_flags;
49 //! used to sorting back the visual order after line breaking
50 u32 original_index;
51 u16 flags;
52 //! this is the face_idx used in stk face ttf
53 u16 face_idx;
54 };
55 
56 namespace Private
57 {
58     inline void breakLine(std::vector<GlyphLayout> gls, f32 max_line_width,
59         f32 inverse_shaping, f32 scale, std::vector<std::vector<GlyphLayout> >& result);
60 }
61 
eraseTopLargerThan(std::vector<GlyphLayout> & gls,f32 height_per_line,f32 max_height)62 inline void eraseTopLargerThan(std::vector<GlyphLayout>& gls,
63     f32 height_per_line, f32 max_height)
64 {
65     if (max_height < height_per_line * 2.0f)
66         return;
67 
68     std::vector<u32> newline_positions;
69     for (unsigned i = 0; i < gls.size(); i++)
70     {
71         const GlyphLayout& glyph = gls[i];
72         if ((glyph.flags & GLF_NEWLINE) != 0)
73         {
74             newline_positions.push_back(i);
75             continue;
76         }
77     }
78 
79     // Handle the first line
80     f32 total_height = height_per_line +
81         (f32)newline_positions.size() * height_per_line;
82     if (total_height > max_height)
83     {
84         u32 idx = (u32)((total_height - max_height) / height_per_line);
85         if (idx < newline_positions.size())
86         {
87             auto end_it = gls.begin() + newline_positions[idx] + 1;
88             if (end_it != gls.end())
89                 gls.erase(gls.begin(), end_it);
90         }
91     }
92 }
93 
94 inline core::dimension2d<u32> getGlyphLayoutsDimension(
95     const std::vector<GlyphLayout>& gls, s32 height_per_line, f32 inverse_shaping,
96     f32 scale, s32 cluster = -1)
97 {
98     core::dimension2d<f32> dim(0.0f, 0.0f);
99     core::dimension2d<f32> this_line(0.0f, (f32)height_per_line);
100 
101     for (unsigned i = 0; i < gls.size(); i++)
102     {
103         const GlyphLayout& glyph = gls[i];
104         if ((glyph.flags & GLF_NEWLINE) != 0)
105         {
106             dim.Height += this_line.Height;
107             if (dim.Width < this_line.Width)
108                 dim.Width = this_line.Width;
109             this_line.Width = 0;
110             continue;
111         }
112         f32 cur_width = (s32)(glyph.x_advance * inverse_shaping) * scale;
113         bool found_cluster = false;
114         // Cursor positioning
115         if (cluster != -1)
116         {
117             auto it = std::find(glyph.cluster.begin(), glyph.cluster.end(), cluster);
118             if (it != glyph.cluster.end() &&
119                 (i == gls.size() - 1 || cluster != gls[i + 1].cluster.front()))
120             {
121                 found_cluster = true;
122                 // Get cluster ratio to total glyph width, so for example
123                 // cluster 0 in ffi glyph will be 0.333
124                 f32 ratio = f32(it - glyph.cluster.begin() + 1) /
125                     (f32)glyph.cluster.size();
126                 // Show cursor in left side, so no need to add width
127                 if ((glyph.flags & GLF_RTL_CHAR) != 0)
128                     cur_width = 0;
129                 else
130                     cur_width *= ratio;
131             }
132         }
133         this_line.Width += cur_width;
134         if (found_cluster)
135             break;
136     }
137 
138     dim.Height += this_line.Height;
139     if (dim.Width < this_line.Width)
140         dim.Width = this_line.Width;
141 
142     core::dimension2d<u32> ret_dim(0, 0);
143     ret_dim.Width = (u32)(dim.Width + 0.9f); // round up
144     ret_dim.Height = (u32)(dim.Height + 0.9f);
145 
146     return ret_dim;
147 }
148 
getCurosrFromDimension(f32 x,f32 y,const std::vector<GlyphLayout> & gls,s32 height_per_line,f32 inverse_shaping,f32 scale)149 inline s32 getCurosrFromDimension(f32 x, f32 y,
150     const std::vector<GlyphLayout>& gls, s32 height_per_line,
151     f32 inverse_shaping, f32 scale)
152 {
153     if (gls.empty())
154         return 0;
155     f32 total_width = 0.0f;
156     for (unsigned i = 0; i < gls.size(); i++)
157     {
158         const GlyphLayout& glyph = gls[i];
159         if ((glyph.flags & GLF_NEWLINE) != 0)
160         {
161             // TODO: handling newline
162             break;
163         }
164         f32 cur_width = (s32)(glyph.x_advance * inverse_shaping) * scale;
165         if (glyph.cluster.size() == 1)
166         {
167             // One more character threshold because we show the cursor position
168             // opposite side for RTL character
169             if (glyph.flags & GLF_RTL_CHAR)
170             {
171                 if (i == 0 && cur_width * 0.5 > x)
172                     return glyph.cluster.front() + 1;
173                 if (total_width + cur_width * 1.5 > x)
174                     return glyph.cluster.front();
175             }
176             else
177             {
178                 if (i == 0 && cur_width * 0.5 > x)
179                     return 0;
180                 if (total_width + cur_width * 0.5 > x)
181                     return glyph.cluster.front();
182             }
183         }
184         else if (total_width + cur_width > x)
185         {
186             // Handle glyph like 'ffi'
187             f32 each_cluster_width = cur_width / (f32)glyph.cluster.size();
188             f32 remain_width = x - total_width;
189             total_width = 0.0f;
190             for (unsigned j = 0; j < glyph.cluster.size(); j++)
191             {
192                 if (total_width + each_cluster_width * 0.5 > remain_width)
193                     return glyph.cluster[j];
194                 total_width += each_cluster_width;
195             }
196             return glyph.cluster.back();
197         }
198         total_width += cur_width;
199     }
200     return gls.back().flags & GLF_RTL_CHAR ?
201         0 : gls.back().cluster.back() + 1;
202 }
203 
getGlyphLayoutsWidthPerLine(const std::vector<GlyphLayout> & gls,f32 inverse_shaping,f32 scale)204 inline std::vector<f32> getGlyphLayoutsWidthPerLine(
205     const std::vector<GlyphLayout>& gls, f32 inverse_shaping, f32 scale)
206 {
207     std::vector<f32> result;
208     f32 cur_width = 0.0f;
209     for (auto& glyph : gls)
210     {
211         if ((glyph.flags & GLF_NEWLINE) != 0)
212         {
213             result.push_back(cur_width);
214             cur_width = 0;
215             continue;
216         }
217         cur_width += (s32)(glyph.x_advance * inverse_shaping) * scale;
218     }
219 
220     result.push_back(cur_width);
221     return result;
222 }
223 
breakGlyphLayouts(std::vector<GlyphLayout> & gls,f32 max_line_width,f32 inverse_shaping,f32 scale)224 inline void breakGlyphLayouts(std::vector<GlyphLayout>& gls, f32 max_line_width,
225                               f32 inverse_shaping, f32 scale)
226 {
227     if (gls.size() < 2)
228         return;
229     std::vector<std::vector<GlyphLayout> > broken_line;
230     u32 start = 0;
231     for (u32 i = 0; i < gls.size(); i++)
232     {
233         GlyphLayout& glyph = gls[i];
234         if ((glyph.flags & GLF_NEWLINE) != 0)
235         {
236             Private::breakLine({ gls.begin() + start, gls.begin() + i},
237                 max_line_width, inverse_shaping, scale, broken_line);
238             start = i + 1;
239         }
240     }
241     if (start - gls.size() - 1 > 0)
242     {
243         Private::breakLine({ gls.begin() + start, gls.begin() + gls.size() },
244             max_line_width, inverse_shaping, scale, broken_line);
245     }
246 
247     gls.clear();
248     // Sort glyphs in original order
249     for (u32 i = 0; i < broken_line.size(); i++)
250     {
251         if (i != 0)
252         {
253             gui::GlyphLayout gl = { 0 };
254             gl.flags = gui::GLF_NEWLINE;
255             gls.push_back(gl);
256         }
257         auto& line = broken_line[i];
258         std::sort(line.begin(), line.end(), []
259             (const irr::gui::GlyphLayout& a_gi,
260             const irr::gui::GlyphLayout& b_gi)
261             {
262                 return a_gi.original_index < b_gi.original_index;
263             });
264         for (auto& glyph : line)
265             gls.push_back(glyph);
266     }
267 }
268 
269 namespace Private
270 {
271     /** Used it only for single line (ie without line breaking mark). */
getGlyphLayoutsWidth(const std::vector<GlyphLayout> & gls,f32 inverse_shaping,f32 scale)272     inline f32 getGlyphLayoutsWidth(const std::vector<GlyphLayout>& gls,
273                                     f32 inverse_shaping, f32 scale)
274     {
275         return std::accumulate(gls.begin(), gls.end(), 0.0f,
276             [inverse_shaping, scale] (const f32 previous,
277                 const irr::gui::GlyphLayout& cur_gi)
278             {
279                 return previous + (s32)(cur_gi.x_advance * inverse_shaping) * scale;
280             });
281     }
282 
breakLine(std::vector<GlyphLayout> gls,f32 max_line_width,f32 inverse_shaping,f32 scale,std::vector<std::vector<GlyphLayout>> & result)283     inline void breakLine(std::vector<GlyphLayout> gls, f32 max_line_width,
284         f32 inverse_shaping, f32 scale,
285         std::vector<std::vector<GlyphLayout> >& result)
286     {
287         const f32 line_size = getGlyphLayoutsWidth(gls, inverse_shaping, scale);
288         if (line_size <= max_line_width)
289         {
290             result.emplace_back(std::move(gls));
291             return;
292         }
293 
294         // Sort glyphs in logical order
295         std::sort(gls.begin(), gls.end(), []
296             (const GlyphLayout& a_gi, const GlyphLayout& b_gi)
297             {
298                 return a_gi.cluster.front() < b_gi.cluster.front();
299             });
300 
301         u32 end = 0;
302         s32 start = 0;
303         f32 total_width = 0.0f;
304 
305         for (; end < gls.size(); end++)
306         {
307             f32 cur_width = (s32)(gls[end].x_advance * inverse_shaping) * scale;
308             if (cur_width > max_line_width)
309             {
310                 // Very large glyph
311                 result.push_back({gls[end]});
312                 start = end;
313             }
314             else if (cur_width + total_width <= max_line_width)
315             {
316                 total_width += cur_width;
317             }
318             else
319             {
320                 int break_point = end - 1;
321                 do
322                 {
323                     if (break_point <= 0 || break_point == start)
324                     {
325                         // Forcely break at line ending position if no break
326                         // mark, this fix text without space of out network
327                         // lobby
328                         result.push_back(
329                             {gls.begin() + start, gls.begin() + end});
330                         start = end;
331                         total_width = (s32)(gls[end].x_advance * inverse_shaping) * scale;
332                         break;
333                     }
334                     if ((gls[break_point].flags & GLF_BREAKABLE) != 0)
335                     {
336                         result.push_back(
337                             {gls.begin() + start, gls.begin() + break_point + 1});
338                         end = start = break_point + 1;
339                         total_width = (s32)(gls[end].x_advance * inverse_shaping) * scale;
340                         break;
341                     }
342                     break_point--;
343                 }
344                 while (break_point >= start);
345             }
346         }
347         if (gls.begin() + start != gls.end())
348         {
349             result.push_back({gls.begin() + start, gls.end()});
350         }
351     }
352 }
353 
354 } // end namespace gui
355 } // end namespace irr
356 
357 #endif
358 
359