問題タブ [bresenham]

同心円を描くために、ブレゼンハムとしても知られる中点円アルゴリズムを使用しています。各円の半径と次の円の半径の差は常に 1 であるため、最終結果は完全な円形領域になります。

ただし、添付の画像に示すように、一部のピクセルは空のままです。

JavaScript を使用して HTML5 キャンバスにペイントし、canvas.getContext("2d").getImageData(...).data 配列を操作しています。

円は交互に白と赤になり、空のピクセルは黒になります。私が言っていることを正しく理解するには、ズームインする必要があるかもしれません。

対応する円弧を描画するときにそれらのピクセルが塗りつぶされるように、アルゴリズムにコードを追加しようとしています。これらのピクセルのいずれかが、次のアークではなく 1 つのアークに属する理由はないように思われるため、半径が偶数のアークまたは奇数の半径のアークで埋められているかどうかは気にしません (私は私が自分自身を明確にしていることを願っています）。

ピクセルはパターンに従っているように見えますが、それが何であるかはわかりません. 誰かがそれを見つけるのを手伝ってくれますか?

過去 1 時間ほど見回しましたが、この問題に関する解決策が見つかりません。私はこの疑似コードをJavaに変換しようとしていますが、何が間違っているのかわかりません(何かを出力します)。

私の変換は次のとおりです。

誰か助けてくれませんか？

衝突テストでは、線をラスターする必要があります。ブレゼンハムのアルゴリズムはほぼ希望どおりに機能しますが、次のような行を生成するという欠陥があります。

そして私は必要です：

私の現在の実装（ http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Simplificationに基づく）：

私が使用できる他のラインラスタライズアルゴリズムはありますか、またはブレゼンハムを変更する方法を知っている人はいますか？

ミッドポイント サークル アルゴリズムを使用すると、各ピクセルに 1 回だけアクセスして、対称的な円を描くことができます。アルゴリズムの性質上、直径が奇数 (2 * r + 1) の円しか描画できません。このアルゴリズムを拡張して、ピクセル数が偶数の直径の円を正常に描画できるようにすることはできますか?

アルゴリズムの要件:

• ピクセルは 1 回だけ描画する必要があります。
• RAM は非常に高価です。

これを処理するために Midpoint circle アルゴリズムを実際に変更できない場合は、次の解決策で問題ありません。

私は一人称 3D ゲームに取り組んでいます。レベルは完全に立方体ベースで、壁/床/その他はすべてタイル張りの立方体 (1x1x1) です。

現在、カメラの位置とカメラの回転を使用して方向を取得する光線を作成しています。次に、空ではない最初のキューブにレイキャストアウトしたいと考えています（またはレイがグリッドから落ちたとき）。多くの場合、これらは 0,0,1 や 1,0,0 などの方向ベクトルです。

始点/終点ではなく方向ベクトルで機能する Bresenham Line Drawing Algorithm を見つけるのにあまり運がありません。特に、方向ベクトルが整数のみを格納するわけではないことを考慮してください。

したがって、特定の質問については、私がこれを正しい方法で行うことに近づいているかどうか、誰かがそれをどのように行うべきかについて詳しく説明できるかどうかを尋ねていると思います.

ブレゼンハムの浮動小数点アルゴリズムには、私を苛立たせる何かがあります。

アルゴリズムは以下のとおりです。

Y=0.6Xを描画したいとします。したがって、x = 0の最初のステップでは、エラーは0.6に設定され、ifステートメントとyが増加します。エラーは-0.4に設定されます。-0.4は次のステップでどのように役立ちますか？

だから私の問題はこのコード行にあります：

エラーを1つ減らす必要があるのはなぜですか？再調整のためにこれを行うことを読みました！それはどのように私たちを助けることができますか？

私は現在、開発中のタイルベースのワールドエディタにブレゼンハムラインアルゴリズムを実装しています。Shift+機能についてClickは、タイルセットからの選択長方形に基づいて線をレンダリングしたいと思います。アルゴリズムpoint1を使用してからまでの線上の点を見つけ、各点で選択範囲を描くことができるので、これは簡単です。point2

これに関する問題は、選択長方形が1タイルよりも大きい場合、ポイントが重なることです。結果は以下のようになります。

私の質問には、ライン上のすべてのポイントと選択サイズが示されていますが、どうすればこのような結果を得ることができますか？を超えたら、選択範囲の描画を停止したいことに注意してくださいpoint2。

これが、選択サイズに関係なく線をレンダリングするために現在持っているものです。

私のコードのコンテキストがもっと必要な場合は、コメントを残してください。

ブレゼンハムによる線を描くためのこのよく知られたアルゴリズムがあり、ウィキペディアにはそれに関する非常に良い記事があります: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm。

メイン ループは、必要に応じて 1 を加算または減算して、x または y 座標を繰り返し計算します。

start-point x1、y1、 end-point x2、y2および some y( y1<= y<= ) を指定すると、行のアクティブなピクセルのすべての座標y2を直接計算できますか?xy

たとえば、標準の Bresenham メソッドを使用して線を引くとします。

そのためyに、 のシーケンスを取得したいと思い[x1+11, x1+12, x1+13]ます。

上記のように Bresenham を変更することさえ可能かどうかはわかりませんが、それが不可能であることが判明した場合、Bresenham によって計算された場合とまったく同じに見えるシーケンスを取得する他の方法はありますか? 直接評価できる限り、float を使用するかどうか、速いか遅いかは気にしません。

前もって感謝します！

編集：アイデアを比較できるようにするために、簡単な参照テストを作成しました：

タイピング：

プリント: