Bézier e Spline
Curve di Bézier
Le curve di Bézier sono delle importanti curve differenziali, formulate nel 1959 da Paul de Casteljau e pubblicizzate nel 1962 dall'ingegnere francese Pierre Bézier che le usò per disegnare le carrozzerie delle automobili. Vengono definite da un poligono di controllo in un intervallo [0, 1]. Il grado della curva è dato dal numero di vertici -1 del poligono di controllo.
Esistono due metodi principali per ottenere queste curve: uno basato su un algoritmo ricorsivo chiamato algoritmo di de Casteljau, mentre un altro che sfrutta i polinomi di Bernstein
Algoritmo di de Casteljau
Come abbiamo detto il grado della curva è determinato dal numero di vertici del poligono di controllo, procediamo quindi per gradi.
Curva di grado 1
Siano P0 e P1 due punti del piano rappresentati come segue, con t compreso nell'intervallo [0,1]:
Allora un punto qualunque P(t) compreso tra P0 e P1 sarà:
Animazione di una curva di Bézier lineare.
Curva di grado 2
Con 3 punti P0, P1, P2 creiamo due curve ausiliarie di grado 1, date dai segmenti P0P1 e P1P2. Considerato un valore t in [0,1], si definiscono due punti sui segmenti P0P1 e P1P2, unendoli otteniamo un altro segmento chiamato poligonale di primo livello.
Sul nuovo segmento si individua un terzo punto in funzione di t: quello corrispondente alla curva di Bézier di grado 2 per il valore di t. Ripetendo questo algoritmo per ogni t [0,1], ottengo tutti i punti della curva.
L'equazione generale dei punti della curva è quindi ottenuta per sostituzione come segue
Costruzione e animazione di una curva quadratica di Bézier.
Curva di grado 3
Come nelle curve di secondo grado cerchiamo di individuare altri punti così da lavorare su curve di grado di minore.
Costruzione e animazione di una cubica di Bézier.
Abbiamo visto quindi come individuare i punti di una curva di Bézier di grado 1,2 e 3 dato il poligono di controllo, e che questo viene fatto costruendo via via delle polinomiali come segue:
Quello che l'algoritmo di de Casteljau fa non è altro quindi che attuare il meccanismo spiegato per ogni t nell'intervallo [0,1].
Polinomi di Bernstein
Possiamo osservare che dalle formule precedenti i polinomi (1-t) e t sono sempre presenti, corredati da un coefficiente ed un esponente che dipendono chiaramente dal grado della curva in esame. Possiamo quindi definire i cosidetti Polinomi di Bernstein, dove i va da 0 a k, che è il grado della curva:
Grazie a questi polinomi, così definiti tralaltro perchè la loro somma faccia 1 in modo da conservare alcune proprietà, ci permettono di esprimere una curva di Bézier in questo modo:
Curve Spline
La motivazione alla base delle curve Spline nasce con la necessità di realizzare e modellare curve relativamente grandi, in termini di punti nel poligono di controllo, mantenendo però un controllo locale. Immaginiamo infatti di voler modellare una Bézier che abbia almeno una decina di punti di controllo: oltre che computazionalmente inefficiente, sarebbe particolarmente difficile se non impossibile modellare alcune forme.
L'idea quindi è quella di incollare più curve di Bézier imponendo delle condizioni di continuità nei cosidetti punti di saldatura. Queste condizioni di continuità possono essere di tipo:
- C0: Stabilisce che l'ultimo punto di una delle curve che costituiscono la Spline, e il primo della curva successiva, coincidano nel punto di saldatura. C1: Oltre a rispettare la condizione di continuità C0, stabilisce che i polinomi delle due curve adiacenti abbiano la stessa derivata prima nel punto di saldatura. In termini pratici questo è ottenuto facendo giacere il penultimo punto della curva e il secondo punto della successiva sulla stessa retta.
- C2: Rispettando la condizione C1, aggiunge che i due polinomi abbiano anche la derivata seconda uguale nel punto di saldatura, avendo così stessa tangente e curvatura in quel punto.
Dettagli implementativi e scelte di progetto
Disegnare le Bézier
Nella classe statica Bézier sono sono presenti i metodi GetPoint e GetFirstDerivative che rappresentano rispettivamente l’implementazione dell’algoritmo di de Casteljau e della sua derivata prima.
La funzione GetPoint ha come input quattro Vector3 (struttura che in Unity rappresenta un vettore a 3 dimensioni) che rappresentano le coordinate dei punti di controllo della curva nello spazio e un valore float t. Restituisce in output un Vector3 che rappresenta le coordinate del punto P(t) compreso tra P(0) e P(3)
La funzione GetFirstDerivative ha come input gli stessi valori della funzione precedente ma come output un Vector3 rappresentante la tangente nel punto P(t).
In bianco vediamo i segmenti disegnati tramite l’utilizzo della funzione GetPoint e in verde le tangenti ottenute tramite l’utilizzo della funzione GetFirstDerivative.
La funzione AddCurve presente nella classe BézierSpline prende in input la lista dei punti di controllo della nuova curva di Bézier da aggiungere alla spline (di cui sono già stati controllate le condizioni di incollamento) e si occupa di calcolare i punti e le tangenti della curva (attraverso l’utilizzo dei metodi GetPoint e GetFirstDerivative visti precedentemente) con una risoluzione controllata dal valore controlRes che può essere modificato per agire sulla risoluzione con cui la curva viene discretizzata. I punti vengono poi aggiunti ad una struttura dati temporanea e viene controllato che la loro eventuale aggiunta non comporti collisioni con altre porzioni della curva (con un metodo che vedremo in seguito). In caso di esito positivo del controllo i punti vengono aggiunti alla struttura dati globale e si procede, altrimenti viene notificato che sono da correggere i punti di controllo e, a correzione avvenuta, viene richiamata la funzione AddCurve con i punti di controllo aggiornati.
La funzione CheckIntersect si occupa di verificare che i punti della curva che si sta tentando di aggiungere alla spline non intersechi o non sia troppo vicina ad altre porzioni della curva stessa. Per fare ciò prende in input la lista dei punti che si vuole controllare newPoints, la lista dei punti già aggiunti alla spline e considerati stabili oldPoints e un valore booleano lastCurve necessario per controllare la collisione finale del tracciato. Per controllare che non ci siano intersezioni per ogni punto di newPoints viene generato un BoxCollider (in Unity un BoxCollider è un volume a forma di parallelepipedo) ruotato secondo la rotazione di quel punto e se ne calcolano i vertici della faccia inferiore e si verifica che nessuno dei punti stabili sia presente nella porzione di piano descritta dai quattro vertici.
Box collider utilizzati per il controllo delle intersezioni e sovrapposizioni del tracciato.
La funzione CreateMesh della classe ProceduralMesh si occupa, data una curva spline, di generare una geometria piana che segua sia i punti che la rotazione della curva con una determinata larghezza. Questa funzione infatti calcola vertici, triangoli, normali e UVs che andranno poi a comporre la mesh della pista.
Visualizzazione degli elementi della mesh.
Posizionare i punti di controllo
A monte della generazione delle curve vere e proprie c'è il posizionamento dei vari punti dei poligoni di controllo delle singole Bézier. Questo processo coinvolge pesantemente i tre parametri curviness, trackLenght e maxAngleD, determinati dall'utente e li utilizza per costruire un tracciato con determinate caratteristiche piuttosto che altre.
Incominciamo col dire che trackLenght stabilisce si la lunghezza del tracciato in termini di punti, ma che questo influisce solamente con la fase iniziale del percorso. Questo è determinato dal fatto che se da un lato procedere in maniera pseudo-casuale con la generazione dei punti produce effetti notevoli in termini di unicità e divertimento della pista, dall'altra ricongiungere la pista in maniera coerente necessita di un processo più deterministico.
Dividiamo la generazione della pista in tre fasi:
Generazione pseudo-casuale
A partire dal primo punto fino a un massimo di punti definito da trackLenght, ogni elemento dei poligoni di controllo viene generato pseudo-casualmente a patto di rispettare la condizione di continuità C1 nei punti di giunzione delle curve. Di conseguenza l'ultimo punto di una curva e il primo della successiva coincidono, e il secondo punto della successiva verrà posizionato in asse col penultimo della precedente. Vengono stabiliti dei limiti indicativi, e dipendendi dal numero di punti, che la pista può raggiungere, così da poterla "trattenere" e impedire che per tornare al punto iniziale serva troppa strada.
Rappresentazione della spline con un numero di punti dipendente da trackLenght
Raggiungimento del farReturnPoint
Generare una serie di punti in linea retta dalla fine della fase uno fino al ricongiungimento della pista, produceva spesso delle curve in corrispondenza dell'inizio/fine del tracciato troppo pronunciate. Neanche continuare con il processo pseudo-casuale tramite qualche modifica che prediligeva il punto iniziale come destinazione si è dimostrata efficiente perchè anch'essa portava a curve troppo strette. La soluzione è stata quindi quella di indirizzare il tracciato verso un punto posizionato a una certa distanza dal punto iniziale e con direzione opposta a quella che c'è tra il primo e il secondo punto della spline, e indirizzare la curva verso quel punto, sempre rispettando i parametri di curviness ecc...
Evidenziato in arancio il tratto di spline generato nella seconda fase.
Ritorno al punto iniziale
In azzurro l'ultimo tratto di spline che ricongiunge la pista.
Gestire collisioni e intersezioni della pista
Per ogni quartetto di punti dei poligoni di controllo che stabiliamo nelle fasi precedenti, generiamo la relativa Bézier di volta in volta, questo per permetterci di modificare il tracciato a run-time in caso di intersezioni del tracciato o nel caso in cui due tratti siano troppo vicini, tanto da sovrapporsi. Per ogni curva disegnata quindi genereremo dei collider e controlleremo eventuali collisioni, che se presenti daranno il via a un processo di correzione che comporta l'innalzamento o l'abbassamento di quel tratto di pista, di parte del precedente e di parte del successivo, per mantenere le condizioni di continuità.