Share
Ritaglio è il processo per determinare quale regione dello spazio si trova all'interno di un'altra regione dello spazio. Ciò è particolarmente importante nelle aree di studio come la simulazione di computer grafica e fisica. Ad esempio, quando si esegue il rendering di un mondo sullo schermo è meglio sapere cosa sarà visualizzato sullo schermo prima di elaborare qualsiasi dato. Ciò consente di ignorare molti dati estranei, elaborando e presentando solo ciò che verrà visualizzato dall'utente.
Nella simulazione fisica, si trovano spesso corpi rigidi compenetrano - cioè, due oggetti separati si sovrappongono. Questo non va bene. La compenetrazione è qualcosa che non accade mai nel mondo reale, ma è un problema che deve essere affrontato nel rilevamento delle collisioni. Spesso, una forma viene troncata contro un'altra per determinare quali caratteristiche siano realmente toccanti. Da qui può essere avviata una risposta di collisione.
Le funzionalità avanzate dei motori di gioco possono essere implementate con una qualche forma di clipping; simulazione di galleggiabilità, piani di visione della telecamera; fratturazione fragile, generazione di contatti con il test dell'asse di separazione; tutte queste cose (e molte altre) possono essere ottenute con algoritmi di clipping. In effetti, il ritaglio di questo tipo era necessario nel mio precedente tutorial sulla costruzione di un motore fisico rigido.
Questo articolo richiede che tu abbia una comprensione decente di:
Le suddette aree di studio possono essere apprese da un'ampia varietà di risorse su Internet (come la guida di Wolfire all'algebra lineare o Khan Academy) e non sono troppo difficili da imparare!
Molte routine di ritaglio complesse prevedono l'uso di un singolo tipo di operazione: la divisione di una forma con un singolo piano. Dividere una forma di un piano implica prendere una forma e tagliarla in due pezzi attraverso un piano solido.
È importante rendersi conto che dividere una forma con un piano è uno strumento fondamentale in questa routine di ritaglio.
Guarda le eccellenti animazioni di Davide Cervone per una chiara dimostrazione di questo:
Il ritaglio di Sutherland Hodgman è la mia routine di ritaglio preferita, poiché consente di tagliare i loop di linea contro i piani. Con questo algoritmo, dato un elenco di vertici di input e un elenco di piani, può essere calcolato un output di nuovi vertici che esiste puramente all'interno del set di piani.
Il piano del termine può essere usato per riferirsi sia a un piano in 3D che a 2D. Un piano 2D può anche essere chiamato a linea.Possiamo immaginare la lista dei vertici come un singolo poligono. Possiamo immaginare (per ora) la lista degli aerei come una singola linea. Visualizzarlo in due dimensioni potrebbe essere simile alla seguente immagine:
Con il ritaglio di Sutherland Hodgman, il poligono sulla destra è la forma desiderata, mentre il poligono rosso sulla sinistra è la forma di input, e deve ancora essere ritagliato. La linea blu rappresenta un piano di divisione in due dimensioni. È possibile utilizzare qualsiasi numero di piani di divisione; nell'esempio precedente viene utilizzato un solo piano di divisione. Se vengono utilizzati molti piani di divisione, il ritaglio si verifica un piano alla volta, tagliando sempre più forme originali per produrne uno nuovo:
Per semplicità, lavoriamo in rigorose due dimensioni. Quando si divide un poligono su un piano, sarà importante sapere su quale lato del piano si trova un determinato punto.
Sopra è il modo più comunemente usato per trovare la distanza da un punto a un piano. Si noti che il simbolo del punto nell'equazione sopra rappresenta il prodotto punto.
La distanza non ha bisogno di essere calcolata esplicitamente; il vettore normale n non ha bisogno di essere normalizzato (cioè, non ha bisogno di avere una lunghezza esattamente di una unità). Tutto ciò che deve essere controllato è il segno del risultato della distanza d. Se n non è normalizzato allora d sarà in unità della lunghezza di n. Se n è normalizzato, quindi d sarà in unità equivalenti alle unità spaziali del mondo. Questo è importante da realizzare in quanto consente di fare il calcolo per vedere se d è positivo o negativo. Positivo d denota che il punto p è sul lato anteriore dell'aereo. Negativo significa che è sul retro.
Ora, cosa intendiamo esattamente con i lati "frontale" e "posteriore" di un aereo? Beh, dipende davvero da cosa si definisce avanti e indietro come. Di solito "anteriore" significa che si trova sullo stesso lato del piano come normale.
Consente di immergersi direttamente nell'algoritmo. Fai una scansione veloce sullo pseudocodice:
Polygon SutherlandHodgman (const Polygon startingPolygon, Plane [] clippingPlanes) Polygon output = startingPolygon per ogni Plano clippingPlane in clippingPlanes input = output output.Clear () Vec2 startingPoint = input.Last () per ogni endpoint Vec2 in input se startingPoint e endPoint in front of clippingPlane out.push (endPoint) else if startingPoint in front e endPoint behind clippingPlane out.push (Intersection (clippingPlane, startingPoint, endPoint)) else if startingPoint e endPoint behind clippingPlane out.push (Intersection (clippingPlane, startingPoint, endPoint) ) out.push (endPoint) endPoint = startingPoint restituisce output
L'algoritmo prende un poligono di input e alcuni piani di ritaglio e genera un nuovo poligono. L'idea è quella di ritagliare ogni segmento di linea del poligono di input su un piano di ritaglio alla volta. Questa immagine da Wikimedia Commons lo dimostra abbastanza bene:
Ogni operazione di ritaglio ha solo alcuni casi diversi in cui generare i vertici e può essere delineata in questo modo:
// InFront = plane.Distance (point)> 0.0f // Dietro = plane.Distance (point) < 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
Il modo migliore per comprendere questo algoritmo è disegnare una forma 2D su un foglio di carta e tracciare una linea retta attraverso la forma. Quindi fai un loop lungo i vertici del poligono ed esegui l'algoritmo Sutherland-Hodgman e disegna i risultati. Questo creerà intuizione su come l'algoritmo stia correndo lungo ogni linea in sequenza, assicurandosi di mantenere tutti i vertici dietro l'aereo.
Dopo aver eseguito la tua matita e la tua carta, prova questa fantastica pagina web. Ci sono alcuni fantastici effetti visivi e un'applet Java (nella parte superiore della pagina) che consente all'utente di visualizzare parti dell'algoritmo effettivamente eseguito!
Calcolare l'intersezione di un piano dato due punti è molto semplice. L'idea è di usare il calcolo della distanza per trovare la distanza di ogni punto su un piano. Date queste distanze, è possibile calcolare un'intersezione utilizzando l'interpolazione lineare.
Mancia: L'interpolazione lineare è un concetto estremamente utile da comprendere, con una prolifica applicazione in tutti i software di grafica e nei software di simulazione fisica. L'interpolazione lineare può essere definita colloquialmente lerp. Qualsiasi cosa può essere linearmente interpolata da una posizione di partenza a una posizione di fine, a condizione che il equazione del moto è lineare.In generale, la formula per interpolare linearmente da inizio a fine con intersezione alfa è:
Lerp (inizio, fine, alpha) ritorno inizio * (1 - alfa) + fine * alfaMancia: Nell'esempio sopra,
Accentsconagua
alfa è ciò che è chiamato un interpolante. Gli interpolanti vengono utilizzati nei calcoli di interpolazione lineare per calcolare le posizioni tra i punti iniziale e finale. Sapendo questo, le distanze dal piano a ciascun punto possono essere utilizzate come valori di cui calcolare un alfa interpolante. Le variabili t1 e t2 può rappresentare le distanze dal piano di p1 e p2 rispettivamente.
A questo proposito, il punto di intersezione è semplicemente a Lerp dal punto di partenza al punto finale, dato un tempo di intersezione.
Questo algoritmo può essere facilmente esteso nello spazio tridimensionale e eseguito lì. (Questo algoritmo può essere eseguito in qualsiasi dimensione superiore, qualunque cosa significhi.) Tuttavia nelle applicazioni pratiche, questo algoritmo non è mai in genere in realtà eseguito in 3D. Usando trasformazioni intelligenti inverse, il problema di tagliare un poliedro 3D su un piano può essere semplificato (in alcuni scenari) in una poligonale 2D a una routine di ritaglio poligonale. Ciò consente una significativa ottimizzazione computazionale.
Allo stesso modo, se si studiasse il codice sorgente di Bullet Physics, si scoprirà che il ritaglio viene effettivamente eseguito in uno spazio a dimensione singola, anche se viene effettivamente eseguito un ritaglio 3D completo. Ciò è dovuto alla capacità di calcolare un interpolante valido dato solo una singola dimensione dello spazio del problema.
Ad esempio, se si conosce il tempo di intersezione del X valori di un problema semplice, questo tempo di intersezione può essere utilizzato come interpolante per eseguire a Lerp su un punto tridimensionale.
Esaminiamo questo in modo più dettagliato. Dai uno sguardo al seguente diagramma:
Supponiamo che la linea gialla sia il terreno in una posizione y di 0. Supponiamo ora che la posizione y iniziale sia a 10, e la posizione Y finale è a -1. Calcoliamo una posizione di interpolazione e intersezione valida lungo la coordinata y:
// alpha = 0.9 / 10.0f float alpha = 0.9f // finalY = 0.0f float finalY = Lerp (y1, y2, alpha);
Quanto sopra può essere letto come "90% del modo da 10 a -1", che sarebbe zero. Questo interpolante può essere applicato a tipi di dati arbitrari, incluso un vettore bidimensionale:
// alpha = 9.0f / 10.0f float alpha = 0.9f Vec2 finalPosition = Lerp (p1, p2, alpha);
Il codice sopra calcola effettivamente la corretta coordinata x per il tempo di impatto, senza nemmeno eseguire operazioni con la coordinata x per determinare l'interpolante. Questa idea di calcolare gli interpolanti e applicarli a dimensioni superiori a quelle da cui sono stati calcolati è un ottimo modo per ottimizzare il codice.
Ci sono alcuni problemi che possono persistere quando si esegue un'implementazione ingenua di questa routine di ritaglio. Ogni volta che si calcola l'errore numerico del punto di intersezione nel calcolo. Questo pone un grosso problema quando si divide un poligono con un piano durante la generazione dell'output entrambi i lati dell'aereo. Al fine di generare output per entrambi i lati di un piano di scissione, l'algoritmo originale Sutherland-Hodgman deve essere leggermente modificato, ed è qui che sorgono problemi.
Ogni volta che viene calcolato un punto di intersezione, si verifica un errore numerico. Si tratta di un problema come il punto di intersezione calcolato dal punto UN indicare B sarà leggermente diverso dal calcolo dal punto B indicare UN. Per evitare tali problemi, l'intersezione deve essere calcolata in modo coerente. Questo evita un terribile T-Junction problema. Va bene se c'è un errore numerico finché l'errore è coerente.
Problema con l'incrocio a T: Uno spazio vuoto tra due mesh che fa sì che la rasterizzazione triangolare lasci uno spazio visibile tra tre triangoli. Solitamente causato da una cattiva gestione del epsilon della macchina durante il calcolo in virgola mobile. Possibili soluzioni: trasformazioni di vertici coerenti; post-saldatura per saldatura a vertice.
Un altro problema è quando si determina se un punto è su un lato di un piano o su un altro. Per un sacco di motivi, dovrebbero essere fatti controlli spessi sul piano. L'idea è di trattare un piano come un piano spesso, piuttosto che uno con una larghezza infinitamente piccola. Ciò consente di creare un caso aggiuntivo all'interno della routine Sutherland-Hodgman: il sull'aereo Astuccio.
float D = plane.Distance (point); // EPSILON è un numero numericamente significativo e visivamente insignificante. Forse 0.00001f. bool OnPlane (float D) return D> -EPSILON e D < EPSILON;
Se si trova un punto sul piano di ritaglio, basta premere il punto finale. Questo porterà il numero di casi 3 a 4 in totale. Per maggiori informazioni su EPSILON, Vedere qui.
Il miglior riferimento per questo algoritmo di ritaglio si trova nel libro Real-Time Collision Detection di Christer Ericson (noto anche come Orange Book). Puoi trovare questo libro praticamente in ogni studio di gioco esistente.
Oltre a sborsare molti soldi per un libro, esistono un paio di risorse gratuite:
Il ritaglio Sutherland-Hodgman è un ottimo modo per eseguire il ritaglio sia nello spazio 2D che in quello 3D. Questo tipo di routine può essere applicato per risolvere molti problemi diversi, alcuni dei quali sono applicabili in aree di studio piuttosto avanzate. Come sempre, non esitate a fare domande nella sezione commenti qui sotto!
