問題タブ [bezier]

現在、複数のベジエに等間隔のポイントを持たせようとしています。現在、ポイントを見つけるためにキュービック補間を使用していますが、ベジエの動作方法により、一部の領域は他の領域よりも密集しており、距離が可変であるため、テクスチャ マッピングの粗さが証明されています。 パーセンテージではなく距離でベジェ上のポイントを見つける方法はありますか? さらに、これを複数の接続された曲線に拡張することは可能ですか?

空間内の任意のポイントのシーケンスが与えられた場合、それらの間でスムーズな連続補間をどのように生成しますか？

2Dおよび3Dソリューションは大歓迎です。任意の粒度でポイントのリストを生成するソリューション、およびベジェ曲線の制御ポイントを生成するソリューションも高く評価されています。

また、ポイントを受け取ったときに曲線の初期セクションを近似できる反復解を見ると、それを使って描画できるので便利です。

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

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

ある友人が、コードベースで、スイッチ テーブルの巨大なラット ネストを使用して計算を実行する 2 次ベジエ曲線関数に出くわしました。彼は私に、巨大なコード ブロックを置き換えることができる短い式を 1 つ見つけるように要求しました。

2 つの異なる好奇心を満たすために、この関数を OCaml で実装してみようと思いました。私は非常に初心者の OCaml プログラマーであり、関数にも慣れていないため、この特定の実装を Google 経由で入手するのは困難です。

関数のパフォーマンス/正確性とその実装の両方に対する批評は非常に高く評価されます。

二次ベジエ曲線の実装:

私は Python の Imaging Library を使用しており、いくつかのベジエ曲線を描画したいと考えています。ピクセルごとに計算できると思いますが、もっと簡単なものがあることを願っています。

私は、2 次元の連続データの視覚化プロジェクトに取り組んでいます。これは、2D マップで標高データや温度パターンを調べるために使用できるようなものです。本質的には、3 次元を 2 次元と色にフラット化する方法です。私の特定の研究分野では、実際に地理的な標高データを扱っているわけではありませんが、これは良い比喩であるため、この投稿全体を通してこれを使用します。

とにかく、この時点で、私は非常に満足している「連続カラー」レンダラーを持っています。

グラデーションは標準のカラー ホイールであり、赤いピクセルは高い値を持つ座標を示し、紫色のピクセルは低い値を示します。

基礎となるデータ構造は、いくつかの非常に巧妙な (私がそう言うなら) 補間アルゴリズムを使用して、マップの詳細への任意の深いズームを可能にします。

この時点で、(二次ベジエ曲線を使用して) いくつかの地形等高線を描画したいと考えていますが、これらの曲線を見つけるための効率的なアルゴリズムを説明している適切な文献を見つけることができませんでした。

私が考えていることのアイデアを提供するために、これは貧しい人の実装です (レンダラーは、輪郭線と交差するピクセルに遭遇するたびに黒の RGB 値を使用するだけです):

ただし、このアプローチにはいくつかの問題があります。

• 勾配が急なグラフの領域では、トポ ラインが細くなります (しばしば壊れます)。理想的には、すべてのトポ ラインが連続している必要があります。

• 勾配がより平坦なグラフの領域では、トポ ラインが広くなります (特にレンダリング領域の外周では、領域全体が黒くなることがよくあります)。

だから私は、それらの素晴らしい、完璧な 1 ピクセルの太さの曲線を得るためのベクトル描画アプローチを検討しています。アルゴリズムの基本構造には、次の手順を含める必要があります。

1. トポ ラインを描画する個別の標高ごとに、その座標の標高が目的の標高に非常に近い (任意のイプシロン値を指定) 座標のセットを見つけます。

2. 余分なポイントを削除します。たとえば、3 つの点が完全に直線上にある場合、曲線の形状を変更せずに中心点を削除できるため、中心点は冗長です。同様に、ベジェ曲線では、隣接するコントロール ポイントの位置を調整することで、特定のアンカー ポイントを削除できることがよくあります。

3. 2 つのポイント間の各セグメントが高度に中立な軌道に近似し、2 つのライン セグメントがパスを交差しないように、残りのポイントをシーケンスに組み立てます。各ポイント シーケンスは、閉じた多角形を作成するか、レンダリング領域の境界ボックスと交差する必要があります。

4. 各頂点について、ステップ 2 で削除された冗長点に関して、結果の曲線が最小の誤差を示すような制御点のペアを見つけます。

5. 現在のレンダリング スケールで表示される地形のすべてのフィーチャが適切な地形線で表されていることを確認します。たとえば、データに標高の高いスパイクが含まれているが、直径が非常に小さい場合でも、トポ ラインを描画する必要があります。垂直方向の特徴は、それらの特徴の直径が画像の全体的なレンダリングの粒度よりも小さい場合にのみ無視する必要があります。

しかし、これらの制約の下でも、行を見つけるためのいくつかの異なるヒューリスティックを考えることができます。

