Рендеринг диаграмм: не так просто, как кажется

Что сложнее: отрендерить сцену со взрывающимися вертолётами или нарисовать унылый график функции y=x²? Да, верно, вертолёты взрывать дорого и сложно — но народ справляется, используя для этого такие мощные штуки, как OpenGL или DirectX. А рисовать график, вроде, просто. А если хочется красивый интерактивный график — можно его нарисовать теми же мощными штуками? Раз плюнуть, наверное?

А вот и нет. Чтобы заставить унылые графики вменяемо выглядеть и при этом работать без тормозов, нам пришлось попотеть: едва ли не на каждом шагу подстерегали неожиданные трудности.

Задача: разработать кроссплатформенную библиотеку для построения диаграмм, которая была бы интерактивной, из коробки поддерживала анимационные переходы и, главное, не тормозила.

Проблема 1: float и пиксельные соответствия

^[1]
Казалось бы, поделить отрезок на n равных частей сможет и первоклассник. В чём же наша проблема? Математически тут всё верно. Жизнь портит точность float’a. Совместить две линии пиксель в пиксель, если на них действуют эквивалентные, но разные преобразования, оказывается практически невозможно: в недрах графического процессора возникают погрешности, которые проявляются в процессе растеризации, каждый раз по-разному. А пиксель влево-пиксель вправо — весьма заметно, когда речь идёт о контурах, отметках на осях и т.п. Отладить это практически невозможно, так как невозможно ни предсказать наличие погрешности, ни повлиять на механизм растеризации, в котором она возникает. При этом погрешность оказывается разной в зависимости от того, включен ли Scissor Test ^[2] (который мы используем для ограничения области отрисовки графика).

Приходится делать костыли. Например, мы округляем значение смещений в преобразовании переноса до 10^–4. Откуда такое число? Подобрали! Код выглядит страшно, зато работает:

const float m[16] = {
                        1.0f, 0.0f, 0.0f, 0.0f,
                        0.0f, 1.0f, 0.0f, 0.0f,
                        0.0f, 0.0f, 1.0f, 0.0f,
                        (float)(ceil(t.x() * 10000.0f) / 10000.0),
                        (float)(ceil(t.y() * 10000.0f) / 10000.0),
                        (float)(ceil(t.z() * 10000.0f) / 10000.0),
                        1.0f
                    };

В итоге для большинства случаев, возникающих на практике, мы подобрали нужные значения, компенсирующие погрешности. Остаётся надеяться, что ничего критичного не пропустили.

Проблема 2: стыковка перпендикулярных линий

^[3]
Тут уже дело не в погрешности, а в том, как реализуются «аппаратно ускоренные» линии. Толщина 2 px, координаты одинаковые, пересечение в центре. И — великолепный «выкушенный» угол, как следствие. Решение — опять же, костыльное смещение Х- или Y-координаты одного из концов на один пиксель. Но сместить что-то на пиксель, работая с координатами полигонов — целая проблема. Координаты сцены и координаты экрана связаны друг с другом преобразованиями, пронизанными погрешностью — особенно если размер области видимости, которую описывает матрица проекции, не равен размеру экрана.

В конце концов, мы подобрали смещения, которые дают приемлемые результаты, «но осадочек остался»: решение всё-таки ненадёжное и всегда есть вероятность, что у юзеров уголки окажутся щербатыми. Выглядит это примерно так:

m_border->setFrame(NRect(rect.origin.x + 0.5f, rect.origin.y + 0.5f, rect.size.width - 3.5f, rect.size.height - 3.0f));
m_xAxisLine->setFrame(NRect(rect.origin.x, rect.origin.y, rect.size.width - 1.5f, rect.size.height - 1.0f));
m_yAxisLine->setFrame(NRect(rect.origin.x, rect.origin.y, rect.size.width - 1.5f, rect.size.height - 0.5f));

Проблема 3: линии вообще

И снова линии. В любой диаграмме присутствует довольно много линий — обычных линий, без излишеств. Это и оси, и сетка, и деления на осях, и границы элементов графика, иногда и сам график. И эти линии надо как-то рисовать. Казалось бы, что проще? Как это ни парадоксально, современные графические API чем дальше, тем увереннее выкидывают поддержку обычных линий: пруф для OpenGL ^[4], пруф для Direct3D ^[5].

Пока что линии ещё поддерживаются, но сильно ограничена их допустимая толщина. Практика показала, что на iOS-устройствах это 8 px, а на некоторых андроидах и того меньше. Когда-то бывшая в спецификации OpenGL функция установки шаблона пунктира (glLineStipple ^[6]) более не поддерживается, на мобильных устройствах в OpenGLES 2.0 она не доступна. Сами же линии — даже те, которые по толщине вписываются в допустимые границы — выглядят ужасающе:
^[7]

