1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#include "Text/BsTextData.h"
4#include "Text/BsFont.h"
5#include "Math/BsVector2.h"
6#include "Debug/BsDebug.h"
7
8namespace bs
9{
10 const int SPACE_CHAR = 32;
11 const int TAB_CHAR = 9;
12
13 void TextDataBase::TextWord::init(bool spacer)
14 {
15 mWidth = mHeight = 0;
16 mSpacer = spacer;
17 mSpaceWidth = 0;
18 mCharsStart = 0;
19 mCharsEnd = 0;
20 mLastChar = nullptr;
21 }
22
23 // Assumes charIdx is an index right after last char in the list (if any). All chars need to be sequential.
24 UINT32 TextDataBase::TextWord::addChar(UINT32 charIdx, const CharDesc& desc)
25 {
26 UINT32 charWidth = calcCharWidth(mLastChar, desc);
27
28 mWidth += charWidth;
29 mHeight = std::max(mHeight, desc.height);
30
31 if(mLastChar == nullptr) // First char
32 mCharsStart = mCharsEnd = charIdx;
33 else
34 mCharsEnd = charIdx;
35
36 mLastChar = &desc;
37
38 return charWidth;
39 }
40
41 UINT32 TextDataBase::TextWord::calcWidthWithChar(const CharDesc& desc)
42 {
43 return mWidth + calcCharWidth(mLastChar, desc);
44 }
45
46 UINT32 TextDataBase::TextWord::calcCharWidth(const CharDesc* prevDesc, const CharDesc& desc)
47 {
48 UINT32 charWidth = desc.xAdvance;
49 if (prevDesc != nullptr)
50 {
51 UINT32 kerning = 0;
52 for (size_t j = 0; j < prevDesc->kerningPairs.size(); j++)
53 {
54 if (prevDesc->kerningPairs[j].otherCharId == desc.charId)
55 {
56 kerning = prevDesc->kerningPairs[j].amount;
57 break;
58 }
59 }
60
61 charWidth += kerning;
62 }
63
64 return charWidth;
65 }
66
67 void TextDataBase::TextWord::addSpace(UINT32 spaceWidth)
68 {
69 mSpaceWidth += spaceWidth;
70 mWidth = mSpaceWidth;
71 mHeight = 0;
72 }
73
74 void TextDataBase::TextLine::init(TextDataBase* textData)
75 {
76 mWidth = 0;
77 mHeight = 0;
78 mIsEmpty = true;
79 mTextData = textData;
80 mWordsStart = mWordsEnd = 0;
81 }
82
83 void TextDataBase::TextLine::finalize(bool hasNewlineChar)
84 {
85 mHasNewline = hasNewlineChar;
86 }
87
88 void TextDataBase::TextLine::add(UINT32 charIdx, const CharDesc& charDesc)
89 {
90 UINT32 charWidth = 0;
91 if(mIsEmpty)
92 {
93 mWordsStart = mWordsEnd = MemBuffer->allocWord(false);
94 mIsEmpty = false;
95 }
96 else
97 {
98 if(MemBuffer->WordBuffer[mWordsEnd].isSpacer())
99 mWordsEnd = MemBuffer->allocWord(false);
100 }
101
102 TextWord& lastWord = MemBuffer->WordBuffer[mWordsEnd];
103 charWidth = lastWord.addChar(charIdx, charDesc);
104
105 mWidth += charWidth;
106 mHeight = std::max(mHeight, lastWord.getHeight());
107 }
108
109 void TextDataBase::TextLine::addSpace(UINT32 spaceWidth)
110 {
111 if(mIsEmpty)
112 {
113 mWordsStart = mWordsEnd = MemBuffer->allocWord(true);
114 mIsEmpty = false;
115 }
116 else
117 mWordsEnd = MemBuffer->allocWord(true); // Each space is counted as its own word, to make certain operations easier
118
119 TextWord& lastWord = MemBuffer->WordBuffer[mWordsEnd];
120 lastWord.addSpace(spaceWidth);
121
122 mWidth += spaceWidth;
123 }
124
125 // Assumes wordIdx is an index right after last word in the list (if any). All words need to be sequential.
126 void TextDataBase::TextLine::addWord(UINT32 wordIdx, const TextWord& word)
127 {
128 if(mIsEmpty)
129 {
130 mWordsStart = mWordsEnd = wordIdx;
131 mIsEmpty = false;
132 }
133 else
134 mWordsEnd = wordIdx;
135
136 mWidth += word.getWidth();
137 mHeight = std::max(mHeight, word.getHeight());
138 }
139
140 UINT32 TextDataBase::TextLine::removeLastWord()
141 {
142 if(mIsEmpty)
143 {
144 assert(false);
145 return 0;
146 }
147
148 UINT32 lastWord = mWordsEnd--;
149 if(mWordsStart == lastWord)
150 {
151 mIsEmpty = true;
152 mWordsStart = mWordsEnd = 0;
153 }
154
155 calculateBounds();
156
157 return lastWord;
158 }
159
160 UINT32 TextDataBase::TextLine::calcWidthWithChar(const CharDesc& desc)
161 {
162 UINT32 charWidth = 0;
163
164 if (!mIsEmpty)
165 {
166 TextWord& lastWord = MemBuffer->WordBuffer[mWordsEnd];
167 if (lastWord.isSpacer())
168 charWidth = TextWord::calcCharWidth(nullptr, desc);
169 else
170 charWidth = lastWord.calcWidthWithChar(desc) - lastWord.getWidth();
171 }
172 else
173 {
174 charWidth = TextWord::calcCharWidth(nullptr, desc);
175 }
176
177 return mWidth + charWidth;
178 }
179
180 bool TextDataBase::TextLine::isAtWordBoundary() const
181 {
182 return mIsEmpty || MemBuffer->WordBuffer[mWordsEnd].isSpacer();
183 }
184
185 UINT32 TextDataBase::TextLine::fillBuffer(UINT32 page, Vector2* vertices, Vector2* uvs, UINT32* indexes, UINT32 offset, UINT32 size) const
186 {
187 UINT32 numQuads = 0;
188
189 if(mIsEmpty)
190 return numQuads;
191
192 UINT32 penX = 0;
193 UINT32 penNegativeXOffset = 0;
194 for(UINT32 i = mWordsStart; i <= mWordsEnd; i++)
195 {
196 const TextWord& word = mTextData->getWord(i);
197
198 if(word.isSpacer())
199 {
200 // We store invisible space quads in the first page. Even though they aren't needed
201 // for rendering and we could just leave an empty space, they are needed for intersection tests
202 // for things like determining caret placement and selection areas
203 if(page == 0)
204 {
205 INT32 curX = penX;
206 INT32 curY = 0;
207
208 UINT32 curVert = offset * 4;
209 UINT32 curIndex = offset * 6;
210
211 vertices[curVert + 0] = Vector2((float)curX, (float)curY);
212 vertices[curVert + 1] = Vector2((float)(curX + word.getWidth()), (float)curY);
213 vertices[curVert + 2] = Vector2((float)curX, (float)curY + (float)mTextData->getLineHeight());
214 vertices[curVert + 3] = Vector2((float)(curX + word.getWidth()), (float)curY + (float)mTextData->getLineHeight());
215
216 if(uvs != nullptr)
217 {
218 uvs[curVert + 0] = Vector2(0.0f, 0.0f);
219 uvs[curVert + 1] = Vector2(0.0f, 0.0f);
220 uvs[curVert + 2] = Vector2(0.0f, 0.0f);
221 uvs[curVert + 3] = Vector2(0.0f, 0.0f);
222 }
223
224 // Triangles are back-facing which makes them invisible
225 if(indexes != nullptr)
226 {
227 indexes[curIndex + 0] = curVert + 0;
228 indexes[curIndex + 1] = curVert + 2;
229 indexes[curIndex + 2] = curVert + 1;
230 indexes[curIndex + 3] = curVert + 1;
231 indexes[curIndex + 4] = curVert + 2;
232 indexes[curIndex + 5] = curVert + 3;
233 }
234
235 offset++;
236 numQuads++;
237
238 if(offset > size)
239 BS_EXCEPT(InternalErrorException, "Out of buffer bounds. Buffer size: " + toString(size));
240 }
241
242 penX += word.getWidth();
243 }
244 else
245 {
246 UINT32 kerning = 0;
247 for(UINT32 j = word.getCharsStart(); j <= word.getCharsEnd(); j++)
248 {
249 const CharDesc& curChar = mTextData->getChar(j);
250
251 INT32 curX = penX + curChar.xOffset;
252 INT32 curY = ((INT32) mTextData->getBaselineOffset() - curChar.yOffset);
253
254 curX += penNegativeXOffset;
255 penX += curChar.xAdvance + kerning;
256
257 kerning = 0;
258 if((j + 1) <= word.getCharsEnd())
259 {
260 const CharDesc& nextChar = mTextData->getChar(j + 1);
261 for(size_t j = 0; j < curChar.kerningPairs.size(); j++)
262 {
263 if(curChar.kerningPairs[j].otherCharId == nextChar.charId)
264 {
265 kerning = curChar.kerningPairs[j].amount;
266 break;
267 }
268 }
269 }
270
271 if(curChar.page != page)
272 continue;
273
274 UINT32 curVert = offset * 4;
275 UINT32 curIndex = offset * 6;
276
277 vertices[curVert + 0] = Vector2((float)curX, (float)curY);
278 vertices[curVert + 1] = Vector2((float)(curX + curChar.width), (float)curY);
279 vertices[curVert + 2] = Vector2((float)curX, (float)curY + (float)curChar.height);
280 vertices[curVert + 3] = Vector2((float)(curX + curChar.width), (float)curY + (float)curChar.height);
281
282 if(uvs != nullptr)
283 {
284 uvs[curVert + 0] = Vector2(curChar.uvX, curChar.uvY);
285 uvs[curVert + 1] = Vector2(curChar.uvX + curChar.uvWidth, curChar.uvY);
286 uvs[curVert + 2] = Vector2(curChar.uvX, curChar.uvY + curChar.uvHeight);
287 uvs[curVert + 3] = Vector2(curChar.uvX + curChar.uvWidth, curChar.uvY + curChar.uvHeight);
288 }
289
290 if(indexes != nullptr)
291 {
292 indexes[curIndex + 0] = curVert + 0;
293 indexes[curIndex + 1] = curVert + 1;
294 indexes[curIndex + 2] = curVert + 2;
295 indexes[curIndex + 3] = curVert + 1;
296 indexes[curIndex + 4] = curVert + 3;
297 indexes[curIndex + 5] = curVert + 2;
298 }
299
300 offset++;
301 numQuads++;
302
303 if(offset > size)
304 BS_EXCEPT(InternalErrorException, "Out of buffer bounds. Buffer size: " + toString(size));
305 }
306 }
307 }
308
309 return numQuads;
310 }
311
312 UINT32 TextDataBase::TextLine::getNumChars() const
313 {
314 if(mIsEmpty)
315 return 0;
316
317 UINT32 numChars = 0;
318 for(UINT32 i = mWordsStart; i <= mWordsEnd; i++)
319 {
320 TextWord& word = MemBuffer->WordBuffer[i];
321
322 if(word.isSpacer())
323 numChars++;
324 else
325 numChars += (UINT32)word.getNumChars();
326 }
327
328 return numChars;
329 }
330
331 void TextDataBase::TextLine::calculateBounds()
332 {
333 mWidth = 0;
334 mHeight = 0;
335
336 if(mIsEmpty)
337 return;
338
339 for(UINT32 i = mWordsStart; i <= mWordsEnd; i++)
340 {
341 TextWord& word = MemBuffer->WordBuffer[i];
342
343 mWidth += word.getWidth();
344 mHeight = std::max(mHeight, word.getHeight());
345 }
346 }
347
348 TextDataBase::TextDataBase(const U32String& text, const HFont& font, UINT32 fontSize, UINT32 width, UINT32 height,
349 bool wordWrap, bool wordBreak)
350 : mChars(nullptr), mNumChars(0), mWords(nullptr), mNumWords(0), mLines(nullptr), mNumLines(0), mPageInfos(nullptr)
351 , mNumPageInfos(0), mFont(font), mFontData(nullptr)
352 {
353 // In order to reduce number of memory allocations algorithm first calculates data into temporary buffers and then copies the results
354 initAlloc();
355
356 if(font != nullptr)
357 {
358 UINT32 nearestSize = font->getClosestSize(fontSize);
359 mFontData = font->getBitmap(nearestSize);
360 }
361
362 if(mFontData == nullptr || mFontData->texturePages.size() == 0)
363 return;
364
365 if(mFontData->size != fontSize)
366 {
367 LOGWRN("Unable to find font with specified size (" + toString(fontSize) + "). Using nearest available size: " + toString(mFontData->size));
368 }
369
370 bool widthIsLimited = width > 0;
371 mFont = font;
372
373 UINT32 curLineIdx = MemBuffer->allocLine(this);
374 UINT32 curHeight = mFontData->lineHeight;
375 UINT32 charIdx = 0;
376
377 while(true)
378 {
379 if(charIdx >= text.size())
380 break;
381
382 UINT32 charId = text[charIdx];
383 const CharDesc& charDesc = mFontData->getCharDesc(charId);
384
385 TextLine* curLine = &MemBuffer->LineBuffer[curLineIdx];
386
387 if(text[charIdx] == '\n' || text[charIdx] == '\r')
388 {
389 curLine->finalize(true);
390
391 curLineIdx = MemBuffer->allocLine(this);
392 curLine = &MemBuffer->LineBuffer[curLineIdx];
393
394 curHeight += mFontData->lineHeight;
395
396 charIdx++;
397
398 // Check for \r\n
399 if (text[charIdx - 1] == '\r' && charIdx < text.size())
400 {
401 if (text[charIdx] == '\n')
402 charIdx++;
403 }
404
405 continue;
406 }
407
408 if (widthIsLimited && wordWrap)
409 {
410 UINT32 widthWithChar = 0;
411 if (charIdx == SPACE_CHAR)
412 widthWithChar = curLine->getWidth() + getSpaceWidth();
413 else if (charIdx == TAB_CHAR)
414 widthWithChar = curLine->getWidth() + getSpaceWidth() * 4;
415 else
416 widthWithChar = curLine->calcWidthWithChar(charDesc);
417
418 if (widthWithChar > width && !curLine->isEmpty())
419 {
420 bool atWordBoundary = charId == SPACE_CHAR || charId == TAB_CHAR || curLine->isAtWordBoundary();
421
422 if (!atWordBoundary) // Need to break word into multiple pieces, or move it to next line
423 {
424 UINT32 lastWordIdx = curLine->removeLastWord();
425 TextWord& lastWord = MemBuffer->WordBuffer[lastWordIdx];
426
427 bool wordFits = lastWord.calcWidthWithChar(charDesc) <= width;
428 if (wordFits && !curLine->isEmpty())
429 {
430 curLine->finalize(false);
431
432 curLineIdx = MemBuffer->allocLine(this);
433 curLine = &MemBuffer->LineBuffer[curLineIdx];
434
435 curHeight += mFontData->lineHeight;
436
437 curLine->addWord(lastWordIdx, lastWord);
438 }
439 else
440 {
441 if (wordBreak)
442 {
443 curLine->addWord(lastWordIdx, lastWord);
444 curLine->finalize(false);
445
446 curLineIdx = MemBuffer->allocLine(this);
447 curLine = &MemBuffer->LineBuffer[curLineIdx];
448
449 curHeight += mFontData->lineHeight;
450 }
451 else
452 {
453 if (!curLine->isEmpty()) // Add new line unless current line is empty (to avoid constantly moving the word to new lines)
454 {
455 curLine->finalize(false);
456
457 curLineIdx = MemBuffer->allocLine(this);
458 curLine = &MemBuffer->LineBuffer[curLineIdx];
459
460 curHeight += mFontData->lineHeight;
461 }
462
463 curLine->addWord(lastWordIdx, lastWord);
464 }
465 }
466 }
467 else if (charId != SPACE_CHAR && charId != TAB_CHAR) // If current char is whitespace add it to the existing line even if it doesn't fit
468 {
469 curLine->finalize(false);
470
471 curLineIdx = MemBuffer->allocLine(this);
472 curLine = &MemBuffer->LineBuffer[curLineIdx];
473
474 curHeight += mFontData->lineHeight;
475 }
476 }
477 }
478
479 if(charId == SPACE_CHAR)
480 {
481 curLine->addSpace(getSpaceWidth());
482 MemBuffer->addCharToPage(0, *mFontData);
483 }
484 else if (charId == TAB_CHAR)
485 {
486 curLine->addSpace(getSpaceWidth() * 4);
487 MemBuffer->addCharToPage(0, *mFontData);
488 }
489 else
490 {
491 curLine->add(charIdx, charDesc);
492 MemBuffer->addCharToPage(charDesc.page, *mFontData);
493 }
494
495 charIdx++;
496 }
497
498 MemBuffer->LineBuffer[curLineIdx].finalize(true);
499
500 // Now that we have all the data we need, allocate the permanent buffers and copy the data
501 mNumChars = (UINT32)text.size();
502 mNumWords = MemBuffer->NextFreeWord;
503 mNumLines = MemBuffer->NextFreeLine;
504 mNumPageInfos = MemBuffer->NextFreePageInfo;
505 }
506
507 void TextDataBase::generatePersistentData(const U32String& text, UINT8* buffer, UINT32& size, bool freeTemporary)
508 {
509 UINT32 charArraySize = mNumChars * sizeof(const CharDesc*);
510 UINT32 wordArraySize = mNumWords * sizeof(TextWord);
511 UINT32 lineArraySize = mNumLines * sizeof(TextLine);
512 UINT32 pageInfoArraySize = mNumPageInfos * sizeof(PageInfo);
513
514 if (buffer == nullptr)
515 {
516 size = charArraySize + wordArraySize + lineArraySize + pageInfoArraySize;;
517 return;
518 }
519
520 UINT8* dataPtr = (UINT8*)buffer;
521 mChars = (const CharDesc**)dataPtr;
522
523 for (UINT32 i = 0; i < mNumChars; i++)
524 {
525 UINT32 charId = text[i];
526 const CharDesc& charDesc = mFontData->getCharDesc(charId);
527
528 mChars[i] = &charDesc;
529 }
530
531 dataPtr += charArraySize;
532 mWords = (TextWord*)dataPtr;
533 memcpy(mWords, &MemBuffer->WordBuffer[0], wordArraySize);
534
535 dataPtr += wordArraySize;
536 mLines = (TextLine*)dataPtr;
537 memcpy(mLines, &MemBuffer->LineBuffer[0], lineArraySize);
538
539 dataPtr += lineArraySize;
540 mPageInfos = (PageInfo*)dataPtr;
541 memcpy((void*)mPageInfos, (void*)&MemBuffer->PageBuffer[0], pageInfoArraySize);
542
543 if (freeTemporary)
544 MemBuffer->deallocAll();
545 }
546
547 const HTexture& TextDataBase::getTextureForPage(UINT32 page) const
548 {
549 return mFontData->texturePages[page];
550 }
551
552 INT32 TextDataBase::getBaselineOffset() const
553 {
554 return mFontData->baselineOffset;
555 }
556
557 UINT32 TextDataBase::getLineHeight() const
558 {
559 return mFontData->lineHeight;
560 }
561
562 UINT32 TextDataBase::getSpaceWidth() const
563 {
564 return mFontData->spaceWidth;
565 }
566
567 void TextDataBase::initAlloc()
568 {
569 if (MemBuffer == nullptr)
570 MemBuffer = bs_new<BufferData>();
571 }
572
573 BS_THREADLOCAL TextDataBase::BufferData* TextDataBase::MemBuffer = nullptr;
574
575 TextDataBase::BufferData::BufferData()
576 {
577 WordBufferSize = 2000;
578 LineBufferSize = 500;
579 PageBufferSize = 20;
580
581 NextFreeWord = 0;
582 NextFreeLine = 0;
583 NextFreePageInfo = 0;
584
585 WordBuffer = bs_newN<TextWord>(WordBufferSize);
586 LineBuffer = bs_newN<TextLine>(LineBufferSize);
587 PageBuffer = bs_newN<PageInfo>(PageBufferSize);
588 }
589
590 TextDataBase::BufferData::~BufferData()
591 {
592 bs_deleteN(WordBuffer, WordBufferSize);
593 bs_deleteN(LineBuffer, LineBufferSize);
594 bs_deleteN(PageBuffer, PageBufferSize);
595 }
596
597 UINT32 TextDataBase::BufferData::allocWord(bool spacer)
598 {
599 if(NextFreeWord >= WordBufferSize)
600 {
601 UINT32 newBufferSize = WordBufferSize * 2;
602 TextWord* newBuffer = bs_newN<TextWord>(newBufferSize);
603 memcpy(WordBuffer, newBuffer, WordBufferSize);
604
605 bs_deleteN(WordBuffer, WordBufferSize);
606 WordBuffer = newBuffer;
607 WordBufferSize = newBufferSize;
608 }
609
610 WordBuffer[NextFreeWord].init(spacer);
611
612 return NextFreeWord++;
613 }
614
615 UINT32 TextDataBase::BufferData::allocLine(TextDataBase* textData)
616 {
617 if(NextFreeLine >= LineBufferSize)
618 {
619 UINT32 newBufferSize = LineBufferSize * 2;
620 TextLine* newBuffer = bs_newN<TextLine>(newBufferSize);
621 memcpy(LineBuffer, newBuffer, LineBufferSize);
622
623 bs_deleteN(LineBuffer, LineBufferSize);
624 LineBuffer = newBuffer;
625 LineBufferSize = newBufferSize;
626 }
627
628 LineBuffer[NextFreeLine].init(textData);
629
630 return NextFreeLine++;
631 }
632
633 void TextDataBase::BufferData::deallocAll()
634 {
635 NextFreeWord = 0;
636 NextFreeLine = 0;
637 NextFreePageInfo = 0;
638 }
639
640 void TextDataBase::BufferData::addCharToPage(UINT32 page, const FontBitmap& fontData)
641 {
642 if(NextFreePageInfo >= PageBufferSize)
643 {
644 UINT32 newBufferSize = PageBufferSize * 2;
645 PageInfo* newBuffer = bs_newN<PageInfo>(newBufferSize);
646 memcpy((void*)PageBuffer, (void*)newBuffer, PageBufferSize);
647
648 bs_deleteN(PageBuffer, PageBufferSize);
649 PageBuffer = newBuffer;
650 PageBufferSize = newBufferSize;
651 }
652
653 while(page >= NextFreePageInfo)
654 {
655 PageBuffer[NextFreePageInfo].numQuads = 0;
656
657 NextFreePageInfo++;
658 }
659
660 PageBuffer[page].numQuads++;
661 }
662
663 UINT32 TextDataBase::getWidth() const
664 {
665 UINT32 width = 0;
666
667 for(UINT32 i = 0; i < mNumLines; i++)
668 width = std::max(width, mLines[i].getWidth());
669
670 return width;
671 }
672
673 UINT32 TextDataBase::getHeight() const
674 {
675 UINT32 height = 0;
676
677 for(UINT32 i = 0; i < mNumLines; i++)
678 height += mLines[i].getHeight();
679
680 return height;
681 }
682}