Rimozione delle linee nascoste: Svelare l'invisibile: i segreti della visione artificiale

Di Fouad Sabry

Che cos'è la rimozione delle linee nascoste

Gli oggetti solidi sono generalmente modellati come poliedri nel campo della grafica computerizzata tridimensionale. All'interno di un poliedro, una faccia è un poligono planare circondato da segmenti rettilinei chiamati spigoli. Quando si tenta di imitare superfici curve, viene generalmente utilizzata una mesh poligonale. È necessario che i programmi informatici utilizzati per creare disegni al tratto di oggetti opachi abbiano la capacità di determinare se i bordi o le sezioni dei bordi sono nascosti dall'oggetto stesso o da altri oggetti. Ciò consente di ritagliare i bordi durante il processo di rendering. La difficoltà in questione viene definita rimozione delle linee nascoste.

Come trarrai vantaggio

(I) Approfondimenti e convalide sui seguenti argomenti:

Capitolo 1: Rimozione delle linee nascoste

Capitolo 2: Algoritmo di Painter

Capitolo 3: Geometria computazionale

Capitolo 4: Ray casting

Capitolo 5: Determinazione della superficie nascosta

Capitolo 6: Posizione del punto

Capitolo 7: Albero di copertura minimo euclideo

Capitolo 8: Problema della galleria d'arte

Capitolo 9: Rendering ad alta gamma dinamica

Capitolo 10: Scheletro dritto

(II) Rispondere alle principali domande del pubblico sulla rimozione delle linee nascoste .

(III) Esempi reali dell'utilizzo della rimozione delle linee nascoste in molti campi.

A chi è rivolto questo libro

Professionisti, studenti universitari e laureati, appassionati, hobbisti e coloro che desiderano andare oltre le conoscenze o le informazioni di base per qualsiasi tipo di rimozione delle linee nascoste.

 

 

• Lingua: Italiano
• Editore: Un Miliardo Di Ben Informato [Italian]
• Data di uscita: 5 mag 2024

Anteprima del libro

Capitolo 1: Rimozione delle linee nascoste

Nella computer grafica 3D, i poliedri sono tipicamente utilizzati per modellare cose solide. Una faccia di un poliedro è un poligono piano delimitato da spigoli, che sono segmenti di linea retta. In genere, una mesh poligonale viene utilizzata per rappresentare le superfici curve. Per ritagliare i bordi durante il rendering, i programmi per computer per i disegni al tratto di oggetti opachi devono essere in grado di determinare quali bordi o porzioni di bordi sono oscurati da un elemento o da altri oggetti. Questo problema viene definito rimozione delle linee nascoste.

Roberts sviluppò la prima soluzione conosciuta al problema delle linee nascoste. Ivan E. Sutherland evidenziò dieci questioni irrisolte nella computer grafica nel 1966.

Nella progettazione assistita da computer, ad esempio, i modelli possono avere migliaia o milioni di spigoli. Pertanto, è essenziale utilizzare un metodo di complessità computazionale che esprima i requisiti di risorse (come tempo e memoria) in funzione delle dimensioni dei problemi. Particolarmente cruciali sono i vincoli di tempo per i sistemi interattivi.

Le dimensioni problematiche per la rimozione delle linee nascoste sono il numero n degli spigoli del modello e il numero v dei segmenti visibili degli spigoli.

Nei punti di incrocio delle immagini dei bordi, la visibilità può cambiare.

Sia k il numero totale di siti in cui le immagini dei bordi si intersecano.

Sia k = Θ(n2) che v = Θ(n2) nel caso peggiore, ma tipicamente v k.

Prima del 1984, gli algoritmi a linee nascoste pubblicati da Ottmann e Widmayer e Wood proposero algoritmi a linee nascoste O((n + k) log2 n)-tempo.

Poi Nurmi ha migliorato il tempo di esecuzione a O((n + k) log n).

Questi algoritmi impiegano Θ(n2 log2 n), rispettivamente Θ(n2 log n) tempo nel peggiore dei casi, se k è comunque inferiore al quadratico, può essere più veloce in realtà.

