Bezier-Clipping

Question

Ich versuche, einen Algorithmus zu finden /, um die Kreuzung zu berechnen (ein neues gefülltes Objekt) von zwei beliebigen gefüllt 2D-Objekten. Die Objekte werden entweder Linien oder kubischen beziers mit und Löchern oder selbst schneiden können. Ich bin mir dessen bewusst mehrere existierende Algorithmen die gleiche mit Polygonen zu tun, hier aufgeführt. Ich möchte jedoch beziers unterstützen, ohne sie in Polygone unterteilt, und die Ausgabe sollte in etwa die gleichen Kontrollpunkte als Eingang in Bereichen haben, wo es keine Überschneidungen.

Dies ist für ein interaktives Programm etwas CSG zu tun, aber das Clipping braucht nicht in Echtzeit zu sein. Ich habe für eine Weile gesucht, aber keine gute Ausgangspunkte gefunden.

Answer 1

Ich fand die folgende Veröffentlichung die besten Informationen über Bezier Clipping zu sein:

T. W. Sederberg, BYU, Computer Aided Geometric Design Course Hinweise

Kapitel 7, die über Curve Überschneidung spricht ist online verfügbar. Es umreißt 4 verschiedene Ansätze Kreuzungen zu finden und beschreibt Bezier Clipping im Detail:

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

Answer 2

Ich weiß, dass ich in Gefahr bin überflüssig zu sein, aber ich war das gleiche Problem zu untersuchen und eine Lösung gefunden, die ich in wissenschaftlichen Arbeiten gelesen habe, hatte aber nicht eine funktionierende Lösung für.

gefunden

Sie können die Bezier-Kurven als ein Satz von zwei bi-variate kubischen Gleichungen wie folgt umschreiben:

• & Delta; x = ax₁ * t₁ ^ 3 + bx₁ * t₁ ^ 2 + cx₁ * t₁ + dx₁ - ax₂ * t₂ ^ 3 - bx₂ * t₂ ^ 2 - CX₂ * t₂ - dx₂
• & Delta; y = ay₁ * t₁ ^ 3 + by₁ * t₁ ^ 2 + cy₁ * t₁ + dy₁ - ay₂ * t₂ ^ 3 - by₂ * t₂ ^ 2 - cy₂ * t₂ - dy₂

Offensichtlich schneiden sich die Kurven für Werte von (t₁, t₂), wobei & Delta; x = & Delta; y = 0. Leider ist es durch die Tatsache erschwert, dass es schwierig ist Wurzeln in zwei Dimensionen zu finden, und die ungefähre Ansätze sind in der Regel (wie ein anderer Schriftsteller legte es) sprengen.

Wenn Sie aber auf ganze Zahlen oder rationale Zahlen für die Kontrollpunkt verwenden, dann können Sie Gröbner Basen neu zu schreiben Ihre bi-variate auftrag 3 Polynome in einen (möglicherweise-up-to um-9-so-your-neun-möglich-Kreuzungen) monovariate Polynom. Danach müssen Sie nur Ihre Wurzeln finden (für, sagen t₂) in einer Dimension, und stecken Sie Ihre Ergebnisse zurück in eine Ihrer ursprünglichen Gleichungen, die die andere Dimension zu finden.

Burchburger hat eine Laien freundliche Einführung in Gröbner Basen genannt „ Gröbner Basen: Eine kurze Einführung für Systeme Theorists “, die für mich sehr hilfreich war. Google es. Das andere Papier, das hilfreich war, nannte man „ Schnell, präzise Abflachung der kubischen Bézierpfad und Offset-Kurven “ von TF Hain, die viele Gebrauchsgleichungen für Bezier-Kurven haben, wie es die Polynomkoeffizienten zu finden für die x- und y-Gleichungen.

Als ob der Bezier-Ausschnitt mit diesem speziellen Verfahren helfen wird, bezweifle ich, aber Bezier-Clipping ist ein Verfahren zur Eingrenzung wo Kreuzungen sein könnten, nicht für eine endgültige (obwohl möglicherweise ungefähre) zu finden Antwort von wo es ist. Viel Zeit mit dieser Methode wird bei der Suche nach der Mono-variate Gleichung ausgegeben werden, und diese Aufgabe bekommt keine einfacher mit Clipping. Das Finden der Wurzeln ist im Vergleich trivial.

