Создатели картографического движка выпустили earstrip: триангулятор быстрее earcut на 14% в C++

Команда, которая делает картографический движок (globus.software), опубликовала его триангулятор полигонов как небольшую библиотеку earstrip под лицензией ISC, той же, что у earcut. Это один заголовочный файл на C++ и сборка WebAssembly на npm, принимающая те же аргументы, что и earcut. По заявлению авторов, в C++ библиотека на 14% быстрее earcut.hpp, а в браузере в 1,4-2,1 раза быстрее earcut.js. Сравнение находится ближе к концу статьи, а сама статья рассказывает, как к этому пришли.

Задача такая: видеокарта заливает только треугольники, а карта на деле состоит в основном из полигонов, зданий, парков, парковок, полос травы между трамвайными путями. Перед заливкой каждый контур нужно разрезать на треугольники. Для замеров авторы взяли 13-й уровень масштаба (zoom 13) их офлайн-карты Мазовецкого воеводства вокруг Варшавы: 3 740 425 полигонов. Прежний триангулятор движка, ограниченный триангулятор Делоне (constrained Delaunay), обрабатывал их все за 2,93 секунды на одном ядре M4 Pro. В октябре автор заменил его на отсечение «ушей» (ear clipping). Для статьи он заново собрал отсекатель по одной идее на коммит и замерял каждый коммит на тех же 3,7 млн полигонов.

Почему Делоне здесь избыточен: он даёт треугольники с наибольшим из возможных минимальным углом, а это важно при интерполяции или моделировании. Плоской заливке всё равно: видеокарта одинаково корректно закрашивает и тонкую иглу, и «толстый» треугольник. При этом почти половина полигонов Мазовии, 1,8 млн, имеют четыре вершины или меньше; на них код Делоне тратит 419 мс, каждый раз строя триангуляцию с нуля, хотя треугольник резать не нужно, а выпуклый четырёхугольник, это два треугольника.

«Ухо» полигона, угол, который отсекается одним прямым разрезом: три подряд идущие вершины a, b, c, где угол в b выпуклый и никакая другая часть полигона не заходит в треугольник abc. Гэри Мейстерс в 1975 году доказал, что у любого простого полигона больше чем с тремя вершинами есть минимум два непересекающихся уха, поэтому следующее ухо всегда найдётся, а полигон из n вершин распадается на n − 2 треугольников. Точка на ребре треугольника считается внутри него, а исключение, точка в том же месте, что и a, b или c; такое бывает там, где контур касается сам себя в одной вершине, и дыры делают это частым случаем.

Дыры. Отсечение работает с одним замкнутым контуром, а у 11 345 полигонов Мазовии есть дыры (дворики, поляны в лесах). Каждую дыру разрезают и пришивают к внешнему кольцу мостом, ребром от вершины дыры к вершине границы, которое проходят дважды, в обе стороны; полигон остаётся тем же, но становится одним кольцом. Мост ищут по описанию Дэвида Эберли: берут самую правую вершину дыры m, пускают луч вправо, находят первое пересечённое ребро в точке I и его правый конец P. Если внутри треугольника m, I, P нет вершин границы, мост идёт в P; иначе выбирают вогнутую вершину из этого треугольника, ближайшую по углу к лучу. Дыры соединяют справа налево. Карты добавляют два особых случая: координаты целочисленные на сетке тайла, поэтому луч вдоль линии сетки встречается постоянно (автор признаёт, что первая версия обработала этот случай неверно), а картографы часто рисуют дворик так, что он касается внешнего контура в одной точке, тогда мост не нужен, кольца соединяются в общей вершине.

Шаги ускорения. (1) Наивный отсекатель (−1 812 мс): обход границы, проверка каждого угла на «ухо» против всех остальных вершин, три индекса на треугольник. На всех полигонах, 1,12 с, в 2,6 раза быстрее Делоне. Но самые большие 1 123 полигона (257 вершин и больше) отсекаются за 199 мс против 90 мс у Делоне: там каждая проверка обходит сотни вершин, а проверок нужны сотни, то есть стоимость растёт как квадрат размера. (2) Проверять только вогнутые вершины, «впадины» (−237 мс): если в треугольнике выпуклого угла вообще есть вершина, то среди них есть вогнутая, поэтому достаточно смотреть только их. Список таких вершин только сокращается. 28,1 млн проверок «уха» теперь просматривают 185 млн точек вместо 353 млн. Выигрыш меньше ожидаемого, потому что у контуров зданий много впадин (у здания с аркой, 15 из 27 вершин), а самые маленькие полигоны даже замедлились, с 34 до 54 мс, так как сортировка углов дороже обхода. (3) Пропуск проверок у выпуклых полигонов (−2 мс): полигон без впадин выпуклый, и любой его угол, ухо. Одного условия «все повороты влево» мало, звезда, обходящая центр дважды, его проходит; поэтому добавляется условие, что направление по x меняется ровно два раза. Оба счётчика считаются в том же цикле, что отмечает впадины. Это убирает 4,4 млн из 28,1 млн проверок, но самых дешёвых, так что общий итог почти не меняется; полигоны из четырёх вершин и меньше возвращают часть потерь, с 54 до 48 мс. (4) Полосы треугольников (−118 мс): видеокарта умеет рисовать triangle strip, где каждый новый индекс добавляет треугольник из него и двух предыдущих. После отсечения уха углы его соседей становятся острее, и они, первые кандидаты на следующее ухо; движок чередует два конца полосы, пока уши находятся. 21,5 млн треугольников занимают 35,8 млн индексов вместо 64,5 млн. Число проверок слегка растёт (25,0 млн вместо 23,7 млн), потому что каждая полоса заканчивается неудачной проверкой, но общее время всё равно падает.

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

