Earcut на битах

Earcut - базовый, почти учебный алгоритм триангуляции, но при некоторых раскладах он обгоняет более "продвинутые" решения.

Я убедился в этом, тестируя iTriangle, который построен на монотонной триангуляции. Для замеров я использовал Earcut от MapBox - и C++ версию, и Rust-порт.

Результаты оказались предсказуемыми: Earcut стабильно выигрывал на простой геометрии и малом числе точек. Причём настолько уверенно, что я задумался: почему бы не встроить Earcut прямо в iTriangle?

Так и родилась идея: сделать мини-версию, заточенную только под одиночные контуры до 64 точек. С таким ограничением можно выжать максимум: обойтись без аллокаций, работать напрямую с битовой маской и попытаться обойти решение от MapBox.

Теория

Идея Earcut строится на простом наблюдении: в любом не самопересекающемся многоугольнике всегда найдутся три подряд идущие вершины, которые образуют так называемое ухо - внутренний треугольник, не содержащий других точек внутри.

Вся суть алгоритма - находить такие уши и последовательно их "отрезать", пока от многоугольника не останется последний треугольник.

Из этого подхода вытекает простая и красивая формула: каждый раз, отрезая ухо, мы теряем одну вершину, но получаем один треугольник. Алгоритм заканчивается, когда остаётся три вершины - это и есть последний треугольник.

В итоге: Tcount = N - 2

где Tcount - количество трегольников, N - количество вершин

Для простоты дальнейших рассуждений будем считать, что точки в контуре перечислены против часовой стрелки.

Жадный Earcut

Проходим по контуру и перебираем все подряд идущие тройки точек. Для каждой тройки проверяем:

1. Образуют ли они треугольник в правильном порядке (против часовой стрелки).

2. Не содержит ли этот треугольник других вершин внутри.

Если оба условия выполняются - это ухо. Отрезаем его (удаляем центральную вершину) и продолжаем проход с обновлённым контуром.

Однако при неудачном раскладе, чтобы найти одно ухо, может понадобиться обойти весь контур. А таких ушей надо найти N - 3. А внутри каждой проверки треугольника - потенциально приходится проверять все остальные вершины, чтобы убедиться, что треугольник пустой внутри.

Отсюда и получается асимптотика:

• O(N) - пройти по всем вершинам, чтобы найти одно ухо.

• O(N) - таких ушей нужно вырезать.

• O(N) - на проверку "ухо ли это" (нет ли точек внутри).

Итог: O(N³) - в худшем случае.

К слову, на практике всё не так печально. Большинство контуров ближе по форме к окружности, чем к спирали или другому "запутанному" многоугольнику. В таких случаях уши находятся значительно быстрее - зачастую на первом или втором проходе. Поэтому реальная асимптотика ближе к O(N²).

Большеухая реализация

Часто выгоднее отрезать сразу несколько треугольников, если это возможно. Такой подход позволяет сократить количество проверок на наличие внутренних точек. Суть такая вместо треугольника мы ищем выпуклый многоугольник.

Логика простая: мы постепенно расширяем ухо, добавляя к нему новые вершины. Главное - чтобы каждый новый угол образовывал треугольник против часовой стрелки (векторное произведение соседних рёбер - положительное).

Почему именно выпуклый многоугольник?

• Тривиальная триангуляция.

• Проверка на внутренние точки проще и быстрее (см. ниже).

Как только мы собрали выпуклый сегмент, возникает вопрос:

• Содержит ли он внутренние точки? Если нет - отрезаем.

• Если содержит - как разбить его так, чтобы избавиться от внутренних точек?

Проверка на пустоту

Есть два простых метода, которые можно использовать для проверки, лежит ли точка внутри многоугольника:

• Even-Odd (чет-нечет) - пускаем луч из точки и считаем количество пересечений с рёбрами. Если нечётное - точка внутри.

• Векторное произведение - для каждой стороны многоугольника смотрим векторное произведение стороны и вектора до точки. Если все произведения одного знака (например, положительные), значит точка внутри.

Векторное произведение чуть проще и позволяет закончить проверку досрочно если появляется противоречие.

Проще всего понять метод векторного произведения - через порядок точек треугольника.

• Если точка лежит внутри, то все векторные произведения (от стороны к точке) будут направлены в одну сторону - против часовой стрелки.

• Если снаружи - направление будет обратным.

Максимально допустимое ухо

Итак, мы нашли большое ухо - выпуклый многоугольник - и выяснили, что внутри него есть лишние точки.

Как найти ту часть, где нет внутренних точек?

Здесь важно понимать одно: первую вершину уха (то есть ту, с которой мы начинали) менять не нужно. Именно по ней идёт основной проход по контуру. Если ухо в текущем виде не подойдёт - всё равно цикл дойдёт до следующей вершины и начнёт попытку заново.

Поэтому логика простая: отматываем ухо с конца, от последней добавленной вершины ближе к началу - и проверяем, в какой момент внутренние точки "вываливаются" из многоугольника. Как только они перестают попадать внутрь - всё, мы нашли максимально допустимое ухо. Его можно отрезать.

