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

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

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

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

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

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

Здравствуйте, _vanger_, Вы писали:

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

Для треугольников можно использовать Boost Geometry и/или Boost Polygon. Для работы со смежностью можно использовать Boost Graph Library, то есть представить меш как неориентированный граф, вершины которого — треугольники, а рёбра — признак смежности.

(Подождите, что я делаю в разделе C/C++ в шесть утра первого января?)

Здравствуйте, Qbit86, Вы писали:

Q>Для треугольников можно использовать Boost Geometry и/или Boost Polygon. Для работы со смежностью можно использовать Boost Graph Library, то есть представить меш как неориентированный граф, вершины которого — треугольники, а рёбра — признак смежности.

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

Если допускать промежуточную ситуацию, когда граф смежности не соответствует полностью валидному графу смежности некоторого меша, когда треугольнику может быть смежно более трёх треугольников (например, при разбиении очередного треугольника, просто удалять его, и устанавливать для каждого соседнего треугольника смежность с двумя маленькими треугольничками), и потом, постепенно, восстанавливать валидность, дробя треугольники, то придётся помнить, какие из смежных треугольничков родились от одного (допустим, треугольнику смежно 4; для его правильного подразбиения надо знать, какая пара из этих четырёх родилась в результате измельчения).

Больно скрупулёзная возня. И не покидает ощущение, что нечто подобное должно быть уже реализовано, а я велосипедирую. Есть, например, VTK, где, вроде как, должно быть нечто подобное (или нет). Но там больно монструозно как-то.

Q>(Подождите, что я делаю в разделе C/C++ в шесть утра первого января?)

+1