1. Oписание на алгоритъма Описание на реализация Описание на функционалност



Дата24.04.2017
Размер90 Kb.
Butterfly subdivision (схема на пеперудата)

Съдържание



1. Oписание на алгоритъма

2. Описание на реализация

3. Описание на функционалност

4. Описание на графичен интерфейс

5. Описание на нефункционални спецификации

6. Наръчник за употреба

7. Диаграми

1. Описание на алгоритъма



Butterfly subdivision е интерполационен стационарен алгоритъм, работещ с триъгълни мрежи. Първоначалните точки от контролната мрежа принадлежат на повърхнината и са неподвижни при всяка стъпка от алгоритъма. Това важи и за новите точки в изходната мрежа на всяка стъпка от алгоритъма.

През 1990 година Dyn, Levin и Gregory публикуват статията ,,A Butterfly Subdivision Scheme for Surface Interpolation with Tension Control”, описващ първия такъв алгоритъм. Идеята е всяко ребро на триъгълна мрежа да се раздели на две нови ребра, вследствие на което всеки триъгълник се подразделя на 4 нови триъгълника. Наименованието на алгоритъма произлиза от шаблона, използван за оценка на съседите при това разбиване, който показва с какви тежести те участват при позиционирането на новата точка за всяко ребро.






W е параметър, контролиращ колко плътно граничната повърхност бива придърпвана към контролната мрежа. В случаите, когато w = -1/16, схемата просто линейно интерполира краищата на реброто и тогава повърхността не е гладка. В случай че контролната мрежа не изглежда по начина, представен на шаблона, е нямало друг избор, освен w = -1/16 в тази област, което прави повърхността там да не е гладка изобщо. Затова през 1993 година моделът е разширен до 10 точков, запазващ свойствата на афинната комбинация от съседните точки.





Ако w = 0, новата схема се редуцира до старата. За да се постигне гладкост, обаче, през 1996 година схемата е допълнена от Zorin, Schröder и Sweldens с друг шаблон, който гарантира C1 гладкост навсякъде.









Ако и двата върха на някое ребро са от степен 6, тогава се използва старата схема. Ако само единият е от степен, различна от 6 , се прилага новият шаблон върху този връх. Ако и двата върха на реброто имат степени, различни от 6, се прилага новата схема и за двата и се взима средното аритметично на резултата.

2. Описание на реализацията

Алгоритъмът е реализиран с използване на JDK 6.18. Визуализацията на моделите се извършва върху графичната карта чрез Java3D. За целта се построява граф на сцената, съдържащ модела, две насочени лампи и допълнително ambient осветеление, фон и контроли за трансформация (ротация, транслация, zoom in & out). Атрибути на модела като геометрия и изглед са в режим ,,ALLOW_GEOMETRY_WRITE” и ,,ALLOW_APPEARANCE_WRITE”, за да се позволи смяна на геометрията и външния вид на обекта динамично по време на изпълнение. Аналогични настройки са поставени и върху контролите за навигация.

Класът „Loader” зарежда геометрия от даден файл, като разчита коректно *.оff формат. Извлича списък от уникални точки от геометрията и списък от индекси към тях за лицата. Класът извежда тази своя вътрешна информация под формата на Shape3D, като предварително е извършена триангулация и пресмятане на нормалите за shading.

Информацията от този клас служи за инициализация на класа „Mesh”. Контролната геометрия е представена като списък от точки, списък от лица, граф на съседство на точките, асоциативен списък, свързващ точките с прилежащите им лица и асоциативен списък, свързващ ребро към точка, който пази новосъздадените точки от всяко ребро. Тук „Face” и „Edge” са помощни класове.

