Teorema Axei de Separare [SAT]

SAT este o teorema utila pentru programatorii de jocuri, folosindu-se in detectarea ciocnirilor dintre doua poligoane convexe.
Ea afirma ca pentru doua polygoane, daca exista o "axa" astfel incat proiectiile lor pe acea axa nu se suprapun, atunci poligoanele nu se intersecteaza.
Aici, cuvantul "axa" se refera la un vector normalizat(de modul 1). Cunoastem deja vectorii standard din geometria vectoriala : (1,0) adica directia pozitiva a axei OX  si (0,1) directia pozitiva a axei OY.
Punctele de pozitie p1(x1,y1) , p2(x2,y2),.....,pN(xN,yN) pot fi considerate de fapt vectori cu originea in O(0,0). Deci am avea  vectorii v1[ O(0,0) , p1(x1,y1)], s.a.m.d;
Sigur, exista si vectori cu originea in alte puncte, cum ar vi [(2,2), (5,6)]. Pentru a-l obtine pe cel "legat" in origine, nu facem decat sa scadem din coordonatele celui de-al doilea punct pe cele ale primului punct.
Deci pentru exemplu, am avea (5,6)-(2,2)=(3,4), sau [ (0,0) , (3,4)].
Oricum, cei doi vectori sunt egali, in sensul ca au aceeasi directie, acelasi sens si acelasi modul.
Spunem ca sunt "echipolenti".
   1)Proiectia unui obiect geometric pe o dreapta.
Ce este o proiectie? Imaginati-va ca este umbra lasata de acea figura geometrica pe dreapta, cand o sursa de lumina perpendiculara pe directia dreptei se afla in spatele obiectului geometric.
Umbra unui punct pe o dreapta este tot un punct.
Umbra oricarei figuri geometrice pe o dreapta este un segment(deci triungiul,patratul,hexagonul,etc.. toate au drept umbra un segment).
Sa zicem ca avem in sistemul Oxy un patrat cu varfurile (4,4)--(8,4)---(8,1)---(4,1).
Atunci proiectia lui pe Ox sau, mai bine zis, pe vectorul-axa (1,0) este segmentul cu extremitatile in [4,8].
Sau punctul P(5,6). Proiectia lui pe vectorul (1,0) este in punctul 5 de pe axa. Cum am aflat asta?
Facand produsul scalar desigur : 5*1 + 6*0 = 5.
Proiectia pe o axa (adica pe un vector normalizat) a unui punct se afla efectuand produsul scalar dintre punct si acel vector. Proiectia este o coordonata intr-o singura dimensiune, sau numarul de unitati cu care te deplasezi de la originea axei ca sa ajungi unde esti.
Deci daca avem doua proiectii p1(min,max) si p2(min,max) de-a lungul unei axe, putem afla folosind diverse formule daca ele se suprapun sau nu.
Cum afli segmentul de proiectie al unui polygon cu numar de varfuri n>=2 de-a lungul unei axe?
-Pentru aceasta trebuie efectuat produsul scalar dintre fiecare punct al poligonului si vectorul axa.
   -Apoi, trebuie tinute minte valorile extreme : minimul si maximul. Segmentul de proiectie este deci p(minim,maxim);
  Avem poligonul cu punctele in (4,4)--(8,4)---(8,1)---(4,1) si axa Ox adica vectorul (1,0).
Daca desenezi pe foaie, se observa cu ochiul liber ca segmentul de proiecte este [4,8].
Hai sa vedem cum face calculatorul asta:
   (4,4) * (1,0)=4
   (8,4)* (1,0) = 8
   (8,1) * (1,0)=8
   (4,1) *(1,0)=4.
Se pastreaza minimul si maximul, se creeaza o structura de tip proiecte in care se memoreaza acestea si apoi gata.
Binenteles, Ox pozitiva este doar un exemplu. Putem avea o alta axa, cum ar fi v2(1,1) sau v3(0.5,0.86). Ideea e sa fie vectori normali, adica de modul ~1.
   2)Perpendiculara unei axe
Avem un vector v(x,y). Pentru a obtine un vector perpendicular pe acesta, pur si simplu interschimbam coordonatele si schimbam semnul uneia dintre acestea.
Pentru (1,0) adica directia pozitiva Ox avem vectorii (0,1) si (0,-1).
Deci pentru v(x,y) avem v_perp(v.y,-v.x) sau v_perp=(-v.y,v.x) .
Daca avem un polygon cu N varfuri, putem afla perpendiculara fiecariei laturi astfel:
  

			 pentru i=0,N-1,i=i+1
			 x=punct[i].x-punct[i+1].x;
			 y=punct[i].y-punct[i+1].y;
			
			 vector_2D axis,perp_axis;
			 axis=(x,y);
			 normalize(axis);
			 perp_axis(axis.y,-axis.x)
			
			 //Prelucreaza perp_axis

De fapt, am considerat fiecare latura a acestuia ca vector, de la punct[i], la punct[i+1]. Evident, un poligon se memoreaza sub forma unui tablou de puncte, in caz ca nu v-ati dat seama.
  3)Algoritmul de detectare a ciocnirilor folosind SAT
  Ideea este urmatoarea: Noi,pe foaie, daca putem trage o dreapta care separa cele doua poligoane convexe, e clar ca ele nu se intersecteaza (ceea ce se vede si cu ochiul liber).
