ベジェクリッピング

Question

2つの任意の塗りつぶされた2Dオブジェクトの交差(新しい塗りつぶされたオブジェクト)を計算するアルゴリズムを見つけたり作成しようとしています。オブジェクトは線または立方体ベジェを使用して定義され、穴や自己交差が存在する場合があります。ポリゴンに対して同じことを行っている既存のアルゴリズムがいくつかあることは知っていますが、 ここにリストされています. 。ただし、ベジェをポリゴンに再分割せずにサポートしたいと考えています。また、交差のない領域では、出力には入力とほぼ同じ制御点が含まれる必要があります。

これは対話型プログラムが CSG を実行するためのものですが、クリッピングはリアルタイムである必要はありません。しばらく検索しましたが、適切な出発点が見つかりませんでした。

Answer 1

ベジェ クリッピングに関する最良の情報は次の出版物であることがわかりました。

T.W.Sederberg、BYU、コンピュータ支援幾何学設計コースノート

曲線交差について説明する第 7 章はオンラインで入手できます。交差を見つけるための 4 つの異なるアプローチを概説し、ベジェ クリッピングについて詳しく説明します。

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

Answer 2

冗長になるリスクがあることは承知していますが、同じ問題を調査していて、学術論文で読んだものの有効な解決策が見つからなかった解決策を見つけました。

次のように、ベジェ曲線を 2 つの二変量 3 次方程式のセットとして書き直すことができます。

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

明らかに、曲線は (t₁,t₂) の値 (∆x = ∆y = 0) で交差します。残念なことに、二次元でルーツを見つけるのは難しく、近似的なアプローチは（別の作家が言ったように）爆発する傾向があるという事実によって状況は複雑になります。

ただし、制御点に整数または有理数を使用している場合は、次のように使用できます。 グレブナー塩基 二変量 3 次多項式を (おそらく最大 9 次、つまり 9 つの交差が考えられる) 単変量多項式に書き換えます。その後、1 つの次元で根 (たとえば t₂ など) を見つけ、その結果を元の方程式の 1 つに戻して他の次元を見つけるだけです。

Burchburger には、「Groebner Bases についての素人向けの入門書」があります。グレブナー塩基:システム理論家向けの簡単な紹介「それは私にとってとても役に立ちました。ググってみてください。役に立ったもう 1 つの論文は、「」と呼ばれるものです。3 次ベジェ パスとオフセット カーブの高速かつ正確な平坦化" by TF Hain。これには、x および y 方程式の多項式係数を見つける方法を含む、ベジェ曲線のユーティリティ方程式が多数含まれています。

ベジェ クリッピングがこの特定の方法に役立つかどうかについては、私は疑問に思っていますが、ベジェ クリッピングは交差の可能性がある場所を絞り込むための方法であり、交差点がどこにあるかの最終的な (おそらく近似的な) 答えを見つけるための方法ではありません。この方法では単変量方程式を見つけるのに多くの時間が費やされますが、クリッピングを使用してもその作業はそれほど簡単にはなりません。それに比べれば、ルーツを見つけることは簡単です。

ただし、この方法の利点の 1 つは、曲線の再帰的な細分化に依存せず、問題が単純な 1 次元の根探索問題になることです。これは簡単ではありませんが、十分に文書化されています。主な欠点は、浮動小数点多項式を扱っている場合や高次のベジェ曲線を使用している場合、グレブナー基数の計算にコストがかかり、非常に扱いにくくなることです。

Haskell で交差部分を見つけるための完成したコードが必要な場合は、私に知らせてください。

Answer 3

私はずっと前にこれを行うコードを書きました。私が取り組んでいたプロジェクトでは、PostScipt パスとして生成された区分的ベジェ境界を使用して 2D オブジェクトを定義しました。

私が使用したアプローチは次のとおりです。

曲線 p、q をベジェ制御点によって定義するとします。それらは交差しますか?

制御点の境界ボックスを計算します。重なり合わない場合、2 つの曲線は交差しません。さもないと：

p.x(t)、p.y(t)、q.x(u)、q.y(u) は、0 <= t,u <= 1.0 の 3 次多項式です。距離の二乗 (p.x - q.x) ** 2 + (p.y - q.y) ** 2 は、(t,u) 上の多項式です。ニュートン・ラフソンを使用して、それをゼロで解いてみます。0 <= t,u <= 1.0 の外側にある解はすべて破棄します。

N-R は収束する場合もあれば収束しない場合もあります。曲線が交差しないか、2 つの曲線がほぼ平行になったときに N-R が爆発する可能性があります。したがって、任意の回数の反復を行っても収束しない場合は、N-R を切り捨てます。これはかなり小さい数になる可能性があります。

N-R が解に収束しない場合は、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) の間のさらなる交差を再帰的にチェックする必要があります。

Answer 4

ベジェ クリッピングの実行に関する学術研究論文が多数あります。

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