1

RAPPRESENTAZIONE DI CURVE
Mesh di poligonimesh di poligoni

Un mesh di poligoni è costituito da una collezione di lati, vertici e poligoni connessi tra loro in modo tale che ciascun lato è condiviso da al più due poligoni. Un lato connette due vertici, e un poligono è una sequenza chiusa di lati. Un lato può essere condiviso da due poligoni adiacenti, un vertice è condiviso da almeno due lati, e ogni lato deve infine essere parte di qualche poligono.

Un mesh di poligoni può essere rappresentato in diversi modi, inoltre si può ricorrere a rappresentazioni diverse anche allíinterno di una singola applicazione. Infatti, si può scegliere una rappresentazione per la memorizzazione esterna, una per uso interno, e uníaltra ancora per creare il mesh in modo interattivo.

I criteri di base per valutare le diverse rappresentazioni sono il costo in tempo e in spazio delle rappresentazioni stesse. Le operazioni tipiche su un mesh di poligoni sono: trovare tutti i lati incidenti ad un certo vertice; individuare i vertici connessi da un lato; trovare i lati di un poligono; visualizzare il mesh; identificare eventuali errori nella rappresentazione (ad esempio vertici, o lati, o poligoni mancanti).

Rappresentazione dei Mesh di Poligoni

Discuteremo tre tipi di rappresentazione: la rappresentazione esplicita, la rappresentazione con puntatori ad una lista di vertici, e la rappresentazione con puntatori ad una lista di lati.

Nella rappresentazione esplicita, ogni poligono è rappresentato da una lista di coordinate di vertici: P = ((x₁, y₁, z₁), (x₂, y₂, z₂), Ö , (x_n, y_n, z_n)). I vertici sono memorizzati nellíordine secondo il quale vorremmo incontrarli viaggiando lungo il poligono. In altre parole, le coppie di vertici successivi sono connesse da lati, inoltre cíè un lato che connette líultimo vertice della lista al primo. Per un poligono singolo, questa rappresentazione è efficiente in spazio; per un mesh di poligoni, invece, viene usato inutilmente dello spazio poiché le coordinate dei vertici condivisi sono memorizzate due volte. Inoltre manca una rappresentazione esplicita dei lati e dei vertici condivisi. Ad esempio per trascinare un vertice assieme a tutti i lati ad esso incidenti, in una tipica applicazione interattiva, dobbiamo trovare tutti i poligoni che condividono il vertice selezionato. Questa ricerca richiede diversi confronti tra le coordinate dei vertici di un poligono con quelle di tutti gli altri poligoni. Il metodo più efficiente per eseguire questo compito sarebbe quello di ordinare tutte le N coordinate, operazione che richiede nel migliore dei casi un tempo dellíordine di N log₂ N. Inoltre esiste anche la possibilità che, a causa degli arrotondamenti dovuti alla computazione, uno stesso vertice possa trovarsi ad avere coordinate diverse in ogni poligono. Per quanto riguarda la visualizzazione, questa rappresentazione richiede la trasformazione di ogni vertice e il clipping di ogni lato di ciascun poligono. Inoltre, i lati condivisi vengono disegnati due volte, e questo può introdurre degli inconvenienti dovuti alla sovrascrittura.

Nei poligoni definiti usando i puntatori a liste di vertici, ogni vertice del mesh di poligoni è memorizzato nella lista di vertici V = ((x₁, y₁, z₁), (x₂, y₂, z₂), Ö , (x_n, y_n, z_n))), una sola volta. Un poligono è quindi definito da una lista di puntatori alla lista di vertici. Questa rappresentazione presenta diversi vantaggi. Per prima cosa garantisce un notevole risparmio di spazio di memoria. Inoltre, le coordinate di un vertice possono essere modificate facilmente. Díaltro canto, tuttavia, risulta ancora computazionalmente difficile trovare i poligoni che condividono un lato, e i lati condivisi sono di nuovo disegnati due volte.