Qualsiasi algoritmo a linee nascoste deve determinare l'unione di intervalli nascosti Θ(n) su n archi nel peggiore dei casi.

Poiché Ω(n log n) è un limite inferiore per determinare l'unione di n intervalli, sembra che il meglio che si possa sperare di ottenere sia Θ(n2 log n) il tempo del caso peggiore, Di conseguenza, l'algoritmo di Nurmi è il migliore.

Tuttavia, il  fattore log n è stato eliminato da Devai, affermando che i metodi di Devai e McKenna sono pietre miliari negli algoritmi di visibilità, rompendo una barriera teorica da O(n2 log n) a O(n2) per l'elaborazione di una scena di n bordi.

L'altra questione in sospeso, presentata da Devai, se esista un  algoritmo O(n log n + v)-time hidden-line, dove v, come già detto, è il numero di segmenti visibili, è rimasta senza risposta al momento in cui scriviamo.

Nel 1988 Devai propose un  algoritmo parallelo O(log n)-time che utilizzava processori n2 per il problema della linea nascosta sotto la lettura simultanea, Model of computing using exclusive write (CREW) parallel random-access machine (PRAM).

Poiché il prodotto del numero del processore e del tempo di esecuzione è asintoticamente maggiore di Θ(n2), la complicazione sequenziale del problema, l'algoritmo è inefficiente, tuttavia, dimostra che il problema a linee nascoste appartiene alla classe NC di difficoltà, cioè può essere risolto utilizzando un numero polinomiale di processori in tempo polilogaritmico.

Tuttavia, gli algoritmi di superficie nascosta possono essere utilizzati per eliminare le linee nascoste, non il contrario.

Reif e Sen hanno proposto un algoritmo O(log⁴ n)-time per il problema della superficie nascosta, utilizzando i processori O((n + v)/log n) CREW PRAM per un modello ristretto di terreni poliedrici, dove v è la quantità di output.

Nel 2011 Devai ha pubblicato un algoritmo O(log n)-time hidden-surface, e un algoritmo più semplice, anch'esso O(log n)-time, a linee nascoste.

L'algoritmo della superficie nascosta, che utilizza i processori n2/log n CREW PRAM, è il migliore in termini di efficienza.

L'algoritmo a righe nascoste utilizza processori PRAM n2 di lettura esclusiva, EREW (scrittura esclusiva).

EREW è il tipo di PRAM più simile alle macchine reali.

L'algoritmo a linee nascoste funziona O(n2 log n), Qual è il limite superiore per gli algoritmi sequenziali più efficaci in uso?.

Cook, Dwork e Reischuk hanno dato un limite inferiore Ω(log n) per trovare il massimo di n numeri interi che consentono un numero infinito di processori di qualsiasi PRAM senza scritture simultanee.

{Fine Capitolo 1}

Capitolo 2: L'algoritmo di Painter

L 'algoritmo del pittore (anche algoritmo di ordinamento della profondità e riempimento prioritario) è un algoritmo per la determinazione della superficie visibile nella computer grafica 3D che funziona su una base poligono per poligono piuttosto che su una base pixel per pixel, per riga, o su una base regione per regione utilizzando tecniche aggiuntive di rimozione della superficie nascosta.

Nel 1972, mentre tutti e tre erano impiegati al CADCentre, Martin Newell, Richard Newell e Tom Sancha presentarono per la prima volta l'algoritmo del pittore come soluzione di base al problema della determinazione della superficie nascosta.

L'algoritmo di Painter opera concettualmente come segue:

Ordina ogni poligono in base alla profondità

Posiziona ogni poligono dal più lontano al più vicino.

Ordina i poligoni in base alla profondità

Per ogni poligono P:

Per ogni pixel coperto da P :

Dipingi P.Color su pixel

La complessità temporale dell'algoritmo del pittore dipende fortemente dal meccanismo di ordinamento utilizzato per disporre i poligoni. Assumendo la tecnica di ordinamento più efficiente, la complessità del caso peggiore dell'approccio del pittore è O(n log n + m*n), dove n