問題タブ [bresenham]

私のグラフィックコースでは、ナイーブラインラスタライズアルゴリズム、次にブレゼンハムのライン描画アルゴリズムを教えられました. コンピューターは整数マシンであると言われたので、整数マシンを使用する必要があります。

1. ソフトウェア レベルでの最適化がないと仮定すると、これは mmx やその他の命令セットを備えた最新の CPU に当てはまりますか? Intel の 64-ia-32-architectures-optimization-manual.pdf を見たところ、加算減算乗算のレイテンシは、mmx の int と比較して、float で同じかそれ以上です。

2. アルゴリズムが GPU で実行される場合、これは問題になりますか? NVIDIA CUDA Programming Guide 1.0 (pdf)の 41 ページを確認したところ、int と float のクロック サイクルは同じです。

3. float を int にキャストすることの非効率性は何ですか? load-hit-store ストールは私たちにとって本当の問題ですか?

4. 数値を切り上げる/切り下げる関数はどれくらい効率的ですか? (c++ stl での実装を考えることができます)

5. 内側のループで使用される乗算の代わりに加算により、ブレゼンハム アルゴリズムから得られる効率はありますか?

1 つのピクセルから次のピクセルへのステップが斜めに、水平または垂直にのみ許可されていない、修正された Bresenham アルゴリズムはありますか? またはそれを行う他のアルゴリズムはありますか？(PHP を推奨)

超球をラスタライズして塗りつぶそうとしています。本質的に、固定サイズの d 次元グリッドと球 (中心、半径) があり、グリッドのどのセルが球と重なっているかを調べ、それらの座標を保存したいと考えています。

8 方向のミラーリングを利用して円の外側のセル (境界線) を生成するMidpoint circle アルゴリズムを認識しています。また、リンクされたウィキペディア コードを変更して、円を塗りつぶします (つまり、境界内のすべてのセルの座標を生成します)。

ただし、高次元のアルゴリズムは知りません。たとえば 4d では、次の疑似コードのようにすべての可能な円を生成して実装することを考えていました。基本的な考え方は、4d 球体は (x-x0) 2 + (y-y0)**2 + (z-z0)**2 + (k-k0)**2 = r 2 であるため、これは等しいということです。 (x-x0) 2 + (y-y0)**2 = r 2 - (z-z0)**2 - (k-k0)**2. 私は円を描く方法を知っているので、z と k のすべての可能な値に対してすべての円を作成する必要があります。

この質問は関連しているようですが、答えがわかりません。

私はOpenGL/GLUTを使用してブレゼンハムの線描画アルゴリズムを実装していますが、一見任意のアーティファクトが表示されるという問題があります。次に例を示します。

これが私が関連すると思ういくつかのコードです。頂点バッファーにデータを取り込むコードは含めませんでした。これは、99％正しいと確信しており、書き直したためです。問題は、GLUTマウスコールバックを使い始めたときに発生しました。

アイデアは、ポイントをクリックすると、そのポイントから離したポイントまで線が移動するというものです。呼び出しと一緒にその機能を追加する前はglutPostRedisplay()、線画はうまく機能しているようでした。

上の写真では、描く予定の線が左側の線です。それは機能しましたが、他のアーティファクトが現れました。それらは頂点バッファにもありません、私はチェックしました。

彼らがどこから来ているのかアイデアはありますか？

プレイヤーの動きにブレゼンハムアルゴリズムを使用してゲームのプロトタイプを作成しています。ここでは「編集」の下の実装を使用しましたが、ポイントは保存しません：Javascriptのブレゼンハムアルゴリズム

私は数学が苦手なので（そして私は開発者ではありません！）、これが私の問題が何であるかを理解する能力をおそらく妨げています。より高いレベルでアルゴリズムを説明する素晴らしい投稿を見つけました：簡略化されたブレゼンハムのラインアルゴリズム：それは*正確に*何をしますか？

