Trovare punti su una curva bezier in base alla distanza da un altro punto

Question

Quindi ho una curva cubica 3D bezier e un punto iniziale trovato ovunque lungo la curva e ho bisogno di trovare un secondo punto più in basso lungo la curva che è una specifica distanza dello spazio del mondo (distanza non arclength) lontano dal primo punto.

Un altro problema sarebbe se il secondo punto raggiungesse la fine della curva e non fosse ancora alla distanza desiderata dallo spazio del mondo, nel qual caso vorrei continuare lungo la tangente fino a raggiungere la distanza.

Qualche idea?

Answer 1

Ahimè, non conosco nessuna equazione in forma chiusa che ti dà il punto (i) che vuoi. Forse la tecnica più semplice per approssimare quel punto è tagliare in modo ricorsivo la curva di Bezier in 2 curve Bezier più piccole usando de Casteljau's algorithm. La ricorsione scende in fondo quando (a) tutti i punti di delimitazione per la curva sono tutti troppo vicini o troppo lontani dal punto specificato, oppure (b) tutti i punti di delimitazione della curva sono "abbastanza vicini" a essere uguale alla distanza desiderata (forse si adattano tutti allo stesso pixel).

Sono quasi sicuro che il numero massimo di punti su una data curva di Bezier che sono una determinata distanza lineare da un dato punto è di 4 punti. (Ciò può accadere quando la curva di Bezier specificata ha un'intersezione automatica).

EDIT:

Forse dovrei leggere l'intera questione prima di saltare in con una risposta, sì? Il segmento di curva Bezier "a quattro punti" standard può essere visto come un pezzo di una curva cubica infinitamente lunga. Potrebbe esserci una piega o un loop o una cuspide in una posizione, ma sufficientemente lontano da quella curva acuta il percorso si appiattisce per chiudere a 2 raggi dritti, ognuno dei quali punta in qualche direzione arbitraria. Purtroppo, la soluzione sopra trova solo i punti che si trovano sul segmento corto della curva di Bezier. Suppongo che tu voglia il punto (i) lungo quella curva cubica infinitamente lunga che sono la distanza data dal punto dato, anche se non si trovano sul segmento corto della curva di Bezier.

== de Casteljau in == inverso

È possibile eseguire (punto medio ricorsivo) algoritmo di de Casteljau in retromarcia, generando un nuovo quattro punti Bezier curva "doppio" la dimensione dell'ultima ad ogni iterazione, fino ne hai una abbastanza grande da includere i punti desiderati. (Quando tutti e 4 i punti iniziali sono "troppo vicini" al punto dato, allora è garantito il raddoppio per produrre un segmento di curva con il punto di partenza "troppo vicino", il punto finale "troppo lontano", e quindi puoi usare il punto sopra algoritmo per convergere su un punto che è la distanza desiderata lontano dal punto specificato). Questo approccio si basa solo su addizione, sottrazione, moltiplicazione per due e media, quindi in linea di principio dovrebbe essere relativamente numericamente robusto. (Non valuta mai effettivamente la formula cubica in qualsiasi posizione t).

== zero scoperta ==

si potrebbe convertire dalla rappresentazione a quattro punti alla rappresentazione polinomiale cubica, e utilizzare qualsiasi algoritmo radice conoscitiva a convergere su uno dei punti desiderati. Il metodo di Newton dovrebbe funzionare piuttosto bene, poiché i pezzi corti di una curva di Bezier sono quasi dritti. Possiamo adattare le equazioni del metodo di Newton da Finding the Minimum Distance Between a Point and a Cubic Spline a questo problema? Userò l'algoritmo di bisezione per semplicità nella descrizione, anche se gira più lentamente del metodo di Newton.

Come sempre, un segmento cubico curva di Bezier può essere descritto come

B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3. 

(Purtroppo, questa equazione non è sempre numericamente affidabile - è per questo che molte persone usano dimezzamento ricorsivo utilizzando l'algoritmo di de Casteljau invece).

Sto assumendo che hai (o trovare) il valore t_given per il vostro punto dato,

x_given = B(t_given).x 
y_given = B(t_given).y 

La distanza tra il punto dato e qualche altro punto lungo la curva è dato da teorema di Pitagora,

distance2(t) = (x_given - B(t).x)^2 + (y_given - B(t).y)^2. 
distance(t) = sqrt(distance2(t)). 

il punto (s) che si sta cercando sono le zeri della funzione

given_distance2 = given_distance^2. 
f(t) = distance2(t) - given_distance2. 

Supponendo che la distanza data non è zero, e il punto dato ha un algoritmo di t_given < 1, bisezione sarebbe eseguire qualcosa di simile

left = t_given 
right = 1 // the endpoint of the given Bezier curve segment 
while(distance2(right) < given_distance2){ 
    right = right*2 
} 

A questo punto, il t_left è più vicino al punto dato che il desiderato distanza, e t_right è più lontano della distanza desiderata (o forse esattamente uguale). Dato che abbiamo un punto troppo vicino e un altro punto troppo lontano, l'algoritmo di bisection dovrebbe funzionare.

Quindi controlliamo: il primo segmento è a sinistra ... il punto medio contiene lo zero o il punto medio ... giusto?

if(f(left)*f(midpoint) < 0) then 
     // throw away right half 
     right = midpoint 
    else 
     // throw away left half 
     left = midpoint 
} 

return(right) 

A questo punto, il valore "giusto" è il valore di t, e B (destra) è il punto corrispondente, in modo tale che la distanza da quel punto a punto dato originale è (circa) la data distanza.

Answer 2

L'affermazione del problema richiede un tocco più raffinato. Nello specifico, non sei vincolato quando chiedi un punto B che è N lontano dal punto di partenza A. Potrebbero esserci più punti che sono N distanza da A.

A parte ciò che ti impedisce di campionare la curva sul set intervalli lungo la curva e quindi calcolare una distanza lineare indietro a A. Non è ottimale ma funzionerebbe. Per gestire più punti a distanza di distanza devi trovare una regola. Potrebbe essere semplice come il primo punto trovato.