Зачем вообще его писать
Любой просмотрщик SVG, который у меня был под Windows, оказывался либо браузером, либо 40-мегабайтным приложением на Electron, показывающим иконку в 12 КБ за две секунды. Все части стека векторной графики хорошо изучены — на входе XML, в середине фигуры, на выходе покрытие, — поэтому я написал всё целиком: 16 файлов, 4 280 строк C11, из внешнего только gdi32, comdlg32, shell32 и user32. Сборка одной строкой gcc под MinGW-w64.
Интересно не то, что это работает. Интересно, какие четыре решения делают это быстрым.
1. Разбирать на месте, выделять в арене
xml.c не копирует ни одной строки. Файл читается один раз в буфер, а DOM хранит указатели и длины внутрь этого буфера; сущности разворачиваются переписыванием на месте. Узлы и атрибуты берутся из bump-аллокатора (arena.h), поэтому разбор выделяет память несколькими крупными блоками и освобождает её одной инструкцией. Поиск элементов по id — а он постоянно нужен для use, градиентов по href и clip-path — идёт через хеш-таблицу, а не обходом дерева. Есть и свой парсер float: strtod учитывает локаль и неожиданно медленен, когда его зовут несколько миллионов раз на данных путей.
2. Компилировать DOM в плоский список фигур
svg.c превращает дерево в плоский массив фигур: геометрия, заливка, трансформация, обтравка. Все команды путей, абсолютные и относительные, компактные флаги дуг; линейные и радиальные градиенты с наследованием через href, gradientUnits, gradientTransform и spreadMethod; clipPath и mask (как геометрическая обтравка); разворачивание use/symbol; CSS в <style> с селекторами tag, .class, #id, tag.class и .a.b; 148 именованных цветов; viewBox с preserveAspectRatio; единицы px, pt, pc, mm, cm, in, em, ex и %.
Текст — та часть, которую все ожидают увидеть сложной. Она несложная, если отказаться писать шрифтовой движок: контуры глифов берутся из установленных системных шрифтов через GetGlyphOutline из GDI, а дальше это обычные пути. То есть text заливается, обводится, обтравливается, трансформируется и сглаживается ровно тем же кодом, что и прямоугольник, и вложенные tspan, text-anchor, letter-spacing и подстановка шрифтов достаются бесплатно.
3. Растеризатор: точная площадь, без суперсэмплинга
Это сердце проекта. raster.c использует аккумулятор знакового покрытия в стиле font-rs: для каждого ребра в буфер накопления добавляется его точный вклад по площади, а префиксная сумма вдоль строки превращает накопленные приращения в покрытие. Важны два следствия:
- Стоимость ребра пропорциональна числу строк, которые оно пересекает, а не площади, которую оно покрывает, и не числу выборок. Никакого суперсэмплинга 4x или 16x нигде нет.
- Сглаживание аналитически точное, поэтому оно не деградирует на почти горизонтальных рёбрах так, как деградирует выборочное.
Заливки используют накопленное число оборотов для правил nonzero и even-odd. Обводки строятся как объединение согласованно ориентированных четырёхугольников со стыками и наконечниками и заливаются по nonzero — то есть отдельного пути растеризации для обводки не нужно вовсе. Градиенты считаются через таблицы на 256 записей с предумноженной альфой.
4. Распараллелить обе половины и не убивать пул
Две фазы, обе на всех ядрах, на постоянном пуле потоков, который между кадрами не пересоздаётся:
- Подготовка — флаттенинг кривых, обводка, пунктир — идёт по кускам списка фигур, которые потоки забирают атомарным счётчиком, так что неравномерная сложность фигур балансируется сама.
- Растеризация делит изображение на горизонтальные полосы, по полосе на поток. Аккумулятор свой у каждой полосы, блокировать нечего.
Сверх этого готовятся только фигуры, попадающие во вьюпорт, а вид — это обычная аффинная матрица, поэтому панорамирование и зум — это просто перерисовка с другими числами.
Цифры
На ноутбуке с 8 потоками стресс-файл из 20 000 путей и 1,9 млн рёбер рендерится в 1600x1600 примерно за 60 мс. Обычные иконки и иллюстрации — 1–3 мс. В заголовке окна вживую показываются время разбора, время рендера, число фигур и рёбер и число потоков, а клавиша T переключает однопоточный режим, так что любое утверждение отсюда проверяется одним нажатием. Есть и безоконный режим — svgviewer.exe file.svg -o out.png -n 10, — который пишет PNG и файл с таймингами; именно им я и меряю.
Чего намеренно нет
Нет image, фильтров, паттернов, кривизны textPath, а маски приближаются геометрией, а не яркостью. Фильтры, в частности, удвоили бы размер проекта, а просмотрщику они не нужны. Иконку приложения, к слову, генерирует сам просмотрщик из icon.svg.
Что бы я сделал иначе
Я бы написал безоконный вывод в PNG и отчёт по таймингам в первый день, а не ближе к концу. Каждое решение по производительности выше принято по измерениям, а первое время я измерял, глядя на заголовок окна: для прикидки годится, для сравнения двух сборок бесполезно. Второе: постоянный пул потоков должен был появиться с самого первого параллельного коммита. Создание потоков на каждый кадр прятало настоящую стоимость фазы подготовки за шумом планировщика дольше, чем хотелось бы признавать.