Pe acest principiu se bazeaza SAT. Dreapta pe care am trasat-o noi este de fapt axa de separare dintre cele doua poligoane. Evident, in calculator aceasta este memorata sub forma unui vector, axis(x,y).
  Sa zicem ca avem o lista de axe posibile, pe acre putem sa le testam.
Atunci, algoritmul e simplu:

pentru fiecare axa din lista
		 proiecteaza primul poligon pe axa si determina segmentul in S1(min,max);
		 fa la fel cu al doilea si salveaza segmentul in S2(min,max);
		 daca S1 si S2 NU se suprapun
			 Aceasta e axa de separare.Nu mai are rost sa cautam mai incolo, deci iesi fortat.

-daca s-a ajuns pana in punctul acesta, inseamna ca poligoanele se intersecteaza.
De aici depinde de programator ce se intampla cu ele. Ar putea fi impinse inapoi, distruse, etc...

   Cum obtin lista de axe posibile pe care sa le testez?
   Lista e formata din normalele laturilor primului poligon + normalele laturilor celui de-al doilea. Am scris mai sus cum se determina acestea.

4)Vectorul de translatie minima
Avem doua poligoane convexe : un patrat si un triunghi. Intr-un joc, modelez patratul ca fiind jucatorul si triunghiul ca fiind terenul pe care acesta sta.
Deci patratul se misca stanga, dreapta, etc... iar triunghiul sta nemiscat.
Daca jucatorul intra "prea adanc" in triunghi, altfel spus patratul si triungiul se intersecteaza, atunci jucatorul trebuie "impins" inapoi dar atat cat sa atinga marginile triunghiului.
  Pentru aceasta, avem nevoie de vectorul de translatie minima. Practic, il vom aduna la fiecare punct al patratului (pentru ca pe el vrem sa il impingem inapoi).
Vectorul MTV nu este decat axa pe care avem cea mai mica suprapunere dintre S1 si S2.
Atunci, algoritmul devine :

	 suprapunere=10000000000;
pentru fiecare axa din lista
		 proiecteaza primul poligon pe axa si determina segmentul in S1(min,max);
		 fa la fel cu al doilea si salveaza segmentul in S2(min,max);
		 daca S1 si S2 NU se suprapun
			 Aceasta e axa de separare.Nu mai are rost sa cautam mai incolo, deci iesi fortat.
		 altfel
				 daca suprapunerea dintre S1 si S2 este < suprapunere
						 { suprapunere = suprapunerea dintre S1 si S2
							 MTV= axa curenta;
						 }

-daca s-a ajuns pana in punctul acesta, inseamna ca poligoanele se intersecteaza.
De aici depinde de programator ce se intampla cu ele. Ar putea fi impinse inapoi, distruse, etc...
	 ///"suprapunere" este un scalar.
	 MTV= MTV * suprapunere
	 return MTV;

Inca ceva. Sensul axei s-ar putea sa fie gresit, si vectorul sa-l impinga de fapt mai tare in triunghi. Atunci MTV trebuie inmultit cu -1.
Ca sa ne dam seama, avem nevoie de vectorul de la centroidul triunghiului la centroidul patratului, sa-l denumim ctd;
Daca unghiul dintre MTV si CTD este mai mare de de 90 de grade, adica produsul lor scalar e negativ, atunci MTV trebuie negat.

Ca sa vedeti algoritmul in actiune, am scris un program in C++ folosind SDL pentru desenarea formelor geometrice.
  Puteti desena pe ecran orice poligon, dand click pe mouse in locul unde vor fi varfurile sale. Pe masura ce sunt create varfurile, sunt desenate automat laturile dintre ele.
Pentru a finaliza constructia, apasati ori B ori E:
  --- B : atunci forma pe care o miscati, folosind sagetile, va deveni noua figura
----E : atunci figura devine una statica.
Ca sa vedeti linia ce uneste centroidele dintre figura voastra si celelalte, apasati S. Ca sa vedeti MTV apasati M. Acesta devine mai vizibil daca opriti/ porniti detectarea ciocnirilor apasand C.
Si, ca sa rotiti figura pe care o controlati, tineti apasat R.
http://www.mediafire...for_bitcell.zip


Pentru mai multe informatii, vedeti si http://www.codezealot.org/archives/55

Edited by pale_and_pale, 11 July 2013 - 01:39.

Pacat ca nu se mai face nimic in 2D zilele astea...

Cum sa nu, n-ai auzit de Angry Birds sau Fruit Ninja ?

Edited by pale_and_pale, 11 July 2013 - 08:24.

JayBird, on 11 iulie 2013 - 04:08, said:

Multe probleme au o interpretare geometrică.

Felicitari pentru primul articol (de aici).
Pentru a face articolul mai usor de urmarit si a-i da un aspect mai profesional, iti recomand sa folosesti http://forum.softped...latex-math-ide/ pentru a scrie formulele, urmand ca apoi sa le introduci in post sub forma de poze (cu fundal transparent).