Drawing multi-line text fast in C++, MLTextOut

Question

I need to draw a lot of multi-line text to the screen so I first used DrawText but it was getting a bit slow... So I've been looking at a few alternatives: save the drawn text in memory DC's, use Direct3D/Direct2D, write my own function. I don't want my program to be a memory hog so using memory DC's wasn't too great. I don't want to be dependent on D3D either so I was left with one option.

Here is my routine to draw multi-line text using the standard Windows GDI. It splits up the text in lines (split by \r\n's) and then calculates the length of the full line and estimates where it should break.

Since speed is crucial, does anyone sees optimization I could perform to increase speed?

bool MLTextOut(HDC hDC, int x, int y, int cx, int cy, CString str, int nLineHeight = 0)
{
    if (!hDC || cx <= 0 || cy <= 0)
        return false;

    if (str.IsEmpty() || x + cx <= 0 || y + cy <= 0)
        return true;

    const TCHAR *lpszEnd = (const TCHAR *)str + str.GetLength();
    const TCHAR *p1 = str, *p2, *p3, *p4;
    SIZE sz;
    int yInc = 0, n;
    RECT rc = {x, y, x + cx, y + cy};
    bool bContinue;

    while (true)
    {
        p2 = _tcsstr(p1, _T("\r\n"));
        if (!p2)
            p2 = lpszEnd;

        // check if we're already out of the rect

        if (y + yInc >= rc.bottom)
            break;

        // calculate line length

        GetTextExtentPoint32(hDC, p1, p2 - p1, &sz);

        // if line fits

        if (sz.cx <= cx)
        {
            //TextOut(hDC, x, y + yInc, p1, p2 - p1);
            ExtTextOut(hDC, x, y + yInc, ETO_CLIPPED, &rc, p1, p2 - p1, NULL);
            yInc += (nLineHeight ? nLineHeight : sz.cy);
        }

        // when line does not fit

        else
        {
            // estimate the line break point in characters

            n = ((p2 - p1) * cx) / sz.cx;
            if (n < 0)
                n = 0;

            // reverse find nearest space

            for (p3 = p1 + n; p3 > p1; p3--)
                if (*p3 == _T(' '))
                    break;

            // if it's one word spanning this line, but it doesn't fit... let's clip it

            if (p3 == p1)
            {
                // find first space on line

                for (p3 = p1; p3 < p2; p3++)
                    if (*p3 == _T(' '))
                        break;

                ExtTextOut(hDC, x, y + yInc, ETO_CLIPPED, &rc, p1, p3 - p1, NULL);
                yInc += (nLineHeight ? nLineHeight : sz.cy);

                p1 = (p3 == p2 ? p2 + 2 : p3 + 1);
                continue;
            }

            // see if p3 as line end fits

            GetTextExtentPoint32(hDC, p1, p3 - p1, &sz);
            if (sz.cx <= cx)
            {
                // try to add another word until it doesn't fit anymore

                p4 = p3;
                do
                {
                    p3 = p4; // save last position that was valid
                    for (p4 = p4+1; p4 < p2; p4++)
                        if (*p4 == _T(' '))
                            break;
                    if (p4 == p2)
                        break;

                    GetTextExtentPoint32(hDC, p1, p4 - p1, &sz);

                } while (sz.cx <= cx);

                ExtTextOut(hDC, x, y + yInc, ETO_CLIPPED, &rc, p1, p3 - p1, NULL);
                yInc += (nLineHeight ? nLineHeight : sz.cy);
                p1 = p3 + 1;
                continue;
            }
            else
            {
                // try to strip another word until it fits

                bContinue = false;

                do
                {
                    for (p4 = p3-1; p4 > p1; p4--)
                        if (*p4 == _T(' '))
                            break;

                    // if it's one word spanning this line, but it doesn't fit... let's clip it

                    if (p4 == p1)
                    {
                        // find first space on line

                        for (p3 = p1; p3 < p2; p3++)
                            if (*p3 == _T(' '))
                                break;

                        ExtTextOut(hDC, x, y + yInc, ETO_CLIPPED, &rc, p1, p3 - p1, NULL);
                        yInc += (nLineHeight ? nLineHeight : sz.cy);

                        p1 = (p3 == p2 ? p2 + 2 : p3 + 1);
                        bContinue = true;
                        break;
                    }
                    p3 = p4;
                    GetTextExtentPoint32(hDC, p1, p3 - p1, &sz);

                } while (sz.cx > cx);

                if (bContinue)
                    continue;

                ExtTextOut(hDC, x, y + yInc, ETO_CLIPPED, &rc, p1, p3 - p1, NULL);
                yInc += (nLineHeight ? nLineHeight : sz.cy);
                p1 = p3 + 1;
                continue;
            }
        }

        if (p2 == lpszEnd)
            break;
        p1 = p2 + 2;
    }
    return true;
}

Answer 1

I would split this function into two parts:

1. Text layout part - find positions of text runs / lines of text. You can use GetTextExtentPoint32 as you did.
2. And drawing using single call of PolyTextOut

That will allow to skip #1 if text position is not changing between WM_PAINTs - in this case you will get just single PolyTextOut call.

Answer 2

I didn't take any time to try to figure out what you method is or does, but I would suggest, when drawing text it almost always (I say amost, because you could run into edge cases where resource limitations make the following untrue) faster to save your text up, and draw in big chunks, depending on your need, can be done synced to a framerate or based on a callback to your ui thread.

Answer 3

1. Time your solution to see if it really is significantly faster than DrawText. I'd expect DrawText to be optimized pretty well.

2. I've written code like this using a binary search on the length rather than estimating the length. It may not be as fast as estimating the number of characters, but it's hard to know without profiling.

3. Since it looks like you don't care about complex scripts (you're doing simple breaks on spaces), check out GetCharacterPlacement. Although it does a lot of stuff you don't need, it may be faster since you can set a pixel width limit and it will stop as soon as that is exceeded. This can find a line's worth of text in one call (just back up to the last space). Also, if you do keep the extra info from this call, you can use a faster version of ExtTextOut which otherwise would have to recompute a bunch of the metrics.

4. The PolyTextOut call is probably a good idea. Computing the breaks once and drawing in one go is likely to be a big win.

5. When adding words until you overflow, consider measuring just the new word and add that on to a running total. Otherwise, you're measuring most of the line multiple times. (Again, this applies because you're not dealing with complex scripts.)