問題タブ [bresenham]

円全体を効率的に描画するために、中点円アルゴリズム (ブレセンハム円) を使用しています。円弧を描くのに似たようなものはありますか? 開始角度と終了角度を指定して、円のその部分だけを描画したいと思います。

前もって感謝します！

編集:塗りつぶされた円弧、つまりパイスライスも描きたいと思います。:)

私はゲーム小惑星を作ろうとしています。私が今抱えている問題は、上矢印キーを押すと、「船」が10ピクセル上に移動することです。そして、左矢印キーを押すと、「船」が左に5度回転します。これは、左または右に曲がったときに発生する問題です。そして、上に移動してみてください。回転方向には動きません。回転した「船」をY方向に10度動かすだけです。

私が考えているのは、方向と呼ばれる変数を持つことです。この変数を360度の円と考えてください。私がやろうとしているのは、左矢印を押すたびに、方向から5を引くことです。これは、0から始まり、360から逆方向に進み、355に設定されます。次に、355を10で割ると、35.5になります。次に、10を35.5で割ると、.355になります。次に、10から.355を引きます（Yを上に移動します）。そしてそれを0から引きます（Xを左に移動します）。したがって、Yで9.645を上に移動し、Xで0.355を左に移動します。

私が抱えている問題は、私が持っている小惑星の「船」です。Graphics.FillPieは、開始角度と後退角度として使用するためにIntを必要としますが、ご覧のとおり、ダブルまたはフロートで作業する必要があります。私はこれを複雑にしすぎていると確信しており、100倍単純なものがあると確信しています。ブレゼンハムの線形アルゴリズムに沿って何かを考えています。誰かがもっと簡単なことや私の問題の修正を提案することで助けてくれるなら、それは大いにありがたいです。前もって感謝します。

私はPythonでブレゼンハムのアルゴリズムの実装を書きました（ウィキペディアの記事に続いて）、そしてそれは特定の角度の線を除いて正しく動作します。45〜90度、または135〜270度の範囲で延長する必要があるすべての線は、代わりに線y=xに沿って延長されます。

これが私のコードです：

誰かが私が台無しにしているものを見ますか？

編集：

関数に印刷コードを追加しました。

（0,0）はディスプレイの左上にあります。

私のテストフレームワークは非常に単純です。これはスタンドアロン関数なので、2つのポイントを渡すだけです。

origin =（416、384）
dest =（440、347）
bresenham（origin、dest）
（ 416、384）（440、347
）
x0 = 384
x1 = 347
y0 = 416
y1 = 440
[]

輪郭を描いた線を描くための高速なアルゴリズムを探しています。このアプリケーションでは、アウトラインの幅は1ピクセルで十分です。デフォルトでもオプションでも、共通のポイントを共有している場合は、2本の線をシームレスに接続できるはずです。

アスキーアートを失礼しますが、これはおそらくそれを実証するための最良の方法です。

通常の線：

「アウトライン」行：

私はdsPIC33FJ128GP802に取り組んでいます。これは、40 MIPS（1秒あたり100万命令）が可能な小型のマイクロコントローラー/デジタルシグナルプロセッサーです。整数演算のみが可能です（加算、減算、乗算：除算は可能ですが、約19サイクルかかります）。 OSDレイヤーを同時に処理し、処理時間の3〜4 MIPSのみが計算に使用できるため、速度が重要です。ピクセルは、黒、白、透明の3つの状態を占めます。ビデオフィールドは192x128ピクセルです。これは、オープンソースプロジェクトであるSuper OSD用です：http ：//code.google.com/p/super-osd/

私が考えた最初の解決策は、最初のパスで輪郭が描かれたピクセルと2番目のパスで通常のピクセルを持つ3x3の長方形を描画することでしたが、すべてのピクセルについて少なくとも3ピクセルが上書きされ、それらの描画に費やされた時間が無駄になるため、これは遅くなる可能性があります。だから私はもっと速い方法を探しています。各ピクセルのコストは約30サイクルです。100ピクセルの長さの線を描画するには、ターゲットは<50、000サイクルです。

MSペイントのようなアプリを構築するものを探しています。

MS ペイントのようなアプリケーションを作成しています (opengl プリミティブの使用は許可されていません)。これまでのところ、線と点のみを描画します。ワンクリックでポイントをレンダリングするときに、renderPoint 関数の変換に基づいて、このコードが本来あるべき場所に出力される理由がわかりません。

bresenham 関数内で呼び出された場合、正しくプロットされません ( wikipedia の記事から 1 行ずつ実装したため、正しいと思います)。変換で何か間違ったことをしていますか?

画面に直接レンダリングされないpygameを使用して高速線を描画しようとしています。目的の解像度のピクセル数と同じ大きさのPythonリストがあり、そのピクセルがラインアルゴリズムによってヒットされた回数に対応する整数値を格納します。これを使用して、2Dヒートマップが作成されるため、フラットなピクセル値を描画するのではなく、線が通過する回数に基づいてピクセル値が増分され、「ホット」ピクセルはより明るい色になります。

このようにする理由は、これらの線がいくつ描画されるか、および特定のピクセルがヒットする最大回数が事前にわからないためです。各レンダリングが正しい最大および最小RGB値を持つように出力をスケーリングしたいので、画面に描画するだけでは不十分です。

比較的ナイーブなブレゼンハムのアルゴリズムよりも、これらの線を引くためのより良い方法はありますか？drawLine関数の重要な部分は次のとおりです。

最終結果は、f内の最大値に基づいてスケーリングされ、画面に描画されます。たとえば、最大値が1000の場合、各ピクセルのRGB値は（f [i] * 255）/1000であると想定できます。

プロファイル情報によると、ランタイムはfへのインデックスルックアップによって支配されています。ここで以前の質問を使用して、これらの基本的なリストがnumpy配列やPythonの配列よりも高速であることを証明しましたが、このような線を描画する場合は、まだ改善の余地があるようです。

画面にレンダリングするために最終的に出力をスケーリングすることを知って、画面に未知の数の線を描画するための優れた高速な方法は何ですか？インデックスのオーバーヘッドを取り除く良い方法はありますか？

Every articles I studied about Bresenham Line Algorithm, they talk about a decision variable

Where does the idea of this mathematical term come from?

I mean, what was the idea behind taking dx * (d1 - d2) as decision variable?

Why was not d1 - d2 taken only?

Here is one of the articles.

2 点間の線の座標を計算するための高速なアルゴリズムが必要です。JavaScript Bresenham の優れた実装を見つけようとしましたが、出版物が多すぎて非常に紛らわしいものです。ウィキペディア -ここでは、最速で最も単純な形式 (両方向の除算とエラー計算なし) が次のような擬似コードで示されています。

この疑似コードに基づいたシンプルで堅牢な JavaScript Bresenham の実装をご存知ですか?

Bresenham のライン アルゴリズム (http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm ) を使用して、敵が 2D マップでプレイヤーを追いかけるゲームを作成しています。ゲームのコンセプトは、以下にあるものと似ています。以下の疑似コードは、http://herselfsai.com/2007/07/simple-predator-prey-chase-algorithms.htmlからのものです。

敵はマップの周りでプレイヤーを追いかけますが、それは0、45、90度などの角度であり、直線ではありません。また、私のコードでは、敵もランダムな速度 (0 から 5 の間) を持っており、時々プレイヤーを撃ちすぎてから、何度も何度も修正して撃ち過ぎようとします。それは別の問題かもしれません。

アルゴリズムの概念を完全に把握していないだけです。これを実装する正しい方法は何ですか?

前もって感謝します。