Interpolazione Catmull-Rom su percorsi SVG

Sto sperimentando la creazione di strumenti a matita ad alte prestazioni e di bell’aspetto usando i percorsi SVG.

Sto registrando le coordinate del mouse per tracciare un percorso. Per ottenere un percorso ad alta fedeltà (accurato ai movimenti dell’utente) ho bisogno di registrare un punto per ogni movimento di pixel.

Mantenere ogni punto del percorso crea una quantità enorme di punti che non è l’ideale per le funzionalità collaborative in seguito (l’invio di enormi quantità di punti avanti e indietro non è efficiente), oltre a analizzare enormi percorsi ogni volta che ho bisogno di manipolarli è un collo di bottiglia

Sulle aree lineari del percorso, i punti ridondanti vengono rimossi mantenendo solo i punti necessari per rappresentare il segmento – lo faccio utilizzando l’ algoritmo Ramer-Douglas-Peucker .

Ma semplificare un percorso lo trasforma in un poligono a bassa fedeltà

A questo punto i percorsi sono effettivamente solo linee collegate, quindi i percorsi sembrano frastagliati.

Una ansible soluzione è connettere i punti del percorso con Cubic Bezier – tuttavia ciò non funziona in modo ottimale sui percorsi semplificati. La distanza tra ogni punto è troppo grande perché Bezier cubico possa “sedersi” in modo che il percorso smussato non rappresenti più accuratamente il percorso desiderato dell’utente.

Un’altra soluzione è semplicemente utilizzare un algoritmo di “post-elaborazione” come Algoritmo di Schneider sul percorso originale – Questo algoritmo non funzionerà praticamente in tempo reale sebbene si tratti di un maiale performante

Una soluzione ideale

Una soluzione che (penso) potrebbe funzionare è quella di utilizzare un’interpolazione Centripeta Catmull-Rom .

Centripeta Catmull Rom vs resto delle varianti Catmull-Rom

Tra tutti gli algoritmi che ho studiato, questo sembra essere il più promettente in quanto:

  1. Non crea autointersecazioni nelle curve strette
  2. Si adatta meglio ai punti, quindi rappresenta più accuratamente il percorso originale.

Catmull-Rom è un algoritmo che interpola una serie di punti x / y regolari o il percorso originale deve essere composto da curve?

Per rispondere direttamente alle tue domande:

  1. Sì. La spline Catmull-Rom è un algoritmo per interpolare una serie di punti (x, y, z). Genererà una curva polinomiale cubica tra ogni due punti consecutivi.
  2. Non è ansible utilizzare direttamente la spline Catmull Rom per il percorso SVG. Devi prima convertirlo in una curva cubica di Bezier.

Per un segmento di curva definito dal punto P0, P1, P2 e P3 e dalla sequenza di nodes t0, t1, t2, t3, la spline Catmull-Rom centripeta (definita tra i punti P1 e P2) può essere calcasting mediante la formula ricorsiva fornita in https: //en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline . Pertanto, non elaborerò qui.

Per convertirlo in una curva Bezier cubica, devi calcolare la prima derivata su P1 e P2 come

M1 = (t2-t1)*(c1*(P1-P0)/(t1-t0) + c2*(P2-P1)/(t2-t1)) M2 = (t2-t1)*(d1*(P2-P1)/(t2-t1) + d2*(P3-P2)/(t3-t2)) 

Dove

  c1 = (t2-t1)/(t2-t0), c2 = (t1-t0)/(t2-t0), d1 = (t3-t2)/(t3-t1), d2 = (t2-t1)/(t3-t1) 

Quindi puoi convertirlo in una curva cubica di Bezier con 4 punti di controllo: Q0, Q1, Q2 e Q3:

 Q0 = P1 Q1 = P1 + M1/3 Q2 = P2 - M2/3 Q3 = P2 

Io uso cubi di interpolazione per questo

  1. campione su

    • cambio direzione del mouse in qualsiasi asse
    • se il mouse ha percorso una certa distanza per una maggiore precisione può aggiungere: se l’angolo di direzione cambia troppo (non lo uso)
    • se il mouse si ferma (questo può essere ignorato se si utilizza anche il mouse su / giù)
  2. utilizzare i punti campionati come punti di controllo per l’interpolazione cubica

    vedi Interpolazione cubica vs. Bezier cubico trovi anche la trasformazione tra l’interpolazione e Bezier cubico

  3. se questo non è abbastanza, puoi unire le linee con la stessa direzione

    Ecco un esempio di disegni a mano in questo modo:

    segui il mouse

    E lo SVG:

        

    Si tratta di circa 20 KB se si gioca con tresholds è ansible ridurre significativamente il numero di punti. Questo è ottimizzato per soddisfare le mie esigenze.

    Ecco un esempio di come il mouse si sente durante il disegno (catturato in tempo reale durante il disegno)

    mano spezzata disegnata