Possiamo eliminare questi due problemi rappresentando i lati in modo esplicito, come avviene nella rappresentazione tramite puntatori a liste di lati. In questo caso, abbiamo ancora una lista V di vertici, ma il poligono è rappresentato da una lista di puntatori ad una lista di lati, in cui ciascun lato appare una sola volta. Inoltre, in corrispondenza di ciascun lato nella lista, vi sono due puntatori alla coppia di vertici, memorizzati nella lista di vertici, che ne definiscono gli estremi, e uno o due puntatori ai poligoni cui il lato appartiene. Dunque, un poligono è descritto dalla lista P = (L₁, L₂, Ö , L_n) e un lato dalla lista E = (V₁, V₂, P₁, P₂). Quando un lato appartiene ad un solo poligono, P₁, oppure P₂, sarà nullo. I poligoni vengono rappresentati sul display visualizzandone i lati, in modo da evitare operazioni ridondanti di clipping e scan conversion.

In nessuna delle tre rappresentazioni, la determinazione dei lati incidenti ad un certo vertice può essere fatta in modo efficiente: tutti i lati devono essere ispezionati. Naturalmente, è possibile aggiungere delle informazioni esplicite per permettere di determinare in modo più efficiente queste relazioni.

Equazioni del piano

Quando si lavora con i poligoni, o con mesh di poligoni, spesso è necessario conoscere líequazione del piano su cui giace il poligono. In alcuni casi, líequazione è nota implicitamente dal metodo di costruzione interattiva usato per definire il poligono. Se líequazione non è nota, possiamo usare le coordinate di tre vertici per individuare il piano. Líequazione del piano è definita da

(10.1)

I coefficienti A, B e C definiscono la normale al piano, cioè il vettore . Dati tre punti sul piano, P₁, P₂ e P₃, la normale al piano può essere calcolata, ad esempio, tramite il prodotto P₁ P₂ P₁ P₃. Se il prodotto è zero, allora i tre punti sono allineati e non definiscono un piano. In questo caso, possono essere usati altri vertici, se ve ne sono di disponibili. Se il prodotto è diverso da zero, possiamo determinare D sostituendo la normale a e uno dei tre punti nellíequazione (10.1).

Se ci sono più di tre vertici, essi potrebbero non essere planari, sia per ragioni numeriche, sia a causa del metodo utilizzato per la generazione dei poligoni. In questo caso è opportuno utilizzare uníaltra tecnica per determinare líequazione del piano che più si avvicina ai vertici. Si può dimostrare che A, B e C sono proporzionali alle aree (cui è assegnato un segno) delle proiezioni dei poligoni sui piani (y, z), (z, x), e (x, y), rispettivamente. Ad esempio, se il poligono è parallelo al piano (x, y), risulterà A = B = 0, poiché le proiezioni del poligono sui piani (y, z) e (z, x) hanno area nulla.

Una volta che líequazione del piano è stata determinata, possiamo verificare di quanto il poligono risulti non planare calcolando la distanza ortogonale del piano da ogni vertice. La distanza d relativa al vertice in posizione (x, y, z) è data da

(10.2)

Questa distanza può essere positiva o negativa a seconda di dove è posizionato il punto rispetto al piano (sopra o sotto, a destra o a sinistra). Il segno di d determina infatti da quale parte si trova il punto, e se questa è la sola informazione che ci interessa, la divisione per la radice quadrata non è più necessaria.

Líequazione del piano non è unica; infatti ogni costante moltiplicativa k, diversa da zero, cambia líequazione ma non il piano. Spesso risulta conveniente normalizzare i coefficienti del piano, dividendoli per la costante di normalizzazione

(10.3)

Ciò consente di calcolare più agevolmente la distanza di un punto dal piano, poiché il denominatore dellíequazione (10.2) risulta uguale a 1.

Curve cubiche parametrichecurvecubiche parametriche

Le spezzate poligonali e i poligoni rappresentano una approssimazione di primo grado per le curve e le superfici, rispettivamente. Per raggiungere una accuratezza ragionevole, è necessario creare e memorizzare un gran numero di coordinate di estremi; inoltre la manipolazione interattiva dei dati può risultare complessa poiché è necessario posizionare in modo preciso tutti questi punti. Usando funzioni di grado maggiore è possibile sviluppare un metodo di rappresentazione delle curve più compatto e più facile da manipolare in modo interattivo. Tale metodo, inoltre, consente di ottenere forme più lisce e continue.

