Triangularea Delaunay paralelă

Triangularea unei mulțimi de puncte este o problemă foarte bine cunoscută și utilizată în multe domenii de cercetare științifică dar și în industria de divertisment (scanare 3D, algoritmi de găsire a căii optime în jocuri, etc). Putem rezuma problema triangulării unei mulțimi de puncte P în plan în găsirea unei organizări DT(P) astfel încât să nu existe niciun punct din P în cercul circumscris oricărui triunghi din DT(P). Triangularea Delauney este cea mai populară deoarece maximizează unghiul minim al tuturor triunghiurilor. Această triangulare este denumită după Boris Delaunay pentru munca depusa pe acest subiect din anul 1934.
Algoritmul Delaunay produce triunghiuri aproape echiunghiulare și poate fi calculat utilizând o complexitate de $O(nlog(n))$ (pentru cazul cel mai rău), unde n este numărul de puncte din mulțime.

Datorită popularității acestui algoritm, s-au încercat mai multe soluții paralele sau distribuite cu scopul de a mări viteza de triangulare. Versiunea paralelă cea mai întâlnită de triangulare Delauney este bazată pe metoda Divide et impera și apare în mod natural: problema este împărțită recursiv în subprobleme care apoi sunt rezolvate. Triangularea finală se obține unind toate rezultatele.
Problema esențială a acestei metode este că valorile de intrare devin din ce în ce mai mici la fiecare iterație și din acest motiv procesoarelor nu li se repartizează munca egal. Rezultatele practice sunt destul de slabe.^[1]

Triangularea Delaunay incrementală

O triangulare T(P) a unei mulțimi de puncte P în spațiul Euclidian este o mulțime de arce E astfel încât:

Nu există 2 arce care se intersectează într-un punct care nu este în P
Arcele din E împart anvelopa convexă a lui P în triunghiuri

Triangularea $DT(P)$ a unei mulțimi de puncte P din plan este de tip Delaunay dacă și numai dacă centrul circumscris oricărui triunghi din $DT(P)$ nu conține alt punct din P în interior.

Deși algoritmul de inserție incrementală pentru triangularea Delaunay are complexitatea $O(n^{2})$ în cazul cel mai rău și $O(nlog(n))$ în cazul cel mai des întâlnit, este foarte popular datorită simplității și robusteții. Punctele pot sa vină în orice moment al rulării aplicației și nu trebuie sa fie cunoscute de la început numărul lor fiindcă sunt înserate câte unul pe rând. Însa trebuie să se cunoască de la început intervalele coordonatelor. De asemenea permite modificări în vederea obținerii triangulării cu constrângeri pentru metrici neeuclidiene sau pentru triangulări tridimesionale.

Algoritmul începe cu crearea unei anvelope convexe sau crearea unui triunghi temporar ce cuprinde toate punctele înserate. A doua posibilitate pare sa fie mai bună fiindcă prima construcție adaugă nevoia de diferențiere a triunghiurilor de pe primul nivel în algoritmul de locație. Însă, folosirea triunghiului de început nu vine fără probleme. Acest triunghi temporar trebui scos la sfârșit și o alta problema este cum să alegem vârfurile lui. Poziția recomandată este (k,0), (0,k) și (-k,-k) unde K = 3 * mărimea cutiei învelitoare.
Pentru a insera un punct $p_{r}$ , trebuie localizat rapid triunghiul cu vârfurile $p_{u}$ , $p_{j}$ și $p_{k}$ care conține punctul inserat. Acest triunghi se subdivide în alte 3 noi triunghiuri dacă punctul cade în triunghi și în 2 triunghiuri dacă acesta este pe un arc. În al doilea caz vecinul este împărțit cum apare în figura

Însa după subdiviziune, unele triunghiuri care nu satisfac testul cercului circumscris, pot exista, în acest caz arcul greșit dintre doua triunghiuri este întors. Aceasta întoarcere poate face un alt triunghi sa nu satisfacă testul. Întoarcerea trebuie aplicată în mod repetat (este propagată în valuri până toate triunghiurile sunt corecte). Acest lucru înseamnă că inserția unui punct poate schimba toată triangularea.

