Преобразование формы из контурных сплайнов в простые полигоны

Question

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

Традиционно я могу использовать libfreetype или scan-rasterise такого рода контуры. Но я хочу создать экструдированные 3D-сетки из шрифтов и сделать другие искажения с ними.

Итак, как полигонизировать фигуры, состоящие из квадратичных кривых Безье и линий? Существует много контуров, которые образуют форму вместе. Некоторые контуры являются аддитивными, а другие - субтрактивными. Контуры никогда не открываются. Они образуют петлю.

(На самом деле, я получаю только контурные вершины из глаголов ttf, эти вершины определяют, являются ли они частью кривой или нет. Хотя это легко разложить на кривые и линии безье, зная, что данные представлены таким образом могут быть полезны для полигонирования контуров к треугольникам)

Answer 1

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

Во-первых, вам необходимо оценить кривые и преобразовать их в полилинии.

Тогда вам нужно убедиться, что в каждом месте пересечения двух контуров есть вершина (эта часть действительно может быть вызвана из-за числовых ошибок, вы можете использовать the Bentley-Ottmann algorithm).

Наконец, все, что вам нужно сделать, - это пересечь кривые и подключить их в правильном порядке для выполнения логической операции, производя weakly simple polygons.

Такие полигоны могут быть триангулированы с использованием, например, ear clipping algorithm (который медленный, но довольно простой в реализации).

Надеюсь, что это поможет ...