Алгоритъм на Doo-Sabin Описание на алгоритъма

Алгоритъм на Doo-Sabin

Описание на алгоритъма:
Алгоритъмът на Doo-Sabin е алгоритъм за subdivision на 3D повърхнини. Началната мрежа

обикновено е пространствен многостен, но може да е и с произволна топология. Намираме барицентъра на всяка от стените (те не са непременно равнинни). Съединяваме барицентъра на всяка от стените с върховете на съответната стена и на така получените отсечки намираме средите. Така получените нови точки ще бъдат върхове на нов многостен, който е образуван в резултат на subdivision от изходния. За да бъде построен този нов многостен е нужно да знаем как се свързват новополучените точки, за да получим новите стени. Различаваме 3 типа стени, които се получават:

1. Първият тип са стените, който се получават “под” върховете на изходния многостен. За да ги получим е нужно да вземем новополучените точки, които са породени от съответния връх. Вижда се, че техния брой е равен на броя на стените на изходния многостен с общ връх съответния връх. Той пък от своя страна е равен на броя на ръбовете, които излизат от съответния връх. Следователно “стените под върховете” са р-ъгълници, където р е броят на ръбовете, излизащи от съответния връх .

2. Втория тип стени, които се получават, са стените под ръбовете. За да получим тези стени, вземаме новополучените точки, които са породени от краищата на съответния ръб. Тъй като всеки ръб има точно 2 съседни стени и точно 2 края, то “стените под ръбовете” са четириъгълници (не непременно равнинни).

3. Третият, и последен тип, са стените, които се получават във вътрешността на стените на изходния многостен. При тях на всяка стена на изходния многостен вземаме новополучените точки и ги свързваме. Както се вижда, се получава стена със същия брой върхове, както и изходната стена. Нещо повече – ако изходната стена е равнинна, то се получава стена, подобна на изходната, която е 2 пъти по-малка.

Резултатът от многократното прилагане на алгоритъма на Doo-Sabin е С1-гладка повърхнина.

Описание на програмата
Програмата е реализирана на OpenGL и Qt за графичния интерфейс. Може да бъде компилирана и да работи на Windows, Linux и MacOSX.

При стартиране на програмата се търси за поддиректория на текущата директория с име Geometry. В тази директория се намират основните модели, с които програмата работи. При наличието на тази директория и при наличието на валидни модели, то те автоматично се добавят в падащото меню Select polyhedron. Първият модел се зарежда автоматично и се визуализира. От бутона Load може да бъдат зареждани модели, които не се намират в директорията Geometry. Програмата може да зарежда модели, които са записни във файлов формат OFF. Този формат представлява списък с върхове и списък с стени за съответния модел. Важно е да се отбележи, че не всички разновидности и нови версии на OFF файловия формат се поддържат и зареждат.

След като моделът е зареден може чрез слайдера да се укажат броя итерации, които да бъдат извършени от алгоритъма. Чрез Show vertices се определя дали върховете на изходния многостен да са видими. Те са представени чрез сини точки. Положението им може да бъде променяно с помоща на мишката. Движението на върховете се осъществава в равнина, успоредна на екрана.

От Polyhedron type се определя как да бъде представен многостенът – или като плътен обект или само като контур на стените. Когато е избран да бъде представен като плътен обект може да се избира и типът на светлината. При Flat light всяка стена е различно осветена, докато при Smooth light многостенът се осветява в зависимост от положението на върховете като по този начин се създава по-гладък ефект на осветяването. Ако за тип на представянето на многостена е избрано да бъде само като контур, то е възможно да се визуализират стените, които ще бъдат генерирани на следващата стъпка. Show on vertices показва стените, които са “под” върховете (или от тип 1), Show on edges показва стените, които са “под” ръбовете (или от тип 2) и Show on faces показва стените, които се получават във вътрешността на изходните стени. Важно е да се отбележи, че тези стени се визуализират само при първите 2 стъпки на алгоритъма. Причината е, че алгоритъмът е бързо сходящ и след 2-рата стъпка новополучените стени стават твърде много и няма смисъл да се показват следващите стени.

Със скролера на мишката се осъществява Zoom на сцената, а при влачене с натиснат ляв бутон става и ротация на сцената. Върховете може да се местят, когато мишката е над тях и местенето става с влачене с натиснат ляв бутон. За да се върне сцената в начално положение се използва Reset бутона.

Каталог: fmi -> companal -> krassivl
krassivl -> 3d-алгоритъм на Chaikin
fmi -> Конкурентно Програмиране
fmi -> Лекции по компютърни мрежи и комуникации
fmi -> Ще предпочетеш да наблюдаваш света отстрани или ще се присъединиш към най-голяма студентска организация?
fmi -> Лекции по обектно-ориентирано програмиране
krassivl -> Crossplot на крива на Bezier Аплетът има две основни състояния(modes) Insertion mode
krassivl -> 1. Oписание на алгоритъма Описание на реализация Описание на функционалност
krassivl -> Повърхнина на Peters-Reif За да работи приложението е необходимо на компютъра да е инсталиран
krassivl -> Алгоритъм за повишаване степента на криви на Безие