Allerdings ist einer der Vorteile dieses Verfahrens besteht darin, dass es nicht auf rekursiv die Kurve unterteilt abhängt, und das Problem wird zu einem einfachen eindimensionalen Wurzelfindungsproblem, das nicht einfach, aber gut dokumentiert ist. Der größte Nachteil ist, dass die Berechnung Gröbner Basen kostspielig ist und wird sehr unhandlich, wenn Sie mit Floating-Point-Polynomen oder mit höherer Ordnung Bezier-Kurven zu tun hat.

Wenn Sie einige fertige Code in Haskell wollen die Schnittstellen zu finden, lassen Sie es mich wissen.

Answer 3

schrieb ich Code schon vor langer, langer Zeit zu tun. Das Projekt arbeite ich an definierten 2D-Objekten mit stückweise Bezier Grenzen, die als PostScipt Wege erzeugt wurden.

Der Ansatz, den ich verwendet wurde:

Lassen Sie Kurven p, q, durch Bezier-Kontrollpunkte definiert werden. Haben sie schneiden?

Berechnen Sie die Begrenzungskästen der Kontrollpunkte. Wenn sie sich nicht überlappen, dann die beiden Kurven nicht schneiden. Ansonsten:
p.x (t), p.y (t), q.x (u), q.y (u) sind kubische Polynome auf 0 <= t, u <= 1,0. Der Abstand zum Quadrat (p.x - q.x) ** 2 + (p.y - q.y) ** 2 ein Polynom auf (t, u). Verwenden Sie Newton-Raphson, um zu versuchen und zu lösen, dass für Null. Verwerfen Lösungen außerhalb 0 <= t, u <= 1,0

N-R kann oder nicht konvergieren. Die Kurven können nicht schneiden, oder N-R kann nur die Luft zu sprengen, wenn die beiden Kurven fast parallel sind. So abgeschnitten N-R, wenn es nicht nach nach einer beliebigen Anzahl von Iterationen konvergieren. Dies kann eine ziemlich kleine Zahl sein.

N-R nicht an einer Lösung konvergieren, spaltete eine Kurve (sagen wir, p) in zwei Kurven Pa, Pb bei t = 0,5. Das ist einfach, es ist nur die Berechnung Mittelpunkte, wie die verlinkten Artikel zeigt. Dann rekursiv Test (q, PA) und (q, pb) für Kreuzungen. (Beachten Sie, dass in der nächsten Schicht der Rekursion, die q p worden ist, so daß p und q abwechselnd auf jeder Lage der Rekursion aufgeteilt sind.)

Die meisten der rekursiven Aufrufe schnell wieder, weil die Begrenzungskästen sind nicht überlappen.

Du musst die Rekursion bei einer beliebigen Tiefe abgeschnitten, seltsame Fälle zu behandeln, in denen sich die beiden Kurven sind parallel und nicht ganz berühren, aber der Abstand zwischen ihnen ist beliebig klein - vielleicht nur 1 ULP Unterschied.

Wenn Sie eine Kreuzung zu tun finden, sind Sie nicht getan, weil kubische Kurven mehrere Kreuzungen haben. Also muss man jede Kurve am Schnittpunkt geteilt, und prüfen Sie rekursiv für mehr interections zwischen (pa, qa), (pa, qb), (pb, qa), (pb, qb).

Answer 4

Es gibt eine Reihe von wissenschaftlichen Forschungsarbeiten zu tun Bezier-Clipping:

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

Ich empfehle die Intervallmethoden, weil, wie Sie beschreiben, müssen Sie nicht auf Polygone aufzuteilen nach unten, und Sie können auch eigene definieren beliebige Genauigkeit für die resultset garantieren Ergebnisse. Weitere Informationen über die Intervall-Wiedergabe, können Sie auch beziehen sich auf http://www.sunfishstudio.com