Как найти крайнюю точку?

Если провести вектора от начальной точки до всех внутренних точек, становится понятно: крайней будет та, чей вектор образует минимальный угол с направлением начального ребра

"Ближайший" вектор к начальному ребру

Считать угол напрямую — плохая идея:

• arccos - дорогая операция

• вычисления могут быть неточными из-за ограниченной точности float'ов

Вместо этого вектора лучше сравнивать попарно, используя векторное произведение.

Пример

Пусть:

• - вектор начального ребра

• и вектора до внутренних точек.

Тогда:

cross_product =

Если cross_product > 0 то переходит в путем поворота против часовой стрелки, и как видно из рисунка он оказывается ближе к

Важное замечание

Все углы гарантировано < 180

Крайний вектор для замыкания уха

Итак, мы нашли "ближайший" вектор - тот, который образует минимальный угол с начальным ребром уха и указывает в сторону внутренней точки.

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

Сравнение выполняем по тому же принципу:

• Для каждого кандидата строим вектор от начальной вершины

• Сравниваем его с найденным крайним вектором через векторное произведение

• Если cross_product > 0 - всё ещё "внутри" угла, продолжаем

• Если cross_product < 0 - вышли за предел -> предыдущая вершина была последней допустимой

Ухо готово к ампутации.

Для триангуляции достаточно замкнуть начальную точку с каждой из не смежных вершин внутри допустимого сегмента.

Где можно ускорить процесс?

Самая затратная часть Earcut - это поиск внутренних точек. Именно эту часть и попробуем ускорить.

• Фильтрация по bounding box
  Сначала отбрасываем все точки, которые гарантированно лежат вне ограничивающего прямоугольника уха (синим на рисунке). Это существенно уменьшает количество кандидатов.

• Фильтрация по первому треугольнику
  Проверяем только базовый треугольник уха. Если он уже содержит внутреннюю точку - отбрасываем всё ухо целиком. Это особенно эффективно на сложной геометрии.

• Heap-поиск
  Даже после фильтрации кандидатов всё ещё может быть много. Но нам не важны все - только ближайшие. Для этого используем Heap.

• Инкрементальная проверка
  Если кандидаты отсортированы, мы можем проверять треугольники инкрементально: следующую точку начинаем проверять с последнего проверенного треугольника.

Оптимизированный проход (см. рисунок)

На примере видно, как это работает:

• Серые точки - отфильтрованы по Bounding Box.

• Оранжевые точки - отсортированные кандидаты.

• Зелёные вектора - финальные треугольники уха.

1. Вектор от точки 1 оказался внутри треугольника 4, но сама точка - вне уха. Продолжаем.

2. Точка 2 - проверяем с треугольника 4, она попадает в треугольник 5, но снова вне.

3. Точка 3 - проверяем с треугольника 5, попадает в треугольник 6 и оказывается внутри - поиск завершается.

В результате - триангулируем ухо, используя треугольники 1–5.

Что если внутренней точки не оказалось?

Возможны два сценария:

• Проверены все кандидаты - значит, внутри нет мешающих точек, и ухо можно отрезать целиком.

• Heap переполнен - проверена лишь часть точек. Все они снаружи, но гарантий нет. В этом случае отрезаем до последнего проверенного треугольника - это безопасно, но мы потенциально теряем часть уха.

Такой компромисс позволяет сохранить быстродействие алгоритма.

Низкоуровневая оптимизация Earcut64

Для описанного выше алгоритма отлично подходит связанный список: навигация идёт только на один шаг вперёд или назад, а при подрезке уха удаляются элементы из середины.

Но если длина контура ≤ 64, для эффективной навигации можно использовать - битовую маску, где каждый бит кодирует наличие точки по индексу.

Вот часть кода вспомогательных методов для навигации вперед:

impl Bit for u64 {
    #[inline(always)]
    fn ones_index_to_end(index: usize) ->; Self {
        // index is included
        debug_assert!(index <= 64);
        let zeros_count = index & 63;
        u64::MAX << zeros_count
    }

    #[inline(always)]
    fn next_wrapped_index(&self, after: usize) -> usize {
        debug_assert!(after <= 63);
        let front = self & u64::ones_index_to_end(after + 1);
        if front != 0 {
            front.trailing_zeros() as usize
        } else {
            self.trailing_zeros() as usize
        }
    }
}

Фильтрация внутренних точек

Имея маску контура, легко получить маску внутренних кандидатов:

let candidates = available & !ear_indices;

• available — все оставшиеся точки

• ear_indices — текущие точки, входящие в ухо

• candidates — точки, которые потенциально могут быть внутри

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

Потому что мы не аллоцируем память вообще.

Аллокация - дорогая операция. И чем меньше объём, тем дороже стоимость одного байта.
В нашем случае объём невелик (64 байта максимум), и поэтому цена аллокации высока.

И напоследок - одна мысль

Всё, что описано выше - работает на CPU, не требуя аллокации.

И тут возникает закономерный вопрос:

А можно ли реализовать, что-то подобное на GPU?
И если да - найдётся ли область, где это даст реальный профит?