問題タブ [bresenham]

現在、円をうまく描画するブレゼンハムの円描画アルゴリズムを使用していますが、指定された太さの円を比較的高速で効率的に描画したいと考えています (ブレゼンハムの方法は単一ピクセルの太さしか描画しないため)。半径の異なる複数の円を単純に描くことができることはわかっていますが、これは非常に非効率的であると思います (そして、これはマイクロ秒が貴重な Arduino 上で実行されるため、効率が重要です)。現在、次のコードを使用しています。

円の厚さを指定できるようにするには、これをどのように変更できますか? PS 外部ライブラリを使用したくありません。

私は HTML キャンバスに線を描いていますが、精度の低い 2D 配列 (10x10 ピクセルのブロックを表す) を使用して、Bresenham のアルゴリズムで線を「描画」して線 ID を格納しているので、その配列を使用してどの行が選択されます。

これは機能しますが、より正確にしたいと思います-使用する10x10サイズではありません(線をクリックする必要がないのが好きです)が、実際の配列の上にその配列の表現を描画するとcanvas を見ると、線が交差しているにもかかわらず、10x10 のブロックが塗りつぶされていないことがわかります。

これに対するより良い解決策はありますか？私が望むのは、実際のラインが通過するすべてのグリッド ブロックをキャッチすることです。

Bresenham の円描画アルゴリズムの実装を作成しました。このアルゴリズムは、円の高度な対称性を利用しています(1 番目の八分円から点のみを計算し、対称性を利用して他の点を描画します)。したがって、私はそれが非常に速いと予想していました。グラフィックス プログラミング ブラック ブック、第 35 章のタイトルは「ブレゼンハムは速く、速いことは良い」であり、線描画アルゴリズムに関するものでしたが、円描画アルゴリズムも高速であると合理的に期待できました (原理は同じ）。

これが私のJava、スイングの実装です

この方法では、次の方法を使用しますdrawPoint。

getNativeX と getNativeY の 2 つのメソッドを使用して、座標を画面の左上隅を起点とする座標系から、より古典的な軸方向でパネルの中央を原点とする座標系に切り替えます。

x=R*Math.cos(angle)また、三角関数の公式 (および)に基づく円描画アルゴリズムのy= R*Math.sin(angle)実装と、標準の drawArc メソッド (Graphics オブジェクトで使用可能) の呼び出しを使用した 3 つ目の実装も作成しました。これらの追加の実装は、ブレゼンハムのアルゴリズムをそれらと比較することのみを目的としています。

次に、費やされた時間を適切に測定できるように、たくさんの円を描くメソッドを作成しました。Bresenhamのアルゴリズムを使用して多数の円を描くために使用する方法は次のとおりです

最後に、使用している JPanel のペイント メソッドをオーバーライドして、多数の円を描画し、各タイプの描画にかかった時間を測定します。ペイント方法は次のとおりです。

生成されるレンダリングの種類は次のとおりです (各タイプの 1000 個の円を描画)

残念ながら、私の Bresenham の実装は非常に遅いです。私は多くの比較測定を行いましたが、ブレゼンハムの実装は よりGraphics.drawArcも遅いだけでなく、三角法のアプローチよりも遅いです。描かれたさまざまな数の円について、次の対策を見てください。

実装のどの部分がより時間がかかりますか? それを改善するために使用できる回避策はありますか？助けてくれてありがとう。

[EDITION] : @higuaro のリクエストに応じて、円を描くための三角法アルゴリズムを次に示します。

そして、三角関数の円の束を描くために使用される方法

この記事を使用して、ブレゼンハムの線画をアンチエイリアスで実装しようとしています: http://members.chello.at/~easyfilter/bresenham.html

そして、ここに関数があります：

何かが変わるかどうかはわかりませんが、すべての int を float に変更しました。float で除算が機能しているかどうかを確認するためです。とにかく整数の結果は同じです。

次に、呼び出しの例:

結果は次のようになります。

y0 + sy を y0 - sy に次のように変更すると:

出力は次のようになります。

x2 + sx を x2 - sx に変更すると、次のようになります。

出力は次のとおりです。

したがって、最後の構成は両方ともマイナスであり、次のようになります。

概ね良好ですが、若干の穴が開いています。だから、それはまだ間違っています。なぜ正しく描画されないのかわかりません。アンチエイリアシングなしで通常のbresenhamを試したところ、問題なく動作しました。

また、重要な注意点として、私の場合は cocos2d-x テクスチャを使用しているため、y が反転しています。それが私がこの方法を持っている理由です：

たぶん問題は、このためです。どうすればこれを修正できますか?
よろしく

一定の太さで線を引く簡単な方法を作りました。これが私の機能です：

(x1, y1) から (x2, y2) に色 (r, g, b, a) と太さ wd で線を引く必要があります。画面上で指を動かしながら描画するときにこのメソッドを使用するので、追加のパラメーター「began」も追加しました。これは、タッチが開始したか、タッチが移動したかを示します。データはピクセルの配列です。エリアデータは関係ありません。

しかし、期待どおりに機能していません。結果の例を次に示します。

少し圧縮されている可能性がありますが、細かく描かれた 2 つの点と、穴のある多くの「太い」線から曲線が構築されていることがわかります。

「wd」が十分に大きくない場合、問題は存在しません。精度に何らかの問題があることはほぼ確実です。

私は試しました: - for ループを 0 から 360 に変更します (角度-90、角度 + 90 ではありません)。- floor の代わりに round を使用 - -sin の代わりに sin を使用 (私の場合、y はいずれにせよ反転されます) - 0.05 のように 1.0 より低い _r を使用します。

また、指定された固定の太さ (この例では 60 ピクセル) では、_r 増分や角度などのパラメーターを設定して、穴なしで描画しないようにする方法はありません。

これを行うために独自の関数を作成することにしました。これは、Web で見つけた他の方法が期待どおりに機能しなかったためです (特にアンチエイリアシングの場合、これは私にとって完璧なソリューションです)。

これは、Web サイトから取得した drawLine 関数です: http://willperone.net/Code/codeline.php