[CG][Алгоритмы]Сглаживание полигонов

>Кто не вкурсе - полигон это пространственный многоугольник, ограниченный ребрами, состоящий из граней.

ага, спасибо, а то ЛОР так бы никогда и не узнал...

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

Из-под могилы Леонарда Эйлера доносятся глухие стоны.

> у грани всегда 3 вершины,

у полигона может быть много (да, полигон может быть не плоским, а кривым)

Суровая русская геометрия, чо.

Поверим условиям наслово, что решение существует, не проверяя их на консистентность. Работаем только с ребрами на границе «полигонов».

Обозначим «полигоны» буквами A, B, C..

Пронумеруем все ребра, которые должны сгладиться 1, 2, 3,... N Ребра, которые должны быть твердыми, начинаем нумеровать с N+1

Например, N = 14. Тогда, например, геометрия запишется (не проверял на консистентность, для схемы достаточно, также номера больше N опущены):

A: 3 5 6 7 8 11
B: 6 8 11
C: 3 5 7 12
D: 1 2 4 9 10 12 13 14
E: 1 2 4 
F: 9 10 13 14

Ищешь пару у которой наибольшее количество общих гладких ребер (D и F). Присваиваешь найденной паре и набору гладких ребер вспомогательный индекс 1. Вычеркиваешь у этих пар общие ребра (9 10 13 14) и повторяешь поиск. И т.д.

Получаешь ряд шагов:

1:  DF (9 10 13 14)
2:  AB (6 8 11)
.......
И т.д.

Но это будет неоптимально, можно ещё уменьшить число групп, так как может оказаться, что если например, пара «полигонов» из шагов, например, 5 KL (блаблабла) не имеет ни одной общей твердой грани с парой, например, 8 FR (блаблабла), то можно порешить этих двух зайцев одной группой (если бы они имели хоть одну общую твердую грань, то этого сделать было бы нельзя, так как при назначении обеим парам одинаковой группы сглаживания она бы сгладилась). Поэтому делаем следующим образом.

Имеем список:

1 DF
2 AB
3 ...
100. CY

Все, че тут думать-то.

</thread>

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

>Отличие грани от полигона - у грани всегда 3 вершины

man треугольник

http://en.wikipedia.org/wiki/Catmull%E2%80%93Clark_subdivision_surface

И что?

Типичный пример, с которым алгоритм не справится:

http://imgur.com/ZpAzq.jpg

Синее - твердое ребро, цифры - группы сглаживания для полигонов.

Ага, ну да, там чуток исправить вторую часть.

Имеем список:

1 DF
2 AB
3 ...
100 CY

Назначаешь первой паре группу №1 и шерстишь остаток списка, последовательно выбирая пары для приобщения к группе №1 так, чтобы результирующее множество «полигонов» из пар группы №1 в совокупности не имело ни одной общей твердой грани. Дойдя до конца, вычеркиваешь все эти пары, присвоенные первой группе. Далее уже первой паре из оставшегося списка назначаешь группу №2 и все повторяется. И т.д.

Все работает.

Огромное спасибо :)

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

>>http://imgur.com/ZpAzq.jpg

В чем рисовал, если сам?

Ага и для полного счастья там везде в объяснении нужно сделать

s/грань/ребро/g

Ибо после такого

Полигон это пространственный многоугольник, ограниченный ребрами, состоящий из граней.

моя словарная база сегфолтнулась и восстановлению не подлежит ;(

>В чем рисовал, если сам?

блендер+гимп

Полигон это пространственный многоугольник, ограниченный ребрами, состоящий из граней.

Не понимаю, что за проблема распарсить это? Полигон может быть прямоугольным. Разбивается на 2 треугольника, ребро между которыми скрывается для удобства работы и сглаживания.