Алгоритм для заполнения замкнутой 2D-кривой
Мне нужно найти способ рисования внутри замкнутой 2D-кривой. Эта кривая на самом деле создается с использованием бикубической кривой Безье, но я считаю, что это не важно.
На данный момент не должно быть никаких «дырок» в нарисованной форме. Таким образом, он будет полностью заполнен. Кажется, что стоит ограничиться триангуляцией Делоне? Но, кажется, есть разные способы сделать это. Я ищу быстрое и простое решение (но буду реализовывать то, что нужно, чтобы оно работало).
Такие программы, как Illustrator, имеют такую функцию (или SVG — с опцией fill).
Я ищу:
- методы, чтобы сделать это
- укажите мне на документ / документ, где объясняется алгоритм
- где-нибудь доступен исходный код рендера SVG?
- Приложение использует OpenGL. Я рисую кривые сам. Просто нужно найти способ их заполнения.
- форма может быть вогнутой или выпуклой
Решение
Полигоны могут быть заполнены с помощью Scanline метод. Принцип прост: переместите горизонтальную линию и сохраните список ребер, которые встречаются. Это называется активный список. Затем соедините пересечения слева направо попарно. Когда края отсортированы по возрастанию ординат, обновление активного списка с одной строки развертки на следующую может быть выполнено эффективно.
Это работает с вогнутыми / выпуклыми многоугольниками и многоугольниками с отверстиями, и даже со скрещенными.
Чтобы заполнить путь Безье, вы можете сгладить его, то есть превратить в многоугольник с разных сторон.
Прямой подход также возможен, основываясь на идее сканлайна: сначала разложим кривые Безье в монотонный участки, то есть участки, которые встречаются на горизонтальной линии только один раз. Это может быть сделано аналитически для кубического Безье путем обнаружения максимумов и минимумов кривой (уравнение является квадратичным).
Теперь вы можете трактовать криволинейный многоугольник точно так же, как многоугольник, зная, что у вас есть одно пересечение с каждой стороны. Есть немного деликатная точка, вычисляющая пересечение. Но это облегчается тем фактом, что вы знаете хорошее приближение дуги Безье (отрезок прямой между одними и теми же конечными точками), и вы можете обновлять пересечение постепенно, от одной линии развертки до следующей.
На рисунке исходные конечные точки отображаются синим цветом. Для получения монотонных участков были добавлены конечные точки разделения (другие контрольные точки опущены). Пунктирные линии показывают многоугольник, который аппроксимирует форму и имеет ту же топологию (тот же активный список, то же количество пересечений с линиями сканирования).
Другие решения
Если вы должны использовать заливку полигонов, нет другого варианта, кроме выравнивания кривой, чтобы получить прямые стороны.
Затем используйте многоугольный заливочный примитив.
Если все, что у вас есть, это примитив, заполняющий треугольник, вы можете
-
триангулировать многоугольник ушная стрижка, или разложение в монотонные полигоны, или же
-
используйте простой метод разметки: если вы проведете горизонталь через каждую вершину, вы нарежете многоугольник на треугольники и трапеции. Трапеция может быть разрезана на два треугольника. Для эффективности используйте метод активного списка.