Problema de bază este cum se poate găsi într-un mod eficient triunghiul care conține punctul. O posibilitate este să se folosească graful aciclic direcționat. Un graf aciclic direcționat este un arbore cu istoria inserțiilor. Fiecare nod din graf corespunde unui triunghi. Triunghiul curent valid este astfel în Frunze si cel mare de început este radacina. Localizarea punctului de inserție în aceasta structura de date poate fi făcută cu o complexitate de $O(log(n))$ , cazul des întâlnit și $O(n)$ cazul cel mai rău. Dacă ordinea inserțiilor este aleatoare, arborele este aproape balansat și probabilitatea cazului cel mai rău scade.^[2]

Algoritmul triangulării aleatoare de tip Delauney incremental

Început
1. Inițializează triunghiul mare
2. Calculează permutație aleatoare a punctelor $p_{0}$ , $p_{1}$ …. $p_{(}n-1)$ din mulțimea P
3. Pentru r = 0 pana la n-1 // incepe inserția
  1. Localizează triunghiul $p_{i}$ $p_{j}$ $p_{k}$ aparținând lui DT(P) care conține $p_{r}$
  2. Dacă $p_{r}$ aparține interiorului $p_{i}$ $p_{j}$ $p_{k}$
    1. Adaugă arc de la $p_{r}$ la $p_{i}$ , $p_{j}$ , $p_{k}$ si subdivide $p_{i}$ $p_{j}$ $p_{k}$ in 3 triunghiuri
  3. Altfel
    1. Adaugă arc de la $p_{r}$ la $p_{j}$ și de la $p_{r}$ la $p_{1}$ , al treilea punct de la celalalt triunghi cu care se împarte $p_{i}p_{k}$ si subdivizează 2 triunghiuri care împart $p_{i}p_{k}$ în patru triunghiuri
    2. Legalizează triangularea (întorcând arcurile)
  4. Încheiere
  5. Ștergerea tuturor triunghiurilor care conțin puncte din triunghiul mare
Încheiere

Paralelizare

Paralelizarea procesului de triangulare Delaunay nu este ușoară deoarece fiecare punct poate influenta drastic toată structura. Fie o arhitectura cu mai multe procesoare și o memorie partajată. Calculele vor fi partiționate între mai multe thread-uri. Un thread va funcționa de obicei pe un singur procesor. (Este posibil să pornească mai mult de un singur thread pe un procesor dar asta nu va îmbunătăți viteza). Deoarece fiecare thread funcționează pe aceeași structura de graf aciclic direcționat, trebuie implementată sincronizarea pe acesta. Sunt 3 metode prin care se poate sincroniza:

Batch
Pesimistă
Optimistă

Metoda Batch

Se poate modifica algoritmul serial după cum urmează: fie mai multe thread-uri care localizează triunghiul în structura grafului care conțin punctul de intrare. Subdivizarea și legalizarea poate fi făcută de un thread specializat care primește un punct de intrare și un triunghi de la care se începe căutarea. Problema de baza este asigurarea comunicării între thread-ul specializat și cel de căutare. Aceasta poate fi rezolvată prin folosirea cozilor în memoria partajată. Dacă aceasta coada este goala thread-ul specializat trebuie sa aștepte. Întrebarea este cât de mare trebuie sa fie coada pentru a evita blocarea thread-urilor de căutare. Pe acest și sistem localizarea trebuie sa dureze mult mai mult decât subdivizarea și legalizarea deoarece în caz contrar, coada se va umple și performanta se va diminua. Din aceste motive, algoritmul Batch nu prea se implementează.^[3]^[4]

Metoda pesimistă

Concluzia măsurătorilor algoritmului serial este aceea ca partea de localizare consuma în jur de 60 % din timpul total necesar construirii triangulării.

Deși nu este suficient pentru metoda de batch, acest procent este suficient pentru cea pesimistă. Metoda pesimistă este o modificare a metodei batch. Nu exista thread specializat; toate thread-urile fac aceleași instrucțiuni. Atât timp cât sunt mai multe thread-uri care pot citi graful simultan, doar unul îl poate modifica. Thread-urile localizează ultimul triunghi părinte care conține punctual (citire) apoi intra într-o secțiune critica, termina localizarea, subdivide și legalizează (scriere) ieșind din secțiunea critica.

