Determines the points needed for rasterizing a circle
ブレゼンハム中点円アルゴリズムを用いて、半径23の円をラスタライズします。緑色の部分のみが 八分儀が実際に計算されると、単純に 8 回反転されて他の 7 つの八分儀が形成されます。 ブレゼンハムアルゴリズムによって描かれた半径23の円 コンピュータグラフィックス において 、 中点円アルゴリズム は、円 を ラスタライズする ために必要な点を決定するために使用されるアルゴリズムです 。これは、 ブレゼンハムの直線アルゴリズムの一般化です。このアルゴリズムは、 円錐曲線 にもさらに一般化できます 。 [1] [2] [3]
要約 このアルゴリズムは、各 基本方向 （0°、90°、180°、270°）から始めて、両方向に45°の最も近い倍数（45°、135°、225°、315°）まで、8つの八分円を同時に描画します。y = x の とき 、45°に達しているため、停止位置を決定できます。これらの角度を使用する理由は上の図に示されています。x が 増加すると、 45°に達するまで xの 値をスキップしたり繰り返したりすることはありません。したがって、 while ループ中、 xは 各反復で1ずつ増加し、 yは 時々1ずつ減少しますが、1回の反復で1を超えることはありません。これは45°で変化します。これは、接線が rise = runと なる点だからです。一方 、rise > run before、 rise < run afterです
問題の 2 番目の部分である行列式は、はるかに扱いにくいです。これは、 y をいつ減分するかを決定します。最初のピクセルで半径を下回ることはないため、通常は各反復でピクセルを描画した後に行われます。 連続関数 では、球の関数は、半径が z (または 3 番目の変数) に依存する円の関数であるため、離散 ( ボクセル ) 球のアルゴリズムで も中点円アルゴリズムを使用するのは当然です。ただし、球を見ると、隣接する円の整数半径は同じですが、同じ半球内にまったく同じ円が隣接することは想定されていません。代わりに、同じ半径の円には、曲線が中心に少し近づいたり、さらに外側に広がったりできるように、異なる行列式が必要です。
アルゴリズム このアルゴリズムの目的は 円を 近似することです。より正式には、ピクセルを使用して 曲線を近似することです。 簡単に言えば、 円の定義と同様に、すべてのピクセルは中心からほぼ同じ距離にある必要があります。各ステップで、を満たすが 最大化する隣接ピクセルを選択することで、経路が延長されます 。候補ピクセルは隣接しているため、後者の式を計算する演算は簡略化され、 ビットシフト と加算のみが必要です。しかし、ビットシフトを理解するために簡略化を行うことができます。2 進数 の左ビットシフトは2を掛けることと同じであることを覚えておいてください。したがって、半径の左ビットシフトは、 半径の2倍として定義される 直径のみを生成します x 2 + y 2 = r 2 {\displaystyle x^{2}+y^{2}=r^{2}} x 2 + y 2 ≤ r 2 {\displaystyle x^{2}+y^{2}\leq r^{2}} x 2 + y 2 {\displaystyle x^{2}+y^{2}}
このアルゴリズムは 円の 方程式から始まります。簡単のため、円の中心は にあると仮定します 。まず、第一八分円のみを考え、点 から 反時計回りに進み、角度 45° に達する曲線を描きます。 ( 0 , 0 ) {\displaystyle (0,0)} ( r , 0 ) {\displaystyle (r,0)}
ここでの速い 方向 （ 値の増加が大きい 基底ベクトル ）は方向です（ 三角関数の微分を 参照）。アルゴリズムは常に正の方向（上方向）にステップを踏み、時折、 遅い 方向（負の方向） にステップを踏みます 。 y {\displaystyle y} y {\displaystyle y} x {\displaystyle x}
円方程式から変換された方程式 が得られます 。ここで、 は初期化中に 1 回だけ計算されます。 x 2 + y 2 − r 2 = 0 {\displaystyle x^{2}+y^{2}-r^{2}=0} r 2 {\displaystyle r^{2}}
円上の点を、点へのベクトルの座標列（通常の基底）とします。点は描画順に番号が付けられ、 最初の点には が割り当てられます 。 n = 1 {\displaystyle n=1} ( r , 0 ) {\displaystyle (r,0)}
各点について、次のことが当てはまります。
x n 2 + y n 2 = r 2 {\displaystyle {\begin{aligned}x_{n}^{2}+y_{n}^{2}=r^{2}\end{aligned}}} これを次のように並べ替えることができます。
x n 2 = r 2 − y n 2 {\displaystyle {\begin{aligned}x_{n}^{2}=r^{2}-y_{n}^{2}\end{aligned}}} 次の点についても同様です。
x n + 1 2 = r 2 − y n + 1 2 {\displaystyle {\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n+1}^{2}\end{aligned}}} 最初の八分円では、次の点は常に最後の点より少なくとも 1 ピクセル高くなります (ただし、連続性を維持するために最大でも 1 ピクセル高くなります)。したがって、次の式は成り立ちます。
y n + 1 2 = ( y n + 1 ) 2 = y n 2 + 2 y n + 1 {\displaystyle {\begin{aligned}y_{n+1}^{2}&=(y_{n}+1)^{2}\\&=y_{n}^{2}+2y_{n}+1\end{aligned}}} x n + 1 2 = r 2 − y n 2 − 2 y n − 1 {\displaystyle {\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n}^{2}-2y_{n}-1\end{aligned}}} したがって、次の式を代入して次の点の式を再帰的に書き直します 。 x n 2 = r 2 − y n 2 {\displaystyle x_{n}^{2}=r^{2}-y_{n}^{2}}
x n + 1 2 = x n 2 − 2 y n − 1 {\displaystyle {\begin{aligned}x_{n+1}^{2}=x_{n}^{2}-2y_{n}-1\end{aligned}}} 円の連続性と両軸の最大値が同じであることから、 数列を進むにつれて x点が飛ばされることは明らかにありません。通常は同じ x 座標に留まりますが、時には左に1つ進むこともあります。
得られた座標は、中点座標を加算することで変換されます。これらの頻繁な整数加算は、平方根計算を内側のループで省略できるため、 パフォーマンス に大きな影響を及ぼしません。ここでも、変換された円周方程式のゼロは誤差項に置き換えられます。
誤差項の初期化は、開始時の1/2ピクセルのオフセットから導出されます。垂直線との交点まで、 誤差項には累積値が生じるため、この値が初期化に使用されます。 r {\displaystyle r}
円方程式、 三角 関数の式、 平方根における頻繁な 平方 の計算は、すべてを単一のステップに分解し、 前の反復からの 二次項の 再帰 計算 を使用することによって、再び回避できます。
整数ベースの演算を持つバリアント ブレゼンハムの直線アルゴリズム と同様に 、このアルゴリズムは整数ベースの計算に最適化できます。対称性のため、1つの八分円のピクセルのみを計算するアルゴリズムが見つかれば、それらのピクセルを反転させて円全体を求めることができます。
まず、半径誤差を、円の正確な表現と各ピクセルの中心点（または、すべてのピクセルで一貫している限り、ピクセル上の任意の数学的点）との差として定義します。 を中心とする任意のピクセルについて 、半径誤差は次のように定義されます。 ( x i , y i ) {\displaystyle (x_{i},y_{i})}
R E ( x i , y i ) = | x i 2 + y i 2 − r 2 | {\displaystyle RE(x_{i},y_{i})=\left\vert x_{i}^{2}+y_{i}^{2}-r^{2}\right\vert } 分かりやすくするために、この円の式は原点を基準に導出されていますが、このアルゴリズムは任意の位置に適用できます。X 軸の正方向の点から始めるのが便利です。半径は整数ピクセルとなるため、半径誤差は明らかにゼロになります。 ( r , 0 ) {\displaystyle (r,0)}
R E ( x i , y i ) = | x i 2 + 0 2 − r 2 | = 0 {\displaystyle RE(x_{i},y_{i})=\left\vert x_{i}^{2}+0^{2}-r^{2}\right\vert =0} 最初の反時計回りの正の八分円から始まるため、 移動量が 最大となる方向、つまりY方向に進みます。したがって、 であることは明らかです 。また、この八分円のみに関係するため、 X 値には、前の反復と同じままにするか、1ずつ減少するかの2つの選択肢しかありません。次の条件が満たされるかどうかを判断する決定変数を作成できます。 y i + 1 = y i + 1 {\displaystyle y_{i+1}=y_{i}+1}
R E ( x i − 1 , y i + 1 ) < R E ( x i , y i + 1 ) {\displaystyle RE(x_{i}-1,y_{i}+1)<RE(x_{i},y_{i}+1)} この不等式が成り立つ場合は をプロットし、 成り立たない場合は をプロットします 。では、この不等式が成り立つかどうかをどのように判断するのでしょうか？まず、半径誤差の定義から始めましょう。 ( x i − 1 , y i + 1 ) {\displaystyle (x_{i}-1,y_{i}+1)} ( x i , y i + 1 ) {\displaystyle (x_{i},y_{i}+1)}
R E ( x i − 1 , y i + 1 ) < R E ( x i , y i + 1 ) | ( x i − 1 ) 2 + ( y i + 1 ) 2 − r 2 | < | x i 2 + ( y i + 1 ) 2 − r 2 | | ( x i 2 − 2 x i + 1 ) + ( y i 2 + 2 y i + 1 ) − r 2 | < | x i 2 + ( y i 2 + 2 y i + 1 ) − r 2 | {\displaystyle {\begin{aligned}RE(x_{i}-1,y_{i}+1)&<RE(x_{i},y_{i}+1)\\\left\vert (x_{i}-1)^{2}+(y_{i}+1)^{2}-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}+1)^{2}-r^{2}\right\vert \\\left\vert (x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right\vert \\\end{aligned}}} 絶対値関数は役に立ちません。平方は常に正なので、両辺を平方します。
[ ( x i 2 − 2 x i + 1 ) + ( y i 2 + 2 y i + 1 ) − r 2 ] 2 < [ x i 2 + ( y i 2 + 2 y i + 1 ) − r 2 ] 2 [ ( x i 2 + y i 2 − r 2 + 2 y i + 1 ) + ( 1 − 2 x i ) ] 2 < [ x i 2 + y i 2 − r 2 + 2 y i + 1 ] 2 ( x i 2 + y i 2 − r 2 + 2 y i + 1 ) 2 + 2 ( 1 − 2 x i ) ( x i 2 + y i 2 − r 2 + 2 y i + 1 ) + ( 1 − 2 x i ) 2 < [ x i 2 + y i 2 − r 2 + 2 y i + 1 ] 2 2 ( 1 − 2 x i ) ( x i 2 + y i 2 − r 2 + 2 y i + 1 ) + ( 1 − 2 x i ) 2 < 0 {\displaystyle {\begin{aligned}\left[(x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}&<\left[x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}\\\left[(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})\right]^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\\left(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right)^{2}+2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<0\\\end{aligned}}} x > 0 なので、 の項 となるので、割ると次のようになります。 ( 1 − 2 x i ) < 0 {\displaystyle (1-2x_{i})<0}
2 [ ( x i 2 + y i 2 − r 2 ) + ( 2 y i + 1 ) ] + ( 1 − 2 x i ) > 0 2 [ R E ( x i , y i ) + Y Change ] + X Change > 0 {\displaystyle {\begin{aligned}2\left[(x_{i}^{2}+y_{i}^{2}-r^{2})+(2y_{i}+1)\right]+(1-2x_{i})&>0\\2\left[RE(x_{i},y_{i})+Y_{\text{Change}}\right]+X_{\text{Change}}&>0\\\end{aligned}}} したがって、決定基準は浮動小数点演算から、単純な整数加算、減算、およびビットシフト（2倍演算の場合）に変わります。 2 ( R E + Y Change ) + X Change > 0 {\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}>0} の場合、 xの 値を減算します。 の場合、 2 ( R E + Y Change ) + X Change ≤ 0 {\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0} xの 値はそのままです 。繰り返しますが、これらの点をすべての八分円で反射させることで、完全な円が得られます。
この決定式の値と、前のステップでの値との差分を計算するだけで計算量を削減できます。まず、 を E {\displaystyle E} 3 − 2 r {\displaystyle 3-2r} （式の初期値） として代入します 。その後は、各ステップで が成立する場合は ( x 0 , y 0 ) = ( r , 0 ) {\displaystyle (x_{0},y_{0})=(r,0)} （そして X を減算）し 、 成立 E > 0 {\displaystyle E>0} し ない 場合は （そして Y を 通常 E = E + 2 ( 5 − 2 x + 2 y ) {\displaystyle E=E+2(5-2x+2y)} 通り 増分 ）します。 E = E + 2 ( 3 + 2 y ) {\displaystyle E=E+2(3+2y)}
ジェスコ法 アルゴリズムについてはすでに大部分説明されていますが、さらなる最適化が行われます
新たに提案された手法 [4] は、1ステップ（8ピクセル）あたりわずか5回の算術演算で済むため、低性能システムに最適です。「if」演算では、符号（正か負か）のみがチェックされ、変数への代入も行われますが、これも算術演算とはみなされません。1行目の初期化（4ビット右シフト）は見た目上の都合であり、実際には不要です。
したがって、メインループ内では可算な演算が実行されます。
比較 x >= y (減算としてカウントされます: x - y >= 0) y=y+1 [y++] t1 + y t1 - x t2 >= 0 の比較は、実数演算が行われないためカウントされません。 変数の 2の補数表現では、 符号ビット のみをチェックする必要があります。 x=x-1 [x--] 演算: 5
t1 = r / 16 x = r y = 0 x < y になるまで繰り返す ピクセル（x, y）とすべての対称ピクセルが色付けされる（8回） y = y + 1 t1 = t1 + y t2 = t1 - x t2 >= 0 の 場合 t1 = t2 x = x - 1
不完全な八分円の描画 上記の実装では、常に完全な八分円または円のみが描画されます。 角度から 角度までの特定の 円弧 のみを描画するには、アルゴリズムはまず これらの端点の座標 と座標を計算する必要があり、三角関数または平方根の計算に頼る必要があります（ 平方根の計算方法を 参照）。次に、ブレゼンハムアルゴリズムを完全な八分円または円に対して実行し、必要な間隔内にあるピクセルのみを設定します。この円弧を描画した後、アルゴリズムを途中で終了することができます α {\displaystyle \alpha } β {\displaystyle \beta } x {\displaystyle x} y {\displaystyle y}
角度が 傾き として与えられている場合は、三角法や平方根は必要ありません。 が目的の傾きの間であることを確認するだけです。 y / x {\displaystyle y/x}
一般化 同じ概念を使って、 放物線 、 楕円 、その他の2次元 曲線 をラスタライズすることも可能です。 [5]
参考文献 ^ ドナルド・ハーン、M・ポーリン・ベイカー（1994年）。 コンピュータグラフィックス 。プレンティス・ホール 。ISBN 978-0-13-161530-4 。 ^ Pitteway, MLV, 「デジタルプロッタによる楕円または双曲線の描画アルゴリズム」、Computer J.、10(3) 1967年11月、282～289ページ ^ Van Aken, JR、「効率的な楕円描画アルゴリズム」、CG&A、4(9)、1984年9月、24～35ページ ^ このアルゴリズムの公開履歴については、https://schwarzers.com/algorithms を参照してください。 ^ Zingl, Alois (2014年12月). 「Bresenhamアルゴリズムの美しさ：直線、円、楕円、ベジェ曲線をプロットするためのシンプルな実装」 easy.Filter . Alois Zingl . 2017年 2月16日 閲覧 。
外部リンク 円の描き方 - シンプルな図から効率的な図まで、円の描き方に関する記事 いくつかのプログラミング言語における中点円アルゴリズム .gif/1280px-Midpoint_circle_algorithm_animation_(radius_23).gif)
_01.png/1280px-Concentric_circles_drawn_with_Bresenham's_circle_algorithm_(all_black)_01.png)
![{\displaystyle {\begin{aligned}\left[(x_{i}^{2}-2x_{i}+1)+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}&<\left[x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right]^{2}\\\left[(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})\right]^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2 }\\\left(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right)^{2}+2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<0\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0818c8732e78a64182d8229371aa2f8c59d5e158)
![{\displaystyle {\begin{aligned}2\left[(x_{i}^{2}+y_{i}^{2}-r^{2})+(2y_{i}+1)\right]+(1-2x_{i})&>0\\2\left[RE(x_{i},y_{i})+Y_{\text{Change}}\right]+X_{\text{Change}}&>0\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4edd2f984e728a380b43a4f3be840ac30b2e07e)
.gif){kind=link}
_01.png){kind=link}
