Algoritmo di Warnock

L'algoritmo di Warnock è un algoritmo per la determinazione della superficie nascosta inventato da John Warnock che è tipicamente utilizzato nel campo della computer grafica.^[1] Esso risolve il problema di renderizzare immagini complicate, attraverso una suddivisione ricorsiva di una scena, che arriva a ottenere aree che sono banali da calcolare. In altre parole, se la scena è abbastanza semplice da calcolare in modo efficiente, viene resa; altrimenti viene divisa in parti più piccole. ^[2]

Visibilità di poligoni in una data viewport: a) il poligono riempie la viewport, b) parzialmente, c) completamente visibili, d) poligono invisibile.

Quattro passi per una divisione di una viewport per una semplice scena

Questo è un algoritmo divide et impera con run-time di ${\displaystyle O(np)}$, dove n è il numero di poligoni e p è il numero di pixel nella viewport.

Gli input sono un elenco di poligoni e una viewport (finestra di visualizzazione). Il caso migliore è che se l'elenco dei poligoni è semplice, allora i poligoni vengono disegnati nella viewport. Per "semplice" si intende se c'è un poligono (quindi il poligono o le sue parti sono disegnate in una parte appropriata della viewport) o se una viewport che vale un pixel in dimensioni (quindi quel pixel ottiene un colore del poligono più vicino all'osservatore). Il passo successivo è quello di dividere la viewport in quattro quadranti dalle dimensioni uguali e chiamare ricorsivamente l'algoritmo per ogni quadrante, con un elenco di poligoni modificato, in modo da contenere solo poligoni visibili in quel quadrante.

Voci correlate

• John Warnock
• Computer grafica
• Rendering
• Determinazione della superficie nascosta

Riferimenti

1. ^ portal.acm.org, http://portal.acm.org/citation.cfm?id=905316&dl=ACM Titolo mancante per url url (aiuto).
2. ^ ISBN 978-0-19-923400-4. Parametro titolo vuoto o mancante (aiuto)Parametro titolo vuoto o mancante (aiuto)

Link esterni

• A summary of the Warnock Algorithm