Fiecare nod din Graful aciclic include un marcator care marchează nodul ca în figură. Frunzele din graf sunt numite copii. Nodurile normale sunt noduri în care toți copiii lor nu sunt frunze. Nodurile ramase sunt marcate printr-o combinație de litere L, M și R. Litera L înseamna ca primul copil este frunză (nodul este ultimul părinte din stânga). Litera M înseamna că al doilea copil este frunză (ultimul părinte din mijloc) și în final litera R înseamnă că al treilea copil este frunză (ultimul părinte din dreapta).

Localizarea poate continua doar pe noduri normale, de exemplu în nodul MR se poate testa triunghiul din stânga copilului, dar testarea triunghiurilor din mijloc sau dreapta poate fi făcuta doar în secțiunea critică (acestea sunt testate doar dacă punctul nu se afla în triunghiul din stânga)

Structura arborelui în algoritmul Delaunay paralel

Metoda pesimista este simplă dar aduce un plus mic de viteză datorită secțiunii critice.

Thread principal

Input: O mulțime de puncte P = { $p_{i}$ , I = 0,1,2… n-1} de n puncte în plan
Output: O triangulare Delaunay a lui P DT(P)

Început
1. Inițializează triunghiul mare
2. Calculează o permutare random a lui $(p_{0})$ , $(p_{1})$ … $(p_{n-1})$ din P
3. Subdivide P în m submulțimi, m este numărul de thread-uri
4. Pornește toate thread-urile și așteaptă până la finalizare
5. Șterge toate thread-urile care conțin puncte din triunghiul mare
Sfârșit

Thread Secundar

Input: O mulțime de puncte Pt = { $(p_{i})$ , i= 0,1…n(m -1)} din planul Pt inclus în P
Output: Modifica DT(P)

Începe
Pentru r = 0 pana la $n(m-1)$ // inserează $p_{r}$ în DT(p)
1. Începe localizarea în arborele aciclic direcționat pe nivelul frunzelor părinților ce conțin $pr$
2. Dacă mai există vreun thread care lucrează cu frunze, se așteaptă
3. Se intrăm în secțiunea critică
  1. Se termină localizarea la nivelul frunzelor pentru triunghiul $p_{i}p_{j}p_{k}$ din DT(P) ce conține $p_{r}$
  2. Se subdivide și se caută triunghiuri noi
4. Ieșire din secțiunea critică
Sfârșit

Metoda Optimistă

Deși întoarcerile pot schimba toată triangularea, întoarcerea se poate face și local. Nu este nevoie sa se blocheze toate frunzele grafului aciclic direcționat pentru un singur thread. Se lasă toate thread-urile sa facă localizarea, subdivizarea și legalizarea. Desigur ca trebuie să se asigure o sincronizare între toate thread-urile. Localizarea este aceeași cu cea din metoda pesimistă. În nodul din graf se mai adaugă un marcator care spune ce thread blochează accesul la triunghi acesta este necesar pentru subdiviziune și legalizare. Thread-ul secundar blochează toate triunghiurile care sunt accesate și după ce punctul de intrare este inserat, toate triunghiurile blocate sunt deblocate. Dacă alt thread a blocat deja triunghiul, thread-ul curent trebuie să aștepte până se deblochează.

Exista o posibiltate de apariție a deadlock-urilor cauzate de așteptări simultane a thread-urilor. Aceasta problema se poate rezolva printr-un sistem de detecție a deadlock-urilor (thread-ul care detectează deadlock-ul se întoarce la partea de localizare și renunța la inserție pentru moment) sau prin prioritizarea thread-urilor (thread-ul nu este pus în așteptare pentru altul cu prioritate mai mare). Ambele posibilități conduc la utilizarea tranzacțiilor. Deoarece există slabe șanse de deadlock-uri folosirea tranzacțiilor limitează îmbunătățirea vitezei.

Se poate evita folosirea tranzacțiilor printr-o variație a metodei optimiste numita metoda hoțului optimist. Aceasta metodă este ușor de înțeles: fiecare triunghi din obiect poate fi asociat cu un lucru. Fiecare lucru (Televizor, scaun, pat) are un proprietar (thread-ul). Lucrurile sunt stocate într-o casa care este a thread-ului (proprietarului). Fie ca toate lucrurile deținute de un thread să fie în casa acestuia. Planul este divizat în mai multe arii (case). Dacă un thread modifică triunghiuri doar din casa lui nu este nevoie să se folosească tranzacții sau să se blocheze triunghiuri. Însa câteodată thread-ul trebuie să între în casa deținută de vecin. Din acest motiv trebuie să sune la ușa și să aștepte să se deschidă. Vecinul deschide ușa când și-a terminat treaba și din acest moment invitatul și gazda trebuie să blocheze triunghiurile.

