ДР/2015/Л9/Група 2

В лекция 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 файл с модел на Пентагона и триангулираме покрива му):

pentagon

Но нека се върнем в Европа. Както е ясно на всички, тук нещата винаги са по-сложни, като в резултат на това обитателите на континента са по-интелигентни. Еквивалентна административна сграда би била тази на Европейската Комисия:

Commission Européenne
Не претендирам за 100% достоверност на очертанията

Ако ползваме наивния алгоритъм за триангулация, ще получим това:

Naive triangulation

Резултатът ще бъгнее очевадно в рендера - можете да проверите: в tag homework9 имате създадена сцена за вашата задача - data/hw9/nonconvex.trinity. Задайте да ви се ренди тя и ще видите как изглежда дефектът наяве.

Подходящи триангулации има най-различни. Автоматичните алгоритми биха постигнали нещо такова:

Ear clipping triangulation

По-стриктни алгоритми, целящи триангулация на "хубави" и сходни по вид триъгълници биха направили по-скоро нещо такова:
Better triangulation

От гледна точка на самия рейтрейсър, и двете представяния са "вярни".

Потърсете в интернет информация как се триангулират неизпъкнали многоъгълници. Използвайте алгоритъм по ваш избор (в първия пример се ползва "рязане на уши" - "ear clipping"). Алгоритъмът трябва да работи с произволни прости многоъгълници - незадължително изпъкнали, но няма да има самопресичане. Имайте предвид, че някои текстове приемат конкретна ориентация на върховете на многоъгълника: счита се, че те са зададени в определен ред - в "правилна" математическа посока, т.е. по посока обратна на часовниковата стрелка. В този ред, насоченото лице на многоъгълника ще е положително. При вас няма да има гаранция, че е така - ще трябва да направите проверка какъв ви е реда предварително.

Ето примерна схема как да решите задачата:

  1. В обработката на 'f'-редовете в loadFromOBJ() си запазете tokens[] масива. Първото число на всеки token е индекс в масива vertices. Ползвайте, примерно
    P[i] = vertices[getInt(split(tokens[i], '/')[0])]
    за да извлечете 3D точките на този многоъгълник (върховете му нека означим с P1, P2, P3, ... ,PN).
  2. Триангулиращите алгоритми работят изцяло в 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))
  3. Сметнете триангулацията на многоъгълника Q, ползвайки избрания от вас алгоритъм. Алгоритъмът трябва да изведе списък от индекси (списък от тройки индекси - триъгълниците, на които е разбит Q).
  4. Ползвайте получените тройки индекси за да триангулирате P. Един вид вкарвайте нови триъгълници в triangles[] по същия начин като сегашния код в loadFromOBJ, но с индексите, получени на предходната стъпка.

В резултат трябва да ви се получи нещо такова:

expected

Ако смените камерата на "pos (0, 100, -100)" и разкоментирате всички обекти в сцената, ще се получи това:

expected

:)

Задачата е трудна - не се колебайте да питате и да пращате код, ако ударите на камък.

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, тогава трите точки са колинеарни.