Nadji negde osnove linearne algebre, a za dalje...pa zavisi kako organizujes skeniranje.
Na primer, moze posmatrac da skenira stapove jedan po jedan, mogu stapovi da skeniraju posmatraca (i time definisu svoju vidljivost), a moze i kamen da odredjuje prohodnost pravca posmatrac-stap. Pod pojmovima posmatrac, stap, kamen mislim naravno na objekte...

Rajko

e tu i jest problem, kako da provjerim dal je pravac posmatrac-stap prohodan, to jest da li duz posmatrac-kamen prolazi kroz neki kamen, dal postoji mozda neka matematicka formula za to?

Ja bih to resio "pesacki" - svaki kamen je neki poligon jel'te, svaki poligon se sastoji od konacnog broja duzi. Vec postoji gotov nacin da se ispita da li prava sece duz (duz je zapravo deo prave od tacke A do tacke B). Posto imas pravac (pravu) kojom posmatrac treba da "ide", onda samo treba da odradis jednu rutinu koja ce da ispita da li ta prava sece duzi koje pripadaju poligonu koji zapravo predstavlja taj objekat (kamen). Ako sece makar jednu duz onda mozes bez problema da setujes neku varijablu na TRUE, koja indikuje da kamen lezi na putu posmatraca...

Sad mozemo malo i da zakomplikujemo, pa da definisemo i putanju kao prostor izmedju dva poligona (koji nisu zatvoreni, logicno) i da postavimo pitanje da li posmatrac (dat takodje kao poligon (objekat)) moze da se "provuce" pored kamena i "zida" :) itd.

To sam i ja prvo pomislio kada sam poceo rjesavati problem,i to sigurno ce dati rjesenje.Al problem je u vremenu, posto broj kamenova moze biti do 5000 a program treba u roku 2 sec dat rjesenje.

Kao npr.situacija na slici,gdje imamo 2 kamena, i ja sam tu proceduru ("rotaciono skeniranje") zamislio da u prvom prolazu izvrsi samo ogranicavanje (kao crvene linije na slici) a zatim u drugom izvrsi samo preprojavanje stapova koji su ostali u "vidljivim" djelovima.Sad kako to programski realizovati...?

Komplikovano :))

naravno da bi to bilo najsporije rešenje. to kako si ti počeo sa crvenim granicama je dobra ideja, ali nije potpuna.

elem, da bi našao sve zelene površine na slici, treba da odbaciš sve druge.

počni recimo od donjeg kamena na tvojoj slici. nađeš njegovu "najleviju" i njegovu "najdesniju" tačku, gledano iz ugla posmatrača. to su njegova gornja-leva i donja-desna tačka u ovom primeru.

zatim, izračunaš uglove pod kojim posmatrač vidi te tačke (ako posmatrača translacijom staviš u centar koordinatnog sistema, onda ugao tačke (x,y) računaš kao arctan(x/y)) i sve između tog najmanjeg i najvećeg ugla (tj između "najlevije" i "najdesnije" tačke za taj kamen) je nevidljivo.

ovaj postupak ponoviš za svo kamenje, i dobiješ da su neviljivi uglovi npr od 13-24, 150-191 i 230-299 stepeni. zatim lepo prođeš kroz sve stubove, i za svaki izračunaš ugao pod kojim ga vidi posmatrač (opet ista formula) i odbaciš sve koji upadaju u jedan od ovih intervala.

(alternativno, ova provera možda može i brže ako jednostavno ispituješ da li je tačka ispot/iznad ovih graničnih pravi, ali tu ima malo više spec slučajeva, a i nisam sugran koliko brže bi to stvarno i bilo, jer svi moderni procesori u FPU imaju tablice za sinusne/kosinusne i sve izvedene funkcije, pa je i to računanje arctan() prilično brzo)

---

e to je bilo prosto i elegantno rešenje. ali kao što rekoh, nije kompletno. vidi dopunjenu sliku. zaboravio si da računaš i ove plave delove kao vidljive.



nažalost, ne mogu baš da vidim elegantan način za određivanje koji su tačno stubići u toj plavoj oblasti. naravno, prost metod je da računaš udaljenost stubića od posmatrača (koren iz x²+y²), i da ispituješ da li je štap bliži od kamena, ali se to komplikuje u okolini samog kamenja (baš primetno oko trouglastog kamena)

no, ovo bi trebalo da ti bude dosta domaćeg za danas.. možda u međuvremenu neko nešto i smisli ;)


// inače: ovo je više za forum Art of Programming, pa se moli moderator...

Pa ako je polje 100*100 a ako su kordinate celi brojevi onda ce ti raditi krace od 2 sec.

hm...

10,000 stubića * 5,000 poligona * 6 stranica po kamenu (prosečno) = 300,000,000 ispitivanja.

a svako ispitivanje podrazumeva računanje jednačina za dve prave, nalaženje tačke preseka, i proveru da li je ta tačka u datom intervalu (na datoj duži).

nisam siguran da to može da se izvede za dve sekunde.. ti?

a mislis da ces za svih 10 000 stubica proveravati 5000 poligona? Pa cim naletis na jedan poligon ti prekida. Sto je veci broj poligona to je veca sansa da naletis na jedan za koji ce seci pravu do posmatraca. Driga stvar je sto ne moras da ides po stubicima nego po poligonima pa cim za jedan poligon vidis da neki stubici ne mogu da se vide onda vise ne proveravas za ostale poligone.
Mislim da moze da se uradi za 2 sec.