Le approssimazioni di grado alto sono basate, a loro volta, su tre metodi. Nel primo metodo, y e z sono espresse come funzioni esplicite di x: y = f(x) e z = g(x). Le difficoltà dovute a questo approccio sono: (1) líimpossibilità di ottenere valori multipli di y in corrispondenza di un singolo valore di x, quindi le curve quali cerchi e ellissi devono essere rappresentate tramite segmenti multipli di curve; (2) questa definizione non è invariante per rotazioni; e (3) descrivere le curve con le tangenti verticali è difficile, poiché è difficile rappresentare una pendenza infinita.

Nel secondo metodo le curve sono modellate dalle soluzioni di equazioni implicite della forma f(x, y, z) = 0. Anche questo metodo, tuttavia, può presentare alcuni inconvenienti. Líequazione potrebbe avere più soluzione di quante se ne desiderino. Ad esempio, per modellare una circonferenza potremmo usare líequazione x² + y² = 1. Ma per modellare solo metà della circonferenza siamo costretti ad aggiungere un vincolo, come x 0, che non può essere contenuto nellíequazione implicita. Inoltre, se due curve definite implicitamente si incontrano in un punto, potrebbe risultare difficile determinare se le loro direzioni tangenziali concordano nel punto di incontro.

Queste due formulazioni matematiche hanno comunque il vantaggio di permettere di determinare rapidamente se un punto giace sulla curva, oppure da quale parte si trova rispetto alla curva.

La rappresentazione parametrica delle curve, x = x(t), y = y(t), z = z(t), consente di superare tutti i problemi delle rappresentazioni in forma esplicita e implicita. Le curve parametriche sostituiscono líuso della pendenza geometrica, che potrebbe essere infinita, con i vettori parametrici tangenziali, che, come vedremo, non sono mai infiniti. Una curva è approssimata da una curva polinomiale a tratti, anziché da una curva lineare a tratti. Ogni segmento Q della curva globale è dato da tre funzioni, x, y, e z, che sono polinomi di terzo grado nel parametro t. Le cubiche sono usate molto spesso poiché i polinomi di grado inferiore consentono poca flessibilità nel controllare la forma della curva, mentre quelli di grado superiore richiedono una computazione più pesante. Nessuna rappresentazione di grado inferiore al terzo consente di interpolare con una curva due estremi specificati, con derivate specificate ad ogni estremo. Data una cubica, e quattro condizioni iniziali, è possibile determinare i suoi quattro coefficienti. Le condizioni iniziali sono date dai due estremi e dalle derivate nei due estremi. Analogamente, i due coefficienti di una retta sono determinati dai due estremi; mentre le derivate negli estremi sono determinate dalla linea stessa e non possono essere controllate indipendentemente. I polinomi di secondo grado, dotati di tre coefficienti, sono determinati dai due estremi più una terza condizione, ad esempio la pendenza o un terzo punto.

Caratteristiche di base

I polinomi di terzo grado che definiscono il segmento curvilineo

sono della forma

(10.4)

Per visualizzare una curva parametrica si deve valutare líequazione (10.4) per n valori successivi di t, separati da un passo di dimensione Per trattare con segmenti curvilinei finiti si limita il parametro t, senza perdere di generalità, allíintervallo [0, 1].

Introducendo il vettore

e la matrice C dei coefficienti

, (10.5)

possiamo riscrivere líequazione (10.4) in forma più compatta:

Q(t) = C _ T. (10.6)

La derivata di Q(t) definisce il vettore tangente parametrico della curva. Applicando questa definizione allíequazione (10.6), abbiamo

. (10.7)

Se due segmenti curvilinei si congiungono, si dice che la curva ha continuità geometrica G⁰. Se le direzioni (e non necessariamente i moduli) dei due vettori tangenti ai segmenti curvilinei coincidono nel punto di giunzione, si dice che la curva ha continuità geometrica di tipo G¹. Questo tipo di continuità, richiesta da molte applicazioni della computer graphics, discende dal fatto che le pendenze geometriche dei segmenti curvilinei sono uguali nel punto di giunzione.