Алгоритъмът обхожда по графа на съседство всички ребра, като според броя на съседите на даден връх и негов съсед (дефиниращи текущото ребро), се определя схемата, която трябва да се използва. Оценката на новата точка започва от оценката на краищата на реброто и започва да се „върти” по съседите на единия връх от реброто в строга последователност, реализирана от интерфейса на класът “Face”. Именно за тази част ни трябва съпоставката точка-лице. Поради симетричността на тежестите (следва от периодичността на косинуса във формулите) няма значение посоката на въртене. Новосъздадената точка се записва в списъка с нови точки, като е индексирана от ребро. След като са обходени всички ребра, започва процес по обновяване на представянето на mesh по такъв начин, че да въведе новите точки с коректно регистрирани съседи и да прекъсне връзките на старите точки. Обхождането става лице по лице, използвайки списъка с вече стари лица. Използвайки ребро – нова точка съответствието, правилно се индексират новолпоучените точки според страните на текущия триъгълник. Обновяват се масивите с точки. Обновява се графът на съседство. Обновява се текущото лице и се добавят 3 нови лица. След като приключи обновяването, списъкът с нови точки се изчиства. Структурата е обновена и може да се приложaт абсолютно същите стъпки отново без корекции за получаване на ново ниво на subdivision. Изходът е аналогичен на този от Loader, а именно Shape3D.

За удобство тежестите на съседите в шаблоните са предварително изчислени и мемоизирани в двумерен масив. Първият индекс „i” се използва за указване на брой съседи, а втория „j” - за указване тежестта на конретния съсед при „i” съседа.

Мемоизация се използва и за предишните състояния на обекта, т.е. всяко вече изчислено ниво не се преизчислява отново. При първото прохождане на нивата се отнема много процесорно време, а след това само се работи с паметта. Броят стъпки е ограничен от броя триъгълници заради огромната консумация на памет (120 – 350 MB), но все пак са позволени разумен на брой стъпки според всяка геометрия.
Архитектурата е стандартен MVC, където View е реализиран от класа ButterflySD, който визуализира интерфейсите и делегира действията на потребителя към Controller-a, чиято дейност се извършва от GeometryController. Той разпределя повикванията към Mesh и Loader, създава сцената и обновява състоянието ѝ, както и работи със заделянето на памет. За четец на базата от геометрии служи Loader.

3. Описание на функционалност




3.1. Увеличаване или намаляване на нивото на subdivision.
Потребителят може да определя степента на subdivision на геометрията посредством бутоните . Самото ниво се указва в полето между бутоните. Броят стъпки е ограничен специфично за всяка геометрия според общия брой триъгълници и ниво на детайл.

3.2. Настройка на ъгъл за заглаждане

При визуализация на обекта в shaded режим се използва заглаждане

на ръбовете между два триъгълника от контролната геометрия. Потребителят може да регулира максималната големина на ъглите, които се заглаждат чрез местене на плъзгача в границите на стойностите от 0 до 90 градуса, . Например ако искаме да наблюдаваме добре контролната мрежа по време на заглаждането на обекта, настройваме този ъгъл на 0. Ако искаме обекта да е с заоблени ъгли, настройваме ъгъла с по-големи стойности според самата геометрия. Понеже нормалите на триъгълниците зависят от този ъгъл, при неговата смяна геометрията става невалидна и е нужно преизчисление. Затова геометрията се зарежда на ново и нивото на subdivision се нулира. По подразбиране стойността е 0.

3.3 Настройка на повърхностно напрежение

Тази настройка позволява на потребителя да регулира тежестите, с

които се взимат съседите на краищата на разглежданото ребро при изчисление на координатите на съответната нова точка, ако се използва стандартната схема, т.е. степените на съответните краища са 6. Тежестите са представени в първата точка на документацията. Потребителят може да избира стойността чрез местене на плъзгача, като избира стойности между -0.1 и 0.1, . Понеже изходната геометрия след поредната стъпка на алгоритъма изцяло зависи от тази стройност, при нейна актуализация се презарежда геометрията и се нулира нивото на subdivision, понеже обектът е вече невалиден.

3.4 Избор на режим на визуализация

Потребителят има възможност да избира два режима за

визуализация на обекта чрез радиобутоните . В режим Shaded обектът е визуализран посредством син дифузен материал. В режим Wireframe обектът се изчертава чрез контури на съставящите го триъгълници. Така може да се наблюдава по-детайлно резултатът от прилагането на алгоритъма и да се види много ясно скоростта на увеличение на детайла. И в двата режима се използва оптимизация при визуализацията, която не допуска изчертаването на задните страни на обектите (Back face culling).

3.5 Избор на геометрия

Програмата предлага възможност за смяна на текущата геометрия.

