A best way to draw a lot of independent characters

Question

I'm writing an application that displays a lot of text. It's not words and sentences though, it's binary data displayed in CP437 charset. Current form:

I'm having a problem though with drawing those characters. I need to draw each character one by one, because later I would like to apply different coloring. Those characters should have a transparent background as well, because later I would like to draw sections and ranges with different colors in the background (to group those characters based on some criteria).

The application supports multiple opened files at the same time, but when there are multiple files opened, the drawing starts to be noticeable on fast i7, so it's probably badly written.

What would be the best approach to draw this kind of data in Qt5? Should I just prerender characters to a bitmap and start from there, or it actually is possible to draw lots of characters by using normal Qt functions to draw text?

Edit: I'm using a normal QFrame widget that does drawing in paintEvent, using QPainter. Is this a wrong approach? I've read some docs on QGraphicsScene, from which I've remembered that it's best used in situations where a widget needs to have some control on the objects it draws. I don't need any control on what I draw; I just need to draw it and that's all. I won't reference any particular character after I'll draw it.

The widget has 2000 lines, so I won't paste the whole code, but currently my drawing approach is like this:

• First, create a table (cache) with 256 entries, put the iterator counter to i variable,
• For each entry, create a QStaticText object that contains drawing information about a character identified by ASCII code taken from i variable,
• Later, in the drawing function, for each byte in the input stream (i.e. from the file), draw the data using QStaticText from the cache table. So, to draw ASCII character 0x7A, I'll look up QStaticText from index 0x7a in cache table, and feed this QStaticText object into the QPainter object.

I was also experimenting with a different approach, rendering the whole line in one QPainter::drawText call, and indeed it was faster, but I've lost possibility of coloring each character with different color. I would like to have this possibility.

Answer 1

One solution I sometimes use is to keep a cache of pre-rendered lines. I normally use a doubly-linked LRU list of entries with about twice the lines that can be seen on the screen. Every time a line is used for rendering is moved to the front of the list; when I need to create a new line and the current cache count is past the limit I reuse the last entry in the list.

By storing the final result of individual lines you can repaint the display very quickly as probably in many cases most of the lines will not change from one frame to the next (including when scrolling).

The increased complexity is also reasonably confined in having to invalidate the line when you change the content.

Answer 2

The use of a QGraphicsScene wouldn't improve things - it's an additional layer on top of a QWidget. You're after raw performance, so you shouldn't be using it.

You could implement a QTextDocument as a viewmodel for the visible section of your memory buffer/file, but painting the fresh QTextDocument each time you scroll wouldn't be any faster than drawing things directly on a QWidget.

Using QStaticText is a step in the right direction, but insufficient: rendering QStaticText still requires the rasterization of the glyph's shape. You can do better and cache the pixmap of each QChar, QColor combination that you wish to render: this will be much faster than rasterizing character outlines, whether using QStaticText or not.

Instead of drawing individual characters, you then draw pixmaps from the cache. This commit demonstrates this approach. The character drawing method is:

void drawChar(const QPointF & pos, QChar ch, QColor color, QPainter & p) {
    auto & glyph = m_cache[{ch, color}];
    if (glyph.isNull()) {
        glyph = QPixmap{m_glyphRect.size().toSize()};
        glyph.fill(Qt::white);
        QPainter p{&glyph};
        p.setPen(color);
        p.setFont(m_font);
        p.drawText(m_glyphPos, {ch});
    }
    p.drawPixmap(pos, glyph);
}

You could also cache each (character,foreground,background) tuple. Alas, this gets quickly out of hand when there are many foreground/background combinations.

If all of your backgrounds are of the same color (e.g. white), you'd wish to store a negative mask of the character: the glyph has a white background and a transparent shape. This commit demonstrates this approach. The glyph rectangle is filled with glyph color, then a white mask is applied on top:

