Share
Tăiere este procesul de a determina ce regiune a spațiului se află într-o altă regiune a spațiului. Acest lucru este deosebit de important în domenii de studiu, cum ar fi grafica computerizată și simulare fizică. De exemplu, atunci când redați o lume pe ecran, este mai bine să știți ce va apărea pe ecran înainte de a procesa orice date. Acest lucru permite ignorarea o mulțime de date străine, în timp ce numai prelucrarea și prezentarea a ceea ce va fi văzut de utilizator.
În simularea fizică, sunt adesea găsite corpuri rigide întrepătrunsă - adică se suprapun două obiecte separate. Asta e rău. Interpenetrarea este ceva ce nu se întâmplă niciodată în lumea reală, dar este o problemă care trebuie abordată în detectarea coliziunilor. Deseori, o formă este tăiată împotriva alteia pentru a determina ce caracteristici ating de fapt. De aici poate fi inițiat un răspuns de coliziune.
Caracteristicile avansate ale motoarelor de joc pot fi implementate cu o formă de tăiere; simularea flotabilității, planurile de vizualizare a camerei; fracturarea fragilă, generarea de contacte cu testul axei de separare; toate aceste lucruri (și multe altele) pot fi realizate cu algoritmi de tăiere. De fapt, tăierea de genul asta a fost necesară în tutorialul meu anterior privind construirea unui motor fizic rigid al corpului.
Acest articol necesită unii aveți o înțelegere decentă a:
Domeniile de studiu de mai sus pot fi învățate dintr-o mare varietate de resurse pe internet (cum ar fi ghidul Wolfire pentru algebra liniară sau Academia Khan - și nu sunt prea greu de învățat!
Multe rutine complexe de tăiere implică utilizarea unui singur tip de operațiune: împărțirea unei forme cu un singur plan. Împărțirea unei forme cu un plan implică preluarea unei forme și tăierea în două bucăți printr-un plan solid.
Este important să ne dăm seama că împărțirea unei forme cu un plan este un instrument fundamental în această rutină de tăiere.
Vedeți animațiile excelente ale lui Davide Cervone pentru o demonstrație clară a acestui lucru:
Sutherland Hodgman clipping este rutina mea preferată de tăiere, deoarece funcționează pentru tăierea liniilor de linie împotriva avioanelor. Cu acest algoritm, având în vedere o listă de vârfuri de intrare și o listă de planuri, poate fi calculată o ieșire de noi noduri care există doar în setul de planuri.
Planul termen poate fi folosit pentru a se referi la ambele planuri în 3D și 2D. Un plan 2D poate fi, de asemenea, numit a linia.Ne putem imagina lista de vârfuri ca un singur poligon. Ne putem imagina (deocamdată) lista avioanelor ca o singură linie. Vizualizarea acestui aspect în două dimensiuni ar putea să arate după cum urmează:
Cu tăierea lui Sutherland Hodgman, poligonul din dreapta este forma dorită, în timp ce poligonul roșu din stânga este forma de intrare și nu trebuie tăiat încă. Linia albastră reprezintă un plan de divizare în două dimensiuni. Se poate utiliza orice număr de planuri de despicare; în exemplul de mai sus este folosit doar un singur plan de despicare. Dacă se folosesc mai multe planuri de despicare, atunci tăierea va avea loc într-un avion în timp, tăind din ce în ce mai mult o formă originală pentru a scoate un nou plan:
Pentru simplificare, să lucrăm în două dimensiuni stricte. Când divizați un poligon în raport cu un plan, va fi important să știți care parte a planului este pe orice punct dat.
Mai sus este cel mai frecvent utilizat mod de a găsi distanța de la un punct la un avion. Rețineți că simbolul punct din ecuația de mai sus reprezintă produsul dot.
Distanța nu trebuie calculată în mod explicit; vectorul normal n nu trebuie să fie normalizată (adică nu trebuie să aibă o lungime de exact o unitate). Tot ceea ce trebuie verificat este semnul rezultatului distanței d. Dacă n nu este normalizată atunci d va fi în unități de lungime de n. Dacă n este normalizat, atunci d va fi în unități echivalente cu unitățile spațiale mondiale. Acest lucru este important pentru a realiza, deoarece permite efectuarea calculului pentru a vedea dacă d este pozitiv sau negativ. Pozitiv d indică faptul că acest punct p este pe partea din față a avionului. Negativ înseamnă că e pe partea din spate.
Acum, ce anume înțelegem prin laturile "din față" și "din spate" ale unui avion? Ei bine, depinde de ceea ce definiți în față și înapoi ca. De obicei, "față" înseamnă că este pe aceeași parte a planului cu cel normal.
Permiteți scufundarea direct în algoritm. Faceți o scanare rapidă asupra pseudocodului:
Polygon SutherlandHodgman (const Poligonul de pornirePolygon, Plane [] clippingPlanes) ieșire poligon = startPolygon pentru fiecare planetă clippingPlane în clippingPlanes input = ieșire output.Clear () Vec2 startingPoint = input.Last () pentru fiecare Vec2 endPoint în intrare dacă beginPoint și endpoint în fata de clippingPlane out.push (endPoint) altceva daca startPoint in fata si endPoint in spatele clippingPlane out.push (intersectie (clippingPlane, startPoint, endpoint) altfel daca startPoint si endPoint in spatele clippingPlane out.push (intersectie (clippingPlane, startPoint, endpoint) ) out.push (endPoint) endPoint = ieșire de întoarcere StartPoint
Algoritmul ia un poligon de intrare și unele planuri de tăiere și emite un poligon nou. Ideea este de a clipi fiecare segment de linie al poligonului de intrare față de un plan de tăiere la un moment dat. Această imagine din Wikimedia Commons demonstrează acest lucru destul de bine:
Fiecare operație de tăiere are doar câteva cazuri diferite în care se generează noduri și poate fi subliniată astfel:
// InFront = plan.Distanță (punct)> 0.0f // Behind = plan.Distance (punct) < 0.0f Vec2 p1, p2; ClipPlane plane; case p1 InFront and p2 InFront push p2 case p1 InFront and p2 Behind push intersection case p1 Behind and p2 InFront push intersection push p2
Cea mai bună modalitate de a înțelege acest algoritm este să desenați o formă 2D pe o bucată de hârtie și să trageți o linie dreaptă prin formă. Apoi buclă de-a lungul vârfurilor de poligon și de a efectua algoritmul Sutherland-Hodgman și trageți rezultatele. Aceasta va construi o intuiție despre modul în care algoritmul rulează doar de-a lungul fiecărei linii succesiv, asigurându-vă că păstrați toate vârfurile în spatele planului.
După executarea creionului și a hârtiei, încercați această pagină web extraordinară. Există câteva vizualizări minunate și un applet Java (la începutul paginii), care permite utilizatorului să vadă porțiuni ale algoritmului de execuție!
Calculul intersecției unui plan cu două puncte este foarte simplu. Ideea este să utilizați calculul distanței pentru a găsi distanța fiecărui punct într-un plan. Având în vedere aceste distanțe, o intersecție poate fi apoi calculată folosind interpolarea liniară.
Bacsis: Interpolarea liniară este un concept extrem de util pentru a înțelege, având o aplicație prolifică în toate programele grafice și în software-ul de simulare fizică. Interpolarea liniară poate fi denumită în mod colocic lerp. Orice poate fi interpolat liniar dintr-o poziție de pornire până la poziția de capăt, atâta timp cât ecuație de mișcare este liniară.În general, formula pentru interpolarea liniară de la start la Sfârșit cu intersecție alfa este:
Lerp (început, sfârșit, alfa) întoarcere start * (1 - alfa) + sfârșit * alfaBacsis: În exemplul de mai sus,
Accentsconagua
alfa este ceea ce se numește a interpolant. Interpolanții sunt utilizați în calculele de interpolare liniară pentru a calcula pozițiile dintre punctele de început și de sfârșit. Știind acest lucru, distanțele de la planul la fiecare punct pot fi folosite ca valori pentru a calcula un alfa interpolant. Variabilele T1 și t2 poate reprezenta distanțele față de planul lui p1 și p2 respectiv.
În acest sens, punctul de intersecție este pur și simplu a Lerp de la punctul de plecare până la punctul final, dată fiind timpul de intersecție.
Acest algoritm poate fi ușor extins în spațiu tridimensional și efectuat acolo. (Acest algoritm ar putea fi realizat în orice dimensiune mai mare, indiferent de ce înseamnă). Cu toate acestea, în aplicații practice, acest algoritm nu este de obicei niciodată de fapt realizat în 3D. Prin utilizarea unor transformări inverse inteligente, problema tăierii unui polyhedron 3D împotriva unui plan poate fi simplificată (în anumite scenarii) la un poligon 2D până la rutina de tăiere poligonală. Acest lucru permite o optimizare computațională semnificativă.
În mod similar, dacă ar fi studiat codul sursă Bullet Physics, s-ar găsi că tăierea este de fapt făcută într-un spațiu unic dimensional, chiar dacă se efectuează într-adevăr o tăiere 3D completă. Acest lucru se datorează capacității de a calcula un interpolant valabil, dat doar o singură dimensiune a spațiului problemei.
De exemplu, dacă cunoașteți timpul de intersecție al X valorile unei probleme simple, acest timp de intersecție poate fi folosit ca un interpolant pentru a efectua o Lerp pe un punct tridimensional.
Să examinăm acest lucru într-un mod mai detaliat. Consultați următoarea diagramă:
Să presupunem că linia galbenă este la sol la o poziție y 0. Acum, presupuneți că poziția y de pornire este la 10, iar poziția y de sfârșit se află la -1. Să calculam o poziție validă interpolantă și intersecție de-a lungul coordonatei y:
// alfa = 0,9 / 10,0f float alfa = 0,9f // finalY = 0,0f float finalY = Lerp (y1, y2, alfa);
Cele de mai sus pot fi citite ca "90% din calea de la 10 la -1", care ar fi zero. Acest interpolant poate fi aplicat tipurilor de date arbitrare, incluzând un vector bidimensional:
// alfa = 9.0f / 10.0f float alfa = 0.9f Vec2 finalPozi = Lerp (p1, p2, alfa);
Codul de mai sus ar calcula corecția corectă x pentru momentul impactului, fără a efectua chiar operații cu coordonatele x pentru a determina interpolarea. Această idee de a calcula interpolanții și de a le aplica la dimensiuni mai mari decât de la care au fost calculate este o modalitate foarte bună de a optimiza codul.
Există unele probleme care pot persista atunci când se execută o implementare naivă a acestei rutine de tăiere. Ori de câte ori se calculează eroarea numerică a punctului de intersecție, se introduce în calcul. Aceasta reprezintă o problemă majoră atunci când se împarte un poligon cu un avion în timp ce se generează ieșirea ambele părți ale avionului. Pentru a genera ieșire pentru ambele părți ale unui plan de divizare, algoritmul inițial Sutherland-Hodgman trebuie modificat ușor și aici vor apărea problemele.
Ori de câte ori se calculează un punct de intersecție, eroarea numerică se strecoară. Aceasta este o problemă, deoarece punctul de intersecție calculat de la punctul A la punctul B va fi ușor diferită de calculul de la punctul B la punctul A. Pentru a evita astfel de probleme, intersecția trebuie calculată în mod consecvent. Asta evită un lucru teribil T-Junction problema. Este în regulă dacă există o eroare numerică atâta timp cât eroarea este consecventă.
Problemă T-Junction: Un spațiu între două ochiuri care determină rasterizarea triunghiului pentru a lăsa un decalaj vizibil între trei triunghiuri. De obicei, cauzate de manipularea slabă a epsilon mașină în timpul calculului punctului de plutire. Soluții posibile: transformări vertexale consecvente; top post-procesare sudare.
O altă problemă este atunci când se stabilește dacă un punct este pe o parte a unui plan sau altul. Pentru o multitudine de motive, ar trebui să se facă verificări în plan gros. Ideea este de a trata un avion ca un plan gros, mai degrabă decât unul cu o lățime infinit de mică. Acest lucru permite ca un caz suplimentar să apară în rutina Sutherland-Hodgman: in avion caz.
flotor D = plan.Distanță (punct); // EPSILON este un număr semnificativ și semnificativ din punct de vedere numeric. Poate 0.00001f. bool OnPlane (float D) retur D> -EPSILON și D < EPSILON;
Dacă se găsește vreun punct pe planul de tăiere, apăsați doar punctul final. Acest lucru va aduce numărul de 3 cazuri la 4 în total. Pentru mai multe informații despre EPSILON, Vezi aici.
Cea mai bună referință pentru acest algoritm de tăiere se află în cartea de detecție a coliziunii în timp real a lui Christer Ericson (denumită și Cartea Orange). Puteți găsi această carte în aproape toate studiourile de jocuri existente.
Dincolo de scoaterea unor bani pentru o carte, există câteva resurse gratuite:
Sutherland-Hodgman clipping este o modalitate excelentă de a realiza tăierea atât în spațiul 2D, cât și în spațiul 3D. Acest tip de rutină poate fi aplicat pentru a rezolva numeroase diverse probleme, unele probleme care se aplică în domenii de studiu destul de avansate. Ca întotdeauna, vă rugăm să aveți întrebări în secțiunea de comentarii de mai jos!
