ДР 2013/8+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

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