Appunti Di Metodi Numerici Per La Grafica
-
Upload
daniela-maria-ristei -
Category
Documents
-
view
146 -
download
4
Transcript of Appunti Di Metodi Numerici Per La Grafica
Scuola
Scienze
Corso di studio
Scienze e tecnologie informatiche (8013)
Sede didattica
Cesena
A.A.
2013/2014
Insegnamento
Metodi numerici per la grafica (13209)
Titolare
Prof.ssa Damiana Lazzaro
Appunti di Nicola Gentili
ultimo aggiornamento: 26/03/2014 02:00
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 1/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Introduzione
Computer Graphics (CS)
La Computer Graphics si occupa di sintesi (generazione e manipolazione) di immagini per mezzo del
computer, delle tecniche di produzione di scene rappresentanti oggetti del mondo reale o contenuti
astratti. La Computer Graphics studia le tecniche e gli algoritmi per la visualizzazione di informazioni
numeriche prodotte da un elaboratore1
.
Alcune tecniche di Computer Graphics:
Fotoritocco
effetti speciali e trasformazioni applicati
all’immagine di partenza
Image warping
trasformazione di strutture presenti in
un’immagine a fini ludici o di correzione di
deformazioni introdotte dai dispositivi di
acquisizione.
Image Processing (IP)
Image Processing è la disciplina che si occupa di analisi di immagini.
Immagini o video fornite come input, vengono analizzati tramite tecniche di Image Processing, con gli
obiettivi di ottenere:
immagini rielaborate Image Processing
misurazioni (contenuti informativi) Image Analysis
informazioni di alto livello (contenuti informativi) Image Understanding
Alcune tecniche di Image Processing sono:
Image enhancement: si occupa aumentare la nitidezza, evidenziare bordi, migliorare il
contrasto, ridurre il rumore, applicare filtri, applicare interpolazioni,
ingrandimenti o riduzioni e pseudo colorazioni. Tramite questa tecnica non
si aumenta il contenuto informativo dell’immagine.
Image restoration: si occupa di minimizzare l’effetto di degradazione dell’immagine
osservata, l’efficacia del ripristino dell’immagine dipende dalla misura e
dalla precisione della conoscenza del degrado: non ha l’obiettivo di
migliorare l’immagine.
Image compression: si occupa di minimizzare il numero di bit necessari a memorizzare
un’immagine (utilizzata in TV broadcast, telerilevamento satellitare,
comunicazioni, acquisizione immagini, …).
Computer Vision
Si occupa di riprodurre i processi percettivi propri della visione basandosi su sistemi artificiali di
acquisizione ed elaborazione dei dati.
Pattern Recognition
Si occupa di individuare la presenza di strutture più o meno complesse al fine di svolgere compiti di
riconoscimento, sorveglianza, ispezione di manufatti, individuazione di guasti, …
1
R. Scateni, P. Cignoni, C. Montani, R. Scopigno.Fondamenti di Grafica Tridimensionale Interattiva, 2005, McGraw Hill, ISBN 88-386-6215-0
Computer Graphics
Rappresentazione del mondo reale
Rendering
foto realistico
Rendering
non foto realistico
Rappresentazione
di contenuti
astratti
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 2/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Schema di un’applicazione grafica
Lo schema di massima per la realizzazione di un’applicazione grafica può essere sintetizzato in cinque
fasi:
1. Il mondo che si vuole rappresentare deve essere descritto
La descrizione comprende, in genere, tre elementi:
1.1. Gli oggetti che popolano il mondo (oggetti reali, punti nello spazio, …
gli oggetti hanno proprietà posizionali e di apparenza
1.2. L’illuminazione: le luci che sono presenti nel mondo hanno proprietà
posizionali
1.3. L’osservatore possiede proprietà posizionali, descrive gli algoritmi
necessari a generare un’immagine 2D dalla descrizione 3D del mondo
2. La produzione della descrizione ottenuta è detta modellazione
Esistono tre metodi per ottenere la modellazione:
2.1. Manuale: gli elementi sono disegnati tramite un opportuno strumento
grafico (ad esempio si disegna un cerchio con il mouse partendo da un
punto centrale e trascinando per ottenere il raggio desiderato)
2.2. Automatico: gli elementi sono acquisiti tramite strumenti appositi
(image based modeling)
2.3. Procedurale: gli elementi sono generati tramite opportune procedure (ad
esempio un cerchio è ottenuto specificando posizione del centro e
raggio)
3. La fase di rendering realizza un’immagine bidimensionale
Essa è composta dalle fasi di:
3.1. Proiezione: si deve proiettare geometricamente la scena dallo spazio 3D
alla spazio 2D dello schermo (telecamera virtuale)
3.2. Shading: si deve determinare il colore di ogni punto dell’immagine, in
funzione del colore della superficie dell’oggetto, della sua orientazione,
della posizione delle luci, dei riflessi indiretti della luce da altre superfici,
…
3.3. Rimozione delle superfici nascoste: devono essere eliminate le
superfici di elementi più lontani dalla telecamera virtuale se coperti da
altri elementi
3.4. Rasterizzazione: consiste nella mappatura dei colori di ogni punto
dell’immagine sui pixel
4. Le procedure e gli algoritmi che implementano il rendering prende il
nome di pipeline grafica
5. L’immagine viene infine visualizzata sullo schermo o salvata su file
Ciclo di vita pixar
Descrizione
Modellazione
Rendering
Pipeline grafica
Visualizzazione
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 3/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Realtà aumentata
La realtà aumentata (augmented reality) è un sistema di grafica interattiva che permette di intervenire su
un flusso di immagini video live, modificando la realtà con l’aggiunta, in tempo reale, di contenuti ed
animazioni virtuali.
Si ottiene pertanto un’integrazione delle immagini reali con immagini o informazioni virtuali (derivanti dalla
realtà riconosciuta dal sistema).
Realtà Acquisizione immagine Elaborazione Realtà aumentata
Interattività vs Non interattività
La grafica generata con un calcolatore può essere più o meno interattiva ovvero può permettere ad un
operatore di interagire in tempo reale con uno o più parametri qualsiasi della rappresentazione grafica.
Nel caso di interattività si ha necessità di hardware particolari (schede grafiche e processori potenti,
memoria) e di modelli semplificati di resa grafica (le applicazioni interattive non sono, in genere,
fotorealistiche).
Viceversa, la grafica non interattiva può raggiungere elevati qualità dell’immagine richiedendo tempo di
elaborazione.
Il video controller
Il video controller è il componente hardware responsabile di trasformare le informazioni grafiche (digitali)
in impulsi elettrici (analogici).
Tecnologia vettoriale
I primi dispositivi di output grafico basati sull’uso di monitor CRT (Cathode Ray
Tube, tubo a raggi catodici), utilizzavano tecnologia vettoriale: in questi dispositivi il
fascio di elettroni si muove liberamente da una posizione ad un’altra, guidato dal
computer, secondo l’ordine dei comandi di display; durante lo spostamento il fascio
può essere attivo o meno per cui, rispettivamente, viene modificata o meno
l’immagine sullo schermo. La tecnologia vettoriale utilizza questa tecnica detta
random scan (scansione casuale).
Tecnologia raster
Il termine raster è sinonimo di matrice: nella grafica raster ogni immagine viene
rappresentata tramite una matrice di elementi (pixel) ognuno dei quali corrisponde
ad una precisa posizione dell’immagine. L’elaborazione dell’immagine è basata su
matrici di pixel memorizzate in un’apposita area di memoria (frame buffer) della
CPU o in un’altra memoria separata. Il contenuto del frame buffer è chiamato
pixmap (da pixel map) o bitmap. La risoluzione del frame buffer (numero di bit
memorizzabili) determina la qualità dell’immagine memorizzata.
1. Valutazione della posizione
della telecamera
2. Riconoscimento degli
elementi
3. Generazione immagine
virtuale
4. Posizionamento immagine
virtuale
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 4/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
L’immagine complessiva su un display di tipo raster si ottiene effettuando una scansione sistematica
(raster scan) della matrice di pixel attraverso il fascio di elettroni scorrendo sequenzialmente linee di
scansione orizzontali composte da righe di pixel e regolando l’intensità del fascio in modo da riflettere
l’intensità di ciascun pixel. Ogni volta che un fascio completa un ciclo di scansione, il CRT è refreshed.
I vantaggi della tecnologia raster rispetto a quella vettoriale consistono in costi inferiori, possibilità di
visualizzare aree piene di colore e disegni, tuttavia la natura intrinsecamente discreta della
rappresentazione tramite matrici di pixel richiede una conversione delle primitive grafiche in matrici di
pixel che meglio le rappresentano (scan conversion), inoltre le linee curve possono apparire frastagliate.
Monitor CRT
La struttura del tubo catodico deriva direttamente dal diodo a catodo
freddo, a sua volta derivato dal tubo di Crookes, a cui è aggiunto uno
schermo rivestito di materiale fluorescente, anche chiamato tubo di
Braun.
Il catodo è un piccolo elemento metallico riscaldato all'incandescenza
che emette elettroni per effetto termoionico. All'interno del tubo
catodico, in cui è stato praticato un vuoto spinto, questi elettroni
vengono diretti in un fascio (raggi catodici) per mezzo di una elevata
differenza di potenziale elettrico tra catodo e anodo, con l'aiuto di
altri campi elettrici o magnetici opportunamente disposti per
focalizzare accuratamente il fascio. Il raggio (detto anche pennello
elettronico) viene deflesso dall'azione di campi magnetici (Forza di
Lorentz, deflessione magnetica) o campi elettrici (deflessione
elettrostatica) in modo da arrivare a colpire un punto qualunque sulla
superficie interna dello schermo, l'anodo. Questa superficie è rivestita
di materiale fluorescente (detti fosfori, in genere metalli di transizione oppure terre rare) che eccitato
dall'energia degli elettroni emette luce.
Monitor LCD
L'LCD è basato sulle proprietà ottiche di particolari sostanze
denominate cristalli liquidi. Tale liquido è intrappolato fra due
superfici vetrose provviste di numerosissimi contatti elettrici con i
quali poter applicare un campo elettrico al liquido contenuto. Ogni
contatto elettrico comanda una piccola porzione del pannello
identificabile come un pixel (o subpixel per gli schermi a colori), pur
non essendo questi ultimi fisicamente separati da quelli adiacenti
come avviene invece in uno schermo al plasma. Sulle facce esterne
dei pannelli vetrosi sono poi posti due filtri polarizzatori disposti su
assi perpendicolari tra loro. I cristalli liquidi torcono di 90° la
polarizzazione della luce che arriva da uno dei polarizzatori,
permettendole di passare attraverso l'altro.
Prima che il campo elettrico sia applicato, la luce può passare
attraverso l'intera struttura, e, a parte la porzione di luce assorbita
dai polarizzatori, l'apparecchio risulta trasparente. Quando il campo elettrico viene attivato le molecole del
liquido si allineano parallelamente al campo elettrico, limitando la rotazione della luce entrante. Se i
cristalli sono completamente allineati col campo, la luce che vi passa attraverso è polarizzata
perpendicolarmente al secondo polarizzatore, e viene quindi bloccata del tutto facendo apparire il pixel
non illuminato. Controllando la torsione dei cristalli liquidi in ogni pixel, si può dunque regolare quanta
luce far passare. Si noti però che in questo modo un pixel guasto apparirà sempre illuminato. In realtà
Sezione schematica di un tubo a raggi
catodici monocromatico
1) Controllo della griglia
2) Anodo
3) Bobina deflettrice
4) Riscaldatore
5) Catodo
6) Fascio di elettroni
7) Bobina di messa a fuoco
8) Schermo fluorescente
Componenti di un LCD twisted nematic
riflettivo
1) Polarizzatore verticale
2) Schermo di vetro con maschera delle
zone scure
3) Strato con i cristalli liquidi
4) Strato di vetro con elettrodi
5) Polarizzatore orizzontale
6) Superficie riflettente
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 5/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
alcune tipologie di pannelli funzionano all'opposto, cioè sono trasparenti quando accesi ed opachi quando
spenti per cui un pixel guasto resta sempre opaco.
Monitor LED
OLED è l'acronimo di Organic Light Emitting Diode ovvero diodo organico a emissione di luce.
Tecnologia che permette di realizzare display a colori con la capacità di emettere luce propria: a differenza
dei display a cristalli liquidi, i display OLED non richiedono componenti aggiuntivi per essere illuminati (i
display a cristalli liquidi vengono illuminati da una fonte di luce esterna), ma producono luce propria;
questo permette di realizzare display molto più sottili e addirittura pieghevoli e arrotolabili, e che
richiedono minori quantità di energia per funzionare.
A causa della natura monopolare degli strati di materiale organico, i display OLED conducono corrente solo
in una direzione, comportandosi quindi in modo analogo a un diodo; di qui il nome di O-LED, per
similitudine con i LED.
I monitor LED presentano una migliore qualità dei colori rispetto ai monitor LCD e hanno durata superiore,
inoltre rendono possibile la realizzazione di schermi sottilissimi.
Pipeline di rendering
La pipeline di rendering descrive come viene effettuato il passaggio di rendering dalla rappresentazione
interna dell’universo virtuale 3D all’immagine masterizzata da visualizzare sul dispositivo bidimensionale.
I video controller si sono evoluti:
prima degli anni ’90, i controller VGA (Video and Graphics Array controller) utilizzavano una
memoria DRAM chiamata frame buffer e un generatore di segnali (RAMDAC) collegato direttamente
al video, erano basati su grafica vettoriale
tra il 1990 e il 1997 si sono aggiunte funzioni ai controller VGA: gestione triangoli, rasterizzazione
triangoli, shading
verso il 2000 si è realizzato un chip integrato che incorpora tutti gli elementi di una pipeline di
rendering: nasce la Graphics Processing Unit (GPU)
dopo il 2005, la GPU si è evoluta implementando aritmetica in virgola fissa e mobile e si sono
realizzate GPU programmabili tramite API di alto livello (OpenGL, Direct3D)
dopo il 2008 i processori sono paralleli e multithread: Streaming Processors (SP) a flusso continuo,
organizzati in Streaming Multiprocessors;
o la memoria è condivisa su due livelli: dentro gli Streaming Multiprocessors tra Streming
Processors e tramite una rete di interconnessione tra gli Streaming Multiprocessors.
Architettura di una GPU unificata
Architettura TESLA
Nvidia GeForce 8800
112 Streaming Processors
14 Streaming Multiprocessors
96 thread per ogni SM
DRAM a 64 bit
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 6/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Programmazione grafica
La programmazione grafica è realizzata su tre livelli:
1. API grafiche: OpenGL, Direct3d
Si tratta di API di alto livello che definiscono logicamente le pipeline di rendering: l’applicazione si
sviluppa definendo i vari stadi con primitive di alto livello e i dettagli sono nascosti agli sviluppatori
e gestiti dalle API
2. Linguaggi di shading: GLSL, HLSL, Ch
Gestiscono tre tipi di shader:
o Shader dei vertici: mappano la posizione dei vertici dei triangoli nello
schermo, modificano posizione, colore e orientamento
o Schader delle geometrie: lavorano sulla base di primitive geometriche definite
come insiemi di vertici, le modificano e ne aggiungono
di nuove
o Shadere dei pixel (o dei frammenti): dipingono i pixel sullo schermo e gestiscono artefatti
visivi
Gli shader sono “programmati a flusso continuo” cioè su sequenze ininterrotte di dati, le strutture
dati su cui operano consentono un elevato parallelismo e quindi possono essere lanciati più thread
dello stesso shader.
3. API di programmazione diretta dei core SP: CUDA, OpenCL
Si tratta di API di programmazione general purpose su GPU (GPGPU), tramite il loro utilizzo il
problema viene parallelizzato sull’architettura: il programmatore CUDA, ad esempio, scrive una
procedura detta kernel che istanzia tante esecuzioni di thread paralleli, i thread sono organizzati
gerarchicamente in blocchi mono, bi o tridimensionali organizzati in griglie anch’esse mono, bi o
tridimensionali; il mapping dipende dai core SP disponibili ed è scelto dal programmatore.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 7/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Model and view
transformations
Lighting
Projection
Clipping
Screen mapping
Fragment
generation
Texture mapping
and shading
Z-Buffer
Blending
La pipeline di rendering
La pipeline di rendering si suddivide in due parti:
1. Sottosistema geometrico: porta la geometria del modello nelle coordinate dello schermo
2. Sottosistema raster: accende i pixel dello schermo con il giusto colore in funzione della geometrica,
dell’illuminazione e delle texture.
Queste due parti sono affidate, nei sistemi programmabili, a due shader:
1. Vertex shaker: calcola le trasformate geometriche per ogni vertice del modello
2. Pixel (Fragment) shader: calcola il colore per ogni pixel.
Sottosistema geometrico
Model and view transformation
Agli oggetti, definiti nel loro sistema di coordinate (object space)
vengono applicate le trasformazioni di modellazione che portano il
modello nel sistema comune del mondo da rappresentare (world space),
successivamente vengono applicate le trasformazioni per ottenere le coordinate
degli oggetti dal punto di vista dell’osservatore.
Lighiting
Projecton
Tutto ciò che si trova all’interno del volume di vista (view frustum) viene proiettato; il view frustum viene
così trasformato in un cubo di lato unitario (normalized device coordinates).
Clipping
Le primitive geometriche al di fuori del cubo ordinario (fuori dal volume di vista)
sono scartate e non proseguono l’elaborazione; quelle che intersecano il cubo sono
modificate secondo l’intersezione.
Screen mapping
La scena viene infine mappata sulle coordinate dello schermo (screen space).
Applicazione
grafica (CPU)
Sottositema
geometrico
Sottosistema
raster Frame buffer Frame buffer Display
Pipeline di rendering
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 8/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Spazi di coordinate
È necessario considerare, in un’applicazione grafica:
uno spazio di coordinate del modello (modeling coordinates)
si tratta dello spazio rispetto al quale ogni singolo oggetto viene modellato
uno spazio di coordinate del mondo (world coordinates system)
descrive in modo unificato l’intero universo dell’applicazione
uno spazio di coordinate del dispositivo (device coordinates system)
è definito dalla periferica utilizzata.
Entità geometriche
Punto - entità geometrica caratterizzata da un solo attributo: la posizione rispetto ad un sistema di
riferimento
Vettore - entità geometrica caratterizzata da due attributi: lunghezza e direzione
Lunghezze e angoli sono espresse mediante scalari.
Le trasformazioni geometriche sono gli strumenti che permetto di manipolare punti e vettori all’interno
del mondo dell’applicazione grafica, esse sono funzioni che mappano un’entità in un’altra entità.
La trasformazione di una primitiva geometrica si riduce alla trasformazione dei punti caratteristici (vertici)
che la identificano nel rispetto della connettività originale (trasformazioni affini).
Trasformazioni geometriche affini
Sono trasformazioni lineari:
che preservano:
- collinearità: i punti di una linea giacciono ancora su una linea dopo la trasformazione
- rapporto tra le distanze: il punto medio di un segmento rimane il punto medio di un segmento
anche dopo la trasformazione
Le trasformazioni geometriche permettono di traslare, ruotare, scalare o deformare oggetti che siano stati
modellati nel loro spazio di coordinate permettendo di istanziarli nel modello con attributi (posizione,
orientamento, fattori di scala) diversi nello spazio di coordinate del mondo (permettono il passaggio dal
sistema di coordinate locali al sistema di coordinate del mondo).
Ogni oggetto, a partire dal proprio sistema di riferimento, viene trasformato opportunamente in un sistema
di riferimento comune per entrare a far parte della scena finale.
Trasformazioni geometriche nel piano
Trasformazioni di base:
Traslazione
Traslare una primitiva geometrica nel piano significa muovere ogni suo punto P(x,y) di dx
unità lungo l’asse
x e di dy
unità lungo l’asse y fino a raggiungere una nuova posizione P(x’,y’) dove x’ = x + dx
e y’ = y + dy
In notazione matriciale:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 9/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Scalatura
Scelto un punto C (fisso) di riferimento, scalare una primitiva geometrica significa riposizionare rispetto a C
tutti i suoi punti in accordi a fattori di scala sx
(lungo l’asse x) e sy
(lungo l’asse y) scelti.
Se il punto fisso è l’origine O degli assi, la trasformazione di P in P’ si ottiene con x’ = sx
∙ x y’ = sy
∙ y
In notazione matriciale (S pre-moltiplica P in quanto P è definito come vettore colonna):
Osservazioni:
fattori di scala inferiori a 1 avvicinano l’oggetto al punto fisso di riferimento
fattori di scala superiori a 1 lo allontanano
se sx
≠ sy
le proporzioni dell’oggetto non sono mantenute e si parla di scalatura non uniforme
se sx
= sy
le proporzioni dell’oggetto sono mantenute e si parla di scalatura uniforme
Rotazione
Fissato un punto C (pivot) di riferimento ed un verso di rotazione (orario o antiorario), ruotare una primitiva
geometrica attorno a C significa muovere tutti i suoi punti nel verso assegnato in maniera che si conservi,
per ognuno di essi, la distanza da C.
Una rotazione di θ attorno all’origine O degli assi è definita come:
x’ = x ∙ cos θ – y sen θ e y’ = x ∙ cos θ + y sen θ
la relazione tra P’ e P si ricava trigonometricamente, le coordinate di P possono essere espresse in
coordinate polari: x = r ∙ cos θ y = x ∙ sin θ
∙ ∙ ∙ ∙ ∙ ∙ ∙
∙ ∙
∙ ∙
∙ ∙ ∙ ∙ ∙ ∙ ∙
∙ ∙
∙ ∙
In notazione matriciale:
Osservazioni:
gli angoli sono considerati positivi quando misurati in senso orario
per le rotazioni di angoli negativi si ricorre alle identità:
cos ( - θ ) = cos ( θ ) sin ( - θ ) = - sin ( θ )
Coordinate omogenee
Le trasformazioni geometriche possono essere applicate in sequenza di una somma di vettori (traslazione)
e di moltiplicazioni (scalatura e rotazione) rende disomogenea la concatenazione di trasformazioni:
Il punto P di coordinate ( x, y ) è rappresentato, in coordinate omogenee come ( xh
, yh
, w ), dove:
x = xh
/ w y = yh
/ w w ≠ 0
Due punti di coordinate ( x, y, w ) e ( x’, y’, w’ ) rappresentano lo stesso punto del piano se e solo se le
coordinate di uno sono multiple delle corrispondenti coordinate dell’altro.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 10/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Quanto w = 1 (forma canonica), coordinate cartesiane ed omogenee coincidono.
Con ( x, y, w ≠ 0 ) si rappresentano punti. Con ( x, y, 0 ) si rappresentano vettori.
Trasformazioni di base in coordinate omogenee
∙
∙
∙
Altre trasformazioni comuni (ma derivabili dalle precedenti):
∙
∙
∙
Deformazione (shear)
∙
∙
∙
Composizione di trasformazioni
La rappresentazione in coordinate omogenee permette la concatenazione di trasformazioni. Le
trasformazioni geometriche non sono, generalmente, commutative, per questo motivo l’ordine con cui
vengono applicate non è ininfluente.
La corretta sequenza delle trasformazioni T1
, T2
, T3
, T4
si ottiene componendo T = T4
∙ T3
∙ T2
∙ T1
L’immagine a fianco mostra un esempio di non commutatività
della composizione di trasformazioni: una traslazione e una
Dalle relazioni
x’ = x + ay e y’ = y + bx
si evince che la deformazione lungo l’asse
x è linearmente dipendente dalla
coordinata y e la deformazione in y è
strettamente correlata all’ascissa del
punto
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 11/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
rotazione attorno all’origine, se applicate in ordine diverso, realizzano un esito differente.
Una rotazione oraria di un angolo θ attorno ad un punto P generico è una composizione di:
una traslazione che sposta P nell’origine degli assi
una rotazione attorno all’origine
una traslazione opposta alla prima che riporta P alla sua posizione originale:
∙
∙
Una trasformazione di scalatura attorno ad un punto P generico è una composizione di:
una traslazione che sposta P nell’origine degli assi
una trasformazione di scala attorno all’origine
una traslazione opposta alla prima che riporta P alla sua posizione originale:
∙
∙
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 12/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Trasformazione Window to viewport
Si tratta di una delle trasformazioni più comuni che il sistema grafico deve realizzare: quella dalle
coordinate del mondo a quelle del dispositivo di output; al termine del rendering si ottengono sempre
valori nel sistema di coordinate dello schermo (device coordinate system).
Si effettua definendo una porzione rettangolare del mondo (window) e mappandola su un rettangolo dello
schermo (viewport).
Definiti window e viewport si deve calcolare la trasformazione che effettua tale mapping tramite una
matrice definita in tre stadi:
1. la window è traslata nell’origine del sistema di coordinate
2. la dimensione della window è scalata sino ad essere uguale alla dimensione della viewport
3. la viewport è traslata nella posizione finale nel sistema di coordinate del dispositivo.
La matrice che realizza tale trasformazione è:
∙
∙
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 13/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Trasformazioni 3D
Come tutte le trasformazioni nel piano possono essere rappresentate (in coordinate omogenee) da matrici
3x3, le trasformazioni nello spazio possono essere rappresentate da matrici 4x4.
Nello spazio un punto in coordinate omogenee è rappresentato da una quadrupla (x, y, z, w).
Traslazione
Scalatura
La rotazione 3D è descritta da una matrice più complessa: ogni rotazione 3D può essere ottenuta come
composizione di 3 rotazioni attorno ai 3 assi:
Rotazione intorno all’asse x
Rotazione intorno all’asse y
Rotazione intorno all’asse z
Nel caso più generale, una volta fissato l’asse di rotazione e l’angolo di rotazione, la trasformazione può
essere effettuata applicando i cinque passi seguenti:
1. l’oggetto è traslato in maniera tale che l’asse di rotazione passi per l’origine degli assi cartesiani
2. l’oggetto è ruotato in maniera tale che l’asse di rotazione coincida con uno degli assi cartesiani
3. l’oggetto è ruotato nel verso e per la quantità angolare richiesta
4. l’oggetto è ruotato in maniera inversa rispetto alla rotazione effettuata al passo 2 in modo tale che
l’asse di rotazione assuma la direzione finale
5. l’oggetto è traslato in maniera inversa rispetto alla traslazione effettuata al passo 1 in modo tale
che l’asse di rotazione sia riprtata alla sua posizione iniziale.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 14/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Il processo di vista in 3 dimensioni
Le proiezioni
Una proiezione è una trasformazione geometrica con il dominio di uno spazio di dimensione n ed il
codominio in uno spazio di dimensione n-1 (o minore).
Una proiezione di un oggetto 3D è definita da un insieme di rette
parallele (proiettori) aventi origine comune da un centro di
proiezione, che passano per tutti i punti dell’oggetto e
intersecano un piano di proiezione per formare la proiezione vera
e propria.
In queste proiezioni, dette proiezioni geometriche piane:
- i proiettori sono rette (potrebbero essere curve generiche)
- la proiezione è effettuata su un piano (potrebbe essere
una superficie generica).
Le proiezioni geometriche piano possono essere categorizzate in:
proiezioni prospettiche: la distanza tra il centro di
proiezione e il piano di proiezione è finita
parallele: la distanza tra il centro di proiezione e il piano di
proiezione è infinita
Proiezioni prospettiche
Le proiezioni prospettiche sono più realistiche in quanto
riproducono il modo con cui nella realtà sono visti gli oggetti:
oggetti più vicini appaiono più grandi e viceversa.
La proiezione di ogni insieme di linee parallele non parallele al piano di proiezione, converge in un punto
detto vanishing point (punto di convergenza). Il numero di questi punti è infinito, come il numero di
possibili direzioni di fasci di rette parallele.
Se l’insieme di linee parallele è a sua volta parallelo ad uno degli assi coordinati, il punto di convergenza si
chiama axis vanishing point. Possono esiste al massimo tre axis vanishing point.
Le proiezioni si possono classificare in base al numero di vanishing point principali (numero di assi del
sistema di coordinate che intersecano il piano di proiezione).
1 punto di fuga 2 punti di fuga 3 punti di fuga
Proiezioni prospettiche
Proiezioni parallele
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 15/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Proiezioni parallele
Le proiezioni parallele, utilizzate nel disegno tecnico per poter effettuare misurazioni sul risultato della
proiezione stessa, mantengono le linee parallele del modello tridimensionale.
Queste proiezioni si classificano in base alla relazione tra la direzione di proiezione e la normale al piano di
proiezione: se la direzione di proiezione coincide con la normale si parla di proiezioni ortografiche,
altrimenti si parla di proiezioni oblique.
Proiezioni ortografiche
Proiezioni ortografiche assonometriche:
proiezioni ortografiche con l’asse di proiezione non allineata con una delle assi principali
Proiezione (assonometria) isometrica: la direzione di proiezione è identificata da una delle bisettrici degli
ottanti dello spazio cartesiano
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 16/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Proiezioni oblique:
tipo più generale di proiezioni parallele, caratterizzate dal fatto che i proiettori possono formare un angolo
qualsiasi con il piano di proiezione; i più frequenti casi di proiezione obliqua sono:
la proiezione Cavaliera, in cui la direzione di proiezione forma un angolo di 45° con il piano di proiezione e
quindi le linee ortogonali al piano conservano la loro lunghezza
la proiezione Cabinet, in cui la direzione forma un angolo di arctan(2) = 63.4°, e quindi le linee
perpendicolari al piano hanno lunghezza pari alla metà di quella reale
Proiezioni planari
geometriche
Parallele
Ortografiche
Dall'alto Di fronte Laterali Assono-
metriche
Isometriche
Altre
Oblique
Cavaliere
Cabinet
Altre
Prospettiche
1 punto di fuga
2 punti di fuga
3 punti di fuga
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 17/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
I parametri della vista 3D
La vista in 3 dimensioni non è definita unicamente dalla proiezione ma anche dal volume di vista, cioè dalla
regione dello spazio tridimensionale che include solamente gli oggetti visibili. Proiezione e volume di vista
forniscono tutte le informazioni necessarie per clippare e proiettare.
Le entità fondamentali nella sintesi automatica di scene 3D sono gli oggetti sintetici che descrivono la
scena e un osservatore che definisce il punto di vista, la direzione di osservazione e l’angolo di vista
ovvero la porzione di scena inquadrata.
La metafora più utilizzata per la descrizione delle relazioni osservatore-scena è quella della macchina
fotografica virtuale (synthetic camera). Si tratta di un apparecchio fotografico molto semplice costituito da
un parallelepipedo con un foro di diametro infinitesimo (pinhole camera) sulla faccia anteriore tramite il
quale, sulla faccia posteriore coincidente con la pellicola
fotografica, si formano le immagini. I raggi luminosi
attraversano il foro e impressionano la pellicola
riproducendo un’immagine ruotata di 180° dell’oggetto
fotografato. Le immagini che si formano sono nitide,
senza problemi di luminosità; l’angolo θ di vista può
essere modificato variando il rapporto tra la distanza focale d
(dimensione della scatola) e la dimensione h del piano dell’immagine.
Dalla relazione di similitudine tra i due triangoli che si formano si può
ricavare che il generico punto P = ( x, y, z ) della scena avrà
coordinate
P = ( xp
, yp
, -d ) sul piano dell’immagine dove:
Per convenzione si assume l’esistenza di un piano virtuale di
identiche dimensioni del piano di proiezione posto a distanza d
dal centro di proiezione.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 18/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Definire i parametri di una vista sintetica
Mondo reale Passo Con l’utilizzo del computer
Disporre gli
oggetti da
fotografare nella
scena
1
Impostare la modelling transformation
Consiste nella definizione degli oggetti della scena in un sistema di coordinate
conveniente e nella loro trasformazione nel sistema di coordinate del mondo.
Sistemare la
macchina
fotografica
2
Impostare la viewing transformation
Consiste nel definire il volume che contiene gli oggetti visibili, ovvero il
poliedro individuabile dal rettangolo che ne costituisce la sezione e dalle
quattro rette che passano attraverso i vertici del rettangolo.
Per le proiezioni prospettiche il volume è una piramide semi-infinita con vertice
nel PRP e spigoli che passano attraverso i vertici della finestra sul piano di
vista.
Per limitare il numero di primitive proiettate il volume di vista deve essere
finito e limitato tramite un front clipping plane e un back clipping plane
paralleli al piano di vista con VPN come normale; essi sono specificati da una
front distance (F) e una back distance (B).
Scegliere una
lente o
aggiustarlo zoom
3
Impostare la projection transformation
Il piano di proiezione (o piano di vista) è definito da un punto sul piano (detto
view reference point, VRP) e dalla normale al piano in questo punto (detta view
plano normal, VPN); il piano di vista può trovarsi ovunque rispetto agli oggetti
del mondo che devono essere proiettati (davanti, dietro o tra gli oggetti).
Il centro di proiezione (COP) e la direzione di proiezione (DOP) sono definiti da
un projection reference poiint (PRP); se la proiezione è di tipo prospettiva il PRP
coincide con il centro di proiezione; se la proiezione è di tipo parallelo, la
direzione di proiezione va dal PRP al centro della finestra.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 19/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Mondo reale Passo Con l’utilizzo del computer
Scegliere la
dimensione dalla
foto 4
Impostare la viewport transformation
Si deve definire un sistema di coordinate (u, v, n) detto 3D viewing coordinate
system, VRC con origine in VRP; l’asse v è definito per proiezione del view-up
vector VUP sul piano di vista; l’asse u è ortogonale agli altri due ed è scelto in
modo da formare un sistema di coordinate right-handed; il contenuto della
finestra sul piano di vista sarà mappato sulla viewport e qualunque parte del
mondo 3D proiettata sul piano di vista, ma fuori dalla finestra, non sarà
visualizzata.
Il contenuto del volume di vista deve essere mappato sulla superficie del
dispositivo di output, per farlo deve essere trasformato da coordinate del
mondo a coordinate normalizzate di proiezione (normalized projection
coordinates, NPC): il volume di vista viene trasformato in un volume canonico
in nuove coordinate, il risultato è mappato sul 3D viewport; disegnano le
primitive ignorando la z, si ottiene l’immagine da mandare al display.
Matematica delle proiezioni
∙
∙
∙ ∙
∙
∙
∙
∙
Clipping
Fare il clipping in coordinate nel mondo (WC) è molto oneroso; pertanto si
effettua prima la normalizzazione (riduzione del volume di vista ad un volume
canonico).
Esistono due volumi canonici, si effettua la moltiplicazione per le matrici di
normalizzazione, poi si effettua il clipping, poi la proiezione ed infine si porta
alle coordinate del dispositivo.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 20/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Sottosistema raster
Il sottosistema raster si occupa di passare dalla proiezione continua in screen space ai pixel dell’immagine
visualizzata. Si parla più precisamente di frammenti poiché alcuni di essi diverranno parte dell’immagine
finale e altri no. I frammenti sono pixel potenziali.
Il sottosistema raster si occupa inoltre di rimuovere le superfici nascoste (Z-buffer) e applicare le texture.
Nei sistemi moderni la funzione di illuminazione è deferita dal sottosistema geometrico al sottosistema
raster.
La rasterizzazione è legata a tutto ciò che comporta il prendere una decisione sul colore di un pixel da
accendere sullo schermo; costituisce la parte finale della pipeline di rendering (è solitamente inserita nel
ciclo dell’algoritmo scan-line) ed è affidata al fragment (o pixel) shader che determina se le proprietà di
colore di un pixel possono essere propagate ad un intero frammento di linea di scansione in modo da
applicare gli algoritmi coinvolti in parallelo.
Algoritmi
Algoritmi per il drawning (tracciamento di primitive 2D ed eventuali proiezioni di primitive 3D)
o DDA
o Midpoint
Algoritmi per il filling (riempimento di una figura chiusa con un colore solido, sfumatura,
trama, trasparenza tra più colori, …)
Algoritmi per il clipping (troncamento di una linea rispetto ad altre linee presenti: poligoni che
si occludono, bordi esterni dell’immagine ovvero del front pane del
volume di vista mappato sullo schermo)
o Cohen-Sutherland
Antialiasing (riduzione dell’effetto di sotto-campionamento dell’immagine generata
dovuto alla risoluzione spaziale fissa data dalla dimensione dei pixel)
o Unweighted Area Sampling
o Weighted Area Sampling
Drawing
Per tracciare un segmento di retta all’interno della griglia di pixel che hanno distanza unitaria in ascissa e
ordinata, l’algoritmo di drawing deve individuare le coordinate dei pixel che giacciono sulla linea ideale o
che sono il più vicino possibile ad essa: la sequenza di pixel deve approssimare al meglio il segmento; lo
spessore minimo del segmento masterizzato risulterà uguale ad un pixel.
Per coefficienti angolari minori o uguali ad 1, la rasterizzazione presenta un pixel per ogni colonna; per
coefficienti angolari maggiori di 1, la rasterizzazione presenta un pixel per ogni riga.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 21/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Algoritmo DDA (digital differential analyzer)
Regola:
e e
e e
Algoritmo:
calcola m = ( y1 – y0 ) / ( x1 – x0 )
se |m| <= 1 allora
y := y0
ripeti per x = x0; x <= x1; x++
accendi il punto ( x, round(y) )
y += m
altrimenti
x := x0
ripeti per y = y0; y <= y1; y99
accendi il punto ( round(x), y )
x += ( 1 / m )
Algoritmo di Bresenham (midpoint)
L’algoritmo di Bresenham (algoritmo del punto di mezzo) risolve il problema dell’errore introdotto dall’uso
di aritmetica floating point nell’algoritmo DDA: fa uso unicamente di operazioni in aritmetica intera. Si
tratta di un algoritmo di tipo differenziale: fa uso delle informazioni calcolate per individuare il pixel al
passo i per individuare il pixel al passo i + 1.
L’idea di base di questo algoritmo è di individuare, passo dopo passo, il pixel più vicino all’effettivo punto
Q di intersezione tra la retta e l’ascissa x = xp
+ 1 corrispondente al successivo punto da accendere. Ad
ogni passo i candidati sono solo i due pixe E ( xp
+ 1, yp
) e NE ( xp
+ 1, yp
+ 1 ) (assumendo m > 1 per
semplicità).
Per scegliere il punto si valuta il passaggio della retta, espressa nella
forma implicita F ( x , y ) = ax + by + c = 0 nel punto medio
M ( xp
+ 1 , yp
+ ½ )
Algoritmo:
ripeti per ogni punto da accendere
se F ( M ) > 0 //la retta passa sopra M
accendi NE
altrimenti // F ( M ) <= 0, la retta passa per M
// oppure sotto M
accendi E
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 22/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
L’implementazione è incrementale; considerando l’equazione della retta in forma implicita:
è possibile ottenere la forma esplicita: ∙ ∙ ∙
Si definisce una variabile di decisione d:
Per d > 0 si accenderà NE, mentre per d 0 si accenderà E.
L’algoritmo consiste nel calcolare, incrementalmente, solo la variabile di decisione:
se ad un certo passo p+1 si accende il pixel E, allora il nuovo valore della variabile dnew
, noto dold
al passo
precedente p, si ottiene come:
viceversa, se ad un certo passo p+1 si accende il pixel NE, allora il nuovo valore della variabile dnew
, noto dold
al passo precedente p, si ottiene come:
Il processo si inizializza calcolando il valore di partenza: partendo da ( x0
, y0
) si calcola dstart
:
È possibile eliminare la divisione ed utilizzare solo l’aritmetica intera facendo riferimento ad una nuova
variabile di decisione 2d che deve essere confrontata con il valore 0 ad ogni passo:
Algoritmo:
dx := x1 – x0
dy := y1 – y0
dstart := 2dy – dx
deltaE := 2( dy – dx )
deltaNE := 2( dy )
x := x0
y := y0
d := start
ripeti finché x < x1
se d <= 0 allora
d += deltaE
x ++
altrimenti
d += deltaNE
x++
y++
accendi il pixel ( x , y )
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 23/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Algoritmo Midpoint per circonferenze o ellissi
L’equazione implicita di una circonferenza: F ( x , y ) = x2
+ y2
– R2
= 0
fornisce 2 valori di y per un dato valore di x.
Si calcola allora il midpoint per il primo ottante x ∈ [ 0 , R / √2 ] e poi si
replica per gli altri.
Partendo dal punto di valutazione della circonferenza P = ( xp
, yp
) si
sceglie il successivo pixel da accendere sulla base del punto medio:
M ( xp
+ 1, yp
– ½ ) tra i pixel E ed SE di P.
La variabile di decisione è definita come l’equazione implicita della
circonferenza valutata in M:
se F ( M ) > 0 // M giace o è esterno alla circonferenza
accendi SE
altrimenti // F(M) < 0 cioè interno alla circonferenza
accendi E
Allo stesso modo di come si calcolano gli incrementi per le rette, si possono calcolare i due incrementi
della variabile di decisione al generico passo p + 1, noto il valore dold della variabile di decisione al passo,
nei due casi in cui venga accesso il pixel E o SE. Nel caso di accensione, al passo p, di E:
Mentre nel caso di accensione di SE:
dstart
è valutato nel punto ( 0 , R ) che è l sommità dell’ottante (per mantenere l’uso dell’aritmetica intera si
considera h = d – ¼ hstart
= 1 – R; h si confronta sempre con 0):
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 24/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Algoritmo:
void MidpointCirlce (int radius, int value)
// si assume che il centro della circonferenza sia all’origine
// si utilizza solo l’aritmetica intera
{
int x = 0;
int y = radius;
int d = 1 – radius;
circlePoints(x, y, value);
while (y > x)
{
if (d < 0) /* select E */
d += 2 * x + 3;
else /* select SE */
{
d += 2 * (x – y) + 5;
y—-;
}
x++;
circlePoints(x, y, value);
}
}
Per quanto riguarda le ellissi, l’algoritmo è lo stesso a meno del valore della F ( x , y ); inoltre, per ogni
quadrante, si individuano due regioni separate dal punto in cui il vettore di gradiente F è inclinato a 45°,
esse differiscono per i punti candidati all’accensione ad ogni passo.
Filling
L’algoritmo di filling opera incrementalmente sulle scan-line: una
volta effettuato il filling del poligono su una scan-line, l’algoritmo
sfrutta le informazioni travate per aggiornare incrementalmente le
intersezioni e fare il filling sulla scan-line successiva.
Per ogni scan-line:
Devono essere individuate le intersezioni della scan-line con tutti gli spigoli del poligono
Si devono ordinare le intersezioni sulla coordinata x
Si devono selezionare tutti i pixel, tra coppie di intersezioni, che sono interni al poligono.
Per la determinazione dei pixel interni (per determinare se un pixel appartiene ad un poligono), si usa la
regola di odd-parity: si utilizza un bit (flag) di parità che può assumere valore pari o dispari; la parità è
inizialmente pari, ogni intersezione cambia il bit di parità, se il bit è dispari allora i pixel fanno parte del
poligono, viceversa se è pari.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 25/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Devono essere considerati quattro casi distinti:
1. Intersezione su un generico valore x non
intero
Effettuando lo scan-line, se si incontra
l’intersezione provenendo da dentro il
poligono (parity bit dispari), si arrotonda
all’intero inferiore; viceversa si arrotonda
ll’intero superiore
2. Intersezione su un generico valore x di coordinate intere
L’intersezione a coordinate intere all’estremo sinistro della linea di pixel
è interna al poligono, all’estremo destro è invece esterna al poligono
3. Intersezione in un vertice (sempre coordinate intere)
Nel calcolo del parity bit si considera solo il vertice con y minima e non
quello con y massima
4. Vertici che definiscono uno spigolo orizzontale
I vertici di una linea orizzontale non influiscono sul parity bit, in modo
automatico (vedi caso 3) i lati orizzontali bassi del poligono sono
disegnati, mentre quelli alti sono omessi.
Clipping
L’operazione di clipping consiste nell’individuare e rimuovere le primitive grafiche, o parti di esse, esterne
alla viewport o nascoste da altri elementi. Si tratta di un problema intrinsecamente legato al 3D, ma si
verifica anche nel 2D quando bisogna determinare l’estensione di curve proiettate sullo schermo.
Clipping di un punto
Un punto è all’interno del rettangolo di clipping se e solo se sono
soddisfatte 4 disuguaglianze:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 26/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Clipping di un segmento
Per effettuare il clipping di un segmento è necessario analizzare le posizioni dei suoi punti estremi:
se sono entrambi all’interno del rettangolo di clipping, il segmento è interno
se un estremo è interno e l’altro esterno, allora il segmento interseca il rettangolo di clipping ed è
necessario determinare l’intersezione
se entrambi gli estremi sono esterni al rettangolo si rende necessaria un’analisi ulteriore per
individuare le eventuali parti interne del segmento che può
o essere completamente esterno all’are di clipping
o attraversare l’area di clipping.
Ad esempio, nella figura sono rappresentati alcuni
segmenti:
AB: interno
CD: interseca l’area di clipping
EF e IJ: entrambi i punti estremi sono esterni all’area di
clipping e tutto il segmento è esterno
GH: entrambi i punti estremi sono esterni all’area di
clipping ma il segmento interseca l’area di clipping
Un approccio diretto alla soluzione del problema dei punti estremi esterni, consiste nel determinare le
intersezioni tra la retta su cui giace il segmento e le quattro rette su cui giacciono i lati del rettangolo di
clipping: una volta individuati i punti di intersezione occorre verificare l’effettiva appartenenza al
rettangolo di clipping.
Le intersezioni si determina mediante l’equazione parametri dei segmenti relativi:
∈
Per ogni coppia segmento-lato di rettangolo si risolve il sistema di equazioni parametriche che definiscono
il segmento in funzione di tsegm
ed il lato in funzione di tlato
. Se entrambi assumono valori nell’intervallo [0,1]
allora l’intersezione appartiene al segmento ed al rettangolo di clipping. L’eventuale parallelismo va
verificato prima di determinare l’intersezione.
Tuttavia questo tipo di algoritmo è costo e inefficiente.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 27/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Algoritmo di Cohen-Sutherland
L’idea di base di questo algoritmo consiste nel fatto che le rette che delimitano il rettangolo di clipping
suddividono il piano in nove regioni; ad ogni regione viene associato un codice numero di quattro cifre
binarie:
bit 1: sopra edge alto y > ymax
bit 2: sotto edge basso y < ymin
bit 3: a destra edge destro x > xmax
bit 4: a sinistra edge sinistro x < xmin
Il clipping di un segmento prevede la codifica dei suoi estremi sulla base delle regioni di appartenenza ed il
confronto:
1. se il codice di entrambi gli estremi è 0000 (OR logico), allora si può
assumere che il segmento è interamente interno al rettangolo di clipping
2. se l’operazione di AND logico tra i codici degli estremi restituisce un
risultato non nullo, allora il segmento è esterno all’area di clipping (gli
estremi giacciono in uno stesso semipiano)
3. se il risultato dell’AND è nullo, allora il segmento potrebbe attraversare
l’area di clipping e si procede come segue:
a. Si individua l’intersezione tra il segmento
ed il lato relativo al primo bit discordante
tra i codici (bit 1, y = ymax
)
b. L’estremo con bit a 1 viene sostituito dal
nuovo vertice
c. Si itera il procedimento
d. Ad ogni iterazione si controlla l’eventuale terminazione del processo (OR logico nullo)
L’algoritmo rimuove progressivamente le parti esterne. Risulta efficiente se molti dei segmenti da
clippare sono completamente esterni al rettangolo di clipping.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 28/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Ripeti
Valuta i codici dei due estremi
Se entrambi i codici sono nulli
La linea è totalmente visibile // caso AB
Altrimenti se l’AND bit a bit degli estremi è diverso da 0
La linea è totalmente invisibile // caso CD: si tratta di
// linee che sono tutte in una
// delle 4 regioni definite dai
// bit del codice perché gli
// estremi hanno un bit 1 nella
// stessa posizione)
Altrimenti
Si considera il primo estremo con codice diverso da 0
// caso EF e IL: se un estremo ha codice pari a 0
// allora è visibile
Si effettua l’intersezione con la retta corrispondente al
primo bit 1 del codice // punto H in EF e punto M in IL
Si considera il nuovo segmento che va dal punto
intersezione al secondo estremo e si calcola il nuovo
codice per l’intersezione
Finché non ricadi in uno dei due casi banali
Antialiasing
Le tecniche di rasterizzazione producono l’effetto indesiderato di segmenti o bordi di poligoni non
rettilinei ma con “andamento a scaletta”. Tale effetto prende il nome di aliasing e deriva dal fatto che la
frequenza di campionamento (dipendente dalla dimensione del pixel) è troppo piccola rispetto al segnale.
L’aliasing dipende dal numero finito di pixel, dalla posizione prefissata dei pixel, dalla forma e dalla
dimensione prefissate dei pixel.
Aumentando la risoluzione dello schermo (aumentando il
numero di pixel) è possibile attutire l’effetto di aliasing.
Una tecnica di antialiasing consiste nell’approccio unvweighted area sampling (UAS) per vengono accesi
cui tutti i pixel interessati anche marginalmente dal rettangolo che rappresenta analiticamente il segmento
di retta di dato spessore o, più in generale, la striscia che rappresenta la generica linea curva. Ai pixel è
data un’intensità proporzionale in base alla proporzione della loro area interessata dalla linea. Questo
metodo genera un effetto visivo che inganna l’occhio e fa percepire contorni continui e non seghettati.
Quindi:
1. L’intensità di ciascun pixel decresce al crescere della distanza tra il centro del pixel e il bordo
esterno del segmento con spessore
2. L’intensità dei pixel non intersecati dal segmento non è influenzata dalla rasterizzazione del
segmento stesso
3. Porzioni di pixel di uguale superfici danno luogo ad intensità uguali indipendentemente dalla loro
distanza dal centro del pixel stesso.
La tecnica UAS non è apprezzabile da un punto di vista percettivo perché gli estremi della primitiva
tendono a sbordare in quanto pixel molto distanti dal centro della linea, ma con una piccola
sovrapposizione con essa, risultano accesi.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 29/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Una tecnica che sopperisce ai difetti dell’UAS tenendo conto anche della distanza del centro del pixel dalla
traccia teorica della primitiva, pensata come priva di spessore, è la tecnica weighted area sampling (WAS).
Entrambe le tecniche seguono lo stesso approccio.
Sia lmax
l’intensità massima di accensione di un pixel in assenza di antialiasing.
Sia L ⊂ R2
l’insieme dei punti della primitiva.
Ogni pixel che ha intersezione non vuota con L sarà acceso con un’intensità l = lmax
* Ws
ottenuto come
filtraggio con un opportuno nucleo di convoluzione W( /, { ) centrato nel pixel p ( xp
, yp
) con una funzione
dA ( x , y ) che esprime l’area ricoperta dalla primitiva.
La modalità WAS, rispetto a quella UAS, le aree di pixel egualmente interessate dalla primitiva non sono in
generale accese con la stessa intensità: i pixel i cui centri sono più vicini al confine teorico della primitiva
sono accesi più intensamente degli altri, a parità di porzione di area interessata. Le estremità della linea,
che sono pixel parzialmente coperti, ma con il centro vicino o interno alla linea stessa, sono accese più
intensamente con WAS e forniscono una impressione visiva di terminazione netta.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 30/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
OpenGL
Introduzione
Open Graphics Library è una libreria di funzioni per applicazioni che realizzano computer grafica. Si tratta
di una specifica per diverse piattaforme, derivata dall’interfaccia GL (sviluppata per le workstation Silicon
Graphics) progettata per il rendering in tempo reale ad alta velocità.
Assolve due compiti principali:
nascondere la complessità di interfacciamento con acceleratori 3D differenti, rendendo disponibile
un’unica API
nascondere le capacità offerte dai diversi acceleratori 3D, richiedendo che tutte le implementazioni
supportino completamente l’insieme di funzioni OpenGL, ricorrendo ad un’emulazione software se
necessario.
OpenGL rende disponibili primitive (punti, linee, poligoni, …) e ha il compito di convertirle in pixel
attraverso l’esecuzione della pipeline grafica.
OpenGL opera a basso livello: richiede al programmatore i passi precisi necessari per disegnare una scena
e richiedendo una buona conoscenza della pipeline grafica lasciando libertà di implementazione di
algoritmi di rendering specializzati.
Documentazione: http://www.opengl.org/sdk/docs/man/
Le funzioni OpenGL possono essere classificate in base alle loro funzionalità:
Funzioni primitive: definiscono gli oggetti di basso livello che il sistema grafico può
visualizzare: punti, segmenti, poligoni, curve, …
Funzioni attributo: governano il modo in cui le primitive appaiono sullo schermo
Funzioni di visualizzazione: descrivono la posizione e l’orientamento, permettono di fissare la
visualizzazione delle immagini
Funzioni di trasformazione: traslazioni, rotazioni e scalature
Funzioni di input: gestiscono l’interazione con le diverse forme di input che
caratterizzano i sistemi grafici moderni
Funzioni di controllo: permettono la comunicazione con i sistemi window, l’inizializzazione
dei programma, la gestione degli errori
Librerie GLU e GLUT
Connesse alle librerie OpenGL, è possibile utilizzare:
Libreria GLU (Graphics Library Utility)
Usa solo funzioni GL e contiene solo il codice per oggetti comuni (sfere, …) che l’utente preferisce non
scrivere ripetutamente.
Libreria GLUT (Graphics Library Utility Toolkit)
Si occupa della gestione delle interfacce con il sistema window, fornisce le funzionalità minime attese da
qualsiasi sistema moderno di windowing.
Programmazione window-based
I programmi window-based sono controllati dagli eventi: eseguono determinate azioni al verificarsi di
determinati eventi. Il sistema gestisce automaticamente una coda di eventi che memorizza messaggi che
comunicano gli eventi accaduti. Il sistema risponde agli eventi secondo il criterio primo avvenuto, primo
servito.
Le azioni che il sistema esegue quando si verifica un evento sono realizzate tramite callback functions:
ogni evento deve avere la sua callback function.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 31/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Alcune funzioni per la gestione della window
void glutInit(int *argcp, char **argv);
Inizializza la libreria GLUT.
void glutInitWindowSize(int width, int height);
Inizilizza la dimensione della finestra dello schermo.
void glutInitWindowPosition(int x, int y);
Inizializza la posizione della finestra nello schermo.
void glutInitDisplayMode(unsigned int mode);
Inizializza la modalità di visualizzazione.
mode può assumere i seguenti valori (combinabili in OR logico):
GLUT_RGBA Bit mask to select an RGBA mode window. This is the default if neither GLUT_RGBA
nor GLUT_INDEX are specified.
GLUT_RGB An alias for GLUT_RGBA.
GLUT_INDEX Bit mask to select a color index mode window. This overrides GLUT_RGBA if it is
also specified.
GLUT_SINGLE Bit mask to select a single buffered window. This is the default if neither
GLUT_DOUBLE or GLUT_SINGLE are specified.
GLUT_DOUBLE Bit mask to select a double buffered window. This overrides GLUT_SINGLE if it is
also specified.
GLUT_ACCUM Bit mask to select a window with an accumulation buffer.
GLUT_ALPHA Bit mask to select a window with an alpha component to the color buffer(s).
GLUT_DEPTH Bit mask to select a window with a depth buffer.
GLUT_STENCIL Bit mask to select a window with a stencil buffer.
GLUT_MULTISAMPLE Bit mask to select a window with multisampling support. If multisampling is not
available, a non-multisampling window will automatically be chosen. Note: both
the OpenGL client-side and server-side implementations must support the
GLX_SAMPLE_SGIS extension for multisampling to be available.
GLUT_STEREO Bit mask to select a stereo window.
GLUT_LUMINANCE Bit mask to select a window with a ``luminance'' color model. This model provides
the functionality of OpenGL's RGBA color model, but the green and blue
components are not maintained in the frame buffer. Instead each pixel's red
component is converted to an index between zero and
glutGet(GLUT_WINDOW_COLORMAP_SIZE)-1 and looked up in a per-window color
map to determine the color of pixels within the window. The initial colormap of
GLUT_LUMINANCE windows is initialized to be a linear gray ramp, but can be
modified with GLUT's colormap routines.
int glutCreateWindow(char *name);
Crea una finestra principale. È possibile specificare il titolo della finestra.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 32/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
int glutCreateSubWindow(int win, int x, int y, int width, int height);
Crea una finestra secondaria all’interno di una finestra principale, specificandone dimensioni e posizione.
void glutSetWindow(int win);
Imposta la finestra attiva.
int glutGetWindow(void);
Individua la finestra attiva.
void glutDestroyWindow(int win);
Elimina dall’esecuzione la finestra desiderata.
void glutPositionWindow(int x, int y);
Sposta la finestra nella posizione desiderata. Se si tratta di una finestra principale la posizione è relativa
allo schermo, se si tratta di una finestra secondaria la posizione è relativa alla finestra principale.
void glutReshapeWindow(int width, int height);
Ridimensiona la finestra e ne ridisegna il contenuto.
void glutFullScreen(void);
Ingrandisce a tutto schermo la finestra attiva.
void glutShowWindow(void);
void glutHideWindow(void);
void glutIconifyWindow(void);
Rispettivamente: visualizza la finestra attiva, nasconde la finestra attiva, riduce ad icona la finestra attiva.
void glutSetWindowTitle(char *name);
void glutSetIconTitle(char *name);
Permettono di modificare il nome e il testo dell’icona della finestra attiva.
void glutSetCursor(int cursor);
Imposta la forma per il cursore del mouse, utilizza le seguenti costanti:
GLUT_CURSOR_RIGHT_ARROW: Arrow pointing up and to the right.
GLUT_CURSOR_LEFT_ARROW: Arrow pointing up and to the left.
GLUT_CURSOR_INFO: Pointing hand.
GLUT_CURSOR_DESTROY: Skull & cross bones.
GLUT_CURSOR_HELP: Question mark.
GLUT_CURSOR_CYCLE: Arrows rotating in a circle.
GLUT_CURSOR_SPRAY: Spray can.
GLUT_CURSOR_WAIT: Wrist watch.
GLUT_CURSOR_TEXT: Insertion point cursor for text.
GLUT_CURSOR_CROSSHAIR: Simple cross-hair.
GLUT_CURSOR_UP_DOWN: Bi-directional pointing up & down.
GLUT_CURSOR_LEFT_RIGHT: Bi-directional pointing left & right.
GLUT_CURSOR_TOP_SIDE: Arrow pointing to top side.
GLUT_CURSOR_BOTTOM_SIDE: Arrow pointing to bottom side.
GLUT_CURSOR_LEFT_SIDE: Arrow pointing to left side.
GLUT_CURSOR_RIGHT_SIDE: Arrow pointing to right side.
GLUT_CURSOR_TOP_LEFT_CORNER: Arrow pointing to top-left corner.
GLUT_CURSOR_TOP_RIGHT_CORNER: Arrow pointing to top-right corner.
GLUT_CURSOR_BOTTOM_RIGHT_CORNER: Arrow pointing to bottom-left corner.
GLUT_CURSOR_BOTTOM_LEFT_CORNER: Arrow pointing to bottom-right corner.
GLUT_CURSOR_FULL_CROSSHAIR: Full-screen cross-hair cursor
GLUT_CURSOR_NONE: Invisible cursor.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 33/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
GLUT_CURSOR_INHERIT: Use parent's cursor.
Alcune funzioni per la gestione degli eventi
void glutDisplayFunc(void (*func)(void));
Imposta la funzione di callback per la current window
void glutReshapeFunc(void (*func)(int width, int height));
Imposta la funzione di callback per l’evento di ridimensionamento della current window
void glutKeyboardFunc(void (*func)(unsigned char key, int x, int y));
Imposta la funzione di callback per l’evento di pressione di un tasto della tastiera.
key corrisponde al codice ASCII del carattere corrispondente tasto premuto.
x e y indicano la posizione del mouse al momento della pressione del tasto.
void glutSpecialFunc(void (*func)(int key, int x, int y));
Imposta la funzione di callback per l’evento di pressione di un tasto speciale della tastiera.
Sono definite le costanti per l’individuazione del tasto speciale premuto (GLUT_KEY_F1, …,
GLUT_KEY_HOME, …).
void glutMouseFunc(void (*func)(int button, int state, int x, int y));
Imposta la funzione di callback per l’evento di pressione di un pulsante del mouse.
button è valorizzato in base al pulsante premuto (costanti: GLUT_LEFT_BUTTON, GLUT_MIDDLE_BUTTON,
GLUT_RIGHT_BUTTON).
state indica se il pulsante è stato premuto oppure rilasciato (costanti: GLUT_UP, GLUT_DOWN).
x e y indicano la posizione del mouse al momento della pressione del pulsante.
void glutMotionFunc(void (*func)(int x, int y));
void glutPassiveMotionFunc(void (*func)(int x, int y));
Imposta la funzione di callback per l’evento di movimento del mouse, rispettivamente nel caso in cui il
mouse sia mosso con un pulsante premuto o meno.
x e y indicano la posizione del mouse durante il movimento.
void glutIdleFunc(void (*func)(void));
Imposta la funzione di callback idle globale: per effettuare attività in background.
void glutTimerFunc(unsigned int msecs, void (*func)(int value), value);
Imposta una funzione di callback che deve essere eseguita in determinati intervalli di tempo.
void glutMainLoop(void);
Attiva il ciclo degli eventi GLUT: il programma disegna l’immagine iniziale ed entra in attesa di accadimenti
di eventi.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 34/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Funzioni per la gestione dei menu
int glutCreateMenu(void (*func)(int value));
Imposta la funzione di callback per la selezione di uno dei valori (item) del menu.
void glutSetMenu(int menu);
int glutGetMenu(void)
Rispettivamente: imposta o ottiene il menu attivo.
void glutDestroyMenu(int menu);
Cancella un menu.
void glutAddMenuEntry(char *name, int value);
Aggiunge una voce di selezione alla lista degli elementi di un menu.
void glutAddSubMenu(char *name, int menu);
Aggiunge una voce di sottomenu alla lista degli elementi di un menu.
void glutChangeToMenuEntry(int entry, char *name, int value);
void glutChangeToSubMenu(int entry, char *name, int menu);
Imposta la voce o il sottomenu selezionati.
void glutRemoveMenuItem(int entry);
Rimuove un elemento del menu corrente (entry specifica il numero dell’elemento da rimuovere partendo
dal 1).
void glutAttachMenu(int button);
void glutDetachMenu(int button);
Collega la visualizzazione del menu corrente, nella finestra corrente, alla pressione di uno dei pulsanti del
mouse (utilizza le costanti: GLUT_LEFT_BUTTON, GLUT_MIDDLE_BUTTON, and GLUT_RIGHT_BUTTON)
Funzioni per il testo
void glutBitmapCharacter(void *font, int character);
Disegna un testo (character) nel font selezionato (*font) in formato bitmap.
I tipi di carattere utilizzabili sono:
GLUT_BITMAP_8_BY_13: font di larghezza fissata con ogni carattere che riempie un
rettangolo di 8x13 pixels
GLUT_BITMAP_9_BY_15: font di larghezza fissata con ogni carattere che riempie un
rettangolo di 9x15 pixels
GLUT_BITMAP_TIMES_ROMAN_10: Font times roman a 10 punti proporzionalmente spaziato.
GLUT_BITMAP_TIMES_ROMAN_24: Font times roman a 24 punti proporzionalmente spaziato.
GLUT_BITMAP_HELVETICA_10: Font Elvetica a 10 punti proporzionalmente spaziato.
GLUT_BITMAP_HELVETICA_12: Font Elvetica a 12 punti proporzionalmente spaziato.
GLUT_BITMAP_HELVETICA_18: Font Elvetica a 18 punti proporzionalmente spaziato.
int glutBitmapWidth(GLUTbitmapFont font, int character)
Restituisce la larghezza per un testo bitmap nel font selezionato.
void glutStrokeCharacter(void *font, int character);
Disegna un testo (character) nel font selezionato (*font) in formato stroke.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 35/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
int glutStrokeWidth(GLUTstrokeFont font, int character)
Restituisce la larghezza per un testo stroke nel font selezionato.
I tipi di carattere utilizzabili sono:
GLUT_STROKE_ROMA
GLUT_STROKE_MONO_ROMAN
Funzioni per il colore
void glClearColor(GLfloat red, GLfloat green, GLfloat blue, GLfloat alpha);
Imposta il colore dello sfondo, alpha descrive il grado di trasparenza.
void glClear( GLbitfield mask);
Cancella il buffer e applica il colore di sfondo all’intera finestra.
mask può assumere i valori:
GL_COLOR_BUFFER_BIT: indica i buffer attualmente abilitati per la scrittura di colore
GL_DEPTH_BUFFER_BIT: indica il buffer di profondità
GL_STENCIL_BUFFER_BIT: indica il buffer di stencil.
Funzioni per la definizione di coordinate
Lo spazio delle coordinate del mondo e lo spazio della finestra devono essere correlati tramite funzioni di
traslazione e ridimensionamento) per poter disegnare gli elementi dell’immagine nella viewport.
Deve essere quindi definita una mappatura tra la finestra del mondo (window) e la finestra fisica dello
schermo (viewport). Questo approccio rende più semplice la gestione della visualizzazione di una scena.
La window è espressa in coordinate del mondo.
La viewport è una porzione della finestra sullo schermo.
Ciò che giace nella window viene traslato e ridimensionato per apparire nella viewport.
void gluOrtho2D(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top);
Definisce la window tramite le coordinate del suo angolo basso sinistro e di quello alto destro. Deve essere
preceduta alla funzione glMatrixMode.
void glMatrixMode(GLenum mode);
Definisce quale matrice di trasformazione è utilizzata per le seguenti operazioni.
mode può assumere i seguenti valori:
GL_MODELVIEW: applica alle seguenti operazioni la matrice di modellazione.
GL_PROJECTION: applica alle seguenti operazioni la matrice di proiezione.
GL_TEXTURE: applica alle seguenti operazioni la matrice delle texture.
GL_COLOR: applica alle seguenti operazioni la matrice dei colori.
void glLoadIdentity(void);
Sostituisce l’attuale matrice con la matrice identità.
void gluPerspective(GLdouble fovy, GLdouble aspect, GLdouble zNear, GLdouble zFar);
Definisce una prospettiva per la window.
fovy specifica l’angolo di visione, in gradi, nella direzione y
aspect specifica l’angolo di visione nella direzione x (ovvero il rapporto della larghezza rispetto all’altezza)
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 36/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
zNear specifica la distanza tra la telecamere virtuale il piano più vicino
zFar specifica la distanza tra la telecamere virtuale il piano più lontano
void glViewport(GLint x, GLint y, GLsizei width, GLsizei height);
Definisce la viewport tramite le coordinate del suo angolo basso sinistro e di quello alto destro
(specificando larghezza e altezza).
Funzioni primitive per il disegno
void glPointSize(GLfloat size);
Imposta la dimensione di un punto.
void glVertex{D}{T}(GLType red, GLType green, GLType blue[, GLType alpha]]);
Imposta il colore corrente.
D può assumere i valori:3, 4 che indicano se il colore è definito solo dalle sue componenti rossa, verde e
blu, oppure dalle tre componenti e dal grado di trasparenza.
T può assumere i valori b (byte), s (short), i (int), f (float), d (double), ub (ubyte), us (ushort), ui (uint) e
indica il tipo di variabile che deve essere utilizzata per indicare le componenti.
void glBegin(GLenum mode);
Definisce l’inizio della dichiarazione dei vertici di una certa primitiva di disegno.
glBegin deve esse seguita da una serie di istruzioni glVertex(xx) e da un’istruzione glEnd.
mode definisce la primitiva, può assumere i valori:
GL_POINTS ogni vertice indicato rappresenta un punto.
GL_LINES i vertici sono trattati a coppie e definiscono dei segmenti.
GL_LINE_STRIP disegna una polyline, ovvero traccia una serie di segmenti definiti dai vertici indicati
in modo che: i primi 2 vertici definiscono il primo segmento, i vertici successivi
definiscono un segmento che parte dal vertice terminale del segmento precedente.
GL_LINE_LOOP come GL_LINE_STRIP ma aggiunge automaticamente un segmento che connette il
vertice finale con quello iniziale.
GL_TRIANGLES disegna sequenze di triangoli definiti da tre vertici ciascuno.
GL_TRIANGLE_STRIP disegna sequenze di triangoli adiacenti: per i triangoli di indice n pari, i vertici sono
n, n+1 e n+2, per quelli con n dispari, i vertici sono n+1, n, n+2.
GL_TRIANGLE_FAN disegna sequenze di triangoli adiacenti aventi in comune il vertice iniziale.
GL_QUADS disegna sequenze di quadrilateri definiti da quattro vertici ciascuno.
GL_QUAD_STRIP come GL_TRIANGLE_STRIP, ma applicato ai quadrilateri, disegna sequenze di
quadrilateri adiacenti.
GL_POLYGON disegna poligoni convessi.
void glVertex{D}{T}(GLType x, GLType y[, GLType z[, GLType w]]);
Si tratta di una serie di funzioni (il nome completo della funzione è ottenuto sostituendo {D} e {T} con
opportuni valori) che definiscono un vertice in uno spazio.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 37/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
D può assumere i valori:2, 3, 4 e rappresenta il numero di dimensioni dello spazio.
T può assumere i valori s (short), i (int), f (float), d (double) e indica il tipo di variabile che deve essere
utilizzata per indicare le coordinate.
void glBegin(GLenum mode);
Determina la fine della serie di vertici per la primitiva.
void glFlush(void);
Esegue il comando GL immediatamente (disegna la primitiva, …).
void glRect{T}(GLType x1, GLType y1, GLType x2, GLType y2);
Disegna un rettangolo allineato in base alle coordinate del suo vertice inferiore sinistro e di quello
superiore destro.
Struttura di un programma OpenGL
OpenGL utilizza dati con tipi di dati specifici definiti al suo interno. Per assicurare che le funzioni OpenFGL
ricevano dati appropriati è conveniente usare i nomi intrinseci per i tipi: GLint, GLfloat, …
Ovviamente è possibile definire strutture per le coordinate dei vertici.
typedef struct {GLint x,y;} GLintPoint2i;
Può essere utile definire una serie di funzioni.
void drawDot(GLintPoint2i point)
{
/*draw a 2d GLint point*/
glBegin(GL_POINTS);
glVertex2i(point.x,point.y);
glEnd( );
}
Suggerimenti per i poligoni regolari e cerchi
Un poligono è regolare se:
1. tutti i lati hanno la stessa lunghezza
2. i lati adiacenti formano angoli interni sempre uguali.
Un n-gono è un poligono con n lati.
Se il numero di lati di un n-gono è grande, l’n-gono in
apparenza approssima un cerchio. Si usa questo metodo per
implementare l’area di un cerchio.
I vertici di un n-gono appartengono al suo parent-circle. Essi
giacciono nelle posizioni definite da:
Per posizionare un n-gono in base al suo punto centrale
(nella posizione cx, cy), bisogna aggiungere cx e cy
rispettivamente alle coordinate x e y.
Per ruotare un n-gono di un angolo α è necessario aggiungere α all’argomento del coseno e del seno.
Inizializzazione librerie
OpenGL
Inizializzazione modalità
della finestra dello schermo
Creazione della/e finestra/e
Funzioni di impostazione
(colori, modalità, matrici, ...)
Funzioni di disegno
Attivazione loop attesa
eventi
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 38/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Per scalare un n-gono di un fattore S è necessario moltiplicare il raggio R per il fattore S.
Funzione che disegna un n-gono
void ngon(int n, GLfloat cx, GLfloat cy, GLfloat raggio, Glfloat angolo)
{
GLfloat x, y;
if(n<3) return;
angolo=angolo*3.14159265/180; //trasforma l’angolo di rotazione da gradi in radianti
glBegin(GL_LINE_LOOP)
for(i=0;i<n;i++)
{
x=R*cos((2*3.14159265)*i/n+angolo)+cx;
y=R*sin((2*3.14159265)*i/n+angolo)+cy;
glVertex2f(x,y)
}
glEnd( );
}
void cerchio(int n, GLfloat cx, GLfloat cy, GLfloat raggio, Glfloat angolo)
{
Glfloat x,y;
if(n<3) return;
angolo=angolo*3.14159265/180; //trasforma l’angolo di rotazione da gradi in radianti
glBegin(GL_POLYGON)
for(i=0;i<n;i++)
{
x=R*cos((2*3.14159265)*i/n+angolo)+cx;
y=R*sin((2*3.14159265)*i/n+angolo)+cy;
glVertex2f(x,y);
}
glEnd( );
}
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 39/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Varianti dell’n-gono: è possibile disegnare varianti interessanti dell’n-gono connettendo i suoi vertici in
ordine da quello standard che connette i vertici adiacenti. Ad esempio: connettendo un vertice a tutti i
vertici non adiacenti si ottengono figure tipo stella.
void stellation(int n, float cx, float cy,float radius,float angolo,float scale)
{
int i,j;
typedef struct{GLfloat x,y;} GLfloatPoint;
GLfloatPoint Punto[20];
angolo=angolo*3.14159265/180;
for (i=0;i<n;i++)
{
Punto[i].x=radius*scale*cos(2*3.14159265*i/n+angolo)+cx;
Punto[i].y=radius*scale*sin(2*3.14159265*i/n+angolo)+cy;
}
glBegin(GL_LINE_STRIP);
i=0;
for (j=i+2;j<n-1;j=j+1)
{
glVertex2f(Punto[i].x,Punto[i].y);
glVertex2f(Punto[j].x,Punto[j].y);
}
for (i=1;i<n;i++)
{
for (j=i+2;j<n;j=j+1)
{
glVertex2f(Punto[i].x,Punto[i].y);
glVertex2f(Punto[j].x,Punto[j].y);
}
}
glEnd();
glFlush();
}
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 40/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Gestione del ridimensionamento della finestra
Il ridimensionamento della finestra da parte dell’utente, genera l’esecuzione dell’evento di resize.
Per gestire tale evento si deve impostare la sua funzione di callback tramite la funzione, nel main(),
glutReshapeFunc(myReshape), dove myReshape è la funzione di callback.
La funzione myReshape ha la seguente signature:
void myReshape(Glsizei W, Glsizei H);
Il sistema passa alla funzione myReshape la nuova larghezza e la nuova altezza della finestra.
È necessario pertanto definire nuovamente il viewport in modo che si adatti alla finestra dello schermo e
mantenga le stesse proporzioni della finestra sul mondo (aspect ratio = larghezza / altezza) in modo da
prevenire distorsioni dell’immagine.
Pertanto, se R è l’aspect ratio della window sul mondo e la finestra dello schermo ha larghezza W e altezza
H, si possono verificare due situazioni distinte:
1. la finestra sul mondo ha un aspect ratio più grande della finestra sullo schermo R > W/H
in questo caso la finestra sul mondo è bassa e larga rispetto alla finestra sullo schermo, allora la
viewport dovrà avere larghezza W e altezza W/R
2. la finestra sul mondo ha un aspect ratio più piccolo della finestra sullo schermo R < W/H
in questo caso la finestra sul mondo è alta e stretta rispetto alla finestra sullo schermo, allora la
viewport dovrà avere altezza H e larghezza H*R.
void myReshape(Glsizei W, Glsixei H)
{
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(left, right, bottom, top);
R = (float)(right-left)/(float)(top-bottom);
if (R > W/H)
set Viewport(0, (Glsizei)W, 0, (Glsizei)W/R);
else
set Viewport(0, (Glsizei)H*R, 0, (Glsizei)H);
end
glMatrixMode(GL_MODELVIEW);
}
Tiling della finestra con un motivo
“Fare tiling” significa ricoprire l’intera finestra sullo schermo lato per lato, con un certo numero di copie di
una stessa immagine. L’immagine utilizzata è il motivo. È possibile fare tiling utilizzando una differente
viewport per ogni copia del motivo.
Trasformazioni di modellazione
Per istanziare un oggetto nella scena è necessario:
1. effettuare una scalatura per portare l’oggetto alle proporzioni desiderate
2. effettuare una rotazione per orientare l’oggetto
3. effettuare una traslazione per posizionarlo..
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 41/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Tutte le trasformazioni geometriche necessarie ad OpenGL sono mantenute in tre matrici che fanno parte
dello stato:
a. ModelView (usata dal transformer)
b. Project (usata dal projector)
c. Texture (usata dal rasterizer se si fa texture mapping)
Il comando per selezionare la matrice corrente è glMatrixMode(<matrix>) in cui <matrix> può assumere i
valori GL_MODELVIEW, GL_PROJECT, GL_TEXTURE.
La matrice ModelView permette di definire le trasformazioni affini necessarie per posizionare l’oggetto nel
sistema del mondo e per orientare la macchina fotografica virtuale, ovvero passare al sistema dell’occhio.
La funzione glLoadIdentity() rimpiazza la matrice corrente con la matrice identità, le funzioni di
traslazione, rotazione e scalatura sono:
glRotate(angle, ax, ay, az): rotazione attorno ad un asse passante per l’origine
glTranslate(dx, dy, dz): traslazione
glScale(sx, sy, sz): scalatura attorno all’origine
glMultiMatrix(matrix): per effettuare una moltiplicazione generica con la matrice corrente
Questi comandi postmoltiplicano la matrice corrente per quella specificata: si imposta inizialmente la
matrice identità e si specificano le moltiplicazioni da eseguire; l’ultima operazione indicata è la prima ad
essere eseguita.
Per posizionare oggetti diversi è necessario utilizzare combinazioni di matrici diverse che non siano
reciprocamente influenzate; per fare questo sono disponibili i comandi per salvare la matrice corrente in
uno stack e riutilizzarla successivamente:
glPushMatrix() salva la matrice corrente nello stack
glPopMatrix() ripristina la matrice corrente con quella in cima allo stack.
Si imposta allora la matrice da utilizzare per un gruppo di oggetti e, per ogni oggetto, si impostano le
specifiche trasformazioni dopo aver salvato la matrice corrente nello stack, al termine del disegno
dell’oggetto si ripristina la matrice dallo stack.
Librerie GLUI per l’interfaccia grafica
È possibile utilizzare le librerie GLUI per creare pannelli di interazione contenenti pulsanti, caselle di testo,
selezioni, …; di seguito sono riportate le descrizioni di alcune funzioni utili.
Definizioni
È necessario includere la libreria GLUI: <gl/glui.h> e linkare la libreria glui32.lib.
Nel programma è poi necessario definire le variabili globali per i tipi di controlli che si voglio utilizzare e
per identificare le finestre.
int main_window; //memorizza l’identificativo della finestra creata
GLUI_Spinner *spinner;
GLUI_EditText *text;
GLUI_RadioGroup *radio;
Funzioni
Quando si crea la finestra è necessario memorizzarne l’identificativo per i successivi usi.
main_window = glutCreateWindow(“Nome finestra”);
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 42/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Si deve poi creare l’interfaccia grafica per gestire l’interazione con la finestra grafica creata.
GLUI *glui = GLUI_Master.create_glui(“Opzioni”);
All’interfaccia appena creata è possibile aggiungere un pannello:
pannello = glui->add_panel(“Nome pannello”,GLUI_PANEL_EMBOSSED);
Al pannello possono essere aggiunti i controlli (ad esempio uno spinner):
spinner = glui->add_spinner_to_panel(pannello,”etichetta spinner”,GLUI_SPINNER_FLOAT,
&variabile, value, controlli);
I parametri rappresentano rispettivamente: il pannello cui va aggiunto il controllo, l’etichetta visualizzata, il
tipo di dati trattato, la variabile nella quale viene aggiornato il valore dello spinner, il parametro di input
passato alla funzione chiamata quando si utilizza il controllo, il nome della funzione chiamata.
Il range di validità dello spinner è definito come segue:
spinner->set_float_limits(min, max);
Per aggiungere una casella di testo editabile si usa, ad esempio:
text = glui->add_edittext_to_panel(pannello,” etichetta casella”,GLUI_EDITTEXT_FLOAT,
&variabile);
la casella di testo aggiorna la variabile indicata come quarto parametro.
Un radio-group costituito da radio-button per effettuare una scelta esclusiva, può essere costruito con:
radio = glui->add_radiogroup(&variabile, 0, funzione);
glui->add_radiobutton_to_group(radio, “valore 1”);
glui->add_radiobutton_to_group(radio, “valore 2”);
glui->add_radiobutton_to_group(radio, “...”);
Il valore assegnato alla variabile corrisponde alla scelta fatta (varia da 0 a n-1 per n scelte possibili). La
funzione (terzo parametro di add_radiogroup) dovrà gestire le possibili scelte, ad esempio:
void funzione(int value)
{
switch(variabile)
{
case 0:
//codice per la scelta 0;
break;
case 1:
//codice per la scelta 1;
break;
...
}
}
È possibile aggiungere un pulsante:
glui->add_button(“Etichetta”,0,funzione);
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 43/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
L’interfaccia definita con le funzioni sopra indicate, deve essere poi collegata alla finestra grafica tramite
l’istruzione:
glui->set_main_gfx_window(main_window);
glutMainLoop();
Le variabili utilizzate dovranno essere variabili globali che potranno essere utilizzate nella funzione display.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 44/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Rappresentazione di curve mediante spline polinomiali di ordine m a
nodi semplici
Spesso è necessario modellare oggetti non facilmente ottenibili da figure geometriche: oggetti con
contorni dolci o arrotondati alternati a parti lisce o spigoli vivi. La modellazione geometrica è quella parte
della Computer graphics che si occupa di creare i modelli geometrici di curve, superfici e oggetti 3D.
Curve 2D
Per memorizzare e rappresentare una funzione tramite un calcolatore è necessario discretizzarla in un
numero finito di punti (possibilmente non troppo elevato) e considerare una sua approssimazione ottenuta
un criterio di interpolazione o di approssimazione.
Una curva non matematicamente descrivibile tramite una funzione y = f(x) perché in corrispondenza di un
certo valore di x possono esistere diversi valori di y.
L’equazione implicita di una curva f(x,y) = 0 può essere utile in certi casi, tuttavia presenta svantaggi in
altri (ad esempio l’equazione implicita di una circonferenza con centro all’origine e raggio R: x2
+ y2
= R2
).
Inoltre non è semplice ottenere la forma implicita di una qualsiasi curva.
La forma più semplice, invece, per rappresentare una curva, è la forma parametrica: x = x(t) y = y(t) che
descrive tutti i punti della curva al variare del parametro t in [ tmin
, tmax
].
Esempi di curve in forma parametrica
∈
∙ ∙
∈
∙
∙ ∈
Rappresentazione nel calcolatore
Per rappresentare nel calcolatore una curva è necessario considerarne una discretizzazione, si considerano
cioè i punti sulla curva:
e si costruiscono le due funzioni parametriche , che interpola le coppie , ed , che
interpola le coppie .
È necessario allora risolvere due problemi di interpolazione.
A partire dalle posizioni dei punti P0
, P1
, …, PN+1
, si ottengono diverse possibili curve, la cui forma dipenderà
sia dalla posizione dei punti, sia dalle funzioni base utilizzate per risolvere i due problemi di interpolazione
per le due componenti parametriche.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 45/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Funzioni spline polinomiali a nodi semplici
Definizione 1.1: spline polinomiale a nodi semplici
Sia [a,b] un intervallo chiuso e limitato dell’asse reale e sia ∆ una partizione di [a,b] con:
∆
che genera k+1 sottointervalli così definiti:
Fissato un intero positivo m, con m < k, si definisce spline polinomiale di ordine m (grando m-1), una
funzione s(x) che:
a) in ciascun intervallo coincide con un polinomio di ordine m
b) nei punti detti nodi semplici della spline, soddisfa le seguenti condizioni di raccordo:
Tali condizioni garantiscono che ∈
ovvero che è continua in [a,b] insieme alle sue derivate
fino a quella di ordine m-2.
Lo spazio delle spline di ordine m con nodi semplici
viene indicato con ∆ o .
Teorema: la dimensione dello spazio delle spline ∆ è m+k
Dimostrazione intuitiva: costruire una spline significa definire (k+1) intervalli nei quali calcolare un
polinomio di ordine m, a questi si devono togliere le (m-1) condizioni applicati nei k punti di raccordo,
ottenendo –
Nota: la base migliore per poter calcolare in modo stabile ed efficiente una funzione spline, sia per
complessità che per stabilità, è costituita dalla base delle B-spline.
Definizione 1.2: Funzione base B-spline
Assegnata una successione di nodi , si definisce B-spline normalizzata di ordine m relativa
al nodo con ∈ , una funzione che gode delle seguenti proprietà:
a)
b)
c) In ciascun intervallo coincide con un polinomio di ordine m che si raccorda
opportunamente con i vicini, in modo tale che ∈
.
Formule di Cox per la valutazione di una B-spline
Per calcolare le funzioni base si utilizzano le formule di Cox, che consentono di calcolare mediante
combinazione di due funzioni base di ordine m-1, più precisamente definita come:
per h = 2, …, m si ha:
Le funzioni B-spline così ottenute vengono utilizzate per costruire una base per lo spazio delle spline ∆
Poiché ∆ ha dimensione m+k, è necessario costruire m+k funzioni base B-spline. Essendo k i nodi reali
è necessario inserire 2m nodi fittizi di cui m sono inseriti prima di e m sono inseriti dopo .
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 46/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
La partizione nodale così costituita prende il nome di partizione nodale estesa ∆*.
Partizione nodale estesa
Si definisce l’insieme ∆
partizione nodale estesa associata a ∆ nel seguente modo:
Mediante questa partizione diventa possibile definire le m+k B-spline normalizzate di ordine m:
≠
in cui i casi 0 / 0 devono essere interpretati come 0 (in quanto è possibile scegliere nodi aggiuntivi
coincidenti).
Risultato importante
L’insieme costituisce una base per lo spazio ∆ , quindi, per ogni x ∈ [a,b] è
possibile esprimere ∈ ∆ come:
Osservazione: la base delle funzioni B-spline è una base molto buona sia dal punto di vista della stabilità
che dal punto di vista della complessità computazionale, poiché le funzioni B-spline godono di molte
proprietà.
Proprietà delle B-spline
1. Non negatività:
2. Supporto locale:
3. In un punto ∈ , vi sono m funzioni base diverse da 0 se il punto non coincide con un nodo,
se il punto coincide con un nodo le funzioni base diverse da 0 sono m-1
4. Le funzioni B-spline rappresentano una partizione dell’unità: la somma delle valutazioni di tutte le
B-spline in un punto ∈ vale 1:
Proprietà delle spline valutate mediante B-spline
Le proprietà della base delle B-spline garantiscono che le funzioni spline valutate utilizzando tale base
godano a loro volta di importanti proprietà.
1. Per la proprietà di supporto locale delle B-spline, per ogni ∈ risulta che sul punto x, le
uniche B-spline diverse da 0 siano: , per cui:
2. Per le proprietà di non negatività e partizione dell’unità di cui godono le B-spline, ogni espressa
nella base delle B-spline normalizzate, risulta una combinazione convessa dei coefficienti .
Dalle proprietà di una combinazione convessa si ha che (dalla sommatoria precedente) il valore
assunto dalla funzione spline in un punto ∈ è sempre compreso tra il valore minimo e
massimo dei coefficienti della sua rappresentazione:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 47/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Inoltre, se ∈ allora:
Proprietà di variation diminishing di una spline espressa s(x) nella base delle B-spline normalizzate
Il numero di variazioni di segno della (indicato con ) è sempre minore o uguale al numero di
variazioni di segno della successione dei suoi coefficienti .
Interpolazione mediante funzioni spline polinomiali a nodi semplici
Come già detto, per poter rappresentare una curva sul piano mediante funzioni spline è necessario
discretizzarla e considerarne la rappresentazione parametrica. Per ottenere una rappresentazione continua
delle due componenti parametriche, si devono risolvere due problemi di interpolazione con funzioni spline.
Si deve pertanto affrontare il problema generale dell’interpolazione con funzioni spline polinomiali a nodi
semplici di un insieme di dati .
Poiché la funzione spline ∈ ∆ dipende fortemente dalla posizione e dal numero dei nodi che la
caratterizzano, è necessario per prima cosa studiare come posizionare i nodi veri dell’insieme
∆ .
Il problema consiste nel cercare la funzione ∈ ∆ tale che
Se ∆ ha N+2 gradi libertà, cioè N+2-m = N-2 nodi, il sistema lineare che si ottiene è:
Tale sistema è quadrato e potrebbe essere risolubile, ma certe configurazioni dei noi potrebbero generare
colonne nulle, pertanto non è possibile definirne rango e risolubilità.
Teorema di Schoemberg Whitney
Il Teorema di Schoemberg Whitney fornisce una condizione necessaria e sufficiente affinché il sistema
lineare, che si deve risolvere per calcolare i coefficienti della spline interpolante, abbia rango massimo e
quindi un’unica soluzione.
Sia assegnata una successione crescente di nodi e la successione crescente di punti di
osservazione e sia definita la successione delle B-spline
Il problema di interpolazione di funzioni spline dei dati si esprime come il seguente
sistema lineare:
La matrice A ha rango massimo se e solo se ; cioè se per ciascuna funzione B-spline
esiste almeno un punto di interpolazione nel suo supporto.
Pertanto, è necessario legare la scelta dei nodi ai punti di interpolazione: la scelta dei nodi (individuata da
Schoemberg), garantisce che la matrice delle funzioni
base sia a rango massimo.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 48/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Un’altra possibilità per costruire una spline
che interpoli le coppie consiste nello scegliere il numero dei nodi veri e
scegliere .
Imponendo si ottengono equazioni ognuna delle quali ha incognite.
Nel caso si hanno condizioni in incognite: per avere un sistema quadrato a rango
massimo è necessario aggiungere 2 condizioni. Le altre 2 condizioni vengono applicate agli estremi
dell’intervallo e prendono il nome di condizioni ai bordi.
Condizione di spline cubica naturale
Tra tutte le funzioni interpolanti di classe C2
, la spline cubica naturale è quella che minimizza il funzionale
che rappresenta la curvatura globale della spline interpolante.
La curvatura di una funzione derivabile e continua si definisce come:
Pertanto, se , la curvatura ovvero: la derivata seconda di una funzione è
un’approssimazione della curvatura globale. Poiché una spline naturale minimizza il funzionale
, si può affermare che la spline naturale che ha curvatura minima è quella che oscilla meno.
Condizione sulla derivata prima
Condizione sulla derivata seconda
Condizione di periodicità
Se si vuole costruire una funzione che nel punto ha un valore uguale al valore in
si possono imporre le seguenti condizioni di periodicità:
Tali condizioni sono particolarmente utili nella rappresentazione di curve chiuse, per le quali si ha che:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 49/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Nota
La stima della derivata prima può essere calcolata facendo uso del rapporto incrementale fra i valori della
funzione data agli estremi, ovvero:
oppure facendo uso della stima di Bessel, che approssima la derivata prima della funzione nel primo punto
di interpolazione come la derivata prima del polinomio quadratico che interpola i primi 3 punti di
interpolazione, e la derivata prima della funzione nell’ultimo punto come la derivata prima del polinomio
quadratico che interpola gli ultimi 3 punti di interpolazione.
La scelta delle condizioni ai bordi per le due curve parametriche e influenza notevolmente la
forma della curva che interpola i dati.
Proprietà di convergenza delle funzioni spline di interpolazione
Teorema
Sia ∈ per ∈ ;
sia ∆ una successione di decomposizioni dell’intervallo con passo (o, se il passo non è costante
tali che
sia limitato);
sia ∆ la funzione spline che interpola la funzione in tutti i punti della decomposizione ∆ , ovvero:
∆ ∈ ∆
che soddisfi le condizioni ai bordi
∆
∆
allora: esistono delle costanti , indipendenti da ∆ , tali che ∈ :
∆
∙ ∙
Curve spline interpolanti
Dati i punti
, la curva spline interpolante si esprime nel seguente modo:
dove , sono la soluzione del sistema lineare che nasce dall’imposizione delle condizioni
di interpolazione e delle opportune condizioni ai bordi;
e , sono la soluzione del sistema lineare che nasce dall’imposizione delle condizioni di
interpolazione e delle opportune condizioni ai bordi.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 50/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Parametrizzazione
Il modo in cui viene calcolato il parametro delle coppie ( è
detto parametrizzazione. Tale scelta è di particolare importanza nel calcolo della curva spline che
interpola un insieme di punti nel piano in quanto influenza la scelta dei nodi della spline
interpolante.
Parametrizzazione uniforme
La scelta più semplice, per la quale i valori di sono equidistanti nell’intervallo di variabilità del parametro
, è detta parametrizzazione uniforme ed è quella algoritmicamente più veloce:
Generalmente si utilizza . La parametrizzazione uniforme, tuttavia, non tiene conto della distanza
reale fra i punti da interpolare.
Parametrizzazione mediante corda
La parametrizzazione mediante corda, invece, tiene conto della distanza reale tra i punti: l’intervallo tra
due valori successivi del parametro è proporzionale alla lunghezza del segmento corrispondente.
Per determinare i valori del parametro t si può procedere come segue:
Tale metodo porta a risultati migliori rispetto alla parametrizzazione uniforme.
Parametrizzazione di “Foley”
Questa tecnica è un’evoluzione della parametrizzazione mediante corda in quanto, oltre a considerare le
distanze tra i punti da interpolare, valuta anche gli angoli formati dai segmenti con uniscono segmenti
successivi.
∆ ∙ ∙
∙ ∙
Parametrizzazione centripeta
La parametrizzazione centripeta definisce una distanza specifica per il calcolo di ∆ .
∆
∆
La scelta del valore
permette di definire un modello che definisce le curve in modo da minimizzare
l’accelerazione centripeta di un oggetto che si muove lungo un percorso.
Uniforme Mediante corda Foley Centripeta
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 51/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Non è possibile definire in generale quale sia la parametrizzazione migliore, tuttavia deve essere
considerata un’importante proprietà: l’invanrianza per le trasformazioni affini. Tra le parametrizzazioni
elencate, solo la parametrizzazione uniforme gode di tale proprietà, le altre dipendono dalla lunghezza dei
segmenti che non sono invarianti per le trasformazioni affini.
La scelta della parametrizzazione influenza anche la scelta dei nodi delle due spline parametriche
interpolanti e :
con la parametrizzazione uniforme possono essere scelti nodi coincidenti con i punti del
parametro, in questo caso la matrice dei coefficienti del sistema lineare da risolvere è quasi
tridiagonale e ben condizionata
con la parametrizzazione mediante corda è importante ottenere che i nodi siano distribuiti nel
modo più uniforme possibile, rispettando la condizione che nel supporto di ciascuna funzione base
ci sia almeno un punto di interpolazione.
Regolarità della curva
La derivata di è il vettore tangente alla curva, le cui componenti sono le derivate delle corrispondenti
componenti parametriche:
Una curva composta da due segmenti di curva può vere, nel punto di giunzione, diversi tipi di regolarità. In
particolare si considerano la continuità geometrica ( ) o la continuità parametrica (
).
Tipo di continuità Condizioni
Continuità
geometrica
I due segmenti di curva sono coincidenti in un estremo
Continuità
geometrica
I due segmenti di curva sono coincidenti in un estremo
Le direzioni dei vettori tangenti ai due segmenti di curva sono uguali nel punto di
giunzione (è necessario che i due vettori tangenti siano uno multiplo dell’altro)
Continuità
parametrica
I due segmenti di curva sono coincidenti in un estremo
Le direzioni dei vettori tangenti ai due segmenti di curva sono uguali nel punto di
giunzione
Il modulo dei vettori tangenti ai due segmenti di curva sono uguali nel punto di
giunzione
Continuità
parametrica
I due segmenti di curva sono coincidenti in un estremo
Le direzioni e il modulo dei vettori
sono uguali nel punto di
giunzione
In generale, viste le condizioni, la continuità parametrica implica la continuità geometrica
; tuttavia
esiste un’eccezione: quando i vettori tangenti ai due segmenti di curva hanno entrambi componenti nulle
nel punto di giunzione non si può dire nulla sulla direzione, pertanto può non esserci continuità
geometrica.
Le curve spline polinomiali di ordine m in cui i nodi interni sono tutti nodi semplici, sono curve che hanno
continuità parametrica .
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 52/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Interpolazione di classe C1
Interpolare utilizzando curve spline cubiche di classe C2
è troppo restrittivo in quanto queste lasciano
libera solo la derivata terza: costruire pezzi di polinomi cubici che si raccordano solo sul valore della
derivata prima, lasciando libera anche la derivata seconda, permette una ricostruzione più flessibile.
Interpolare utilizzando curve spline cubiche di classe C1
, significa utilizzare pezzi di polinomi cubici per
ogni intervallo internodale e garantire che i nodi coincidano in valore e derivata prima.
Funzioni base di Hermite
Assegnati agli estremi dell’intervallo i valori e della funzione e e della derivata prima, il
poligono cubico che interpola i dati
è dato da:
∙ ∙ ∙ ∙
dove
∙ ∙
∙
∙ ∙
Polinomio interpolatore di Hermite
Assegnati i valori il polinomio interpolatore di Hermite , tale che
e si esprime come:
∙ ∙ ∙ ∙
Poiché sono definite nell’intervallo , è necessario applicare una
trasformazione lineare affine che mappi il punto ∈ in ∈ :
∈
Si ha che:
e sono invarianti per trasformazioni affini: e
e non sono invarianti per trasformazioni affini e vale che:
o ∙
o ∙
Si può verificare che il polinomio di Hermite in ogni sottointervallo coincide con un polinomio cubico
che soddisfa le seguenti proprietà:
pertanto, globalmente, si tratta di una funzione spline cubica interpolante di classe .
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 53/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Avendo a disposizione solo i valori della funzione, è necessario trovare un criterio per determinare i valori
delle derivate.
Esistono due classi di metodi:
Metodi numerici per il calcolo delle derivate
Metodi di minimizzazione
o Minimizzazione di un funzionale che tiene conto della curvatura globale
o Minimizzazione di un funzionale che tiene conto della lunghezza della funzione interpolante
o Minimizzazione di un funzionale combinazione lineare dei due precedenti.
Metodi numerici per il calcolo delle derivate
La derivata può essere calcolata:
come rapporto incrementale
come media di due rapporti incrementali successivi
come media pesata di due rapporti incrementali successivi
Shape preserving
Le interpolazioni di tipo shape preserving “mantengono l’andamento dei dati”.
Se i dati hanno andamento monotono crescente, ovvero se ∆
allora l’interpolante shape
preserving è tale che .
Se i dati hanno andamento monotono decrescente, ovvero se ∆
allora l’interpolante shape
preserving è tale che .
Se i dati hanno andamento monotono convesso, ovvero se ∆ ∆ , la funzione interpolante shape
preserving è tale che .
Se i dati hanno andamento monotono concavo, ovvero se ∆ ∆ , la funzione interpolante shape
preserving è tale che .
L’interpolazione di Hermite è un tipo di funzione per cui è
facile richiedere tale caratteristica: si tratta di determinare le
derivate agli estremi in modo tale che si abbia monotonia e
convessità (o concavità). Gli studi fatti hanno portato ad
individuare delle regioni del piano che garantiscono che se i
valori delle derivate si trovano in esse, si ha rispettivamente
monotonia e convessità (o concavità). Tali regioni dipendono
dall’intervallo i-esimo e dai valori del rapporto incrementale ∆
dei dati.
Mi = regione di monotonia
Ti = regione di convessità
Vi = regione di concavità
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 54/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Curve interpolanti di Hermite
Dati i punti:
la curva interpolante di Hermite si esprime come:
Dati i punti:
la curva interpolante di Hermite si esprime come:
∙
∙
Le curve interpolanti di Hermite definiscono segmenti di curva quali combinazioni lineare di quattro valori:
P1
, P2
, D1
, D2
, dei quali i primi due assegnano il valore della curva, i secondi ne modellano la forma. I
coefficienti della combinazione lineare assegnati a P1
, P2
, D1
, D2
, sono i valori che le quattro funzioni base
assumono per i diversi valori del parametro nell’intervallo considerato.
Curve di Bezier
L’idea alla base delle curve di Bezier consiste nella sostituzione dei valori D1
e D2
delle curve di Hermite
(che in esse vengono interpolati) con altri due valori puntuali che non vengono interpolati ma solo
approssimati, le cui posizioni influenzano la forma della curva.
I dati di un segmento di curva cubica di Bezier sono quattro valori P0
,
P1
, P2
, P3
, dei quali P0
e P3
vengono interpolati mentre P1
e P2
sono solo
approssimati: la loro posizione determina il vettore tangente
all’inizio e alla fine del segmento di curva.
Bezier ha dimostrato che i pesi (ovvero le funzioni di t) da attribuire a
questi quattro valori, affinché avvenga quanto descritto, sono i
polinomi di Bernstein (di grado 3), essere sono le funzioni base che
permettono di ottenere il segmento di curva cubica di Bezier come
combinazione lineare dei quattro valori P0
, P1
, P2
, P3
:
Il segmento di curva cubica di Bezier è dato da:
∈
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 55/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Nel caso più generale di curve di Bezier di grado n, si utilizzano N+1 punti di controllo:
il primo e l’ultimo punto di controllo vengono interpolati
il secondo e il penultimo punto di controllo definiscono la direzione della derivata negli estremi
gli altri punti di controllo vengono approssimati e hanno lo scopo di modellare la forma della curva.
I polinomi di base di Bernstein di grado n nell’intervallo [0, 1] sono definiti da:
Una curva di Bezier di grado n è data da:
Un vantaggio dell’utilizzo della forma di Bezier rispetto a quella di Hermite
è che, lavorando interattivamente, si ottiene una modellazione della curva
in modo molto più intuitivo: la curva che si ottiene approssima quella del
poligono che formato dai segmenti di retta che congiungono i punti di
controllo; tale poligono è detto poligono di controllo.
Le curve di Bezier presentano proprietà interessanti ed utili per la computer graphics, essere sono collegate
alle proprietà delle funzioni base utilizzate.
I polinomi di Bernstein sono, infatti, adatti a rappresentare un polinomio definito in un intervallo [a, b] in
quanto sono definiti relativamente a quell’intervallo.
In generale, un polinomio di grado n sull’intervallo [a,b] può essere rappresentato come:
∈
in cui sono i polinomi di Bernstein di grado n definiti su [a,b] dalla relazione:
e sono i coefficienti che identificano il polinomio espresso nella base di Bernstein.
Tale rappresentazione si contrappone alla rappresentazione mediante la base monomiale :
Nelle applicazioni è comodo utilizzare l’intervallo [0, 1], tuttavia questo non comporta differenze in quanto
qualsiasi intervallo generico può essere ricondotto all’intervallo [0, 1] senza alterare i coefficienti
utilizzando la trasformazione:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 56/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Allora, nell’intervallo [0, 1] si ha:
∈
Si osserva che questi polinomi sono tutti dello stesso grado, in contrapposizione alla base monomiale che
utilizza monomi di grado diverso.
Esempio: polinomi di base di Bernstein di grado n = 2
Esempio: polinomi di base di Bernstein di grado n = 3
Nota: il concetto di curve di Bezier e lo studio delle proprietà di queste curve sono stati sviluppati
indipendentemente da P. De Casteljau nel 1959 (per la Renault) e da P. Bezier nel 1962 (per la Citroen) per
essere utilizzati nei rispettivi sistemi CAD.
Proprietà dei polinomi di Bernstein di grado n
I polinomi di Bernstein godono di molte proprietà che li rendono una base molto valida dal punto di vista
dei calcoli.
Ricorsività
I polinomi di Bernstein di grado n definiti in [a, b] sono legati ai polinomi di Bernstein di grado n-1 definiti
su [a, b] dalla seguente formula:
Nel caso di [a, b] = [0, 1] si ha:
∈
Tali formule sono numericamente stabili in quanto utilizzano solo quantità positive.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 57/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Non negatività
Dalla formula ricorrente segue che: ∈
I polinomi di Bernstein formano una partizioni dell’unità
Infatti, utilizzando la formula di Newton:
ponendo e si dimostra che:
Combinazione lineare convessa
Dalle due precedenti proprietà si ha che
è una combinazione lineare convessa dei valori dei suoi coefficienti, quindi:
Il numero di variazioni di segno di un polinomio espresso nella base di Bernstein è minore o uguale
al numero di variazioni di segno dei suoi coefficienti
Questa proprietà permette di avere un limite superiore per il numero degli zeri semplici per il polinomio in
[a, b].
Approssimazione uniforme di un polinomio ad una funzione
Si consideri una partizione uniforme dell’intervallo [a, b], cioè
e si consideri
l’espressione dell’approssimazione di Bernstein di grado n definita come:
È possibile dimostrare che ; infatti è una combinazione lineare convessa dei
valori di nei punti dell’intervallo, pertanto i suoi valori sono compresi tra il più piccolo dei valori di ed il
più grande dei valori di .
Interpretazione geometrica dei coefficienti di un polinomio nella base di
Bernstein
Sia dato un polinomio espresso nella base di Bernstein:
Si considerino le coppie con
. La spezzata che passa per i punti prende il
nome di poligono di controllo.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 58/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
I valori di possono essere considerati come la valutazione di una funzioni lineare spezzata nei punti :
Dalla proprietà di approssimazione segue che il polinomio
Espresso nella base di Bernstein approssima il poligono di controllo.
Inviluppo convesso
Definizione
Assegnati i punti si definisce inviluppo convesso dell’insieme dei punti l’intersezione di tutti
gli insiemi convessi contenenti i
Il grafico del poligono espresso nella base di Bernstein è contenuto nell’inviluppo convesso dell’insieme dei
vertici del suo poligono di controllo.
Proprietà dell’approssimazione di forma
Il numero di intersezioni di una qualsiasi retta con il poligono di
controllo è maggiore del numero di intersezioni della stessa retta con il
polinomio.
Queste proprietà geometriche sono di fondamentale importanza per gli
algoritmi che utilizzano le curve nella forma di Bezier in cui le
componenti parametriche sono espresse nella base di Bernstein.
Dati i vertici di controllo:
la curva di Bezier di grado n si esprime come:
Valutazione di un polinomio nella base di Bernstein e algoritmo di De Casteljau
La valutazione, in un punto , di un polinomio di grado n espresso nella base monomiale, può essere
effettuata in modo efficiente facendo uso dello schema di Horner, che ha complessità computazionale
dell’ordine di O(n) ed è numericamente stabile.
L’algoritmo di De Casteljau rappresenta l’analogo per un polinomio espresso nella base di Bernstein:
consiste nell’applicare ripetutamente le formule ricorsive viste per i polinomi della base di Bernstein.
La valutazione in un punto t consiste nella valutazione:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 59/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Dalle proprietà dei polinomi di base di Bernstein, ogni polinomio è esprimibile come combinazione
lineare convessa di due polinomi di base di Bernstein di grado n-1:
∙ ∙
∙ ∙
∙ ∙
considerando che si ha
∙ ∙
∙ ∙
∙ ∙
∙ ∙
∙ ∙
∙ ∙
∙ ∙
ponendo
∙
∙
si ha
Ora, applicando n-1 volte la formula ricorrente si calcolano successivamente i coefficienti:
∙
∙
Si osservi che ogni volta che viene applicata la formula ricorsiva si perde un elemento della base,
diminuisce il grado ma anche il numero degli elementi.
Al passo j-esimo si ha:
∙
∙
Quando j=n si ottiene:
∙
∙
L’algoritmo di De Casteljau non fa uso delle funzioni base: ad ogni passo calcola una combinazione
convessa dei coefficienti al passo precedente. È computazionalmente valido sia perché elimina il problema
di passare attraverso le funzioni base, sia perché permette di calcolare ciascuna nuova grandezza come
combinazione convessa di due grandezze precedenti, mantenendo stabile l’algoritmo. Può essere
schematizzato come segue:
…
…
… … … …
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 60/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
La valutazione di un polinomio nella base di Bernstein con questo algoritmo ha un costo computazionale di
somme e moltiplicazioni.
La maggiore complessità computazionale O(n2
/2) rispetto a quella dello schema di Horner pari a O(n) è
compensata da una maggiore stabilità numerica ovvero ad una minore sensibilità ad eventuali
perturbazioni sui coefficienti rispetto agli algoritmi che utilizzano la base delle potenze.
Interpretazione geometrica dell’algoritmo di De Casteljaue per curve di Bezier
al primo passo, i punti
si trovano rispettivamente sul
primo, secondo, n-esimo lato del poligono di controllo, infatti la formula
∙
∙
mostra che
si trova sul segmento che unisce
e
in una posizione che dipende dai dati. La stessa cose vale ad
ogni passo.
Proprietà dell’algoritmo di De Casteljau
L’algoritmo di De Casteljau:
1. è numericamente stabile: si eseguono solo somme e
moltiplicazioni per coefficienti positivi.
2. è invariante per trasformazioni affini, pertanto invece di valutare una curva e poi applicare una
trasformazione, si può applicare la trasformazione affine ai punti di controllo e poi
applicare l’algoritmo
3. fornisce un metodo semplice per suddividere curve di Bezier: infatti il punto in cui si valuta la
curva, rappresenta un punto di suddivisione della curva in dur curve di Bezier: una per ∈ e
una per ∈ . I punti di controllo delle due nuove curve si trovano rispettivamente nella prima
colonna e sulla diagonale della tabella dell’algoritmo di De Casteljau:
Punti di controllo del
secondo segmento di
curva di Bezier
←
↖ Punti di controllo del primo segmento di
curva di Bezier
Le due curve che si raccordano in fino alla derivata n-esima sono espresse da:
∈
∈
Se il procedimento di suddivisione è iterato, cioè se ogni segmento di curva viene suddiviso a sua
volta, si ottiene che la successione dei poligoni di controllo dei vari segmenti di curva ottenuti
converge velocemente alla curva originale di Bezier, all’addensarsi dei punti di suddivisione
all’interno dell’intervallo parametrico.
Il metodo delle suddivisioni ripetute è spesso utilizzato per rendere la curva graficamente,
sostituendo la curva teorica con l’insieme dei punti di controllo dei vari segmenti.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 61/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Elevamento di grado di un polinomio nella base di Bernstein (Degree Elevation)
Esistono situazioni nelle quali è necessario esprimere un polinomio di grado n come un polinomio di grado
n+1, per esempio nel caso in cui si debbano sommare due polinomi di grado diverso. Nel caso in cui il
polinomio è espresso nella base monomiale, tale operazione risulta essere semplice, viceversa utilizzando
la base di Bernstein, tale passaggio non risulta essere immediato.
Se e allora non è
possibile sommare direttamente questi due polinomi, non è neppure possibile raccogliere le funzioni base
e sommare i coefficienti perché hanno grado diverso. Bisognerebbe passare alla forma nella base
monomiale e poi fare la somma. È possibile però anche elevare di grado il polinomio , ovvero
esprimerlo nella base .
L’operazione di degree elevation permette di esprimere un polinomio di grado n come un polinomio di
grado n+1, sempre nella base di Bernstein. Essa consiste nell’individuare i coefficienti del polinomio di
grado superiore conoscendo i coefficienti del polinomio da elevare di grado:
I coefficienti nella nuova base devono essere tali che:
Allora:
Estendendo la prima sommatoria per , ponendo ed esprimendo la seconda
sommatoria per , si ha:
Variando la seconda sommatoria per , ponendo , si ha:
A questo punto, ricordando che il polinomio in grado n+1 è:
Affinché si abbia deve accadere che:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 62/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
ovvero:
da cui:
∙
∙
∙
∙
∙
∙
In conclusione, i nuovi coefficienti (che si trovano sul segmento che unisce e ) sono ottenuti
interpolando linearmente i vecchi coefficienti per il valore del parametro .
Si osservi che la formula che fornisce i nuovi coefficienti altro non è che una combinazione convessa dei
vecchi coefficienti. Si ha che il nuovo poligono di controllo è interno all’inviluppo convesso dei nuovi
coefficienti.
Il poligono di controllo aumentato di grado è più vicino al grafico del polinomio. Il processo di elevamento
può essere iterato ottenendo una successione di poligoni di controllo che, si dimostra, converge al
polinomio medesimo. Tale convergenza è però troppo lenta per poter essere utilizzata a scopi pratici.
Riduzione di grado di un polinomio nella base di Bernstein
Generalmente scrivere un polinomio di grado n+1 come un polinomio di grado n, non è un’operazione
esatta. Solo nel caso in cui di grado n+1 sia stato ottenuto come elevamento di grado è possibile ottenere i
coefficienti dai coefficienti :
∙
Derivata prima di un polinomio nella base di Bernstein
∈
∈
La derivata di un elemento della base di Bernstein è:
Osservando che:
Si ha:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 63/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Per definizione:
Allora:
Tale espressione evidenzia il fatto che il polinomio di Bernstein è tangente negli estremi al segmento che
unisce i primi due punto e gli ultimi due punti di controllo rispettivamente.
Se , nella prima sommatoria . Se , nella prima sommatoria . Quindi:
Infine, ponendo , si ha:
Cambiamento di base
Come già detto, l’algoritmo di De Casteljau ha una complessità maggiore rispetto allo schema di Horner
per la valutazione di un polinomio. Per questa ragione (oltre alla fatto che a volte è necessario passare
dalla base di Bernstein alla base monomiale e viceversa) si utilizza la matrice di cambiamento di base.
Tale matrice, che permette di passare dalla base dei polinomi di Bernstein di grado n alla base monomiale
di grado n, è la matrice Λ di ordine n+1, i cui elementi sono dati da:
La matrice di cambiamento di base che permette di passare dalla base monomiale di grado n alla base dei
polinomi di Bernstein di grado n è la matrice Λ-1
di ordine n+1, i cui elementi sono dati da:
Si può dimostrare che ogni monomio può essere espresso nella forma
E viceversa, ogni polinomio di Bernstein si può scrivere nella forma:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 64/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Esempio (n=2)
Λ
è la matrice che fa passare dalla base di Bernstein alla base monomiale, mentre la matrice
Λ
Fa passare dalla base monomiale alla base di Bernstein.
Per quanto riguarda i coefficienti si ha:
Siccome:
Λ
Allora:
Λ e Λ
Esempio
Sia , la matrice di cambiamento di base Λ
Λ
quindi il polinomio espresso nella base di Bernstein avrà, per coefficienti:
Pertanto, si passa dai coefficienti di una rappresentazioni ai coefficienti dell’altra semplicemente
moltiplicandoli per la matrice di cambiamento di base.
Osservazione: il primo e l’ultimo coefficiente nella base di Bernstein sono esattamente il valore che
nella base monomiale assume in 0 ed in 1.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 65/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Nota: poiché la valutazione di un polinomio nella base di Bernstein è computazionalmente più costosa
rispetto alla valutazione di un polinomio nella base monomiale utilizzando lo schema di Horner, per
polinomi di grado basso di cui si devono effettuare molte valutazioni può essere conveniente effettuare una
conversione di base e procedere con lo schema di Horner. Tale procedimento è sconsigliato per polinomi di
grado maggiore o uguale a 4 per ragioni di stabilità.
Proprietà delle curve di Bezier
1. Il grado di polinomi Bernstein che parametrizzano la curva è sempre dato dal numero di punti di
controllo meno 1 (n+1 punti di controllo determinano polinomi di grado n).
Questo è uno strumento che permette flessibilità in quanto è possibile aumentare i gradi di libertà
della curva aumentando il numero dei punti di controllo; tuttavia all’aumentare dei nodi di controllo
aumenta il grado dei polinomi e, conseguentemente, la complessità computazionale O(n2
/2).
2. La curva segue la forma del poligono di controllo e si trova sempre nell’inviluppo convesso dei
punti di controllo.
3. Il primo e l’ultimo punto di controllo sono l’inizio e la fine della curva e vengono interpolati.
4. I vettori tangenti alla curva nel primo e nell’ultimo punto coincidono con il primo e l’ultimo lato del
poligono di controllo.
5. Le intersezioni della curva con una retta sono sempre in numero minore o, al massimo, uguale a
quelle che la retta ha con il poligono di controllo (variation diminishig)
6. Le curve di Bezier sono invarianti per trasformazioni affini. La curva è trasformata applicando una
qualunque trasformazione affine ai suoi punti di controllo.
Svantaggi delle curve di Bezier
Esistono alcuni difetti che rendono le curve di Bezier non del tutto adatte alla modellazione:
1. I vertici di controllo non permettono di effettuare un controllo locale della curva. Infatti, muovendo
un qualunque vertice di controllo si ottiene un effetto su tutta la curva, anche se esso è meno
evidente nelle zone lontane dal punto che si è spostato. Questo perché i polinomi di base di
Bernstein sono diversi da zero su tutto l’intervallo.
2. La relazione tra il numero dei vertici di controllo e il grado della curva è obbligata.
Per ovviare a questo problema è possibile utilizzare più segmenti di curve di Bezier di grado basso
(n=3) nel caso si abbia un elevato numero di vertici di controllo. Tuttavia deve essere considerato il
problema della continuità globale: la curva globale potrà essere G0
se solo il punto di raccordo è in
comune, se il punto precedente e quello seguente sono allineati allora la curva potrà essere G1
. Per
ottenere questo risultato si perdono però gradi di libertà.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 66/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Curve Spline polinomiali di ordine m a nodi multipli
In analisi matematica, una spline è una funzione, costituita da un insieme di polinomi raccordati tra loro, il
cui scopo è interpolare in un intervallo un insieme di punti (detti nodi della spline), in modo da essere
continua (almeno fino ad un dato ordine di derivate) in ogni punto dell'intervallo.
Le Spline polinomiali a nodi semplici sono funzioni che presentano la massima regolarità per essere
polinomiali a tratti. Tale massima regolarità di classe Cm-2
è, a volte, troppo elevata per permettere alla
funzione spline di seguire bene l’andamento di dati che presentino un comportamento in parte molto
regolare, in parte meno regolare.
È importante allora aggiungere gradi di libertà alla spline, riducendo all’occasione le condizioni di raccordo
sulle derivate, introducendo il concetto di nodi multipli.
Spline polinomiali a nodi multipli
Definizione
Sia [a, b] un intervallo chiuso e limitato sia ∆ una partizione di [a, b] così definita:
∆
che induce una partizione di [a, b] in k+1 sottointervalli:
Sia m un intero positivo e sia un vettore di interi positivi tali che .
Si definisce funzione spline polinomiale di ordine m con nodi di molteplicità , una funzione
che in ciascun sottointervallo coincide con un polinomio di ordine m, e che nei nodi
soddisfi le condizioni di continuità:
La differenza con le spline polinomiali a nodi semplici consiste nel fatto che è possibile variare il tipo di
raccordo in un nodo a seconda del valore .
In base a questo valore si può decidere sino a quale derivata effettuare il raccordo; maggiore sarà la
molteplicità, minori saranno le condizioni di raccordo sui nodi.
Nota: se si ottiene una spline a nodi semplici. Se non si ottiene alcun raccordo nel
nodo i-esimo.
Esempio
Sia , se per un certo il nodo è semplice:
Se il nodo è doppio
Se il nodo è triplo
Man mano che aumenta la molteplicità dei nodi, si riducono le condizioni di raccordo nei nodi.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 67/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Teorema
Lo spazio ∆ delle spline polinomiali di ordine m a nodi multipli con nodi di molteplicità
, ha dimensioni pari a , dove .
Dimostrazione intuitiva
Per ciascuno dei sottointervalli, il polinomio di ordine m ha m gradi di libertà, si hanno quindi
gradi di libertà; a questi si devono sottrarre le condizioni di raccordo imposte su ogni nodo
. Si ha:
Nel caso in cui e quindi: , si ricade nelle spline polinomiali a nodi semplici di
dimensione .
Funzione B-Spline normalizzate
In analogia con il caso di nodi semplici, si osserva come ogni spline polinomiale a nodi multipli
∈ ∆ possa essere espressa come:
∆
Partizione nodale estesa
Per poter costruire tutte le B-spline normalizzate che costituiscono la base per ∆ è necessario
costruire una partizione nodale estesa ∆
con . Nel caso di nodi multipli la si costruisce
nel seguente modo:
a) i nuovi nodi sono semplici, ma possono coincidere
b)
c) sono scelti in modo tale che siano coincidenti con:
d)
I punti vengono anche chiamati break points.
Una volta costruita la partizione nodale estesa, l’insieme delle B-spline normalizzate viene definito
mediante la seguente formula ricorrente:
≠
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 68/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Proprietà delle funzioni B-Spline con nodi multipli normalizzate
Formano una base per lo spazio ∆
Ciascuna ∈ ∆ può essere espressa come:
∈
Per la proprietà di supporto compatto delle B-Spline, se ∈ , si ha:
Sono non negative sul loro supporto
∈
Costituiscono una partizione dell’unità
Dalle ultime due proprietà, si ha che la spline è una combinazione lineare convessa dei
coefficienti , quindi è compreso tra il minimo e il massimo coefficiente:
Inoltre si ha controllo locale: per la proprietà di supporto compatto delle B-spline, la valutazione del
polinomio in un punto ∈ si riduce a:
In quanto le uniche B-spline diverse da 0 su un punto ∈ sono
Si cha che:
Proprietà di variation diminishing
Sia ∈ ∆ e sia rappresentata nella nase delle B-spline normalizzate:
∈
Si ha che il numero di variazioni di segno della funzione spline è minore uguale al numero di variazioni di
segno dei coefficienti.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 69/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Curve B-Spline
Dati i vertici di controllo per definire una curva B-Spline è necessario:
Fissare l’ordine delle B-Spline normalizzate
Fissare l’intervallo [a, b]
Fissare il numero e la molteplicità dei break points e, conseguentemente, la partizione nodale
estesa
La dimensione dello spazio deve essere uguale al numero dei vertici ci controllo N, cioè .
La curva B-Spline si esprime come:
∈
L’utilizzo delle B-Spline normalizzate risulta essere più complesso, tuttavia è anche più flessibile rispetto
all’uso dei polinomi di Bernstein: infatti se per definire una curva di Bezier, una volta fissati i vertici di
controllo rimane fissato anche il grado dei polinomi di base di Bernstein, nel caso delle curve spline ci sono
maggiori gradi di libertà.
Valutazione di una funzione spline
Si è visto che, assegnata la partizione nodale estesa ∆ , una ∈ ∆ può essere espressa come:
Se ∈ , allora si ha:
Esistono due algoritmi per valutare in un punto.
Il primo algoritmo calcola le funzioni base diverse da zero sul punto ∈ :
… ..
…
Un buon algoritmo per valutare tutte le funzioni base B-Spline normalizzate di ordine m diverse da zero in
un punto, ha complessità:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 70/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Il secondo algoritmo, proposto da De Boor, è l’analogo, per le funzioni B-Spline, dell’algoritmo di De
Casteljau per i polinomi in forma di Bernstein: si ottiene sostituendo, di volta in volta, alle B-Spline di
ordine m la combinazione di due B-Spline di ordine inferiore, come stabilito dalle formule ricorrenti.
Osservando che le funzioni di base di ordine diverse da 0 sull’intervallo ∈ sono quelle che
hanno indice che va da fino a , si può estendere la prima sommatoria a partire da
fino a . Inoltre si può estendere la seconda sommatoria da fino a sostituendo alle
occorrenze di e tenendo conto che per la funzione base nulla:
Ora, ponendo
Si ha:
La B-Spline ottenute è di ordine ; iterando il procedimento volte si ottiene il valore della B-Spline in
un punto in termini di una funzione base di ordine 1, cioè in termini di un solo coefficiente:
Si è ottenuto pertanto che il valore della B-Spline calcolato in è quello di una B-Spline di ordine uno per un
opportuno coefficiente. Lo schema che si ottiene è il seguente:
…
…
… …
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 71/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Ovvero:
La complessità computazionale è
È possibile, come con l’algoritmo di De Casteljau, valutare la curva in un punto mediante una
combinazione dei coefficienti.
Diversamente dall’algoritmo per le curve di Bezier, che lavorano su tutti i coefficienti, il corrispettivo
algoritmo per le B-Spline lavora solo con i coefficienti definiti nel supporto grazie alle proprietà delle
funzioni base, che sono a supporto compatto, e permettendo di superare il grande problema delle curve di
Bezier per cui non sono consentite modifiche a livello locale.
Algoritmo di inserimento di un nuovo nodo in una partizione nodale già
esistente (Knot Insertion)
Considerando, ad esempio, due curve B-Spline cubiche:
∆
∆
non risulta possibile sommarle direttamente, pur essendo entrambe cubiche.
Si vuole allora esprimere come una B-Spline che abbia gli stessi nodi dello spazio cui appartiene .
Per farlo si inserisce un nodo nella rappresentazione di in corrispondenza della posizione 2/4; in
questo modo i due spazi hanno lo stesso grado di libertà e diventa possibile sommare le due curve.
Una volta inserito il nodo cambiano:
Le funzioni base di che diventano uguali a quelle di
I coefficienti di .
In linea generale, considerando una partizione nodale estesa ∆
, si vuole individuare il tipo di
relazione che intercorre tra essa e quella che si ottiene aggiungendo il nodo ∈ .
La nuova partizione nodale ∆
è definita come:
∆
È possibile inserire il nuovo nodo dove si vuole, anche in corrispondenza di un altro nodo già esistente (in
tal caso si aumenta la molteplicità di quel nodo).
Si vuole allora studiare la relazione tra le funzioni base del nuovo spazio, e le
funzioni base , dello spazio iniziale.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 72/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Per la caratteristica di localizzazione delle funzioni base si ha che non cambiano tutte: tra esse esiste la
seguente relazione:
Si vogliono ora individuare i coefficienti tali che sia:
Utilizzando la relazione tra le funzioni base si ha:
I valori sono tutti compresi tra 0 e 1, quindi i sono una combinazione convessa dei e il loro calcolo
risulta stabile.
L’algoritmo di Knot Insertion per B-Spline è l’analogo dell’algoritmo di degree elevation per cuver di Bezier;
la differenza è la localizzazione in quanto solo i coefficienti dai fino a sono modificati per
l’inserimento di un nodo nell’intervallo .
L’algoritmo di Knot Insertion può essere utilizzato ripetutamente per ottenere la valutazione di una
funzione spline in un punto: infatti se un nodo ha molteplicità , solo una funzione base è diversa da 0
e quel nodo vale 1, quindi il coefficiente unico dà anche il valore della B-Spline in quel punto. Si parte allora
dall’inserimento di un nodo nel punto dove si vuole valutare la B-Spline, ottenendo:
Si procede inserendo un secondo nodo in , e si ottiene:
E si procede fino ad inserimenti:
Ora, tenendo conto che man mano che aumenta la molteplicità di un nodo diminuisce il numero di funzioni
base diverse da zero in quel punto, si ottiene la riduzione:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 73/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
La valutazione di una B-Spline in un punto mediante l’inserimento di un nodo, coincidente con di
molteplicità , coincide con l’algoritmo di valutazione di De Boor.
Questo algoritmo può essere utilizzato anche per la suddivisione di funzione B-Spline in due funzioni: una
definita su e l’altra definita su :
∈
∈
L’unica differenza è che deve avere molteplicità .
Osservazioni:
Inserendo un nodo nella partizione nodale, vengono modificate le funzioni base e viene quindi
modificata la base dello spazio vettoriale, tuttavia la curva non cambia; in altri termini: modificando
la partizione nodale con l’inserimento, la modellazione non cambia.
L’inserimento dei nodi è la procedura base dell’algoritmo geometrico di De Boor per il disegno di
una curva B-Spline. Per ottenere un punto sulla curva è necessario inserire un noto un numero di
volte pari al grado delle funzioni base.
Algoritmo di Knot-Insertion (caso curve B-Spline)
Sia
la curva spline di ordine definita sulla partizione nodale estesa ∆
.
Si inserisce un nodo ∈ ottenendo una nuova partizione nodale estesa: ∆
.
La curva, rispetto a questa nuova partizione nodale estesa diventa:
Inserendo un nodo nella partizione nodale estesa, quindi, vengono modificate le funzioni base dello spazio
vettoriale, la curva non cambia: modificano la partizione nodale estesa con l’inserimento non cambia la
modellazione; cambia però il poligono di controllo.
I coefficienti rappresentano i vertici del nuovo poligono di controllo; la modifica è solo locale: il poligono
cambia solo in parte. I punti di controllo che cambiano dipendono dal sottointervallo della partizione
nodale estesa in cui viene inserito il nuovo nodo:
I valori di dipendono dal nodo che si vuole inserire e dall’ampiezza della partizione nodale; non
dipendono dal sottointervallo .
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 74/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Esempio 1
Esempio 2
Data una partizione nodale estesa ed un insieme di vertici di controllo
dando molteplicità 4 a ciascuno dei noti interni
si ottiene la suddivisione della curva in 4 curve di Bezier: la curva non cambia, cambiano solo la poligonale.
In questo modo è possibile applicare l’algoritmo di De Casteljau per valutare ogni pezzo della curva.
L’algoritmo di De Casteljau è più sempre dell’algoritmo di De Boor perché ogni è uguale al valore del
parametro per cui si valuta.
Osservazione: inserendo i nodi nella modellazione permette di
valutare la curva
spezzare la curva
avvicinare il poligono di controllo alla curva.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 75/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Derivata prima della curva B-Spline
Siano
∈
allora la derivata prima della curva B-Spline si esprime nella seguente forma:
dove
allora
–
–
–
nella prima sommatoria, quando si ha che
nella seconda sommatoria, quanto si ha che , allora:
–
–
Pertanto, la derivata prima di una curva B-Spline è una curva B-Spline ottenuta come combinazione lineare
delle funzioni base di ordine , i cui vertici di controllo sono dati dalla combinazione lineare dei
vecchi vertici di controllo:
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 76/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Proprietà delle curve B-Spline
Le proprietà delle curve B-Spline derivano dalle proprietà delle funzioni spline che ne danno una
rappresentazione parametrica.
Il numero dei punti di controllo N, l’ordine della spline m e la somma delle molteplicità di ogni break point
K, sono legati dalla relazione:
questo permette di poter lavorare con curve di ordine basso anche a fronte di un elevato numero di punti
di controllo.
In una curva spline si possono individuare delle parti, dette spans, che corrispondono a ciascun intervallo
internodale; infatti, poiché si ha che per ∈
solo i punti di controllo influenzano la curva nel valore del parametro .
Esempio
∈
∈
∈
Pertanto: la span dipende solo dai punti di controllo ; la span dipende solo dai punti di
controllo ; la span dipende solo dai punti di controllo .
Quindi, un importante vantaggio delle B-Spline è legato a questa proprietà di controllo locale.
Allo stesso modo, se si sposta un punto di controllo, la curva sarà modificata solo relativamente nella
spans in cui risiede il nodo.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 77/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Le curve di Bezier sono un caso speciale delle curve B-Spline
Se i punti di controllo sono e si considera una spline di ordine , poiché deve valere la condizione
, significa che non si possono avere nodi interni e quindi . Ne segue quindi che la partizione
nodale estesa è data da nodi coincidenti con il primo estremo dell’intervallo e nodi coincidenti con il
secondo estremo dell’intervallo; pertanto la curva B-Spline di ordine coincide con la curva di Bezier di
grado .
Se i nodi aggiuntivi sono coincidenti con gli estremi dell’intervallo, la curva B-Spline interpola il
primo e l’ultimo punto di controllo
Invarianza per trasformazioni affini
Le curve B-Spline sono invarianti per trasformazioni affini. Pertanto se si deve traslare, ruotare o deformare
una curva, è sufficiente applicare la trasformazione solo ai punti di controllo e poi costruire la curva sui
punti trasformati. La curva subirà la trasformazione desiderata come se fosse stata applicata a tutti i suoi
punti.
Proprietà forte del guscio convesso (strong convex hull property)
Se ∈ allora
è contenuta nell’inviluppo convesso dei punti di controllo .
Da questa proprietà segue che se gli punti di controllo sono allineati, allora
la curva coincide con una retta.
Se punti sono coincidenti, allora la curva passa per il punto multiplo.
Proprietà di variation diminishing
Il numero di intersezioni di una qualsiasi retta con il poligono di controllo è
maggiore del numero di intersezioni della stessa retta con una curva B-Spline.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 78/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Il vantaggio di utilizzare Curve B-Spline
Le curve B-Spline richiedono più informazioni (grado della curva, vettore dei break points e rispettive
molteplicità) e una teoria più complessa rispetto alle curve di Bezier. I vantaggi però compensano questi
inconvenienti.
1. Una curva B-Spline può essere una curva di Bezier
2. Le curve B-Spline soddisfano tutte le proprietà importanti che hanno le curve di Bezier
3. Le curve B-Spline forniscono più flessibilità di controllo rispetto a ciò che possono fare le curve di
Bezier:
3.1. Si possono utilizzare curve di grado più basso mantenendo un grande numero di punti di controllo
3.2. Si può cambiare la posizione di un punto senza cambiare globalmente la forma dell’intera curva
3.3. Per la proprietà strong convex hull, si ha un maggiore controllo della urva
3.4. Esistono, inoltre, altre tecniche per disegnare ed editare la forma di una curva cambiando i break
points.
Va però osservato che le curve B-Spline sono curve polinomiali e pertanto non sono possono rappresentare
molte utili curve semplici come cerchi o elissi. Infine non godono dell’invarianza per trasformazioni
proiettive.
Pertanto, è richiesta una generalizzazione delle B-Spling, NURBS.
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 79/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Sommario Introduzione ............................................................................................................................................................ 1
Computer Graphics (CS) ...................................................................................................................................... 1 Image Processing (IP) ........................................................................................................................................... 1 Computer Vision .................................................................................................................................................. 1 Pattern Recognition .............................................................................................................................................. 1
Schema di un’applicazione grafica......................................................................................................................... 2 Ciclo di vita pixar ................................................................................................................................................. 2 Realtà aumentata ................................................................................................................................................. 3 Interattività vs Non interattività .......................................................................................................................... 3 Il video controller ................................................................................................................................................. 3
Tecnologia vettoriale ........................................................................................................................................ 3 Tecnologia raster .............................................................................................................................................. 3 Monitor CRT ...................................................................................................................................................... 4 Monitor LCD ...................................................................................................................................................... 4 Monitor LED ...................................................................................................................................................... 5 Pipeline di rendering ........................................................................................................................................ 5
Programmazione grafica ..................................................................................................................................... 6 La pipeline di rendering .......................................................................................................................................... 7
Sottosistema geometrico ..................................................................................................................................... 7 Model and view transformation ....................................................................................................................... 7 Lighiting ............................................................................................................................................................ 7 Projecton ........................................................................................................................................................... 7 Clipping ............................................................................................................................................................. 7 Screen mapping ................................................................................................................................................ 7 Spazi di coordinate ........................................................................................................................................... 8 Entità geometriche ........................................................................................................................................... 8 Trasformazioni geometriche affini .................................................................................................................. 8 Trasformazioni geometriche nel piano ........................................................................................................... 8 Coordinate omogenee ...................................................................................................................................... 9 Trasformazioni di base in coordinate omogenee ........................................................................................ 10 Composizione di trasformazioni ................................................................................................................... 10 Trasformazione Window to viewport ............................................................................................................ 12 Trasformazioni 3D .......................................................................................................................................... 13 Il processo di vista in 3 dimensioni .............................................................................................................. 14 Le proiezioni ................................................................................................................................................... 14 I parametri della vista 3D ............................................................................................................................... 17 Definire i parametri di una vista sintetica .................................................................................................... 18
Sottosistema raster ............................................................................................................................................ 20 Algoritmi ......................................................................................................................................................... 20 Drawing ........................................................................................................................................................... 20 Algoritmo DDA (digital differential analyzer) ............................................................................................... 21 Algoritmo di Bresenham (midpoint) .............................................................................................................. 21 Algoritmo Midpoint per circonferenze o ellissi ............................................................................................ 23 Filling ............................................................................................................................................................... 24 Clipping ........................................................................................................................................................... 25 Antialiasing ..................................................................................................................................................... 28
OpenGL ................................................................................................................................................................... 30 Introduzione ....................................................................................................................................................... 30 Librerie GLU e GLUT ........................................................................................................................................... 30 Programmazione window-based ....................................................................................................................... 30 Alcune funzioni per la gestione della window ................................................................................................. 31
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 80/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
void glutInit(int *argcp, char **argv); ........................................................................................................... 31 void glutInitWindowSize(int width, int height); ............................................................................................ 31 void glutInitWindowPosition(int x, int y); ...................................................................................................... 31 void glutInitDisplayMode(unsigned int mode); ............................................................................................ 31 int glutCreateWindow(char *name); .............................................................................................................. 31 int glutCreateSubWindow(int win, int x, int y, int width, int height); ......................................................... 32 void glutSetWindow(int win); ......................................................................................................................... 32 int glutGetWindow(void); ............................................................................................................................... 32 void glutDestroyWindow(int win); ................................................................................................................. 32 void glutPositionWindow(int x, int y); ........................................................................................................... 32 void glutReshapeWindow(int width, int height); .......................................................................................... 32 void glutFullScreen(void); ............................................................................................................................... 32 void glutShowWindow(void); .......................................................................................................................... 32 void glutHideWindow(void); ........................................................................................................................... 32 void glutIconifyWindow(void); ....................................................................................................................... 32 void glutSetWindowTitle(char *name); .......................................................................................................... 32 void glutSetIconTitle(char *name); ................................................................................................................ 32 void glutSetCursor(int cursor); ...................................................................................................................... 32
Alcune funzioni per la gestione degli eventi ................................................................................................... 33 void glutDisplayFunc(void (*func)(void)); ...................................................................................................... 33 void glutReshapeFunc(void (*func)(int width, int height)); .......................................................................... 33 void glutKeyboardFunc(void (*func)(unsigned char key, int x, int y)); ....................................................... 33 void glutSpecialFunc(void (*func)(int key, int x, int y)); ............................................................................... 33 void glutMouseFunc(void (*func)(int button, int state, int x, int y)); .......................................................... 33 void glutMotionFunc(void (*func)(int x, int y)); ............................................................................................ 33 void glutPassiveMotionFunc(void (*func)(int x, int y)); ................................................................................ 33 void glutIdleFunc(void (*func)(void)); ............................................................................................................ 33 void glutTimerFunc(unsigned int msecs, void (*func)(int value), value); ................................................... 33 void glutMainLoop(void); ............................................................................................................................... 33
Funzioni per la gestione dei menu ................................................................................................................... 34 int glutCreateMenu(void (*func)(int value)); ................................................................................................. 34 void glutSetMenu(int menu); ......................................................................................................................... 34 int glutGetMenu(void) .................................................................................................................................... 34 void glutDestroyMenu(int menu); .................................................................................................................. 34 void glutAddMenuEntry(char *name, int value); .......................................................................................... 34 void glutAddSubMenu(char *name, int menu); ............................................................................................ 34 void glutChangeToMenuEntry(int entry, char *name, int value); ................................................................ 34 void glutChangeToSubMenu(int entry, char *name, int menu); ................................................................. 34 void glutRemoveMenuItem(int entry); ........................................................................................................... 34 void glutAttachMenu(int button); .................................................................................................................. 34 void glutDetachMenu(int button); ................................................................................................................. 34
Funzioni per il testo ........................................................................................................................................... 34 void glutBitmapCharacter(void *font, int character); ................................................................................... 34 int glutBitmapWidth(GLUTbitmapFont font, int character) .......................................................................... 34 void glutStrokeCharacter(void *font, int character); .................................................................................... 34 int glutStrokeWidth(GLUTstrokeFont font, int character) ............................................................................ 35
Funzioni per il colore ......................................................................................................................................... 35 void glClearColor(GLfloat red, GLfloat green, GLfloat blue, GLfloat alpha); .............................................. 35 void glClear( GLbitfield mask); ................................................................................................................... 35
Funzioni per la definizione di coordinate ........................................................................................................ 35 void gluOrtho2D(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top); ............................... 35 void glMatrixMode(GLenum mode); .............................................................................................................. 35 void glLoadIdentity(void); .............................................................................................................................. 35
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 81/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
void gluPerspective(GLdouble fovy, GLdouble aspect, GLdouble zNear, GLdouble zFar); ....................... 35 void glViewport(GLint x, GLint y, GLsizei width, GLsizei height); ............................................................... 36
Funzioni primitive per il disegno ...................................................................................................................... 36 void glPointSize(GLfloat size); ....................................................................................................................... 36 void glVertex{D}{T}(GLType red, GLType green, GLType blue[, GLType alpha]]); ...................................... 36 void glBegin(GLenum mode); ......................................................................................................................... 36 void glVertex{D}{T}(GLType x, GLType y[, GLType z[, GLType w]]); ............................................................ 36 void glBegin(GLenum mode); ....................................................................................................................... 37 void glFlush(void); .......................................................................................................................................... 37
void glRect{T}(GLType x1, GLType y1, GLType x2, GLType y2); ..................................................................... 37 Struttura di un programma OpenGL ................................................................................................................. 37 Ovviamente è possibile definire strutture per le coordinate dei vertici. ....................................................... 37 Può essere utile definire una serie di funzioni. ............................................................................................... 37 Suggerimenti per i poligoni regolari e cerchi .................................................................................................. 37 Gestione del ridimensionamento della finestra ............................................................................................... 40 Tiling della finestra con un motivo ................................................................................................................... 40 Trasformazioni di modellazione ....................................................................................................................... 40
Librerie GLUI per l’interfaccia grafica................................................................................................................... 41 Definizioni .......................................................................................................................................................... 41 Funzioni .............................................................................................................................................................. 41
Rappresentazione di curve mediante spline polinomiali di ordine m a nodi semplici .................................... 44 Curve 2D ............................................................................................................................................................. 44
Esempi di curve in forma parametrica .......................................................................................................... 44 Rappresentazione nel calcolatore ................................................................................................................. 44
Funzioni spline polinomiali a nodi semplici .................................................................................................... 45 Definizione 1.1: spline polinomiale a nodi semplici.................................................................................... 45 Teorema: la dimensione dello spazio delle spline ∆ è m+k ................................................................ 45 Definizione 1.2: Funzione base B-spline ...................................................................................................... 45 Formule di Cox per la valutazione di una B-spline ...................................................................................... 45 Partizione nodale estesa ................................................................................................................................ 46 Risultato importante ....................................................................................................................................... 46 Proprietà delle B-spline .................................................................................................................................. 46 Proprietà delle spline valutate mediante B-spline ........................................................................................ 46 Proprietà di variation diminishing di una spline espressa s(x) nella base delle B-spline normalizzate .. 47 Interpolazione mediante funzioni spline polinomiali a nodi semplici ....................................................... 47 Teorema di Schoemberg Whitney .................................................................................................................. 47 Condizione di spline cubica naturale ............................................................................................................ 48 Condizione sulla derivata prima.................................................................................................................... 48 Condizione sulla derivata seconda ............................................................................................................... 48 Condizione di periodicità ............................................................................................................................... 48 Proprietà di convergenza delle funzioni spline di interpolazione .............................................................. 49 Curve spline interpolanti ................................................................................................................................ 49
Parametrizzazione ............................................................................................................................................. 50 Parametrizzazione uniforme ......................................................................................................................... 50 Parametrizzazione mediante corda............................................................................................................... 50 Parametrizzazione di “Foley” ......................................................................................................................... 50 Parametrizzazione centripeta ........................................................................................................................ 50 Regolarità della curva ..................................................................................................................................... 51
Interpolazione di classe C1
.................................................................................................................................... 52 Funzioni base di Hermite .................................................................................................................................. 52 Polinomio interpolatore di Hermite .................................................................................................................. 52 Metodi numerici per il calcolo delle derivate ................................................................................................... 53 Shape preserving ................................................................................................................................................ 53
Metodi numerici per la grafica (13209) A.A. 2013/2014
Prof.ssa Damiana Lazzaro – [email protected] Pag. 82/83
Appunti di Nicola Gentili – [email protected] Ultimo aggiornamento: 26/03/2014 02:00
Curve interpolanti di Hermite............................................................................................................................ 54 Curve di Bezier ....................................................................................................................................................... 54
Proprietà dei polinomi di Bernstein di grado n ................................................................................................ 56 Ricorsività ........................................................................................................................................................ 56 Non negatività ................................................................................................................................................. 57 I polinomi di Bernstein formano una partizioni dell’unità .......................................................................... 57 Combinazione lineare convessa .................................................................................................................... 57 Il numero di variazioni di segno di un polinomio espresso nella base di Bernstein è minore o uguale al
numero di variazioni di segno dei suoi coefficienti ..................................................................................... 57 Approssimazione uniforme di un polinomio ad una funzione ................................................................... 57
Interpretazione geometrica dei coefficienti di un polinomio nella base di Bernstein .................................. 57 Inviluppo convesso ............................................................................................................................................ 58
Definizione ...................................................................................................................................................... 58 Proprietà dell’approssimazione di forma ..................................................................................................... 58 Valutazione di un polinomio nella base di Bernstein e algoritmo di De Casteljau ................................... 58 Interpretazione geometrica dell’algoritmo di De Casteljaue per curve di Bezier ...................................... 60 Proprietà dell’algoritmo di De Casteljau ....................................................................................................... 60 Elevamento di grado di un polinomio nella base di Bernstein (Degree Elevation) .................................... 61 Riduzione di grado di un polinomio nella base di Bernstein ...................................................................... 62 Derivata prima di un polinomio nella base di Bernstein ............................................................................. 62 Cambiamento di base .................................................................................................................................... 63 Esempio (n=2) ................................................................................................................................................. 64 Esempio ........................................................................................................................................................... 64
Proprietà delle curve di Bezier .......................................................................................................................... 65 Svantaggi delle curve di Bezier ......................................................................................................................... 65
Curve Spline polinomiali di ordine m a nodi multipli ......................................................................................... 66 Spline polinomiali a nodi multipli ..................................................................................................................... 66 Funzione B-Spline normalizzate ........................................................................................................................ 67
Partizione nodale estesa ................................................................................................................................ 67 Proprietà delle funzioni B-Spline con nodi multipli normalizzate .................................................................. 68
Formano una base per lo spazio ∆ ....................................................................................................... 68
Sono non negative sul loro supporto ............................................................................................................ 68 Costituiscono una partizione dell’unità ........................................................................................................ 68 Proprietà di variation diminishing ................................................................................................................ 68
Curve B-Spline..................................................................................................................................................... 69 Valutazione di una funzione spline .................................................................................................................. 69 Algoritmo di inserimento di un nuovo nodo in una partizione nodale già esistente (Knot Insertion) ........ 71
Algoritmo di Knot-Insertion (caso curve B-Spline) ....................................................................................... 73 Esempio 1 ........................................................................................................................................................ 74 Esempio 2 ........................................................................................................................................................ 74
Derivata prima della curva B-Spline .................................................................................................................. 75 Proprietà delle curve B-Spline ............................................................................................................................ 76
Esempio ........................................................................................................................................................... 76 Le curve di Bezier sono un caso speciale delle curve B-Spline .................................................................... 77 Se i nodi aggiuntivi sono coincidenti con gli estremi dell’intervallo, la curva B-Spline interpola il primo e
l’ultimo punto di controllo ............................................................................................................................. 77 Invarianza per trasformazioni affini .............................................................................................................. 77 Proprietà forte del guscio convesso (strong convex hull property)............................................................ 77 Proprietà di variation diminishing ................................................................................................................. 77
Il vantaggio di utilizzare Curve B-Spline ........................................................................................................... 78