Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Metodi Di Rappresentazione Spazio

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Ciao e benvenuto alla lezione numero 9 del corso Computer Graphics. Stiamo discutendo le fasi della pipeline grafica. Come potrete riscuotere, ci sono 5 tappe ampie, la primississima tappa è la rappresentazione dell'oggetto e attualmente stiamo discutendo sulla tecnica di rappresentazione dell'oggetto.
Quindi, questo sarà l'argomento della nostra discussione di oggi, i metodi di partizionamento dello spazio.
Ora, quando si parla di partizionamento dello spazio, a cosa ci riferiamo? Come suggerisce il nome, il partizionamento dello spazio si riferisce alla rappresentazione di un oggetto in termini di spazio 3D che occupa. Lo spazio è definito dai suoi confini e rappresentiamo lo spazio o il volume racchiuso dai confini piuttosto che dai confini, che abbiamo visto nelle lezioni precedenti.
Ora, c'è un concetto importante nelle tecniche di partizionamento dello spazio, questo si chiama voxel. Avete sentito parlare di pixel, abbiamo accennato a questo termine prima. Questa è la più piccola unità di visualizzazione. E su uno schermo di visualizzazione, ipotizziamo che ci sia una griglia di pixel. Analogamente, il voxel è sostanzialmente la controparte 3D del concetto di pixel. Voxel è la più piccola unità di rappresentazione in uno spazio 3D. Qualsiasi spazio 3D può essere ipotizzabile per avere una griglia voxel.
Come una griglia di pixel, possiamo creare o ipotizziamo che una griglia voxel esista per rappresentare uno spazio 3D. Quindi, la griglia di pixel è per lo spazio 2D, la griglia voxel è per lo spazio 3D. E il voxel, come forse ovvio, è il modo più semplice di rappresentare oggetti 3D.
Ora, quando parliamo di voxel, ci riferiamo essenzialmente a cubi di taglia tipicamente uniformi o parallelepipedi. Quindi, essenzialmente, una griglia di cubi di dimensioni uniformi o parallelepipedi che sono la nostra griglia di voxel. Ora, in ogni griglia, ogni elemento voxel della griglia tipicamente trasporta varie informazioni. Quali sono quelle informazioni? L'intensità in quella particolare regione 3D, la temperatura di quella regione e così via. E queste informazioni in realtà aiutano a descrivere univocamente la scena 3D. Quindi, essenzialmente i voxel stanno avendo attributi che sono informazioni caratteristiche per il particolare oggetto in scena.
Utilizzando i voxel, possiamo effettivamente applicare varie tecniche per rappresentare oggetti. Una tale tecnica è il metodo Octree. Che cosa è questo metodo? Come suggerisce il nome, è una specie di rappresentazione dell'albero, ora cerchiamo di capire cosa è questo albero. Quindi, essenzialmente si riferisce ad un metodo per creare una griglia di voxel, ma sotto forma di albero.
Quindi, in questo metodo, l'input è una regione 3D. Ora, dividiamo questo spazio di ingresso in 8 sub regioni, e poi ogni sub regione a turno è nuovamente divisa in 8 sub sub. Quindi, essenzialmente questo è un passo ricorrente e questa ricorrenza continua fino a giungere ad alcune dimensioni uniformi preimpostate delle sub regioni. Ora, questa dimensione può essere definita dall'utente, ad esempio un cubo di unità. Quindi, quando vediamo che la nostra divisione porta le regioni di dimensioni cubo, poi ci fermiamo lì, un esempio viene mostrato in questa figura di destra.
Ecco, questa è la nostra regione 3D iniziale. Ora, come potete vedere, abbiamo creato 8 sub regioni da qui, questo è 1, 2, 3, 4, 5, 6, 7 e 8, poi ognuna di queste sub regioni è ulteriormente suddivisa in 8 sub regioni come qui come potete vedere in questa divisione, ancora ci sono 8 sub regioni 1, 2, 3, 4, 5, 6, 7, 8. Allo stesso modo, anche qui, ci siamo divisi e tutte le altre sub regioni anche noi possiamo dividere.
Ora, qual è l'output di questa ricorrenza? Crea un albero. Quindi, abbiamo un nodo root. Per ogni nodo root abbiamo creato 8 nodi child da qui a qui. Ora per ogni nodo bambino, di nuovo stiamo creando 8 nodi figlio e questo processo continua. Quindi, essenzialmente questo porta ad un albero. Dal momento che ogni nodo ha 8 figli, lo chiamiamo albero e i nodi di foglia di questo albero rappresentano lo spazio 3D. Quindi, tutti i nodi intermedi sono rappresentazioni intermedie, non rappresentano l'oggetto finale, a livello di foglia viene rappresentato l'oggetto finale. Ricordate qui che insieme allo spazio gli attributi o le informazioni caratteristiche vengono memorizzate anche a livello di nodo a foglia.
Così, per rappresentare oggetti diversi, possiamo associare proprietà uniche a quei nodi di foglia o voxel, le proprietà come il colore, la densità, la temperatura e così via, questa è l'idea di base. Così, ci viene dato spazio 3D, lo spazio che abbiamo diviso in 8 regioni e continuiamo questa divisione, ogni sub regione è suddivisa ulteriormente in 8 sub regioni e così via. Continuiamo questa divisione in modo ricorsivo fino a raggiungere il livello di voxel o i cubi di taglia uniforme. E questo processo crea un albero; ogni nodo in questo albero ha 8 figli, quindi l'albero si chiama ocalbero.
Il livello di foglia contiene i voxel sono la rappresentazione dell'oggetto 3D e le informazioni caratteristiche come colore, densità, temperatura e così via sono associate ad ogni voxel in questo albero per identificare univocamente gli oggetti. Octree è uno dei vari metodi in cui lo spazio è utilizzato per rappresentare gli oggetti. Un altro metodo popolare si chiama BSP o il metodo BSP.
Ora, BSP spicca il partizionamento dello spazio binario e il metodo è il metodo di partizionamento dello spazio binario. Quindi, che cosa fa? Nell'ocalbero abbiamo fatto qualche partizionamento ricorsivo di spazio. Nell'albero BSP seguiamo ripetizione simile che ci viene dato uno spazio lo dividiamo in subspazio e poi suddividiamo di nuovo il subspazio e proseguiamo fino a qualche condizione.
Tuttavia, invece di dividere uno spazio in 8 subspazi come abbiamo fatto in caso di ottocento, qui quello che facciamo lo dividiamo in 2 spazi o subspazi in ogni passo ricorsivo. Così, in caso di octree stiamo dividendo la regione in 8 sub regioni, in caso di albero BSP stiamo dividendo la regione in 2 sub regioni, ecco perché si chiama partizionamento di spazio binario. Ora, come ci dividiamo? Usiamo aerei. Così, ci viene data una regione che assumiamo gli aerei sono disponibili a dividere la regione in sub regioni. Ma questi aerei non devono essere paralleli agli aerei formati dagli assi XY, YZ o ZX. Possono essere aerei di qualsiasi orientamento. Ovviamente, se ci troviamo paralleli agli aerei formati dall'asse principale allora è più facile da implementare, altrimenti dobbiamo fare ulteriori elaborazioni.
Vediamo un esempio. Supponga di essere dato a questa regione 3D e lo rappresenteremo sotto forma di albero BSP. Quindi, il nostro nodo radice è l'intero oggetto, poi abbiamo usato un aereo questo per dividerlo in due regioni, la regione di sinistra D e la regione giusta C. Left rispetto al piano e al diritto rispetto al piano, alla sub regione e alla sub regione destra. Poi abbiamo usato un altro aereo qui per dividere B in due sub regioni D ed E. Quindi, alla fine quello che abbiamo ottenuto? L'oggetto è rappresentato in termini di tre sub regioni D, E e C.
Quindi, questi tre a livello di foglia rappresentano l'oggetto. E ancora come in caso di ocalbero, possiamo associare proprietà uniche a ciascuna di queste sub regioni per identificare univocamente l'oggetto. Ora, qui abbiamo usato due piani che sono ortogonali l'uno all'altro, sono aerei ortogonali, ma cioè, come abbiamo già visto in precedenza, non è un requisito rigoroso. Gli aerei di qualsiasi orientamento possono essere utilizzati per dividere le regioni in due sub regioni.
Così, qui invece di questi piani ortogonali, avremmo potuto utilizzare qualsiasi piano di qualsiasi orientamento per dividerlo in due regioni, due regioni sub che sono la formulazione più generale per la creazione di alberi BSP. Ma, come detto, se stiamo utilizzando aerei che non sono paralleli agli aerei formati dall'asse principale, possono essere necessarie ulteriori elaborazioni per elaborare la rappresentazione. Vediamo un altro esempio per la creazione di alberi BSP, come possiamo creare, come possiamo scrivere un algoritmo per la creazione di una rappresentazione.
Considerate questa figura, qui vogliamo rappresentare questo cerchio, questo è ovviamente una figura bidimensionale, non è un oggetto 3D, ma questo oggetto 2D vogliamo rappresentare questo cerchio che sta avendo il centro a Pm e raggio r. Quindi, vogliamo rappresentarlo usando l'albero BSP.
Come possiamo fare? Così prende come input la regione circostante R che è la piazza rappresentata dai quattro vertici o i punti d'angolo P 1, P 2, P 3 e P 4 e il cerchio si trova all'interno di questa regione. Quindi, quando rappresentiamo il cerchio, rappresentiamo essenzialmente questa regione con alcune regioni che fanno parte del cerchio che presentano caratteristiche uniche del cerchio. Come possiamo fare?
Così, partiremo la regione in 4 sub regioni. Quindi, prima dividiamo in 2 sub regioni, poi ognuna di queste 2 sub che dividiamo in ulteriori 2 sub regioni e così via. Quindi, solo per semplicità stiamo combinando questi passi insieme qui e affermando che lo stiamo dividendo in 4 sub regioni. E qui utilizziamo linee parallele agli assi.
Usando quell' idea, cosa possiamo fare? Possiamo scrivere un algoritmo per una funzione creata a BSP dove R è la regione di input. Ora, useremo R per creare un nodo, poi da R creeremo 4 regioni aderendo ai midpoint dei lati della piazza, questo vale come applicare le tecniche di partizionamento dello spazio binario in più passaggi. Come in questo caso, creiamo per la prima volta 2, poi per ognuno di questi due ne creiamo altri due e in realtà stiamo combinando questi passi qui in questa linea.
Ora, per ognuna di queste sub regioni qui a questo nodo di foglia di questa figura, se le dimensioni di questa sub - regione, supponiamo che questa regione sia suddivisa in 4 sub regioni, quindi stiamo considerando questo. Ora, se la dimensione della sub regione è una piazza unitaria, dove ipotizziamo che un pixel sia rappresentato come un quadrato unitario. Poi passiamo al passo successivo che è se la distanza tra i centri della regione originaria R e la sub regione che stiamo considerando attualmente è inferiore o uguale al raggio del cerchio, allora questa sub regione fa parte del cerchio.
Quindi, lo aggiungiamo come nodo di foglia all'albero di BSP e lo segnaliamo come "interno". In caso contrario, lo segnaliamo come 'fuori', sebbene aggiungelo come parte di albero BSP. Ora, se la dimensione non è quadrata, cioè non abbiamo raggiunto la condizione di terminazione della reiterazione. Quindi, per ogni nodo eseguiamo di nuovo la funzione, ovvero chiamiamo la funzione nuovamente ricorsivamente menzionata in questi 2 passi. Così, alla fine otteniamo un albero, dove i nodi di foglia rappresentano la regione di arrotondamento, la regione originaria divisa in sub regioni.
Ora, alcune di queste sub regioni sono segnate come all'interno di questo particolare oggetto, all'interno della piazza. Mentre, altri sono contrassegnati come esterni. Così, da quell' albero, otteniamo una rappresentazione della piazza. Fin qui così bene. Ora, qual è il problema? C'è qualche problema con questo approccio di partizionamento spaziale?
Un problema potrebbe essere molto ovvio per voi ormai, ovvero che richiediamo grande memoria per memorizzare queste informazioni sulla griglia voxel. Quindi, stiamo creando albero dove i nodi della foglia rappresentano la griglia e se partiamo uniformemente, poi ci sarà un gran numero di voxel e richiediamo notevole quantità di spazio di memoria per memorizzare le informazioni voxel. Il problema arriva perché stiamo dividendo lo spazio in vuoti di dimensioni uniformi indipendentemente dalle proprietà dello spazio.
Come abbiamo visto nell'esempio precedente, la regione R è una grande regione, all'interno di questo, il cerchio occupa una piccola area, ma stiamo dividendo la regione in sub regioni di dimensioni uniformi e molte sub regioni possono trovarsi al di fuori del cerchio. Quindi, se volete rappresentare il cerchio, non è necessario rappresentare quelle regioni che sono al di fuori del cerchio che effettivamente sprecano qualche spazio di memoria. Quindi, se abbiamo qualche metodo per evitare questi sprechi, allora ovviamente che sarebbe utile.
Allora, che cosa vogliamo? Se una certa regione nello spazio ha le stesse proprietà ovunque, allora idealmente non dovremmo dividerla ulteriormente. Perché anche se dividiamo qualunque cosa otteniamo, otterremo la stessa proprietà. Invece, quello che facciamo, lo dividiamo ancora in voxel, sebbene ogni voxel contenga gli stessi attributi, perché la regione più ampia o quella più ampia nello spazio ha la stessa proprietà ovunque.
Quindi, possiamo davvero risparmiare, questo è qui un typo, è sicuro, possiamo salvare la memoria utilizzando questa idea di partizionamento non uniforme. Così, prima stiamo parlando di partizionare una regione in vuoti di dimensioni uniformi. Ora, stiamo parlando di partizionamento spaziale dimensionato non uniforme. Che cosa è? Ovvero, invece di usare molti voxel per rappresentare una regione omogenea che è una regione dove la proprietà è uguale ovunque usiamo un'unica unità. Quindi, non dividiamo ulteriormente quella regione, invece l'intera regione è rappresentata come un'unità unica.
Come possiamo fare? Un modo è modificare il metodo octree. Ora, prima avevamo fissato 8 bambini per ogni nodo perché dividevamo la regione in 8 sub regioni indipendentemente dalla proprietà della regione. Ora, cosa possiamo fare? O ci dividiamo o non ci dividiamo. Quindi, se una sub regione ha la stessa proprietà ovunque, allora non lo dividiamo. Quindi, quel nodo non avrà figli o 0 bambini. Ma se non è così, allora lo dividiamo in 8 sub regioni o 8 bambini.
Così ora, nel metodo del ottone rivisto, quello che avremo 0 o 8 bambini per ogni nodo, cosa che prima non era il caso. Così, prima stavamo ricevendo 8 bambini per ogni nodo, nodo intermedio, ora otterremo 0 o 8 bambini per ogni nodo intermedio a seconda della proprietà di quello spazio rappresentato dal nodo.
La procedura di ricorrenza, ovviamente, rimarrà, la procedura di ricorrenza rimarrà la stessa. Ma ad ogni passo della ricorrenza controlleremo se gli attributi di uno spazio sono uguali ovunque. Se è così, allora non lo dividiamo ulteriormente. Quindi, non andiamo di nuovo per una divisione ricorsiva per quella determinata regione.
La rappresentazione BSP soffre anche dello stesso problema se stiamo andando per un partizionamento uniforme.
E per evitarlo possiamo andare per un metodo rivisto o un metodo raffinato dove poter dividere la regione in 2 sub regioni se le sub regioni hanno proprietà diverse in luoghi diversi o non ci dividiamo. Quindi, i nodi intermedi avranno o 0 o 2 bambini simili al metodo di ottone rivisto. Quindi, quello che abbiamo imparato è che l'unità di rappresentanza di base sarà il voxel. Ora, usando il voxel possiamo dividere un dato spazio 3D per rappresentare l'oggetto contenuto in quello spazio in due modi, uno è la divisione uniforme.
Ora, quando andremo per una divisione uniforme, otterremo un tipo particolare di albero se seguiamo il metodo octree o un particolare tipo di albero se seguiamo il metodo BSP. Nel metodo octree, se andiamo per una divisione uniforme, allora otterremo 8 bambini per ogni nodo. Nel metodo BSP otterremo due bambini per ogni nodo. Ora, se la regione che stiamo dividendo sta avendo lo stesso attributo o le stesse proprietà ovunque allora si tratterà di sprechi di memoria per dividere quella regione nelle sub regioni e memorizzare le informazioni.
Invece, non occorre dividerlo ulteriormente. Quindi, nel caso del metodo octree, lo modifichiamo per il partizionamento non uniforme imponendo il fatto che un nodo possa avere 0 o 8 bambini. Allo stesso modo, in un metodo BSP rivisto, possiamo modificare imponendo il fatto che ogni nodo intermedio può avere 0 o 2 bambini.
Esiste un altro metodo di partizionamento dello spazio noto come CSG. Cosa significa?
Spicca la Geometria Solida Costruttiva. Ecco, questo è un altro metodo per la rappresentazione spaziale degli oggetti. Ora, in caso di ocalbero o BSP quello che abbiamo visto? Abbiamo visto che queste rappresentazioni si basano sulla divisione dello spazio. Così, ci viene dato uno spazio e lo stiamo dividendo in subspazi. In confronto a quello, in caso di CSG cosa abbiamo? In realtà si basa sull'adesione di spazi, proprio il contrario di quello che facciamo nei metodi BSP o octree. Così, in caso di CSG ci affidiamo all'adesione di spazi per rappresentare oggetti. Proviamo a capirlo con rispetto ad un esempio.
Considera questo oggetto, questo sembra piuttosto complesso. Tuttavia, quando utilizziamo il metodo della geometria solida CSG o costruttiva, possiamo rappresentarlo come unione di altre forme. Così, iniziamo qui a questo livello, qui abbiamo questa forma, questa forma, questa forma e questa forma, quindi 4 forme ci sono. Ora, combiniamo queste 2 forme per ottenere una forma e combiniamo queste 2 forme qui per ottenere questa forma. Ora, queste 2 forme sono poi ulteriormente combinate per ottenere questa forma complessiva.
Quindi, qui iniziamo con set di forme primitive o forme di base, poi applichiamo una serie di operatori booleani cioè unione, incrocio, differenza etc. che sono definiti su questo insieme di forme primitive per ottenere forme più recenti. Come qui su queste 2 forme abbiamo applicato un operatore booleano per ottenere una nuova forma e questo processo continua fino a ottenere qui la forma desiderata. Così, gli operatori possono essere applicati gerarchicamente. Così, da questo livello raggiungiamo a questo livello, da questo livello raggiungiamo a questo livello, ad ogni livello applichiamo gli operatori booleani.
Ecco quindi un'applicazione gerarchica degli operatori. Quindi, in altre parole, abbiamo un insieme di forme primitive definite e un insieme di operatori booleani su quelle forme anche definite. Ora, applichiamo quegli operatori sulle forme per ottenere nuove forme e applichiamo quegli operatori gerarchicamente fino a ottenere la forma desiderata, finché non siamo in grado di rappresentare la forma desiderata. Allora, qual è la rappresentazione? La rappresentazione è essenzialmente le forme primitive e gli operatori booleani applicati in modo gerarchico, quindi ecco la rappresentazione.
Quindi, questo è in sintesi, di cosa si tratta questa geometria solida costruttiva. Ora, riassumiamo ciò che abbiamo imparato finora.
Oggi e nelle precedenti poche lezioni abbiamo imparato varie tecniche di rappresentazione, che è la prima fase della pipeline. Presentazione di confine tra cui spline, rappresentazione dello spazio e anche panoramica di altre rappresentazioni. Ora, ci sono molte tecniche come abbiamo visto finora. Una domanda è quale tecnica utilizzare e quando? Questa è una domanda che si confronta sempre con uno sviluppatore di sistemi grafici. Quale tecnica deve essere utilizzata e in quale situazione? Quali guide quel processo decisionale?
Ora, potremmo desiderare la rappresentazione più realistica. Chiaramente le tecniche avanzate sarebbero utili ma tecniche avanzate come i sistemi di particelle potrebbero non essere sempre possibili perché richiedono molte risorse computazionali che potrebbero non essere disponibili in tutti i sistemi grafici. Quindi, ogni tecnica arriva con un costo e c'è un tradeoff, che tecnica da utilizzare in quale situazione.
Ora, questo costo può essere un requisito di calcolo o di conservazione o entrambi e a seconda della risorsa disponibile, dobbiamo prendere la decisione. Se stiamo avendo una risorsa molto minore allora non possiamo pensare a tecniche avanzate di modellazione, allora potremmo dover perdere qualche realismo e dover accontentarci di alcune scene o immagini meno realistiche.
Per esempio, supponga di voler rappresentare le coste in una scena. Allora, cosa è auspicabile? Le coste sono tipicamente strutture autoripetenti e la rappresentazione frattale è molto buona per tali forme. Quindi, idealmente dovremmo usare la rappresentazione frattale per avere una costa realistica visualizzata. Ma potrebbe non essere possibile se stiamo considerando una piattaforma mobile con processore e batteria a memoria limitata perché la rappresentazione frattale ha un costo computazionale aggiuntivo che potrebbe non essere supportato in dispositivi mobili di fascia bassa.
Quindi, in quel caso, potremmo dover usare un metodo più semplice. Quindi, stiamo perdendo qui qualcosa, l'effetto realistico, ma acquisisce qualcosa che è un'approssimazione di lavoro. Quindi, tali compromessi fanno molto parte del processo decisionale, bilanciando quei traffici.
Un'altra considerazione forse easi di manipolazione. Così, quando stiamo creando animazione, questa considerazione arriva a portata di mano e diventa importante. Ora, come dicevamo ogni rappresentazione ha i suoi metodi, gli algoritmi, il proprio processo. Le fasi successive della pipeline devono elaborare queste rappresentazioni per svolgere le operazioni che fanno parte delle fasi successive. Quindi, questo richiede la manipolazione delle rappresentanze.
Ora, se richiede molto tempo per manipolare, ad esempio, ruotare un oggetto, spostare 10 oggetti in orizzontale o verticalmente, scaldare o giù un oggetto o clip, proiettare o eseguire meglio nella rimozione della superficie, ecc. questi fanno parte di altre fasi della pipeline. Discuteremo delle tappe nei dettagli successivi. Ora, se è necessario molto tempo per eseguire queste operazioni, per oggetti che sono rappresentati in modo particolare, la qualità dell'animazione può essere ridotta. Quindi, in questi casi, dovremmo cercare tipi più semplici.
Ecco, questa è un'altra considerazione che va tenuta in mente pur scegliendo un particolare modello di rappresentazione che sia la facilità di manipolazione. Quindi, se stiamo avendo dispositivi di fascia bassa, sistemi grafici di fascia bassa, allora non è consigliabile andare per tecniche di rappresentazione avanzate che richiedono molte manipolazioni in seguito, in particolare nel contesto dell'animazione.
Terza considerazione è la facilità di acquisizione dei dati. Ad esempio, la rappresentazione di listino vertex per una superficie curvo utilizzando una mesh richiede un elevato numero di vertici da specificare. Ora, consideriamo la rappresentazione spline. In quel caso, richiediamo meno punti di controllo per rappresentare la stessa curva. Quindi, chiaramente qui, rappresentare una curva che utilizza la mesh comporta più sforzo per acquisire dati, mentre rappresentare la stessa curva con una spline comporta meno sforzo per acquisire dati. Quindi, a volte queste facilità di acquisizione dei dati possono essere un fattore decisivo. A seconda del progettista del sistema grafico, un metodo particolare può essere scelto dove i dati possono essere acquisiti facilmente.
Quindi, ci sono diversi compromessi che dobbiamo bilanciare e dobbiamo decidere quali sono quelle risorse di trade-off disponibili, la natura delle interazioni, le risorse in termini di piattaforma di calcolo, la natura dell'interazione in termini di comfort con la fornitura di grandi quantità di dati e anche di effetto, se vogliamo un effetto molto realistico o stiamo cercando qualche approssimazione considerando la mancanza di risorse.
Quindi, a seconda di queste ampie considerazioni di 3, dobbiamo scegliere una tecnica di modellazione particolare. Quindi, con questo, siamo giunti al termine della nostra discussione sulla prima fase della pipeline grafica che è la rappresentazione dell'oggetto.