Ritaglio di Bezier

Question

Sto cercando di trovare / creare un algoritmo per calcolare l'intersezione (un nuovo oggetto riempito) di due oggetti 2D riempiti arbitrariamente. Gli oggetti sono definiti usando linee o bezier cubici e possono avere buchi o autointersezioni. Sono a conoscenza di diversi algoritmi esistenti che fanno lo stesso con i poligoni, elencati qui . Tuttavia, mi piacerebbe supportare i bezier senza suddividerli in poligoni e l'output dovrebbe avere all'incirca gli stessi punti di controllo dell'input in aree in cui non vi sono intersezioni.

Questo è per un programma interattivo per fare un po 'di CSG ma il ritaglio non deve essere in tempo reale. Ho cercato per un po 'ma non ho trovato buoni punti di partenza.

Answer 1

Ho trovato la seguente pubblicazione come la migliore delle informazioni riguardanti Bezier Clipping:

T. W. Sederberg, BYU, Note sul corso di progettazione geometrica assistita da computer

Il capitolo 7 che parla di Curve Intersection è disponibile online. Descrive 4 diversi approcci per trovare incroci e descrive in dettaglio Bezier Clipping:

http://www.tsplines.com/technology/edu/CurveIntersection.pdf

Answer 2

So di essere a rischio di licenziamento, ma stavo indagando sullo stesso problema e ho trovato una soluzione che avevo letto nei documenti accademici ma per cui non avevo trovato una soluzione funzionante.

Puoi riscrivere le curve di Bezier come un insieme di due equazioni cubiche a doppia variazione come questa:

• & # 8710; x = ax & # 8321; * t & # 8321; ^ 3 + bx & # 8321; * t & # 8321; ^ 2 + cx # 8321; t * <> # 8321!; + dx & # 8321; - ax & # 8322; * t & # 8322; ^ 3 - bx & # 8322; * t & # 8322; ^ 2 - cx & # 8322; * t & # 8322; - dx & # 8322;
• & # 8710; y = ay & # 8321; * t & # 8321; ^ 3 + di & # 8321; * t & # 8321; ^ 2 + cy # 8321; t * <> # 8321!; + dy & # 8321; - ay & # 8322; * t & # 8322; ^ 3 - di & # 8322; * t & # 8322; ^ 2 - cy & # 8322; * t & # 8322; - dy & # 8322;

Ovviamente, le curve si intersecano per i valori di (t & # 8321;, t & # 8322;) dove & # 8710; x = & # 8710; y = 0. Sfortunatamente, è complicato dal fatto che è difficile trovare radici in due dimensioni e che gli approcci approssimativi tendono a (come dice un altro scrittore) esplodere.

Ma se stai usando numeri interi o numeri razionali per i tuoi punti di controllo, puoi usare basi di Groebner per riscrivere i tuoi polinomi di ordine 3 bi-variabile in un (possibilmente-up-to- ordine-9-quindi-il-tuo-nove-possibili-intersezioni) polinomio monovariato. Dopodiché devi solo trovare le tue radici (per, diciamo t & # 8322;) in una dimensione e ricollegare i risultati in una delle tue equazioni originali per trovare l'altra dimensione.

Burchburger ha un'introduzione per laici alle basi di Groebner chiamata " Gr & # 246; basi di bner: una breve introduzione per i teorici dei sistemi " è stato molto utile per me. Google esso. L'altro documento che è stato utile è stato chiamato & Quot; Appiattimento rapido e preciso della B cubica & # 233; percorso della cerniera e curve di offset & Quot; di TF Hain, che ha molte equazioni di utilità per le curve di Bézier, incluso come trovare i coefficienti polinomiali per le equazioni xey.

Per quanto riguarda se il ritaglio di Bezier aiuterà con questo particolare metodo, ne dubito, ma il ritaglio di Bezier è un metodo per restringere dove potrebbero essere le intersezioni, non per trovare una risposta finale (anche se forse approssimativa) di dove si trova. Molto tempo con questo metodo sarà impiegato per trovare l'equazione mono-variabile e quell'attività non sarà più facile con il clipping. Trovare le radici è al confronto banale.

Tuttavia, uno dei vantaggi di questo metodo è che non dipende dalla suddivisione ricorsiva della curva e il problema diventa un semplice problema di ricerca delle radici unidimensionale, che non è facile, ma ben documentato. Il principale svantaggio è che il calcolo delle basi di Groebner è costoso e diventa molto ingombrante se hai a che fare con polinomi a virgola mobile o usi curve di Bezier di ordine superiore.

Se vuoi che un po 'di codice finito in Haskell trovi le intersezioni, fammi sapere.

Answer 3

Ho scritto codice per farlo molto, molto tempo fa. Il progetto su cui stavo lavorando su oggetti 2D definiti usando i confini di Bezier a tratti generati come percorsi PostScipt.

L'approccio che ho usato era:

Lascia che le curve p, q siano definite dai punti di controllo di Bezier. Si intersecano?

Calcola i rettangoli dei punti di controllo. Se non si sovrappongono, le due curve non si intersecano. Altrimenti:

p.x (t), p.y (t), q.x (u), q.y (u) sono polinomi cubici su 0 < = t, u < = 1.0. La distanza al quadrato (p.x - q.x) ** 2 + (p.y - q.y) ** 2 è un polinomio su (t, u). Usa Newton-Raphson per provare a risolverlo a zero. Scarta qualsiasi soluzione esterna a 0 & Lt; = t, u & Lt; = 1.0

N-R può o meno convergere. Le curve potrebbero non intersecarsi o N-R può semplicemente esplodere quando le due curve sono quasi parallele. Quindi taglia N-R se non converge dopo un numero arbitrario di iterazioni. Questo può essere un numero abbastanza piccolo.

Se N-R non converge su una soluzione, dividere una curva (diciamo, p) in due curve pa, pb at t = 0,5. Questo è facile, sta solo calcolando i punti medi, come mostra l'articolo collegato. Quindi test ricorsivo (q, pa) e (q, pb) per le intersezioni. (Si noti che nel successivo strato di ricorsione che q è diventato p, in modo che peq siano alternativamente divisi su ogni strato della ricorsione.)

La maggior parte delle chiamate ricorsive ritornano rapidamente perché i riquadri di delimitazione non si sovrappongono.

Dovrai interrompere la ricorsione ad una profondità arbitraria, per gestire strani casi in cui le due curve sono parallele e non si toccano del tutto, ma la distanza tra loro è arbitrariamente piccola - forse solo 1 ULP di differenza.

Quando trovi un incrocio, non hai finito, perché le curve cubiche possono avere incroci multipli. Quindi devi dividere ogni curva nel punto di intersezione e controllare ricorsivamente per più interazioni tra (pa, qa), (pa, qb), (pb, qa), (pb, qb).

Answer 4

Esistono numerosi documenti di ricerca accademica su come fare il ritaglio più bezier:

http://www.andrew.cmu.edu/user /sowen/abstracts/Se306.html

http://citeseerx.ist.psu.edu /viewdoc/summary?doi=10.1.1.61.6669

http://www.dm.unibo.it/~casciola /html/research_rr.html

Raccomando i metodi di intervallo perché, come descritto, non è necessario suddividere in poligoni e è possibile ottenere risultati garantiti e definire la propria precisione arbitraria per il gruppo di risultati. Per ulteriori informazioni sul rendering a intervalli, puoi anche fare riferimento a http://www.sunfishstudio.com