ДР/2015/Л9/Група 2
- Forums:
В лекция 7 споменахме, че триъгълните мрежи (например задавани в OBJ файлове) всъщност са полигонални мрежи, но ние лесно можем да ги разбием до триъгълници. Задачата тук ще е да напишете по-сериозен алгоритъм за триангулация.
В лекция 8 споменахме, че OBJ файловете съдържат описания на многоъгълници в редовете, започващи с 'f'. Когато видим f-ред, прочитаме точките на многоъгълника и прилагаме следният симплистичен алгоритъм за триангулирането му (редове 335-338):
Дадено: многоъгълник, върховете му са номерирани 1, 2, 3, ..., N.
Генерираме триъгълниците (1, 2, 3), (1, 3, 4), (1, 4, 5), ..., (1, N - 1, N).
Лесно се вижда, че този алгоритъм работи в частния случай, когато многоъгълникът всъщност е триъгълник, както и за квадрат или правоъгълник; всъщност работи за произволен изпъкнал многоъгълник, като ето една примерна триангулация (да речем са ни дали .obj файл с модел на Пентагона и триангулираме покрива му):
Но нека се върнем в Европа. Както е ясно на всички, тук нещата винаги са по-сложни, като в резултат на това обитателите на континента са по-интелигентни. Еквивалентна административна сграда би била тази на Европейската Комисия:
Не претендирам за 100% достоверност на очертанията
Ако ползваме наивния алгоритъм за триангулация, ще получим това:
Резултатът ще бъгнее очевадно в рендера - можете да проверите: в tag homework9 имате създадена сцена за вашата задача - data/hw9/nonconvex.trinity. Задайте да ви се ренди тя и ще видите как изглежда дефектът наяве.
Подходящи триангулации има най-различни. Автоматичните алгоритми биха постигнали нещо такова:
По-стриктни алгоритми, целящи триангулация на "хубави" и сходни по вид триъгълници биха направили по-скоро нещо такова:
От гледна точка на самия рейтрейсър, и двете представяния са "вярни".
Потърсете в интернет информация как се триангулират неизпъкнали многоъгълници. Използвайте алгоритъм по ваш избор (в първия пример се ползва "рязане на уши" - "ear clipping"). Алгоритъмът трябва да работи с произволни прости многоъгълници - незадължително изпъкнали, но няма да има самопресичане. Имайте предвид, че някои текстове приемат конкретна ориентация на върховете на многоъгълника: счита се, че те са зададени в определен ред - в "правилна" математическа посока, т.е. по посока обратна на часовниковата стрелка. В този ред, насоченото лице на многоъгълника ще е положително. При вас няма да има гаранция, че е така - ще трябва да направите проверка какъв ви е реда предварително.
Ето примерна схема как да решите задачата:
- В обработката на 'f'-редовете в loadFromOBJ() си запазете tokens[] масива. Първото число на всеки token е индекс в масива vertices. Ползвайте, примерно
P[i] = vertices[getInt(split(tokens[i], '/')[0])]
за да извлечете 3D точките на този многоъгълник (върховете му нека означим с P1, P2, P3, ... ,PN). - Триангулиращите алгоритми работят изцяло в 2D, затова прехвърлете си P в 2D многоъгълника Q. За целта, ползвайте триъгълника P1P2P3 за да сметнете геометричния нормал на многоъгълника, като векторно произведение на P1P2 и P1P3. Чрез orthonormedSystem() сметнете два перпендикулярни вектора a и b. Скаларните произведения на Pi с a, b дават, респективно, x и y координатите на 2D проекцията P → Q: Qi = (dot(Pi, a), dot(Pi, b))
- Сметнете триангулацията на многоъгълника Q, ползвайки избрания от вас алгоритъм. Алгоритъмът трябва да изведе списък от индекси (списък от тройки индекси - триъгълниците, на които е разбит Q).
- Ползвайте получените тройки индекси за да триангулирате P. Един вид вкарвайте нови триъгълници в triangles[] по същия начин като сегашния код в loadFromOBJ, но с индексите, получени на предходната стъпка.
В резултат трябва да ви се получи нещо такова:
Ако смените камерата на "pos (0, 100, -100)" и разкоментирате всички обекти в сцената, ще се получи това:
:)
Задачата е трудна - не се колебайте да питате и да пращате код, ако ударите на камък.
Comments
Удължаване на срока
Може ли да пратя моето решение, в неделя следобяд. Тази седмица съм залят с контролни и утре също имам контролно. Няма да успея да я напиша до края на срока. Вярвам, че мога да го направя до обяд на неделя.
Той срокът е до неделя
Той срокът е до неделя вечерта, или по-точно до малко след полунощ в Понеделник - пиши си спокойно.
Reflex angles
Има ли някакъв начин да намерим reflex angles от 3 точки?
Ето
Да.
Ако точките са ти A, B и C, като върхът с ъгъла е B, то формираш векторите BA и BC (посока от B към A и от B към C). Нормираш ги, след което смяташ скаларното произведение на BA и BC, по същия начин, както е и в 3D. Така получаваш косинуса на вътрешния ъгъл. Оттам - чрез аркускосинус получаваш вътрешния ъгъл α. Външния (reflex) ъгъл е 360°-α.
Аз не съм си представил добре
Аз не съм си представил добре въпроса. Как може да се определи дали един ъгъл е вдлъбнат или изпъкнал за многоъгълник? Опитвам се да имплементирам monotone triangulation.
Насочено лице
Ползвайки насоченото лице (shoelace formula-та). Първо проверяваш дали насоченото лице за целия многоъгълник е положително или отрицателно. Да речем се оказало положително. Оттам насетне, взимайки три последователни върха A, B и C, смяташ насоченото им лице. Ако то е положително (т.е. със същия знак като целия многоъгълник), значи върхът B е изпъкнал; иначе е вдлъбнат. Насоченото лице може и да е 0, тогава трите точки са колинеарни.