Ключевые факты

earstrip, один заголовочный файл на C++ плюс сборка WebAssembly на npm с теми же аргументами, что у earcut; лицензия ISC. По заявлению авторов, в C++ она на 14% быстрее earcut.hpp, в браузере в 1,4-2,1 раза быстрее earcut.js.
Бенчмарк, 3 740 425 полигонов Мазовецкого воеводства на 13-м уровне масштаба карты (zoom 13), на одном ядре M4 Pro. Прежний ограниченный триангулятор Делоне справлялся за 2,93 с.
Первый наивный отсекатель «ушей» дал 1,12 с, в 2,6 раза быстрее Делоне, но на 1 123 самых больших полигонах (257 вершин и больше) проигрывал: 199 мс против 90 мс.
Дальше по заголовкам шагов: проверка только вогнутых вершин (−237 мс), пропуск проверок у выпуклых полигонов (−2 мс), запись полос треугольников (−118 мс; 35,8 млн индексов вместо 64,5 млн).
Текст обрывается на разделе про полосы; итоговое сравнение с earcut и цифра 489 мс из заголовка в доступной части не раскрыты.

Почему это важно

Карты состоят в основном из полигонов, а видеокарта заливает только треугольники, поэтому разбиение контуров на треугольники, обязательный этап отрисовки. Любое ускорение на миллионах полигонов сокращает время подготовки данных. Показательно, что авторы заменили общепринятую для геометрии триангуляцию Делоне на более простое отсечение «ушей»: для плоской заливки качество треугольников неважно, а на почти половине полигонов (1,8 млн с четырьмя вершинами и меньше) Делоне тратил 419 мс впустую. Разбор шагов с замером каждого на одном и том же наборе данных полезен как пример оптимизации.

Кому это важно

Разработчикам картографических движков и веб-карт, графики на WebGL и WebAssembly, а также всем, кто использует earcut для заливки полигонов: earstrip принимает те же аргументы, что earcut. Статья будет интересна и тем, кто занимается вычислительной геометрией и ищет приёмы ускорения: проверка только вогнутых вершин, обработка дыр через мосты, вывод полос треугольников.

Как это применить

Библиотека распространяется как один заголовочный файл на C++ и как сборка WebAssembly на npm с теми же аргументами, что у earcut, так что в проектах на earcut её можно пробовать как замену. Лицензия ISC, та же, что у earcut. Цену, поддерживаемые платформы и порядок подключения в доступном тексте подробно не описывают, поэтому детали стоит смотреть в репозитории и документации самой библиотеки. Из идей статьи переносимы: проверка только вогнутых вершин, пропуск проверок у выпуклых полигонов и запись полос треугольников, сокращающих число индексов.

Можно ли доверять

Статья написана самими авторами библиотеки, и основные цифры, это их замеры. Условия описаны: один набор данных (Мазовецкое воеводство, zoom 13), одно ядро M4 Pro, по шагам указаны изменения времени. Числа 14% и 1,4-2,1 раза приведены во вступлении как итог сравнения, но само сравнение в доступном тексте обрывается до того, как его можно проверить; цифра 489 мс стоит только в заголовке без указания оборудования и сборки. Сторонних замеров или откликов на earstrip в тексте нет. Результат на других данных (не картах зданий) может отличаться.

Риски и подводные камни

Ускорение показано на картографических данных с большим числом маленьких полигонов и зданий; на другой геометрии выигрыш может быть иным. Отсечение «ушей» не даёт триангуляцию с хорошими углами, а для интерполяции и моделирования это важно: авторы подчёркивают, что нужна лишь плоская заливка. Отдельные шаги дают разный эффект: проверка только вогнутых вершин замедлила самые маленькие полигоны (с 34 до 54 мс), а пропуск проверок у выпуклых почти не изменил итог (−2 мс). Целочисленные координаты сетки порождают крайние случаи, на которых, по признанию автора, его первая версия ошибалась. Сравнение с earcut в доступном фрагменте не показано.