Se i vettori tangenti di due segmenti curvilinei cubici sono uguali sia in modulo che in direzione nel punto di giunzione, la curva ha una continuità di primo grado nel parametro t, ovvero ha una continuità parametrica, e si dice di classe C¹. Se la direzione e il modulo delle derivate n-esime dei segmenti curvilinei nel punto di giunzione sono uguali, la curva è detta di classe Cⁿ. In generale, la continuità di classe C¹ implica la continuità geometrica di tipo G¹, ma il viceversa non è sempre vero. (Si osservi che un segmento curvilineo parametrico è continuo ovunque, e che la continuità di cui ci stiamo ora occupando è relativa esclusivamente ai punti di giunzione.)

In genere perchÈ due curve si congiungano perfettamente Ë sufficiente che coincidano le direzioni delle loro tangenti coincidano nel punto di giunzione, senza che necessariamente coincidano anche in grandezza: questa Ë la base della continuit‡ geometrica.

Un segmento curvilineo Q(t) è definito dai vincoli posti sugli estremi, sui vettori tangenti, e sulla continuità tra i segmenti curvilinei. Ogni cubica ha quattro coefficienti; dunque sono necessarie quattro costanti per poter derivare un sistema di quattro equazioni in quattro incognite la cui soluzione ci fornisce i quattro coefficienti incogniti. A seconda della scelta delle quattro costanti che definiscono le condizioni iniziali, si distinguono diversi tipi di curve. Le curve di Hermite sono definite tramite i due estremi e i vettori tangenti nei due estremi. Le curve di Bézier sono definite dai due estremi e da altri due punti che controllano i vettori tangenti negli estremi. Ci sono poi diversi tipi di curve spline, definite da quattro punti di controllo.

Per comprendere come i coefficienti dellíequazione (10.4) dipendono da quattro vincoli, riscriviamo la matrice dei coefficienti C come prodotto C = G M, dove M è una matrice 4 4 detta matrice base, e G è la matrice geometrica che contiene i quattro vincoli geometrici, cioè le condizioni iniziali che definiscono la curva. Utilizziamo la notazione G_x per indicare il vettore riga composto dalle sole componenti x della matrice geometrica. G_y e G_z sono definite in modo analogo. La matrice geometrica e/o la matrice base sono diverse per ogni tipo di curva.

Gli elementi di G e di M sono costanti, così il prodotto Q(t) = G M T risulta pari a

. (10.8)

La componente è data da

(10.9)

La curva risulta dunque esprimibile tramite una somma pesata degli elementi della matrice geometrica. I pesi sono espressi da polinomi di terzo grado in t, definiti dal prodotto M T, e sono chiamati funzioni blending. Si noti la somiglianza con le approssimazioni di secondo grado a tratti, in cui sono necessari solo due vincoli geometrici (gli estremi), e ogni tratto è dato da un segmento lineare:

(10.10)

Le curve parametriche cubiche sono dunque una generalizzazione dellíapprossimazione lineare a tratti.

Curve di Hermitecurvedi Hermite

Le curve di Hermite sono determinate dai vincoli sugli estremi, P₁ e P₄, e dai vettori tangenti negli estremi, R₁ e R₄. Per trovare la matrice base di Hermite M_H che lega la matrice geometrica di Hermite G_H ai coefficienti dei polinomi di terzo grado, dobbiamo formare e risolvere il sistema di quattro equazioni, una per ogni vincolo, nei quattro coefficienti polinomiali incogniti. Se definiamo la componente x della matrice geometrica di Hermite, M_Hx, nel modo seguente

, (10.11)

e riscriviamo x(t), definito nelle equazioni (10.4) e (10.9), come

, (10.12)

i vincoli su x(0), che deve coincidere con P₁, e x(1) che deve coincidere con P₄, si trovano per sostituzione diretta nellíequazione (10.12):

, (10.13)

. (10.14)

Derivando líequazione (10.12), otteniamo . Quindi, le equazioni relative ai vincoli sui vettori tangenti si possono scrivere nel modo seguente