void drawChar(const QPointF & pos, QChar ch, QColor color, QPainter & p) {
    auto & glyph = m_glyphs[ch];
    if (glyph.isNull()) {
        glyph = QImage{m_glyphRect.size().toSize(), QImage::Format_ARGB32_Premultiplied};
        glyph.fill(Qt::white);
        QPainter p{&glyph};
        p.setCompositionMode(QPainter::CompositionMode_DestinationOut);
        p.setFont(m_font);
        p.drawText(m_glyphPos, {ch});
    }
    auto rect = m_glyphRect;
    rect.moveTo(pos);
    p.fillRect(rect, color);
    p.drawImage(pos, glyph);
}

Instead of storing a fully pre-rendered character of a given color, you could store just the alpha mask and composite them on-demand:

1. Start with a pre-rendered white glyph on a transparent background (CompositionMode_Source).
2. Fill the glyph rect with background in CompositionMode_SourceOut: the background will remain with a hole for the character itself.
3. Fill the glyph rect with foreground in CompositionMode_DestinationOver: the foreground will fill the hole.
4. (Optional) Draw the composite on the widget, if you're not painting on the widget already.

This turns out to be reasonably fast, and the rendering is fully parallelizable - see the example below.

Note: The pre-rendered glyph could use further premultiplication of the color with alpha to appear less thick.

Yet another approach, with excellent performance, would be to emulate a text-mode display using the GPU. Store the pre-rendered glyph outlines in a texture, store the glyph indices and colors to be rendered in an array, and use OpenGL and two shaders to do the rendering. This example might be a starting point to implement such an approach.

A complete example, using CPU rendering across multiple threads, follows.

We start with the backing store view, used to produce QImages that are views into the backing store for a given widget, and can be used to parallelize painting.

On a 2013 iMac, this code repaints the full-screen widget in about 8ms.

// https://github.com/KubaO/stackoverflown/tree/master/questions/hex-widget-40458515
#include <QtConcurrent>
#include <QtWidgets>
#include <algorithm>
#include <array>
#include <cmath>

struct BackingStoreView {
    QImage *dst = {};
    uchar *data = {};
    const QWidget *widget = {};
    explicit BackingStoreView(const QWidget *widget) {
        if (!widget || !widget->window()) return;
        dst = dynamic_cast<QImage*>(widget->window()->backingStore()->paintDevice());
        if (!dst || dst->depth() % 8) return;
        auto byteDepth = dst->depth()/8;
        auto pos = widget->mapTo(widget->window(), {});
        data = const_cast<uchar*>(dst->constScanLine(pos.y()) + byteDepth * pos.x());
        this->widget = widget;
    }
    // A view onto the backing store of a given widget
    QImage getView() const {
        if (!data) return {};
        QImage ret(data, widget->width(), widget->height(), dst->bytesPerLine(), dst->format());
        ret.setDevicePixelRatio(widget->devicePixelRatio());
        return ret;
    }
    // Is a given image exactly this view?
    bool isAView(const QImage &img) const {
        return data && img.bits() == data && img.depth() == dst->depth()
                && img.width() == widget->width() && img.height() == widget->height()
                && img.bytesPerLine() == dst->bytesPerLine() && img.format() == dst->format();
    }
};

Then, the CP437 character set:

static auto const CP437 = QStringLiteral(
            " ☺☻♥♦♣♠•◘○◙♂♀♪♫☼▶◀↕‼¶§▬↨↑↓→←∟↔▲▼"
            "␣!\"#$%&'()*+,-./0123456789:;<=>?"
            "@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_"
            "`abcdefghijklmnopqrstuvwxyz{|}~ "
            "ÇüéâäàåçêëèïîìÄÅÉæÆôöòûùÿÖÜ¢£¥₧ƒ"
            "áíóúñѪº¿⌐¬½¼¡«»░▒▓│┤╡╢╖╕╣║╗╝╜╛┐"
            "└┴┬├─┼╞╟╚╔╩╦╠═╬╧╨╤╥╙╘╒╓╫╪┘┌█▄▌▐▀"
            "αßΓπΣσµτΦΘΩδ∞φε∩≡±≥≤⌠⌡÷≈°∙·√ⁿ²■ ");

The HexView widget derives from QAbstractScrollArea and visualizes a memory-mapped chunk of data:

class HexView : public QAbstractScrollArea {
    Q_OBJECT
    QImage const m_nullImage;
    const int m_addressChars = 8;
    const int m_dataMargin = 4;
    const char * m_data = {};
    size_t m_dataSize = 0;
    size_t m_dataStart = 0;
    QSize m_glyphSize;
    QPointF m_glyphPos;
    int m_charsPerLine, m_lines;
    QMap<QChar, QImage> m_glyphs;
    QFont m_font{"Monaco"};
    QFontMetricsF m_fm{m_font};
    struct DrawUnit { QPoint pos; const QImage *glyph; QColor fg, bg; };
    QFutureSynchronizer<void> m_sync;
    QVector<DrawUnit> m_chunks;
    QVector<QImage> m_stores;
    using chunk_it = QVector<DrawUnit>::const_iterator;
    using store_it = QVector<QImage>::const_iterator;

    static inline QChar decode(char ch) { return CP437[uchar(ch)]; }
    inline int xStep() const { return m_glyphSize.width(); }
    inline int yStep() const { return m_glyphSize.height(); }
    void initData() {
        int const width = viewport()->width() - m_addressChars*xStep() - m_dataMargin;
        m_charsPerLine = (width > 0) ? width/xStep() : 0;
        m_lines = viewport()->height()/yStep();
        if (m_charsPerLine && m_lines) {
            verticalScrollBar()->setRange(0, m_dataSize/m_charsPerLine);
            verticalScrollBar()->setValue(m_dataStart/m_charsPerLine);
        } else {
            verticalScrollBar()->setRange(0, 0);
        }
    }
    const QImage &glyph(QChar ch) {
        auto &glyph = m_glyphs[ch];
        if (glyph.isNull()) {
            QPointF extent = m_fm.boundingRect(ch).translated(m_glyphPos).bottomRight();
            glyph = QImage(m_glyphSize, QImage::Format_ARGB32_Premultiplied);
            glyph.fill(Qt::transparent);
            QPainter p{&glyph};
            p.setPen(Qt::white);
            p.setFont(m_font);
            p.translate(m_glyphPos);
            p.scale(std::min(1.0, (m_glyphSize.width()-1)/extent.x()),
                    std::min(1.0, (m_glyphSize.height()-1)/extent.y()));
            p.drawText(QPointF{}, {ch});
        }
        return glyph;
    }

The parallelized rendering is done in class methods - they don't modify the state of the widget, other than accessing read-only data, and rendering into the backing store. The threads each act on isolated lines in the store.

    static void drawChar(const DrawUnit & u, QPainter &p) {
        const QRect rect(u.pos, u.glyph->size());
        p.setCompositionMode(QPainter::CompositionMode_Source);
        p.drawImage(u.pos, *u.glyph);
        p.setCompositionMode(QPainter::CompositionMode_SourceOut);
        p.fillRect(rect, u.bg);
        p.setCompositionMode(QPainter::CompositionMode_DestinationOver);
        p.fillRect(rect, u.fg);
    }
    static QFuture<void> submitChunks(chunk_it begin, chunk_it end, store_it store) {
        return QtConcurrent::run([begin, end, store]{
            QPainter p(const_cast<QImage*>(&*store));
            for (auto it = begin; it != end; it++)
                drawChar(*it, p);
        });
    }

This method distributes the chunks of work between threads:

    int processChunks() {
        m_stores.resize(QThread::idealThreadCount());
        BackingStoreView view(viewport());
        if (!view.isAView(m_stores.last()))
            std::generate(m_stores.begin(), m_stores.end(), [&view]{ return view.getView(); });
        std::ptrdiff_t jobSize = std::max(128, (m_chunks.size() / m_stores.size())+1);
        auto const cend = m_chunks.cend();
        int refY = 0;
        auto store = m_stores.cbegin();
        for (auto it = m_chunks.cbegin(); it != cend;) {
            auto end = it + std::min(cend-it, jobSize);
            while (end != cend && (end->pos.y() == refY || (refY = end->pos.y(), false)))
                end++; // break chunks across line boundaries
            m_sync.addFuture(submitChunks(it, end, store));
            it = end;
            store++;
        }
        m_sync.waitForFinished();
        m_sync.clearFutures();
        m_chunks.clear();
        return store - m_stores.cbegin();
    }

The remainder of the implementation is uncontroversial:

protected:
    void paintEvent(QPaintEvent *ev) override {
        QElapsedTimer time;
        time.start();
        QPainter p{viewport()};
        QPoint pos;
        QPoint const step{xStep(), 0};
        auto dividerX = m_addressChars*xStep() + m_dataMargin/2.;
        p.drawLine(dividerX, 0, dividerX, viewport()->height());
        int offset = 0;
        QRect rRect = ev->rect();
        p.end();
        while (offset < m_charsPerLine*m_lines && m_dataStart + offset < m_dataSize) {
            const auto address = QString::number(m_dataStart + offset, 16);
            pos += step * (m_addressChars - address.size());
            for (auto c : address) {
                if (QRect(pos, m_glyphSize).intersects(rRect))
                    m_chunks.push_back({pos, &glyph(c), Qt::black, Qt::white});
                pos += step;
            }
            pos += {m_dataMargin, 0};
            auto bytes = std::min(m_dataSize - offset, (size_t)m_charsPerLine);
            for (int n = bytes; n; n--) {
                if (QRect(pos, m_glyphSize).intersects(rRect))
                    m_chunks.push_back({pos, &glyph(decode(m_data[m_dataStart + offset])), Qt::red, Qt::white});
                pos += step;
                offset ++;
            }
            pos = {0, pos.y() + yStep()};
        }
        int jobs = processChunks();
        newStatus(QStringLiteral("%1ms n=%2").arg(time.nsecsElapsed()/1e6).arg(jobs));
    }
    void resizeEvent(QResizeEvent *) override {
        initData();
    }
    void scrollContentsBy(int, int dy) override {
        m_dataStart = verticalScrollBar()->value() * (size_t)m_charsPerLine;
        viewport()->scroll(0, dy * m_glyphSize.height(), viewport()->rect());
    }
public:
    HexView(QWidget * parent = nullptr) : HexView(nullptr, 0, parent) {}
    HexView(const char * data, size_t size, QWidget * parent = nullptr) :
        QAbstractScrollArea{parent}, m_data(data), m_dataSize(size)
    {
        QRectF glyphRectF{0., 0., 1., 1.};
        for (int i = 0x20; i < 0xE0; ++i)
            glyphRectF = glyphRectF.united(m_fm.boundingRect(CP437[i]));
        m_glyphPos = -glyphRectF.topLeft();
        m_glyphSize = QSize(std::ceil(glyphRectF.width()), std::ceil(glyphRectF.height()));
        initData();
    }
    void setData(const char * data, size_t size) {
        if (data == m_data && size == m_dataSize) return;
        m_data = data;
        m_dataSize = size;
        m_dataStart = 0;
        initData();
        viewport()->update();
    }
    Q_SIGNAL void newStatus(const QString &);
};

We leverage modern 64-bit systems and memory-map the source file to be visualized by the widget. For test purposes, a view of the character set is also available:

int main(int argc, char ** argv) {
    QApplication app{argc, argv};
    QFile file{app.applicationFilePath()};
    if (!file.open(QIODevice::ReadOnly)) return 1;
    auto *const map = (const char*)file.map(0, file.size(), QFile::MapPrivateOption);
    if (!map) return 2;

    QWidget ui;
    QGridLayout layout{&ui};
    HexView view;
    QRadioButton exe{"Executable"};
    QRadioButton charset{"Character Set"};
    QLabel status;
    layout.addWidget(&view, 0, 0, 1, 4);
    layout.addWidget(&exe, 1, 0);
    layout.addWidget(&charset, 1, 1);
    layout.addWidget(&status, 1, 2, 1, 2);
    QObject::connect(&exe, &QPushButton::clicked, [&]{
        view.setData(map, (size_t)file.size());
    });
    QObject::connect(&charset, &QPushButton::clicked, [&]{
        static std::array<char, 256> data;
        std::iota(data.begin(), data.end(), char(0));
        view.setData(data.data(), data.size());
    });
    QObject::connect(&view, &HexView::newStatus, &status, &QLabel::setText);
    charset.click();
    ui.resize(1000, 800);
    ui.show();
    return app.exec();
}

#include "main.moc"