Триангуляция вогнутого многоугольника с использованием библиотеки треугольников

Question

Я использую a C++ wrapper of the Triangle library и не могу избавиться от треугольников, которые находятся вне моего полигона.

Вот что я хочу получить:

И вот что я с треугольником:

(я намеренно не заполнял треугольники, чтобы показать, что из полигона имеются некоторые треугольники)

Я попытался избавиться от внешних треугольников с помощью алгоритма Ray casting (найти центр краев треугольников и посмотреть, находится ли он в многоугольнике. Если хотя бы один из них не существует, не рисуйте этот треугольник), но он очень медленный для моей цели (полигон обновляется каждый кадр). Я что-то пропустил? Какими параметрами я должен перейти в треугольник для триангуляции вогнутого многоугольника?

Если невозможно сделать то, что я хочу, с помощью треугольника, может кто-нибудь предложить мне быстрый метод для рисования многоугольника (моя программа использует график быстрой графики Qt, и я ограничусь только рисованием только треугольников или выпуклых полигонов, таких как OpenGL требуется)? В настоящее время я хочу попробовать метод тесселяции из GLU и рисования с использованием буфера трафарета. Также планирую попробовать this library.

Answer 1

GLU тесселяция решена проблема. Он показывает высокую производительность и хорошее качество триангуляции и хорошо работает на моем ноутбуке, а также на Android-планшете Nexus 7. Вы можете найти автономную версию GLU libtess here.

Answer 2

Вы можете попробовать скрытое растровое изображение с помощью теста на удар, но оно работает только с выходом. Я сделал это для контурных участков: https://cntm.codeplex.com/. Или вы можете попробовать альфа-формы. Он определяется как удаление краев, превышающих альфа.

Answer 3

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

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

2. Используйте буфер трафарета. Это проиллюстрировано в моих ответах на эти старые вопросы: Black out everything outside a polygon, How to force openGL to draw a non-convex filled polygon.

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

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

0            9 
    17          10 
    1 16        11 8 
      15     12 
     2    14 13    7 

      3      6 
        4  5 

Вы можете оказать эту форму непосредственно примитивный тип GL_TRIANGLE_STRIP заказав вершины по-разному, так что вершины из нижней дуги чередуются с вершинами из верхней дуги:

0            17 
    2          16 
    1 4        14 15 
      6     12 
     3    8 10    13 

      5      11 
        7  9