Пока мы миримся с тем, что есть, но всё идёт к тому, что придётся писать свой визуализатор линий, который сохранял бы постоянную толщину на экране, не зависящую от масштаба контура (как сейчас делает GL_LINES), но умел бы делать красивые сочленения на изгибах. Вероятно, для этого придётся строить их из полигонов:

Проблема 4: дырки между полигонами

^[8]
И снова проблема точности. На скриншоте видны светлые «вкрапления» на круговой диаграмме. Это не что иное, как результат погрешности растеризации (опять!), и здесь никакие костыли уже не спасают. Чуть лучше становится, если включить сглаживание границ:
^[9]

На данный момент смирились и оставили в таком виде.

Проблема 5: особенности системного антиалиасинга

Совсем без сглаживания границ результат рендеринга режет глаз даже на ретина-дисплеях. Но системный алгоритм сглаживания MSAA, доступный на любой современной платформе, имеет три серьёзных проблемы:

1. Снижение производительности: по нашим наблюдениям, на мобилках она падает в среднем в три раза, и при воспроизведении анимации на сложных сценах появляются ощутимые лаги.
2. Затруднение мультиплатформенности (а мы за ней гоняемся): на разных платформах системный антиалиасинг включается по-разному, мы же пытаемся по максимуму унифицировать код.
3. Артефакты изображения: объекты, стороны которых параллельны сторонам экрана (например, линии сетки на графике) размываются под действием системного антиалиасинга (если у них в итоге всех преобразований получились дробные координаты), хотя должны оставаться резкими:

^[10]

Из-за всего этого нам пришлось отказаться от стандартного сглаживания и изобретать очередной велосипед реализовать собственный алгоритм. В итоге, мы собрали оптимизированный под мобилки гибрид SSAA ^[11] и FXAA ^[12], который:

1. Умеет автоматически отключаться на периоды воспроизведения анимации (при анимации пользователю нужна плавность движения, а в статике — сглаженность границ).
2. По производительности сглаживания совпадает с системным антиалиасингом, при этом реализуется исключительно внутренними механизмами нашего графического движка (то есть сохраняет мультиплатформенность).
3. Может воздействовать на часть сцены, а не на всю целиком (так удаётся избежать артефактов размытия: просто исключаем из множества сглаживаемых объектов те, которым оно заведомо не пойдёт на пользу).

Воздействие на часть сцены организуется через «послойный» рендеринг, когда всё множество объектов делится на группы (слои) по их взаимному расположению (передний, средний, задний план и т.д.) и необходимости сглаживания. Слои отрисовываются последовательно, и сглаживание применяется только к тем, у которых выставлен соответствующий атрибут.
^[13]

Проблема 6: Многопоточность и экономия энергии

Хороший тон — обрабатывать события пользовательского интерфейса и рендеринг графической сцены в разных потоках. Однако, действия пользователя влияют на внешний вид сцены, а значит, необходима синхронизация. Мы решили, что расставлять мьютексы во всех визуальных объектах — это чересчур, и вместо этого реализовали транзакционную память.

Идея состоит в том, что есть две хеш-таблицы свойств: для главного потока (Main thread table, MTT) и для потока рендеринга (Render thread table, RTT). Все изменения настроек внешнего вида объектов попадают в MTT. Попадание в неё очередной записи приводит к планированию «тика синхронизации» (если он ещё не был запланирован), который произойдёт в начале следующей итерации главного потока (предполагается, что обработка пользовательского интерфейса происходит именно в главном потоке). Во время тика синхронизации содержимое MTT перемещается в RTT (это действие защищено мьютексом — единственным на всю графическую сцену). В начале каждой итерации потока рендеринга проверяется, нет ли записей в RTT, и если они есть — они применяются к соответствующим объектам.

Здесь же реализуется установка тех или иных свойств с анимацией. Например, можно указать изменение масштаба от 0 до 1 за определённое время, и запись из RTT применится не сразу, а за несколько шагов, на каждом из которых конкретное значение будет результатом интерполяции значения масштаба от 0 до 1 по заданному закону.

И этот же механизм обеспечивает возможность визуализации по требованию: фактический рендеринг выполняется только в том случае, если в RTT есть записи (то есть состояние сцены изменилось). Визуализация по требованию очень актуальна для мобильных устройств, так как разгружает процессор и тем самым позволяет экономить драгоценный заряд аккумулятора.

Как-то так. Хватало, конечно, и задач на умение пользоваться гуглом — но самые неожиданные грабли мы вроде перечислили. В итоге, несмотря на усилия организаторов, праздник состоялся удалось-таки получить картинки, за которые не очень стыдно:
^{[14] [15]
[16] [17]}

Автор: Ixtaccihuatl

Источник ^[18]