"u najgorem slučaju" (a sve ovo posmatramo iz tog ugla), poligoni će biti mali (1x1), pa će se retko dešavati da je jedan stubić zaklonjen sa više poligona.

u tom slučaju možemo da pretpostavimo da se broj stubića koji su zaklonjeni sa više poligona potire sa brojem stubića koji nisu uopšte zaklonjeni (znači, za koje MORAŠ da izvrtiš svih 5000 poligona).

znači da si ovim dokazom sveo proj pregledanja na prosečno 2500, zato što je 50% šansa da se poligon koji zaklanja određeni stubić nađe u prvoj polovini pregledanih poligona.


a to drugo što si rekao (da vrtiš po poligonima) se svodi na isto ovo. razmisli ponovo, za svaki poligon moraš da izvrtiš sve stubiće (koji već nisu označeni kao zaklonjeni), i da vidiš da li ih taj poligon zaklanja.


dakle, iako je broj ispitivanja pao na 150,000,000 -- opet mi se ne čini da su 2 sekunde dovoljne...

E ovo vec moze znatno da se ubrza. Prvo proveris za kamenje koje je najblize posmatracu cime si najveci broj stubica vec oznacio kao nevidljive. Posle moras da proveravas za mnogo manji broj stubica.

e to je bilo prosto i elegantno rešenje. ali kao što rekoh, nije kompletno. vidi dopunjenu sliku. zaboravio si da računaš i ove plave delove kao vidljive.



nažalost, ne mogu baš da vidim elegantan način za određivanje koji su tačno stubići u toj plavoj oblasti. naravno, prost metod je da računaš udaljenost stubića od posmatrača (koren iz x²+y²), i da ispituješ da li je štap bliži od kamena, ali se to komplikuje u okolini samog kamenja (baš primetno oko trouglastog kamena)


Mislim da ste tu malo pogrijesili, kao sto rekoh stubici se nalaze na stranicama ovog polja i to na svakom metru po 1, znaci posto je polje 100*100 znaci ukupno ima 400 stubica.

I usput hvala vam puno ste pomogli,tu je negdje rjesenje.

Te sad nam kazes da je tu samo 400 stubica!!!! :-))))
Pa sigurno moze u 2 sec! Gledas samo uglove kako ti je zombie pokazao i vidis koji stubici pripadaju/ne pripadaju uglovima koja pokriva svaki kamen.

He he, pravo da ti kazem imao sam isti problem koji sam resio, vezan za aiarena

http://alas.matf.bg.ac.yu/~mr97209/libaiarena.h

Kod je pod GPL-om, pa ako ti odgovara GPL kao licenca http://www.gnu.org/copyleft/gpl.html
(ili nas nezvanicni prevod http://www.elitesecurity.org/tema/27296 radi boljeg razumevanja samog GPL-a) kontaktiraj me pa cu ti dati kod posto jos uvek razvijam projekat pa nisam nista jos objavio javno.

Ako ti neodgovara GPL onda mogu da ti dam mali hint, uzmi tacku posmatraca i tacke stapova pa onda "crtaj" linije od posmatraca do stapa stim sto ce umesto crtanje tacke u liniji tebi biti ispitivanje uslova da li si naisao na kamen. Najbrzi algoritam za crtanje linija je mid-point algoritam, naci ces ga sigurno na netu.

libaiarena je kewl ;)

Ma moze i za mnogo manje vremena sta je iscrtati 400 linija sa recimo mid-point algoritmom, to je kod mene na p2 433 mhz odradjeno za 0.15 sec

Dosta davno radio sam slican algoritam. Najbrze je da se panorama podeli na sekcije od 90 stepeni i koristi z depth buffer 3D projekcije. Svaka linija se predstavi pomocu vektora nomale i ako je naopako okrenuta ne iscrtava se.

Ako ti nije bitno koji kamen zaklanja koji sutbić onda je jednostavno.

Postavi koordinatni početak u posmatrača i razvrstaš duži koje sačinjavaju poligone u 4 grupe prema kvadrantima kojima pripadaju. Onda za svaki stubić proveravaš da li se duž posmatrač-stubić seče sa svakom pozitivno orjentisanom duži u tom kvadrantu, dok ne nađeš prvu koja se seče.

A ako ima više duži poligona kamenja od stubića brže je proveravati obrnuto, tj za svaku duž poligona da li se seče sa duži posmatrač stubić.

Ako još imaš istu konfiguraciju kamenja za različite položaje posmatrača, sortiranje kamenja u BSP ubrzava proces.

Ostaje pitanje da li ćeš koristiti inverzne trigonometrijske funkcije ili osnovne aritmetičke operacije za proveru preseka, odnosno da li ćeš računati ugao pod kojim se vidi kamen i duž te projekcije proveravati za presek ili ćeš svaku duž poligona zasebno, šta je brže?

Potraži na google
fast 2D line segment intersection algorithm
verujem da ćeš naći gotove procedure.



[Ovu poruku je menjao Cybernoid II dana 27.11.2003. u 04:16 GMT]

pa što nereče odma tako ;)

znači, za tih 400 tačaka, bilo koji algoritam koji ti padne na pamet će završiti za 2 sekunde (a i dalje je onaj moj predlog najlakši ;)

Ako poligon predstaviš kao nadovezane vektore u smeru ubrnutom od kazaljke na satu u prvom kvadrantu negativno orjentisani su oni vektori koji idu nagore ulevo i analogno tome.