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

Question

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

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

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

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

Answer 1

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

Сначала вам нужно оценить кривые и преобразовать их в полилинии.

Затем вам нужно убедиться, что в каждом месте, где пересекаются два контура, есть вершина (эта часть может действительно пытаться из-за числовых ошибок; вы можете использовать алгоритм Бентли-Оттмана ) .

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

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

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