Postupak odabiranja objekata

Diplomski projekt

Hrvoje Gazibara, Marijan Šuflaj

Fakultet elektrotehnike i računarstva

Sveučilište u Zagrebu

Siječanj 2014.

Sadržaj

• Uvod
• Odabiranje objekata
• Oktalno stablo
• Pomoćni spremnik

Odabiranje objekata

• Temelji se na postupku bacanja zrake
  • Kreira se zraka na temelju podataka o kameri te točki dodira
  • Pronalaze se objekti probodeni zrakom
  • Pronađeni objekti slažu se od najbližeg do najudaljenijeg od kamere
  • Odabire se najbliži objekt

Problem

• Traženje probodišta potrebno provesti za sve objekte
• Vremenski zahtjevno u slučaju većeg broja objekata
• Usporava rad aplikacije

Poboljšanja

• Smanjiti broj pretraživanja organizacijom scene
• Koristiti naprednije WebGL-ove tehnike

Organizacija scene

• Početna ideja
  • Podijeliti scenu na nekoliko dijelova
  • Svaki dio sadrži neke objekte
  • Tijekom odabiranja objekata pretražuje se samo dio scene
• Vremensko ubrzanje: pretraživanje korištenjem svih objekata vs korištenjem samo nekih objekata

Oktalno stablo

• Tehnika organizacije scene
• Postupak
  • Podijeli scenu na 8 dijelova – oktanata
  • Dijeli oktante dok god je to potrebno (npr. Previše objekta u oktantu)
• Rekurzivan postupka

Oktalno stablo

Oktalno stablo

Oktalno stablo

• Kako odrediti koji oktant sadrži željene objekte
• • Provjerava se kojem početnom oktantu zraka pripada
  • Nastavlja se obavljati provjera dok se ne dođe do lista stabla
  • Za svaki objekt unutar lista provjerava se postojanje probodišta

Oktalno stablo

• Zašto je ovo bolje?
• • Pronađeni vršni oktant sadrži manje objekata od kompletne scene
  • Smanjeni broj pretraživanja dovodi do ubrzanja aplikacije

Pomoćni spremnik

• Postupak
  • Dodijeli jedinstvenu boju svakom objektu
  • Stvori prikaz objekata u pomoćnom spremniku
    • Svjetla, magla i ostali efekti moraju biti ugašeni
  • Pročitaj boju točke na odabranoj poziciji
  • Pronađi objekt s pročitanom bojom
• Pomoćni spremnik se koristi kako korisnik ne bi vidio treperenje ekrana

Objekti i njihove jedinstvene boje

Prednosti

• Vrlo jednostavna i brza implementacija
  • WebGL nudi većinu potrebne funkionalnosti
• Brz odaziv za ne tako velik broj selekcija
  • Jedna sličica je rezervirana za selekciju
• Selekcija se odvija u gotovo konstantnom vremenu

Nedostatci

• Usko grlo je komunikacija između CPU-a i GPU-a
• U najjednostavnijoj implementaciji ograničenje na 16777215 objekata
  • Broj dopuštenih boja bez boje pozadine

Broj sličica u sekundi za neoptimiranu implementaciju

Broj sličica u sekundi za optimiranu implementaciju

Rezultati

• Gotovo dvostruko ubrzanje u odnosu na neoptimiranu implementaciju
  • Selekcija se odvija u prosjeku oko 15ms
  • Primjetite gotovo konstantan FPS u optimiranoj implementaciji
• Većina vremena je otišla na proučavanje biblioteke Three.js
  • Bila je potrebna izravna komunikacija s WebGL-om