• レンダリング境界ボックス内の高点を見つけます。その高い地点から、いくつかの異なる軌道に沿って下り坂を進みます。トラバーサル ラインが標高のしきい値を超えるたびに、そのポイントを標高固有のバケットに追加します。トラバーサル パスが極小値に達したら、コースを変更して上り坂に移動します。

• レンダリング領域の長方形のバウンディング ボックスに沿って高解像度のトラバーサルを実行します。各標高のしきい値 (および勾配が方向を反転する変曲点) で、それらのポイントを標高固有のバケットに追加します。境界トラバーサルが終了したら、それらのバケットの境界点から内側にトレースを開始します。

• レンダリング領域全体をスキャンし、一定間隔で標高を測定します。測定ごとに、標高しきい値への近さをメカニズムとして使用して、その近傍の補間測定を行うかどうかを決定します。この手法を使用すると、レンダリング領域全体のカバレッジがより確実に保証されますが、結果のポイントをパスを構築するための適切な順序に組み立てるのは困難です。

だから、それらは私の考えの一部です...

実装を深く掘り下げる前に、StackOverflow の他の誰かがこの種の問題の経験があり、正確で効率的な実装への指針を提供できるかどうかを確認したかった.

編集：

ellisbben による "Gradient" の提案に特に興味があります。そして、私の核となるデータ構造 (最適化補間ショートカットの一部を無視して) は、完全に微分可能な一連の 2D ガウス関数の合計として表すことができます。

3 次元の勾配を表すデータ構造と、任意の点でその勾配ベクトルを計算する関数が必要になると思います。頭のてっぺんから、それを行う方法がわかりません（簡単なように思えますが）が、数学を説明するリンクがあれば、私は大いに感謝します!

アップデート：

ellisbben と Azim による優れた貢献のおかげで、フィールド内の任意の点の等高線角度を計算できるようになりました。実際のトポ ラインの描画はすぐに続きます。

これは、私が使用してきたゲットー ラスター ベースの topo-renderer を使用した場合と使用しない場合の、更新されたレンダリングです。各画像には、赤い点で表される 1000 のランダムなサンプル ポイントが含まれています。その点の等高線は白い線で表されます。場合によっては、（補間の粒度に基づいて）特定のポイントで勾配を測定できなかったため、対応する等高線なしで赤い点が発生します。

楽しみ！

(注: これらのレンダリングでは、以前のレンダリングとは異なる表面トポグラフィを使用しています。これは、プロトタイプを作成している間に、反復ごとにデータ構造をランダムに生成するためです。ただし、コアのレンダリング方法は同じであるため、アイデア。）

ここに興味深い事実があります。これらのレンダリングの右側に、完全な水平および垂直角度で奇妙な等高線がたくさん表示されます。これらは、補間プロセスのアーティファクトです。補間プロセスでは、補間子のグリッドを使用して、コアのレンダリング操作を実行するために必要な計算の数を (約 500%) 削減します。これらの奇妙な等高線はすべて、2 つの補間グリッド セル間の境界に発生します。

幸いなことに、これらのアーティファクトは実際には重要ではありません。アーティファクトは勾配の計算中に検出できますが、異なるビット深度で動作するため、最終的なレンダラーはそれらに気づきません。

再度更新:

そして、寝る前の最後の楽しみとして、もう 1 組のレンダリングを示します。1 つは昔ながらの「連続カラー」スタイルで、もう 1 つは 20,000 のグラデーション サンプルを使用しています。この一連のレンダリングでは、ポイント サンプルの赤い点を削除しました。これは、イメージが不必要に乱雑になるためです。

ここでは、補間コレクションのグリッド構造のおかげで、前に言及した補間アーティファクトを実際に見ることができます。これらのアーティファクトは、最終的なコンター レンダリングでは完全に見えなくなることを強調しておく必要があります (隣接する 2 つのインターポレーター セル間の大きさの差は、レンダリングされたイメージのビット深度よりも小さいため)。

ボナペティ!!

知っている：

• 制御点 a と d (2D 3 次ベジエ曲線の始点と終点)

• 勾配 a->b、c->d、および b->c (b、c は他のコントロール ポイント)

• ベジエ曲線の中間点の位置。

さて、この情報が与えられた場合、制御点 b と c の位置を求める式は何でしょうか?

3 次ベジエ曲線のストロークとは、曲線「A」を特定の線幅「w」でレンダリングすることを意味します。

ベジェ 'A' のストロークの輪郭を表す他の 3 次ベジェ曲線をどのように導出できますか?

3次ベジエ曲線を近似する最良の方法は何ですか? 理想的には、特定の x の正確な y 値を与える関数 y(x) が必要ですが、これには x 値ごとに 3 次方程式を解く必要があり、これは私のニーズには遅すぎます。また、数値安定性の問題が発生する可能性があります。このアプローチでも同様です。

これは良い解決策でしょうか？

整数座標を持つ 2D の 2 つの二次ベジエが与えられた場合、それらの交点を見つける最良の方法は何ですか? また興味深いのは、交差しない場合の早期拒否です。簡単に言えば、x と y の両方で単調であると見なすことができます。入力曲線の整数への再分割によって表現できる交点のみが有効です。