2つの任意の塗りつぶされた2Dオブジェクトの交差（新しい塗りつぶされたオブジェクト）を計算するアルゴリズムを見つけて作成しようとしています。オブジェクトは、線または立方体のベジエを使用して定義され、穴または自己交差する場合があります。ここにリストされている、ポリゴンで同じことを行ういくつかの既存のアルゴリズムを知っています。ただし、ベジエをポリゴンに分割せずにサポートしたいので、交差点がない領域では、出力は入力とほぼ同じコントロールポイントを持つ必要があります。
これは、インタラクティブプログラムがCSGを実行するためのものですが、クリッピングはリアルタイムである必要はありません。しばらく検索しましたが、良い出発点が見つかりませんでした。
次の出版物が、ベジエ クリッピングに関する最良の情報であることがわかりました。
TW Sederberg、BYU、コンピュータ支援幾何学設計コースノート
Curve Intersection について説明している第 7 章は、オンラインで入手できます。交差点を見つけるための 4 つの異なるアプローチを概説し、ベジエ クリッピングについて詳しく説明します。
http://www.tsplines.com/technology/edu/CurveIntersection.pdf
冗長になるリスクがあることはわかっていますが、同じ問題を調査していて、学術論文で読んだ解決策を見つけましたが、有効な解決策は見つかりませんでした。
次のように、ベジエ曲線を 2 つの 2 変量 3 次方程式のセットとして書き直すことができます。
明らかに、曲線は ∆x = ∆y = 0 である (t₁,t₂) の値で交差します。残念ながら、2 次元で根を見つけることは困難であり、おおよそのアプローチは (別の作家が述べたように) 傾向があるという事実によって複雑になります。それは）爆発します。
しかし、コントロール ポイントに整数または有理数を使用している場合は、Groebner 基底を使用して、2 変量次数 3 多項式を次数 9 に書き換えることができます。可能な交差) 単変量多項式。その後、1 つの次元で根 (t₂ など) を見つけ、その結果を元の方程式の 1 つに戻して、他の次元を見つける必要があります。
Burchburger は、" Gröbner Bases: A Short Introduction for Systems Theorists "と呼ばれる Groebner Bases の初心者向けの入門書を持っています。これは私にとって非常に役に立ちました。ググってください。参考になったもう 1 つの論文は、TF Hain による「立方ベジエ パスとオフセット曲線の高速で正確な平坦化」と呼ばれるもので、x および y 方程式の多項式係数を見つける方法など、ベジエ曲線のユーティリティ方程式が多数あります。
ベジエ クリッピングがこの特定の方法に役立つかどうかについては疑問ですが、ベジエ クリッピングは交点の可能性がある場所を絞り込むための方法であり、最終的な (おおよその) 答えを見つけるためのものではありません。この方法を使用すると、単変量方程式を見つけるのに多くの時間が費やされますが、その作業はクリッピングでは簡単になりません。ルーツを見つけることは、比較すると簡単です。
ただし、この方法の利点の 1 つは、曲線を再帰的に細分化することに依存しないことです。問題は簡単ではありませんが、十分に文書化された単純な 1 次元の求根問題になります。主な欠点は、浮動小数点多項式を扱っている場合や高次のベジエ曲線を使用している場合、Groebner 基底の計算にコストがかかり、非常に扱いにくくなることです。
Haskell で交差点を見つけるための完成したコードが必要な場合は、お知らせください。
私はずっと前にこれを行うためのコードを書きました。私が取り組んでいたプロジェクトでは、PostScipt パスとして生成された区分的なベジエ境界を使用して定義された 2D オブジェクトが使用されていました。
私が使用したアプローチは次のとおりです。
曲線 p、q をベジエ制御点で定義します。それらは交差しますか？
コントロール ポイントの境界ボックスを計算します。オーバーラップしない場合、2 つの曲線は交差しません。それ以外の場合:
px(t)、py(t)、qx(u)、qy(u) は 0 <= t,u <= 1.0 の 3 次多項式です。距離の二乗 (px - qx) ** 2 + (py - qy) ** 2 は (t,u) 上の多項式です。Newton-Raphson を使用して、それをゼロで解決してみてください。0 <= t,u <= 1.0 以外の解は破棄します
NR は収束する場合と収束しない場合があります。曲線が交差しないか、2 つの曲線がほぼ平行になると NR が爆発する可能性があります。したがって、任意の回数の反復後に収束しない場合は、NR を切り捨てます。これはかなり小さい数になる可能性があります。
NR が解に収束しない場合は、t = 0.5 で 1 つの曲線 (たとえば、p) を 2 つの曲線 pa、pb に分割します。これは簡単です。リンクされた記事が示すように、中点を計算するだけです。次に、(q, pa) と (q, pb) の交点を再帰的にテストします。(再帰の次の層では、q が p になっているので、再帰の各層で p と q が交互に分割されることに注意してください。)
境界ボックスが重複していないため、ほとんどの再帰呼び出しはすぐに返されます。
2 つの曲線が平行で、まったく接触していない奇妙なケースを処理するために、任意の深さで再帰を切断する必要がありますが、それらの間の距離は任意に小さく、おそらく 1 ULP しか違いません。
交点が見つかっても、それで終わりではありません。3 次曲線には複数の交点がある可能性があるからです。したがって、交点で各曲線を分割し、(pa、qa)、(pa、qb)、(pb、qa)、(pb、qb) の間の交差を再帰的にチェックする必要があります。
ベジエ クリッピングの実行に関する学術研究論文が多数あります。
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
あなたが説明したように、ポリゴンに分割する必要はなく、結果セットに対して独自の任意の精度を定義するだけでなく、保証された結果を得ることができるため、間隔メソッドをお勧めします。インターバル レンダリングの詳細については、http://www.sunfishstudio.com も参照してください。