Ciao a tutti.
Sappiamo che i punti di controllo sono all’origine di una Bézier o di una B-Spline.
E se vi dicessi che i punti di controllo non sono la “causa” della curva, ma soltanto alcune sue “fotografie”?
Benvenuti nel blossoming. 
Il blossoming ribalta questa prospettiva: i CV non sono l’oggetto matematico primitivo da cui nasce la curva, ma particolari campioni di un oggetto più ampio e interessante, il blossom.
Capire questo concetto permette di vedere sotto un’unica luce De Casteljau, De Boor, l’elevazione del grado, l’inserimento dei nodi e parecchie altre cose.
Confesso che mi sono imbattuto nella questione per puro caso, non ne avevo mai sentito parlare. 
E stavo pure per “archiviare” la cosa tra quegli artifizi matematici carini ma fini a sé stessi.
Poi, leggendo con maggiore attenzione, un paio di passaggi mi hanno colpito.
Il formalismo moderno del blossoming fu sistematizzato da Lyle Ramshaw alla fine degli anni '80, sulla base del concetto classico di polar form e di idee già presenti nei lavori di De Casteljau e De Boor.
In sintesi, la teoria classica ci mostra come funzionano i vari algoritmi, il blossoming permette di capire perché molti di essi hanno proprio quella struttura.
Ma partiamo dalle basi e, una volta tanto, la matematica che sta sotto è decisamente abbordabile.
Consideriamo un polinomio banale: f(t)=t^2
La domanda è intrigante: esiste una funzione di due variabili che contenga questo polinomio come caso particolare? … solo a un matematico possono venire certi pensieri. 
Ovvero, esiste una funzione F(u,v) tale che:
F(t,t)=t^2
Questa condizione si chiama proprietà diagonale.
Con questo esempio vinciamo facile, basta porre:
F(u,v)=uv
Infatti, se u=v=t:
F(t,t)=tt=t^2
Quindi il polinomio t^2 può essere visto come la “traccia diagonale” della funzione uv.
Ma questa soluzione è unica?
Supponiamo di inventarne un’altra:
G(u,v)=uv+(u-v)^2
Sulla diagonale:
G(t,t)=t^2
Anche questa soddisfa la proprietà diagonale.
Esistono quindi infinite funzioni che coincidono con t^2 sulla diagonale.
La sola diagonalità non basta a definire un blossom.
Se però imponiamo altre due proprietà, la situazione cambia completamente.
La prima è la simmetria:
F(u,v)=F(v,u)
Più in generale, per un blossom di n variabili:
b(u_1,u_2,\ldots,u_n)=b(u_{\sigma(1)},u_{\sigma(2)},\ldots,u_{\sigma(n)})
per qualunque permutazione \sigma degli argomenti.
Il risultato quindi non dipende dall’ordine con cui vengono forniti gli argomenti.
La seconda proprietà è la multi-affinità.
Se fissiamo tutte le variabili tranne una, la funzione deve essere affine rispetto alla variabile rimasta libera.
Occhio a non confondere affinità e linearità.
Ad esempio:
F(x)=ax+5
non è lineare perché F(0)\neq0, ma è affine.
Consideriamo invece:
F(u,v)=uv
Se fissiamo v=5:
F(u,5)=5u
e se fissiamo u=7:
F(7,v)=7v
La funzione è quindi affine (e lineare), rispetto a ciascuna variabile quando l’altra viene mantenuta costante.
Vi ricorda qualcosa? 
Questo non significa ovviamente che uv sia affine rispetto a (u,v) considerati simultaneamente nel piano.
La proprietà riguarda ogni argomento separatamente.
Un esempio che invece non va bene è:
H(u,v)=u^2v
Fissando v=3 otteniamo:
H(u,3)=3u^2
che non è affine rispetto a u.
Quindi H non può essere un blossom.
Riassumendo, fissato il grado n della rappresentazione, il blossom è una funzione di n variabili che soddisfa tre proprietà:
-
b(t,t,\ldots,t)=f(t)
-
b(u_1,\ldots,u_n)=b(u_{\sigma(1)},\ldots,u_{\sigma(n)})
-
è affine rispetto a ciascun argomento preso separatamente.
Una precisazione importante sul grado.
Lo stesso polinomio può essere rappresentato a gradi diversi.
Ad esempio t^2, considerato come polinomio di grado 2, ha blossom:
b(u,v)=uv
Ma se lo stesso t^2 viene rappresentato a grado 3, il blossom deve avere tre argomenti e diventa:
b(u,v,w)=\frac{uv+uw+vw}{3}
Non c’è contraddizione.
L’unicità del blossom vale una volta fissato il numero di argomenti, cioè il grado della rappresentazione.
Questa osservazione tornerà utile quando parleremo dell’elevazione del grado.
Vediamo ora un caso leggermente più articolato:
f(t)=3t^2+2t+1
Il termine t^2 diventa uv.
Il termine 2t deve diventare qualcosa di simmetrico e multi-affine che sulla diagonale valga 2t.
La scelta è:
u+v
perché:
t+t=2t
Otteniamo quindi:
F(u,v)=3uv+u+v+1
e infatti:
F(t,t)=3t^2+2t+1
Quaglia!
A questo punto però abbiamo costruito il blossom un po’ a occhio.
Vediamo la regola generale.
Supponiamo di avere un polinomio di grado n:
f(t)=a_nt^n+a_{n-1}t^{n-1}+\ldots+a_1t+a_0t^0
Il blossom avrà n argomenti.
Per una quadratica:
f(t)=at^2+bt+c
abbiamo: t^2\rightarrow uv
mentre il termine t deve diventare: \frac{u+v}{2}
perché: \frac{t+t}{2}=t
Quindi: F(u,v)=auv+b\frac{u+v}{2}+c
Nel caso cubico: f(t)=at^3+bt^2+ct+d
abbiamo:
t\rightarrow\frac{u+v+w}{3}
t^2\rightarrow\frac{uv+uw+vw}{3}
t^3\rightarrow uvw
e quindi:
F(u,v,w)=auvw+b\frac{uv+uw+vw}{3}+c\frac{u+v+w}{3}+d
Ma sa dove saltano fuori queste medie?
Dalle funzioni simmetriche elementari.
Per due variabili compaiono:
u+v
uv
Per tre variabili:
u+v+w
uv+uw+vw
uvw
In generale il termine t^k viene sostituito dalla media di tutti i prodotti di k variabili distinte scelti tra gli n argomenti.
Indicando con e_k(u_1,\ldots,u_n) la funzione simmetrica elementare di grado k:
b(u_1,\ldots,u_n)=\sum_{k=0}^{n}a_k\frac{e_k(u_1,\ldots,u_n)}{\binom{n}{k}}
Il fattore \binom{n}{k} compare perché esistono proprio \binom{n}{k} prodotti distinti di k variabili scelti tra n argomenti.
Sulla diagonale ognuno di questi prodotti diventa t^k, quindi la loro media restituisce esattamente t^k.
Rimane da capire se questa costruzione sia davvero obbligata.
Qui basta il caso quadratico.
Consideriamo:
f(t)=at^2+bt+c
La forma multi-affine più generale in due variabili è:
F(u,v)=Auv+Bu+Cv+D
La simmetria impone:
B=C
quindi:
F(u,v)=Auv+B(u+v)+D
Sulla diagonale:
F(t,t)=At^2+2Bt+D
Confrontando con:
at^2+bt+c
otteniamo:
A=a
B=\frac{b}{2}
D=c
e quindi:
F(u,v)=auv+\frac{b}{2}(u+v)+c
Non abbiamo scelto arbitrariamente il fattore 1/2: è imposto dalle tre proprietà.
Lo stesso ragionamento si generalizza a qualsiasi grado.
Ed è proprio questa unicità, una volta fissato il grado della rappresentazione, a rendere il blossom così interessante.
Veniamo ora alle curve di Bézier.
Partiamo da una quadratica:
C(t)=(1-t)^2P_0+2(1-t)tP_1+t^2P_2
Poiché una curva polinomiale è una funzione vettoriale, anche il suo blossom è vettoriale e restituisce direttamente punti nello spazio.
Indichiamolo con F(u,v).
I punti di controllo della Bézier quadratica possono essere ottenuti semplicemente come:
P_0=F(0,0)
P_1=F(0,1)
P_2=F(1,1)
Per una cubica:
P_0=F(0,0,0)
P_1=F(0,0,1)
P_2=F(0,1,1)
P_3=F(1,1,1)
Il numero di argomenti uguali a 1 coincide con l’indice del punto di controllo, molto carina questa cosa.
Ma perché proprio 0 e 1?
Perché stiamo utilizzando la classica parametrizzazione Bézier sull’intervallo [0,1].
E la curva stessa cos’è?
Nel caso quadratico:
C(t)=F(t,t)
nel caso cubico:
C(t)=F(t,t,t)
e in generale:
C(t)=F(t,t,\ldots,t)
La curva è quindi la restrizione del blossom alla diagonale.
Questo cambia parecchio il modo di vedere i punti di controllo.
Non sono più necessariamente l’oggetto matematico primitivo da cui partire, ma particolari campioni di una funzione più ricca.
E qui entra monsieur De Casteljau.
Consideriamo ancora la quadratica.
Conosciamo:
F(0,0)
F(0,1)
F(1,1)
e vogliamo ottenere:
F(t,t)
Per multi-affinità:
F(0,t)=(1-t)F(0,0)+tF(0,1)
quindi:
Q_0=(1-t)P_0+tP_1
Analogamente:
F(t,1)=(1-t)F(0,1)+tF(1,1)
quindi:
Q_1=(1-t)P_1+tP_2
Interpolando ancora:
F(t,t)=(1-t)F(0,t)+tF(t,1)
otteniamo:
C(t)=(1-t)Q_0+tQ_1
Lo riconoscete?
È esattamente De Casteljau.
Noi normalmente lo vediamo come un algoritmo geometrico fatto di interpolazioni successive.
Il blossoming ci permette invece di leggerlo come il modo naturale di valutare una funzione multi-affine sulla diagonale partendo dai suoi campioni agli estremi.
Le interpolazioni non sono quindi un artificio aggiunto a posteriori: derivano direttamente dalla multi-affinità.
Prima di passare alle B-Spline vediamo un’altra operazione interessante: l’elevazione del grado.
Supponiamo di avere una Bézier di grado n con blossom:
b(u_1,\dots,u_n)
e di voler rappresentare la stessa identica curva con grado n+1.
Il nuovo blossom può essere costruito facendo la media dei vecchi blossom ottenuti eliminando a turno uno degli argomenti:
\widetilde b(u_0,\dots,u_n)=\frac{1}{n+1}\sum_{j=0}^{n}b(u_0,\ldots,\widehat{u_j},\ldots,u_n)
dove \widehat{u_j} indica l’argomento omesso.
Sulla diagonale ogni termine della somma vale C(t), quindi:
\widetilde b(t,\ldots,t)=C(t)
La curva è rimasta identica.
È cambiato soltanto il grado della sua rappresentazione.
Da qui deriva anche la formula classica per i nuovi punti di controllo:
Q_i=\frac{i}{n+1}P_{i-1}+\left(1-\frac{i}{n+1}\right)P_i
con
Q_0=P_0
e
Q_{n+1}=P_n
Anche la degree elevation, quindi, entra nello stesso quadro, cosa che trovo davvero elegante.
Passiamo ora alle B-Spline.
Qui la faccenda diventa ancora più interessante perché entrano in gioco i nodi.
Prendiamo una B-Spline di grado p con vettore nodale completo:
U={u_0,u_1,\ldots,u_m}
Una B-Spline è una funzione polinomiale a tratti, quindi ogni tratto possiede il proprio blossom di p argomenti.
Le condizioni di raccordo tra i vari tratti permettono però di trattare questi blossom in maniera coerente e, per semplicità, continueremo a indicare il blossom con F.
La relazione fondamentale tra nodi e punti di controllo è:
P_i=F(u_{i+1},u_{i+2},\ldots,u_{i+p})
Ma occhio a un dettaglio.
Una B-Spline di grado p coinvolge p+1 punti di controllo per ogni knot span, ma il blossom ha p argomenti.
Ogni singolo punto di controllo corrisponde quindi a una finestra di p nodi consecutivi.
Nel caso cubico:
P_i=F(u_{i+1},u_{i+2},u_{i+3})
Prendiamo il vettore nodale clamped:
U={0,0,0,0,1,2,3,3,3,3}
Scusate ma qui preferisco usare la convenzione matematica completa e non quella interna di Rhino, che omette il primo e l’ultimo nodo.
Abbiamo:
P_0=F(0,0,0)
P_1=F(0,0,1)
P_2=F(0,1,2)
P_3=F(1,2,3)
P_4=F(2,3,3)
P_5=F(3,3,3)
Questa “tabellina” rende evidente la differenza rispetto alla Bézier.
Nella Bézier i campioni corrispondenti ai CV utilizzavano soltanto gli estremi del dominio.
Nella B-Spline gli argomenti sono invece determinati dal vettore dei nodi.
Attenzione però: il blossom può naturalmente essere valutato anche per altre combinazioni di argomenti.
Le finestre di nodi consecutivi sono speciali perché sono proprio quelle che corrispondono ai coefficienti della rappresentazione B-Spline, cioè ai punti di controllo.
Ed eccoci al knot insertion.
Supponiamo di inserire un nuovo nodo \xi con:
1<\xi<2
Il vettore:
U={0,0,0,0,1,2,3,3,3,3}
diventa:
U'={0,0,0,0,1,\xi,2,3,3,3,3}
I nuovi punti di controllo sono ora determinati dalle nuove finestre di tre nodi consecutivi:
Q_0=F(0,0,0)
Q_1=F(0,0,1)
Q_2=F(0,1,\xi)
Q_3=F(1,\xi,2)
Q_4=F(\xi,2,3)
Q_5=F(2,3,3)
Q_6=F(3,3,3)
Quindi:
Q_0=P_0
Q_1=P_1
Q_5=P_4
Q_6=P_5
mentre i tre controlli centrali devono essere ricalcolati.
Vediamone uno:
Q_2=F(0,1,\xi)
Per simmetria:
P_1=F(0,0,1)=F(0,1,0)
mentre:
P_2=F(0,1,2)
Poiché il blossom è affine rispetto al terzo argomento:
Q_2=\left(1-\frac{\xi}{2}\right)P_1+\frac{\xi}{2}P_2
Gli altri nuovi controlli si ottengono nello stesso identico modo, direi estremamente semplice e “lineare”.
La formula generale del knot insertion è quindi:
Q_i=(1-\alpha_i)P_{i-1}+\alpha_iP_i
con:
\alpha_i=\frac{\xi-u_i}{u_{i+p}-u_i}
per gli indici interessati dal raffinamento.
Ed ecco il punto interessante.
Abbiamo inserito un nuovo nodo, costruito le nuove finestre nodali e ricavato i nuovi punti semplicemente sfruttando simmetria e multi-affinità.
La curva non cambia.
Cambiano il vettore dei nodi, la base B-Spline e i punti di controllo con cui rappresentiamo la stessa identica funzione.
Non è un’approssimazione e non è una ri-parametrizzazione.
È una rappresentazione esatta della stessa spline in uno spazio raffinato.
E a questo punto manca De Boor.
De Casteljau valuta il blossom di una Bézier mediante interpolazioni successive.
De Boor fa essenzialmente la stessa cosa per una B-Spline, ma utilizzando gli intervalli definiti dal vettore dei nodi.
La formula può quindi essere scritta:
D_i^r=(1-\alpha_i^r)D_{i-1}^{r-1}+\alpha_i^rD_i^{r-1}
con:
\alpha_i^r=\frac{t-u_i}{u_{i+p-r+1}-u_i}
A prima vista sembra più complicata di De Casteljau ma, in realtà, il principio è identico:
punto\ nuovo=(1-\alpha),punto\ sinistro+\alpha,punto\ destro
È sempre un’interpolazione affine.
Nella Bézier standard su [0,1] il coefficiente è semplicemente:
\alpha=t
Più in generale, su un intervallo [a,b]:
\alpha=\frac{t-a}{b-a}
In De Boor gli estremi dell’interpolazione cambiano invece a ogni livello in funzione dei nodi coinvolti.
Per questo compaiono coefficienti del tipo:
\alpha=\frac{t-u_i}{u_j-u_i}
dove u_i e u_j non sono necessariamente nodi consecutivi.
De Casteljau e De Boor risultano quindi due manifestazioni dello stesso principio: valutare una funzione multi-affine portando progressivamente tutti gli argomenti del blossom allo stesso valore t.
La molteplicità dei nodi ci porta poi naturalmente alla continuità. 
Supponiamo di avere due Bézier cubiche raccordate.
Dal punto di vista del blossom, se il raccordo avviene nel parametro r, la continuità C^0 richiede:
F(r,r,r)=G(r,r,r)
Per avere C^1 deve valere:
F(r,r,u)=G(r,r,u)
per ogni valore ammissibile di u.
Per avere C^2:
F(r,u,v)=G(r,u,v)
per tutti i valori ammissibili di u e v.
Più in generale, due polinomi di grado n raccordati in r sono C^k se e solo se i loro blossom coincidono sulle n-uple contenenti almeno n-k copie di r.
Nelle B-Spline questo si riflette direttamente nella arcinota relazione tra grado e molteplicità dei nodi!
Per una B-Spline di grado p, un nodo interno di molteplicità m garantisce in generale continuità:
C^{p-m}
Per una cubica:
m=1\rightarrow C^2
m=2\rightarrow C^1
m=3\rightarrow C^0
m=4\rightarrow C^{-1}
Con molteplicità p+1 non viene quindi più imposta nemmeno la continuità di posizione tra i due lati del nodo, la curva si spezza.
Una particolare curva può naturalmente avere continuità superiore a quella garantita se i suoi punti di controllo soddisfano relazioni aggiuntive.
Dal punto di vista del blossom l’idea è abbastanza naturale: aumentando la molteplicità del nodo diminuiscono le condizioni condivise dai tratti adiacenti e quindi diminuisce l’ordine delle derivate costrette a coincidere.
A questo punto bisogna distinguere continuità parametrica e continuità geometrica.
Il blossoming rende particolarmente naturale la descrizione della continuità analitica C^k.
Nel design industriale, però, siamo spesso maggiormente interessati alla continuità geometrica G^k.
Le due cose non coincidono.
La continuità C^k implica la corrispondente G^k, ma non vale necessariamente il contrario.
Due curve possono, ad esempio, essere G^1 senza essere C^1: le tangenti hanno la stessa direzione ma modulo differente.
Anche la continuità geometrica può essere descritta nel linguaggio del blossoming, ma occorre introdurre esplicitamente una ri-parametrizzazione.
Nel caso G^1, ad esempio, possiamo avere:
G'(s)=\beta_1F'(s)
con:
\beta_1>0
mentre per G^2 compare anche un termine aggiuntivo:
G''(s)=\beta_1^2F''(s)+\beta_2F'(s)
Quindi credo sia corretto dire che la continuità parametrica emerge direttamente dal confronto dei blossom, mentre quella geometrica richiede di tenere conto della libertà di ri-parametrizzazione.
E nel CAD conviene distinguere ancora una terza questione: la fairness.
Una curva può essere perfettamente G^2 e avere comunque una distribuzione della curvatura poco gradevole.
C^k riguarda la parametrizzazione.
G^k riguarda il raccordo geometrico.
La fairness riguarda invece la qualità con cui la forma e le sue grandezze differenziali evolvono lungo la curva (avevo discusso la questione in maniera più dettagliata in un altro post).
Ma facciamo un’ultima osservazione, direi inevitabile, parlando di Rhino.
Fino ad ora abbiamo trattato curve polinomiali e B-Spline non razionali.
Ma Rhino lavora soprattutto con NURBS.
Il blossoming si estende anche al caso razionale passando alle coordinate omogenee.
Un punto viene rappresentato come:
(wx,wy,wz,w)
Si lavora nello spazio omogeneo con gli stessi strumenti polinomiali e, alla fine, si torna allo spazio euclideo dividendo le prime tre coordinate per w.
Quindi anche le NURBS rientrano nello stesso quadro generale.
Ed eccoci al punto che trovo più interessante.
Noi normalmente impariamo Bézier, Bernstein, De Casteljau, degree elevation, knot insertion, B-Spline, De Boor e continuità come argomenti distinti, ognuno con le proprie formule e i propri algoritmi.
Il blossoming mostra invece che dietro molti di questi strumenti esiste la stessa struttura: una funzione simmetrica, multi-affine e con proprietà diagonale.
I punti di controllo sono particolari campioni di questa funzione.
De Casteljau nasce dalla multi-affinità.
L’elevazione del grado cambia il numero di argomenti mantenendo invariata la diagonale.
Il knot insertion introduce nuovi campioni compatibili con un vettore nodale raffinato.
De Boor applica ancora la multi-affinità, questa volta agli intervalli definiti dai nodi.
La continuità emerge dalle condizioni condivise dai blossom dei tratti adiacenti.
Quello che inizialmente sembrava un artificio matematico abbastanza astratto si rivela quindi un modo sorprendentemente compatto di leggere gran parte della teoria che sta dietro alle curve che utilizziamo tutti i giorni.
Ed è proprio questo che mi ha colpito.
Non tanto il fatto che il blossoming permetta di ricavare formule che già conosciamo, quanto il fatto che mostri come molte di quelle formule non siano realmente indipendenti.
Sono manifestazioni diverse della stessa struttura matematica.
Spero di non avervi annoiato e di essere riuscito a condividere almeno una piccola parte del piacere e dello stupore che ho provato studiando questi concetti.
Spero ancora di più di non avere scritto scemate.
Suggerimenti e correzioni sono certamente graditi.
)