, (10.15)

. (10.16)

In forma matriciale, risulta

. (10.17)

Affinché questa equazione matriciale sia soddisfatta, insieme alle equazioni analoghe relative alle coordinate y e z, M_H deve essere uguale alla matrice inversa della matrice presente nellíequazione (10.17):

. (10.18)

La matrice M_H può ora essere utilizzata nellíequazione x(t) = G_Hx M_H T per trovare x(t), e, analogamente, nelle equazioni y(t) = G_Hy M_H T e z(t) = G_Hz M_H T per determinare y(t) e z(t). Possiamo dunque scrivere

. (10.19)

dove M_H è la matrice [P₁ P₄ R₁ R₄].

Sviluppando il prodotto M_H T nellíequazione che definisce Q(t), si ricava la funzione blending di Hermite B_H, definita dal polinomio che costituisce il peso di ogni elemento della matrice geometrica:

(10.20)

La figura seguente descrive le funziooni di blending di hermite.

Figura 0.1 Le funzioni di blending di Hermite.

Figura 0.2 Esempi di curve parametriche di Hermite.

Curve di Béziercurvedi BÈzier

Le curve di Bézier sono definite dai due estremi e da altri due punti di controllo intermedi, che non appartengono alla curva, e che specificano in modo indiretto i vettori tangenti negli estremi.

Indichiamo con P₁ e P₄ gli estremi, e con P₂ e P₃ i punti intermedi. I vettori tangenti negli estremi, R₁ e R₂, sono legati ai quattro punti di controllo dalle relazioni:

(10.21)

Figura 0.3 Due curve di Bézier con i relativi punti di controllo.

La matrice geometrica di Bézier basata sui quattro punti di controllo, è definita da

. (10.22)

Quindi, la matrice M_HB che definisce la relazione G_H = G_B M_HB tra la matrice geometrica di Hermite G_H e la matrice geometrica di Bézier G_B si ricava riscrivendo líequazione (10.22) in forma matriciale:

. (10.23)

Per trovare la matrice base di Bézier M_B, si sostituisce nellíequazione (10.19) G_H = G_B M_HB, e si definisce M_B = M_HB M_H:

. (10.24)

Eseguendo il prodotto M_B = M_HB M_H, si ottiene

. (10.25)

Infine, il prodotto Q(t) = G_B M_B T risulta pari a

(10.26)

I quattro polinomi B_B = M_B T, che costituiscono i pesi nellíequazione (10.26), sono chiamati polinomi di Bernstein. Si osservi che la somma di questi quattro polinomi risulta sempre pari ad 1. Inoltre, ciascun polinomio risulta sempre maggiore o uguale a zero, per 0 t < 1. Dunque, Q(t) coincide con la media pesata dei quattro punti di controllo. Questa condizione significa che ogni segmento curvilineo, dato dalla somma dei quattro punti di controllo, pesata dai polinomi di Bernstein, è completamente contenuto nel convex hull dei quattro punti. Il convex hull per le curve sul piano è definito dal poligono convesso formato dai quattro punti di controllo (si veda la figura 10.1). Nel caso tridimensionale, il convex hull è definito dal poliedro convesso formato dai quattro punti.

Figura 0.4 I polinomi di Bernstein.

Questa proprietà vale per tutte le cubiche definite dalla somma pesata dei punti di controllo, quando le funzioni blending sono maggiori o uguali a zero. Inoltre, il fatto che la somma dei polinomi sia sempre uguale a 1 consente di ridurre il tempo computazionale, lavorando con tre soli polinomi e determinando il quarto, per ogni valore di t, per sottrazione.

Infine, questa proprietà può essere sfruttata anche per il clipping: si può applicare un algoritmo di clipping di poligoni, ad esempio líalgoritmo di Sutherland-Hodgman, per effettuare il clipping del convex hull. Se il convex hull è completamente allíinterno del rettangolo di clipping, così è anche per la curva; se il convex hull è completamente allíesterno, lo stesso accade per la curva; quindi solo nei casi intermedi in cui il convex hull interseca i bordi del rettangolo di clipping, è necessario esaminare direttamente il segmento curvilineo.

