redzamības noteikšana

Viss par 2D un 3D grafikas programmēšanu
Post Reply
Message
Author
User avatar
kristapuciitis
Posts: 163
Joined: 03 Jun 2011, 14:22

redzamības noteikšana

#1 Post by kristapuciitis » 13 Jul 2011, 16:54

Sveiki!
Vajag palīdzību! Es nezinu, kā noteikt, vai kāds noteikts objekts ir redzams, ja ir dotas tavas atrašanās vietas koordinātas (punkts) (x, y), šķēršļu stūru koordinātas (x, y), caur kuriem nevar redzēt, un objekta stūru koordinātes (x, y). Vai kāds var palīdzēt?
Gooby pls

bubu
Guru
Guru
Posts: 398
Joined: 07 Dec 2010, 11:54

Re: redzamības noteikšana

#2 Post by bubu » 13 Jul 2011, 17:02

Tur ir visvisādi varianti.

Vienkāršotā gadījumā, ja tev karte ir kā rūtiņas, tad var vilkt staru no savas pozīcijas uz mērķi, un skatīties, vai stars krusto sienu, vai nē. Ja nekrusto, un staru var aizvilkt līdz tavam objektam, tad tas nozīmē, ka objekts ir redzams.
Efektīvi to var darīt ar raycasting'u kā darīja Wolfenstein 3D:
http://www.permadi.com/tutorial/raycast/
Nevajag sabīties no 3D. Pats algoritms darbojas divās dimensijās. Wolfenstein 3D iegūto rezultātu izmantoja, lai renderētu 3D telpu.
Visa sāls ir Figure 14 bildē. Raycastings pēc būtības ir Bresanhēma līnijas zīmēšanas algoritms (rūtiņu apstaigšana, velkot līniju aiz sevis - tb tavā gadījumā stars no acs līdz objektam): http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Šeit kautkāds piemērs, kas sadursmes ar šķēršļiem meklē pikseļu līmenī (būs ļoti neefektīvi un dārgi, ja liela karte): http://www.codeproject.com/KB/GDI-plus/ ... ing2D.aspx Šo vispārinot - pārtaisot pikseļus par lielākām rūtiņām - dabūsi augstāk minēto Wolfenstein 3d stila raycasting'u. W3D katra rūtiņa, caurstaigājama vai necaurstaigājama, bija viens bloks - sienas klucītis, durvis, galds, utml.

Ja karte nav pa rūtiņām, un šķēršļi var būt patvaļīgi, tad ir sarežģītāk. Vienkāršākais variants būtu izmantot kādu 2d fizikas bibliotēku, kas tev kolīzijas pati sameklēs. Domāju, ka Box2D vai Chipmunk to vajadzētu mācēt.
Ja gribi pats rakstīt, tad vajadzēs ņemt palīgā ģeometriju un mācēt atrast taisnes/nogriežņa krustpuntu ar tavu šķēršļu objekta formām (kvadrāti/sfēras/nogriežņi/utt). Un lai to visu darītu efektīvāk nāksies izmantot kādu telpas dalīšanas algoritmu pa daļām. Tur visādi BSP, QuadTree, utml.

snake5
Posts: 361
Joined: 07 Dec 2010, 03:54
Contact:

Re: redzamības noteikšana

#3 Post by snake5 » 13 Jul 2011, 18:47

Vienkāršākais variants ir salasīties stara-objektu sadursmes kodus un ciklā testēt visus. Sarežģītākais būtu pateikt, ar kādiem tieši objektiem ir darīšana. Tile-based līmeņiem jāmeklē vokseļu apstaigāšanas algoritms. Tas līniju zīmēšanas algoritms šādam uzdevumam (tile-based līmeņiem) galīgi neder, jo tiek palaisti garām stūri. Ar pikseļiem gan būs OK.

bubu
Guru
Guru
Posts: 398
Joined: 07 Dec 2010, 11:54

Re: redzamības noteikšana

#4 Post by bubu » 13 Jul 2011, 19:05

snake5 wrote:Tas līniju zīmēšanas algoritms šādam uzdevumam (tile-based līmeņiem) galīgi neder, jo tiek palaisti garām stūri.
Labrīt. Kā nu neder, ka der. Robežgadījumu gadījumā < pamaini uz <= (vai > uz >=) un būs tev tie stūri. Un brezahēma algoritmu vienmēr var uzrakstīt 8-way-adjacency pikseļiem, ne tikai 4-way ja tu to domāji ar "stūrus palaidīs garām": http://lifc.univ-fcomte.fr/~dedu/projec ... index.html

Un vokseļi vispār jau ir 3d objekti. 2d gadījumā tavu "vokseļu" apstaigāšanu sauc par raycasting'u.

snake5
Posts: 361
Joined: 07 Dec 2010, 03:54
Contact:

Re: redzamības noteikšana

#5 Post by snake5 » 13 Jul 2011, 23:02

Ir jēga spiest kaut ko ārā no viena algoritma, ja ir cits, kurš visu perfekti izdara?
2d gadījumā tavu "vokseļu" apstaigāšanu sauc par raycasting'u.
Raycasting tas ir neatkarīgi no dimensiju skaita. Un voxel/grid traversal algoritmi atšķiras tikai ar vienu asi (dažas koda līnijas), darbības principi ir tieši tie paši.

bubu
Guru
Guru
Posts: 398
Joined: 07 Dec 2010, 11:54

Re: redzamības noteikšana

#6 Post by bubu » 14 Jul 2011, 00:17

snake5 wrote:Ir jēga spiest kaut ko ārā no viena algoritma, ja ir cits, kurš visu perfekti izdara?
Tieši tā - brezanhēma algoritums visu perfekti izdara :)

snake5
Posts: 361
Joined: 07 Dec 2010, 03:54
Contact:

Re: redzamības noteikšana

#7 Post by snake5 » 14 Jul 2011, 10:36

Neizdara perfekti: http://imageshack.us/photo/my-images/19 ... rvrsl.png/ (bilde no wikipēdijas SVG, nedaudz uzlabota). Wikipēdijai gan pārāk ideāls tas attēls (kad es testēju, gļukoja daudz biežāk), bet problēmas var atrast anyway.
Sarkanie laukumi tiek palaisti garām. Un tajā modifikācijā pārāk daudz laukumus sīkāk testētu.

bubu
Guru
Guru
Posts: 398
Joined: 07 Dec 2010, 11:54

Re: redzamības noteikšana

#8 Post by bubu » 14 Jul 2011, 10:41

Tu linkus, kurus es dodu neskaties? http://lifc.univ-fcomte.fr/~dedu/projec ... index.html

snake5
Posts: 361
Joined: 07 Dec 2010, 03:54
Contact:

Re: redzamības noteikšana

#9 Post by snake5 » 14 Jul 2011, 14:33

Es apskatījos. Atbilde uz to:
Un tajā modifikācijā pārāk daudz laukumus sīkāk testētu.
Es arī nedaudz apšaubu iespēju noteikt secību/sadursmes punktu/normālvektoru tādā veidā.

Post Reply

Return to “Grafikas programmēšana un teorija / Graphics programming and theory”