Наборът от обекти е съставен както от прости геометрични фигури, така и от по-сложни обекти, демонстриращи силата и бързата сходимост на алгоритъма. Изобрът се извършва чрез селекция на файл от падащото меню . Геометрията ще бъде обновена и нивото на subdivision ще бъде занулено.

3.6 Навигация

Навигацията се извършва чрез мишката с drag-and-drop техника. Левият бутон служи за ротация. Десния бутон служи за транслация. Ако искаме фино приближаване или отдалечаване, използваме средния бутон или scroll-a. За по-грубо постъпково приближаване може да се използва scroll wheel.



4. Описание на интерфейс





5. Описание на нефункционални спецификации

За правилното функциониране на аплета е необходимо да се поставят в една и съща директория *jar файлът, директориите с изображения images и директорията с геометрии geometry . За реализацията на проекта са използвани последните версии на JDK (6.18) и Java3D. Препоръчва се тяхното ползване.

Понеже алгоритъмът е реализиран на Java има тенденцията да използва повече памет. Когато работи извън средата на разработка не е ограничен в това колко памет да изолзва, но обикновенно при последните стъпки използва между 120 и 350 MB. Заради съображения за устойчивост (обикновено алгоритъмът се затормозява когато броя триъгълници става много голям и browser-ите не работят добре), всяка геометрия е разумно ограничена според броя на триъгълниците, които се получават.

Понеже самата визуализация се извършва на видео картата, навигацията и смяната на режимите за визуализация на обекта използват незначителни процесорни ресурси. Те се ангажират единствено при първоначалното увеличаване на стъпките (след това вече са записани, така че не е нужно ново пресмятане), но като цяло изглежда сякаш реагира достатъчно адекватно от гледна точка на бързина.

Когато се изпълнява като аплет, от съображения за сигурност е забранено на програмата да работи с потребителската файлова система. Поради евентуални проблеми в това отношение програмата е подписана с електронен подпис на името на автора. Желателно е ако потребителят бъде попитан дали разрешава да се оперира с файловата му система да приеме (само в този случай).

6. Наръчник

6.1. Стартиране


Проектът може да бъде активиран или чрез стартиране на Butterfly.jar

файла, или чрез зареждане на ButterflySD.html файла в интернет browser (не работи под Internet Explorer). И в двата случая трябва да присъстват файловете geometry и images в същата директория, в която е разположен *.jar файлът. HTML файлът също разчита *.jar файлът да е в неговата директория.

6.2. Смяна на обект

Смяната на обект може да се извърши чрез избор на нова геометрия от

падащото меню. При смяна на обект нивото на subdivision се нулира.

6.3. Смяна на визуализация


Програмата позволява обектите да се визуализират в два режима: Shaded и

Wireframe. Изборът става чрез кликване върху съответните радио бутони.

6.4. Настройка на визуализацията

Може да се сменя ъгълът на smooth-ване на геометрията. Всеки ъгъл между две лица (триъгълника) ще бъде загладен, ако е не по-голям от избрания crease angle, според плъзгачa. При 0 градуса няма заглаждане. При 90 градуса се заглаждат всички ъгли. Понеже се налага пресмятане на нормали според ъгъла, при промяна се рестартира геометрията.



6.5. Настройка на алгоритъма

Може да се настройва така нареченото „Повърхностно напрежение” на алгоритъма. По подразбиране е 0.0, което означава, че се прилага стандартният Butterfly шаблон. За останалите стойности се прилага модифицираният шаблон със съответните корекции на тежестите. Понеже се налага преизчисляване на геометрията, при промяна се презарежда с ниво 0.



6.6. Ниво на subdivision


Ниво на subdivision се избира от горните две стрелки. Геометриите отнемат много памет и са ограничени до разумни нива на subdivision според броя триъгълници.



6.7. Навигация

Ляв бутон на мишката служи за ротация (drag and drop). По аналогичен начин, десния служи за транслация. Чрез скролване се приближаваме и отдалечаваме. Може да се натисне и задържи скрола и чрез drag and drop напред и назад да се контролира по-фино приближаването и отдалечаването.


7. Диаграми







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


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©obuch.info 2019
отнасят до администрацията

    Начална страница