B-splineB-spline

Una spline cubica naturale è una curva polinomiale cubica, con una continuità di classe C⁰, C¹ e C², che interpola i punti di controllo. Questo tipo di curva ha un grado di continuità in più rispetto alle curve di Hermite e di Bézier, e quindi risulta di forma più liscia.

I coefficienti polinomiali delle spline naturali dipendono da tutti gli n punti di controllo; quindi per determinarli si rende necessario invertire una matrice n+1 n+1. Ciò introduce due svantaggi: (1) il movimento di un solo punto di controllo influenza tutta la curva, e (2) il tempo computazionale richiesto per líinversione della matrice può causare problemi nelle applicazioni interattive, dove si desidera poter modificare rapidamente la forma di una curva.

Le B-spline sono segmenti curvilinei i cui coefficienti polinomiali dipendono solo da pochi punti di controllo. Dunque, il tempo necessario per determinare i coefficienti risulta fortemente ridotto. Inoltre il movimento di un punto di controllo influenza solo una piccola parte della curva. Questo comportamento è chiamato controllo locale. La ìBî sta per base, infatti le B-spline possono essere rappresentate come somme pesate di funzioni polinomiali di base, a differenza delle spline naturali per cui questa proprietà non è verificata.

Le B-spline hanno lo stesso tipo di continuità delle spline naturali, ma non interpolano i propri punti di controllo. Per descrivere queste curve, non descriveremo solo i singoli segmenti curvilinei che le compongono (come abbiamo fatto nella trattazione precedente), ma descriveremo la curva nel suo insieme, considerando tutti i suoi segmenti contemporaneamente.

Le B-spline cubiche approssimano una serie di m+1 punti di controllo P₀, P₁, Ö e P_m, dove , con una curva composta da mñ2 segmenti curvilinei polinomiali Q₃, Q₄, Ö e Q_m. Il parametro t può essere definito in modo che i domini corrispondenti ai vari segmenti curvilinei siano sequenziali. Diremo quindi che il parametro relativo al tratto Q_i è compreso nellíintervallo t_i t t_i+1, dove 3 i m. Per m = 3 avremo un solo tratto curvilineo Q₃, definito sullíintervallo t₃ t t₄ dai quattro punti di controllo P₀, P₁, P₃ e P₄.

Per ogni i 4, vi è un punto di giunzione, chiamato knot, tra i segmenti Q_i_ñ1 e Q_i, in corrispondenza del valore t_i del parametro, chiamato knot-value. Anche il punto iniziale t₃ e quello finale t_m₊₁ sono detti knot, così che il numero totale di knot è pari a m-1.

Le B-spline si dividono in B-spline uniformi e B-spline non uniformi. Nelle prime gli knot sono ugualmente spaziati rispetto al parametro t. Senza perdere di generalità possiamo fare líipotesi che t₃ = 0, e che gli intervalli tra gli knot siano unitari: t_i₊₁ ñ t_i = 1. Le B-spline non uniformi permettono invece di avere intervalli differenti tra gli knot.

B-spline uniformiB-splineuniformi

Ciascuno degli mñ2 segmenti curvilinei di una B-spline è definito da quattro degli m+1 punti di controllo. In particolare, il tratto Q_i è definito dai punti P_i_ñ3 , P_i_ñ2, P_i_ñ1 e P_i. La matrice geometrica della B-spline relativa al segmento curvilineo Q_i, G_BSi, è dunque data da

. (10.27)

Il primo tratto, Q₃, è definito dai punti P₀, P₁, P₂ e P₃, ed il parametro t varia tra t₃ = 0 e t₄ = 1; Q₄ è definito dai punti P₁, P₂, P₃ e P₄ e t è compreso tra i valori t₄ = 1 e t₅ = 2; líultimo tratto, Q_m, è definito dai punti P_m_ñ3 , P_m_ñ2 , P_m_ñ1 e P_m, e il parametro t è compreso tra i valori t_m = m ñ 3 e t_m₊₁ = m ñ 2. In generale, il tratto curvilineo Q_i inizia in prossimità del punto P_i_ñ2 e termina in prossimità del punto P_i_ñ1. Le funzioni blending relative alle B-spline risultano ovunque non negative e la loro somma risulta pari a 1, così che il segmento Q_i è confinato nel convex hull dei suoi quattro punti di controllo.

