Алгоритм трехмерной триангуляции

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

Редактировать: кстати, псевдокод о том, как реализовать Делоне для 2D-квадрата в 3D-пространстве для создания двух треугольников, более чем приветствуется!

Правка 2. К сожалению, это не ответ в 3D-пространстве (применимо только в 2D).


person Jonas Byström    schedule 28.06.2010    source источник
comment
Переворот (как в вашей ссылке) по-прежнему обычно выполняется на 3D-сетках, но вам могут потребоваться дополнительные ограничения, чтобы избежать переворачивания четырехугольников, которые крайне неплоские.   -  person Alan    schedule 29.06.2010
comment
Да, причуда, похоже, правильно справляется с этими ограничениями.   -  person Jonas Byström    schedule 30.06.2010


Ответы (4)


Я не люблю предугадывать намерения людей, но если вы просто пытаетесь получить из Maya то, что показано в окне просмотра, вы можете извлечь триангуляцию Maya, начав с MItMeshPolygon::getTriangles.

(Соответствующие цвета нормалей и вершин легко доступны. UV требуют немного больше усилий — я не помню деталей (весь мой код Maya принадлежит моему бывшему работодателю), но, хотя на первый взгляд может показаться, что вы не есть данные, на самом деле все это есть, просто не удобно.)

(Еще одно замечание: если ваши художники достаточно постараются, они могут создавать полигоны, которые приводят к сбою Maya при вызове getTriangles, даже если они хорошо визуализируются и ими можно управлять с помощью пользовательского интерфейса. Раньше это происходило каждые несколько месяцев, так что стоит подождать. иметь в виду, но, вероятно, не стоит слишком беспокоиться.)

Если вы не хотите использовать API или Python, то запуск polyTriangulate перед экспортом, а затем undo после него (чтобы вернуть исходные полигоны) позволит вам изучить триангулированную сетку. (Возможно, вам потребуется сохранить сцену во временный файл, а затем перезагрузить ее и использовать file, чтобы вернуть ей старое имя, если ваш процесс экспорта делает что-то, что трудно или невозможно отменить.)

Это немного хакерски, но вы гарантированно получите точную триангуляцию, которую использует Maya. Это проще, чем писать свой собственный код триангуляции, и почти наверняка НАМНОГО проще, чем пытаться решить то, что Maya делает внутри...

person Community    schedule 28.06.2010
comment
К сожалению, у меня есть mel, но нет доступа к API C (почти готовая цепочка инструментов, я ее не заменяю). Боже, меня все больше раздражает внутреннее устройство Майи, так как я вроде как пошел по пути реверс-инжинирингового идиота много месяцев назад. :) - person Jonas Byström; 29.06.2010
comment
Я так понимаю, это то, что вы пытаетесь сделать? Если вы не можете использовать привязки Python к C++ API, возможно, вам поможет что-то вроде polyTriangulate, export, undo. (В качестве альтернативы, сохраните сцену во временный файл, триангулируйте, экспортируйте, перезагрузите, используйте файл, чтобы дать ему его старое имя, на случай, если ваш экспорт делает какие-то случайные вещи, которые искажают очередь отмены.) Немного хакерский, но гораздо проще, чем писать свой собственный код триангуляции, и я готов поспорить, что это было бы НАМНОГО проще, чем пытаться решить то, что Maya делает внутри... - person ; 29.06.2010
comment
Конечно, ты прав. Мне потребовалось два дня и одна ночь проб и ошибок, чтобы понять это. Спасибо за хороший совет в любом случае. :) - person Jonas Byström; 01.07.2010
comment
Я обновил ответ, чтобы он включал суть моего комментария для будущих искателей... - person ; 01.07.2010

У Джонатан Шевчук есть очень популярный инструмент 2D-триангуляции под названием Triangle, и должна появиться его 3D-версия. скоро. У него также есть ряд статей на эту тему, которые могут быть полезны.

person Suresh    schedule 30.06.2010
comment
Fwiw, его треугольник.с (2005) составляет 16 тысяч строк, включая 1 тысячу справки; наслаждаться - person denis; 30.07.2010

Вы можете попробовать просмотреть методы Вороного и Делоне Хенрик Циммер. Я не знаю, используется ли это в Maya, но в статье описываются некоторые распространенные приемы.

person andand    schedule 28.06.2010
comment
Выглядит интересно, я проверю. - person Jonas Byström; 29.06.2010
comment
Ссылка больше недоступна. - person Endery; 21.03.2016

Здесь вы можете найти апплет, демонстрирующий Алгоритмы Incremental, Gift Wrap, Divide and Conquer и QuickHull, вычисляющие триангуляцию Делоне в 3D. Предоставляются указатели на каждый алгоритм.

person Dr. belisarius    schedule 28.06.2010