これが私のコードからの出力です。ループを繰り返すたびに、妥当な領域から出たかどうかを確認します。これは一貫して発生します。エラーの計算とポイントの検索に問題がありますが、それを修正する方法を知るための数学の能力がありません。

以下のコードでは、currentXとcurrentYは、targetXとtargetYに近づくように常に変化している必要があります。現在の座標とターゲットの座標の一方が同じで、もう一方が大きく異なる点があることがわかります。これは意味がありません。アルゴリズムによって、currentXとcurrentYの両方がその時点でターゲット座標に非常に近いはずだからです。

編集3：新しい出力

編集：以下に投稿されたコード。

EDIT2：以下に掲載されているより関連性の高いコード。

hermes.js-プレイヤーのキャラクター（Hermes）と、彼が2Dゲームプレーンとどのように関係しているかを説明します

game.js-高レベルのゲームロジック。焦点を当てる鍵はクリックイベントハンドラーです。それ以外の場合、ここにはまだ多くはありません

私のコンピューター グラフィックスの宿題は、点を描画する機能のみを使用して OpenGL アルゴリズムを実装することです。

drawLine()だから明らかに、他のものを描く前に仕事に 取り掛かる必要があります. drawLine()整数のみを使用して行う必要があります。浮動小数点なし。

これが私が教えられたことです。基本的に、ラインは、正の急勾配、正の急勾配、負の急勾配、負の急勾配の 4 つのカテゴリに分けることができます。これは私が描くことになっている絵です：

これは私のプログラムが描いている絵です：

色は私たちのために行われます。頂点が与えられ、ブレゼンハムの線アルゴリズムを使用して、始点と終点に基づいて線を描画する必要があります。

これは私がこれまでに持っているものです:

私のエラーがばかげたものになることはわかっていますが、正直なところ、何が間違っているのかわかりません。上記のように一部の線が正しく描かれていないのはなぜですか?

中点円アルゴリズムを使用して円を生成しています。これらの円を描きたくありません。代わりに、ポリゴンとして保存したいと思います。明らかに、座標の順序が間違っているため、Graphics.DrawPolygonなどを使用してこれらの円を描画すると、円は線のメッシュになります。

Q：正しく定義されたポリゴンを生成するようにアルゴリズムを変更するにはどうすればよいですか？または、ポイントのセット（この場合は円に属する）から有効なポリゴンを作成するにはどうすればよいですか？

更新：これでうまくいきました。

コルヌ スパイラル (別名、クロソイド) またはスプラインの適切な描画アルゴリズムを見た人はいますか? 弧と線については、ブレゼンハムのアルゴリズムのようなものがあります。それはクロソイドに適応できますか？

ウィキペディアのページには、次の Sage コードがあります。

利用可能なパラメトリック プロットのサンプル コードはありますか? Web 検索ではあまり表示されません。

特定の「ピクセル化された」領域内にピクセルを取得できるアルゴリズムがあるかどうか疑問に思っていますか？

したがって、塗りつぶされていない3 x 3ピクセルの正方形がある場合、塗りつぶされていないプロットは次のようになります。2,2グリッドは次のようになります。

ありがとう！

ライン内のすべてのピクセルをチェックする必要があるため、ブレゼンハムのアルゴリズムを使用して、ライン内の各ピクセルにアクセスしています。特に、すべてのピクセルがビットマップの有効なピクセルにあるかどうかを確認する必要があります。これはコードです：

Check_Pixelは、ラインピクセルが有効なビットマップ上にあるかどうかを確認するために使用されます。に作成されたピクセルを追加してList<Point>、要素を1つずつレンダリングしBresenham、正しいピクセルを確認します（実際にチェックします）。問題は、私のアルゴリズムがすべてのケースをカバーしているわけではなく、それらの約50％をカバーしていることです。

PS：私の座標系の原点は左上隅にあります（xは左から右に、yは下に向かって大きくなります）