In analogia ai segmenti curvilinei, che sono definiti tramite quattro punti di controllo, ogni punto di controllo (ad eccezione del primo e dellíultimo della sequenza P₀, P₁, Ö e P_m) influenza esattamente quattro segmenti curvilinei. Muovendo un punto di controllo in una certa direzione, i quattro segmenti che esso influenza vengono mossi nella stessa direzione, mentre tale movimento non influenza affatto gli altri segmenti curvilinei. Per questo motivo si parla di controllo locale.

Indicando con T_i il vettore colonna [(t ñ t_i)³ (t ñ t_i)² (t ñ t_i) 1]^T, si ottiene la seguente formulazione per líi-esimo tratto curvilineo

. (10.28)

Applicando questa equazione in corrispondenza di tutti i valori di i compresi tra 3 ed m, si genera dunque líintera curva.

La matrice base B-spline, M_BS, mette in relazione i vincoli geometrici espressi nella matrice G_BS con le funzioni blending e i coefficienti polinomiali. Si può dimostrare che tale matrice risulta pari a

. (10.29)

Le funzioni blending B_BS sono definite dal prodotto M_BS _ T_i. Si osservi che le funzioni blending relative a ciascun segmento curvilineo sono esattamente uguali poiché, per ogni i, i valori di t ñ t_i variano tra 0 (per t = t_i) e 1 (per t ñ t_i₊₁). Sostituendo t ñ t_i con t, e líintervallo [t, t_i₊₁] con [0, 1], abbiamo

(10.30)

Sviluppando líequazione, e sostituendo t ñ t_i con t, si ottiene quindi

(10.31)

dove .

Non è difficile dimostrare che Q_i e Q_i₊₁ hanno continuità di classe C⁰, C¹ e C² nei punti di giunzione. Questa maggiore continuità ha però un costo che è dato dal minore controllo sulla direzione della curva. Possiamo forzare la curva facendo in modo che interpoli alcuni punti duplicando i punti di controllo; questo può risultare utile sia per gli estremi che per i punti intermedi sulla curva. Ad esempio, se P_i_ñ2 = P_i_ñ1, la curva risulta più vicino a questo punto poiché il tratto Q_i è definito da tre soli punti diversi, ed il punto P_i_ñ2 = P_i_ñ1 è pesato due volte nellíequazione (10.31), una volta dalla funzione blending B_BS_ñ2 e una volta dalla funzione B_BS_ñ1. Se un punto di controllo è utilizzato tre volte, ad esempio se P_i_ñ2 = P_i_ñ1 = P_i, allora líequazione (10.31) diventa

Q_i(t) = P_i_ñ3 _ B_BS_ñ3 + P_i _ (B_BS_ñ2 + B_BS_ñ1 + B_BS₀). (10.32)

In questo caso, Q_i è chiaramente un segmento rettilineo. Inoltre il punto P_i_ñ2 è interpolato dalla linea in corrispondenza del valore t = 1, dove i tre pesi applicati a P_i hanno somma pari a 1; tuttavia P_i_ñ3 non è in generale interpolato a t = 0. Un altro modo di pensare a questo comportamento è che il convex hull relativo a Q_i è definito da due soli punti distinti, quindi Q_i deve essere un segmento rettilineo.

B-spline non uniformiB-splinenon uniformi

Le B-spline non uniformi permettono di interpolare in modo più naturale sia gli estremi che i punti intermedi sulla curva.

Le B-spline non uniformi si differenziano da quelle uniformi per il fatto che líintervallo parametrico tra gli knot non è necessariamente uniforme. Di conseguenza, le funzioni blending non sono più uguali per tutti gli intervalli, ma cambiano da segmento curvilineo a segmento.

