Есть такая задача (как часть решения другой). Имеется триангулированный меш, некоторые треугольники которого помечены. Надо разбить помеченные треугольники на четыре треугольника вот так:

   /\             /\
  /  \           /__\
 /    \   -->   /\  /\
/______\       /__\/__\

Это разбиение помеченных треугольников ведёт к необходимости разбиения смежных с ними. Всего возможно 7 случаев (3 случая, когда тесселяции требует одна сторона, 3 случая, когда требуют две и 1 случай, когда все три стороны требуют тесселяции). Вот пример, когда левый треугольник помеченный, а средний смежный с ним:

    ____               ____
   /\   |\            /\  /|\
  /  \  | \          /__\/ | \
 /    \ |  \  -->   /\  /\ |  \
/______\|___\      /__\/__\|___\

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

Есть ли библиотека на C/C++, полезная для этого дела? Пусть не непосредственно делающую вышескаанное (идеальный вариант), но предоставляющую удобный интерфейс для работы с такими типами данных (треугольники, смежность).