Soluția nu este sigură din punct de vedere a deadlock-urilor deoarece este posibil ca 2 sau mai multe thread-uri să sune la ușă și să se aștepte. Situația aceasta se poate trata prin forțarea ușii (thread-ul care detectează problema intra și își face treaba) Când proprietarul casei realizează acesta trebuie să verifice la fiecare val de întoarceri că este permis să se schimbe obiectul fiindcă hoțul ar fi putut sa modifice triunghiuri neprocesate. Daca thread-ul nu poate continua în niciun val, contorul-ul de probleme potențiale este incrementat. Fiindcă știm fiecare triunghi care a fost produs de hoț, acestea pot fi marcate ca fiind greșite și corectate la sfârșitul calculelor.

Thread secundar

Input: O mulțime de puncte Pt = { $p_{i}$ , I = 0,1, $n_{m}-1$ } din $n_{m}$ puncte din plan Pt inclus in P
Output: Se modifică DT(P)

Început
1. Pentru r = 0 pana la $n_{m}-1$ // se inserează punctual pr in DT(p)
  1. Se localizează în graf triunghiul $p_{i}p_{j}p_{k}$ care conține $p_{r}$
  2. Cat timp triunghiul subdivizat și toți vecinii sunt blocați de cineva, se așteaptă;
  3. Se blocează triunghiul $p_{i}$ $p_{j}$ $p_{k}$ și toți vecinii
  4. Cât timp triunghiurile legalizate și vecinii sunt blocați/blocate de cineva sa așteaptă;
  5. Se blochează triunghiurile legalizate și vecinii
  6. Se legalizează
  7. Se deblochează toate triunghiurile blocate de acest thread
  8. Se reiau toate thread-urile care așteaptă după acesta;
2. Sfârșit
Sfârșit

Partiționarea mulțimii de puncte

Sunt doua metoda mari de partiționare a mulțimii de puncte în m submulțimi de intrare pentru celelalte thread-uri:

Mulțimea de intrare este împărțită statistic. Acest lucru înseamnă că fiecare thread primește o parte din mulțime. Este o problemă în această partiționare fiindcă ultimul thread primește mai puțin decât celelalte.
Mulțimea de intrare nu este împărțită statistic dar fiecare thread înserează primul punct neinserat referit de un pointer global care este mărit în mod atomic. Aceasta se numește încărcătură dinamică.

Note

^ Parallel Delaunay Triangulation, old.cescg.org
^ http://www.cse.unsw.edu.au/~lambert/java/3d/delaunay.html
^ Triangulation Algorithms and Data Structures, www.cs.cmu.edu
^ Polygon Triangulation, www.cs.unc.edu

Bibliografie

Blelloch, G.E., Miller, G.L., Talmor, D.: Developing a Practical projection-Based Parallel Delaunay algorithm, Proc of the 12th Annual Symposium on Comput. Geometry, ACM, 1996
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry. Algorithms and Applications, Springer-Verlag Berlin Heidelberg, 1997
Guibas, L.J., Knuth, D.E., Sharir, M.: Randomized Incremental Construction of Delaunay and Voronoi Diagrams. Algorithmica (7), pp. 381–413, 1992
Hardwick, J.C.: Implementation and Evaluation of an Efficient Parallel Delaunay Triangulation Algorithm, 9th Annual Symposium on Parallel Algorithm and Architectures, pp. 22–25, 1997
Kolingerová, I., Kohout, J.: Pessimistic Threaded Delaunay Triangulation, GraphiCon'2000, pp. 76–83, 2000
Vigo, M.: An Improved Incremental Algorithm for Constructing Restricted Delaunay Triangulations, Computers & Graphics 21, pp. 215–223, 1997

[1] Parallel Delaunay Triangulation, old.cescg.org

[2] ttp://www.cse.unsw.edu.au/~lambert/java/3d/delaunay.html

[3] Triangulation Algorithms and Data Structures, www.cs.cmu.edu

[4] Polygon Triangulation, www.cs.unc.edu

[1]

[2]

[3]

[4]