Queste curve hanno diversi vantaggi rispetto a quelle uniformi. Per prima cosa la continuità in certi punti di giunzione, opportunamente selezionati, può essere ridotta da C² a C¹ a C⁰ a nessuna continuità. Se la continuità è ridotta alla classe C⁰, allora la curva interpola un punto di controllo, senza gli effetti indesiderati introdotti dalle B-spline uniformi, dove i segmenti curvilinei adiacenti al punto di controllo interpolato diventano rettilinei. Inoltre, il punto iniziale e quello finale risultano facilmente interpolabili, senza dovere introdurre segmenti lineari.

Anche in questo caso abbiamo una curva continua a tratti, composta da curve polinomiali cubiche, che approssima i punti di controllo P₀, P₁, Ö e P_m. La sequenza degli knot-value è una sequenza non decrescente dei valori del parametro t corrispondenti ai punti di giunzione, da t₀ a t_m₊₄. Dunque ci sono quattro knot in più rispetto ai punti di controllo.

Poiché il numero minimo di punti di controllo è quattro, la più piccola sequenza di knot-value è composta da otto valori, e la curva è definita sullíintervallo parametrico da t₃ a t₄.

La sola restrizione sulla sequenza è che essa sia non decrescente, cosa che permette di avere knot-value successivi anche uguali. Quando ciò si verifica, il valore parametrico è chiamato knot-multiplo, e il numero di valore identici è detto molteplicità dello knot.

Il segmento curvilineo Q_i è definito dai punti di controllo P_i_ñ3, P_i_ñ2, P_i_ñ1 e P_i e dalle funzioni blending B_i_3,4(t), B_i_2,4(t), B_i_1,4(t), B_i_,4(t) attraverso la somma pesata

, (10.33)

dove 3 i m e t_i t < t_i₊₁. La curva non è definita al di fuori dellíintervallo . Quando (uno knot-multiplo), il segmento curvilineo Q_i si riduce ad un singolo punto. » proprio grazie a questa nozione di segmento curvilineo che si riduce ad un punto, che le B-spline non uniformi risultano più flessibili rispetto a quelle uniformi.

Le funzioni blending dipendono dagli intervalli tra gli knot e sono definite ricorsivamente in termini delle funzioni blending di ordine inferiore. B_i_,j(t) è la funzione blending di j-esimo ordine, relativa al punto di controllo P_i. Poiché stiamo lavorando con B-spline del quarto ordine (cioè di terzo grado, o cubiche), la definizione ricorsiva si arresta a B_i_,4(t). La ricorrenza per le B-spline cubiche è dunque data da

(10.34)

Si può dimostrare che le funzioni blending risultano ovunque non negative, e che la loro somma è pari a 1. Dunque, i segmenti curvilinei delle B-spline non uniformi giacciono allíinterno dellíinviluppo convesso (convex hull) definito dai loro quattro punti di controllo. Per gli knot di molteplicità maggiore di uno, il denominatore può risultare uguale a zero, e in questo caso si assume che la divisione per zero dia il valore zero.

Líaumento della molteplicità degli knot produce due effetti. Per prima cosa, la spline, valutata ad ogni knot-value t_i conosciuto, fornisce immediatamente un punto interno al convex hull dei punti P_i_ñ3, P_i_ñ2 e P_i_ñ1. Se t_i e t_i₊₁ sono uguali, essi devono trovarsi nel convex hull di P_i_ñ3, P_i_ñ2 e P_i_ñ1, e nel convex hull di P_i_ñ2, P_i_ñ1 e P_i. Dunque, essi devono giacere sul segmento lineare tra P_i_ñ2 e P_i_ñ1. In modo del tutto analogo, se t_i = t_i₊₁ = t_i₊₂, allora questo knot deve trovarsi nel punto P_i_ñ1. Se ancora t_i = t_i₊₁ = t_i₊₂ = t_i₊₃, allora lo knot deve trovarsi sia in corrispondenza del punto P_i_ñ1 che del punto P_i, quindi la curva si spezza. In secondo luogo, gli knot multipli riducono la continuità parametrica: da C² a C¹ per knot di molteplicità 2; da C¹ a C⁰ per knot di molteplicità 3; e da C⁰a nessuna continuità per knot di molteplicità 4.