中点円アルゴリズム

コンピュータグラフィックスにおいて、中点円アルゴリズムは、円をラスタライズするために必要な点を決定するために使用されるアルゴリズムです。これは、ブレゼンハムの線アルゴリズムの一般化です。このアルゴリズムは、円錐曲線にさらに一般化できます。^{[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 番目の変数) に依存する円の関数であるため、離散 (ボクセル) 球のアルゴリズムも中点円アルゴリズムに依存するのは当然です。しかし、球を見ると、隣接する円の整数半径は同じですが、同じ半球内にまったく同じ円が隣接することは想定されていません。代わりに、同じ半径の円には、曲線が中心に少し近づいたり、さらに広がったりできるように、異なる行列式が必要です。

• 中点円アルゴリズムで描かれた150 個の同心円。
• 
  左側では、すべての円が黒く描かれています。
• 
  右側では、赤、黒、青を組み合わせて、円の同心性を示しています。

アルゴリズムの目的は円を近似することです。もっと正式に言えば、ピクセルを使用して曲線を近似することです。平たく言えば、円の定義と同様に、すべてのピクセルは中心からほぼ同じ距離にある必要があります。各ステップで、を満たし、最大化する隣接ピクセルを選択することでパスが延長されます。候補ピクセルは隣接しているため、後者の式を計算する演算は簡略化され、ビットシフトと加算のみが必要です。ただし、ビットシフトを理解するために簡略化を行うことができます。2進数の左ビットシフトは、2を掛けることと同じであることに留意してください。したがって、半径の左ビットシフトは、半径の2倍として定義される 直径のみを生成します。${\displaystyle x^{2}+y^{2}=r^{2}}$${\displaystyle x^{2}+y^{2}\leq r^{2}}$${\displaystyle x^{2}+y^{2}}$

このアルゴリズムは円方程式から始まります。簡単にするために、円の中心は にあると仮定します。まず、第 1 八分円のみを考慮し、点から始まり反時計回りに進み、角度 45° に達する曲線を描きます。 ${\displaystyle (0,0)}$${\displaystyle (r,0)}$

ここでの高速方向（値の増加が大きい基底ベクトル）は方向です（三角関数の微分を参照）。アルゴリズムは常に正の方向（上方向）にステップを踏み、時折、低速の方向（負の方向）にステップを踏みます。 ${\displaystyle y}$${\displaystyle y}$${\displaystyle x}$

円方程式から変換された方程式 が得られます。ここで、 は初期化中に 1 回だけ計算されます。 ${\displaystyle x^{2}+y^{2}-r^{2}=0}$${\displaystyle r^{2}}$

円上の点を、点へのベクトルの座標のシーケンス（通常の基底）とします。点は、描画された順序に従って番号が付けられ、最初の点にはが割り当てられます。 ${\displaystyle n=1}$${\displaystyle (r,0)}$

各点について、次のことが当てはまります。

${\displaystyle {\begin{aligned}x_{n}^{2}+y_{n}^{2}=r^{2}\end{aligned}}}$

これを次のように並べ替えることができます。

${\displaystyle {\begin{aligned}x_{n}^{2}=r^{2}-y_{n}^{2}\end{aligned}}}$

次の点についても同様です。

${\displaystyle {\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n+1}^{2}\end{aligned}}}$

最初の八分円では、次の点は常に最後の点より少なくとも 1 ピクセル高くなります (ただし、連続性を維持するために最大でも 1 ピクセル高くなります)。したがって、次のことが当てはまります。

${\displaystyle {\begin{aligned}y_{n+1}^{2}&=(y_{n}+1)^{2}\\&=y_{n}^{2}+2y_{n}+1\end{aligned}}}$

${\displaystyle {\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n}^{2}-2y_{n}-1\end{aligned}}}$

したがって、次の式を代入して、次の点の式を再帰的に書き直します。 ${\displaystyle x_{n}^{2}=r^{2}-y_{n}^{2}}$

${\displaystyle {\begin{aligned}x_{n+1}^{2}=x_{n}^{2}-2y_{n}-1\end{aligned}}}$

円の連続性と両軸の最大値が同じであることから、シーケンスが進むにつれてx点がスキップされることは明らかにありません。通常は同じx座標に留まり、左に 1 つ進むこともあります。

結果の座標は、中間点座標を追加することによって変換されます。これらの頻繁な整数の追加は、内側のループで平方 (ルート) 計算を省略できるため、パフォーマンスをそれほど制限しません。この場合も、変換された円方程式のゼロは、誤差項に置き換えられます。

誤差項の初期化は、開始時の 1/2 ピクセルのオフセットから導出されます。垂直線との交差まで、誤差項に の累積値が得られるため、この値が初期化に使用されます。 ${\displaystyle r}$

円方程式、三角関数の式、平方根における頻繁な平方の計算は、すべてを単一のステップに分解し、前​​の反復からの二次項 の再帰計算を使用することによって、再び回避できます。

Bresenham の直線アルゴリズムと同様に、このアルゴリズムは整数ベースの計算に最適化できます。対称性のため、1 つの八分円のピクセルのみを計算するアルゴリズムが見つかった場合は、ピクセルを反転して円全体を取得できます。

まず、半径誤差を、円の正確な表現と各ピクセルの中心点（または、すべてのピクセルで一貫している限り、ピクセル上の任意の数学的点）との差として定義します。 を中心とするピクセルの場合、半径誤差は次のように定義されます。 ${\displaystyle (x_{i},y_{i})}$

${\displaystyle RE(x_{i},y_{i})=\left\vert x_{i}^{2}+y_{i}^{2}-r^{2}\right\vert }$

わかりやすくするために、この円の式は原点から導出されていますが、アルゴリズムは任意の場所に対して変更できます。正の X 軸上の点から始めると便利です。半径はピクセルの整数になるため、半径の誤差は明らかにゼロになります。 ${\displaystyle (r,0)}$

${\displaystyle RE(x_{i},y_{i})=\left\vert x_{i}^{2}+0^{2}-r^{2}\right\vert =0}$

最初の反時計回りの正の八分儀から始まるため、移動が最大となる方向、つまり Y 方向に進みます。したがって、 であることは明らかです。また、この八分儀のみに関係するため、X値には、前の反復と同じままにするか、1 ずつ減少するかの 2 つのオプションしかありません。次の条件が当てはまるかどうかを判断する決定変数を作成できます。 ${\displaystyle y_{i+1}=y_{i}+1}$

${\displaystyle RE(x_{i}-1,y_{i}+1)<RE(x_{i},y_{i}+1)}$

この不等式が成り立つ場合は をプロットし、そうでない場合は をプロットします。では、この不等式が成り立つかどうかをどのように判断するのでしょうか? 半径誤差の定義から始めます。 ${\displaystyle (x_{i}-1,y_{i}+1)}$${\displaystyle (x_{i},y_{i}+1)}$

${\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}}}$

絶対値関数は役に立ちません。平方は常に正なので、両辺を平方します。

${\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なので、項 となり、これを割ると次のようになります。 ${\displaystyle (1-2x_{i})<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 倍演算の場合）に変わります。⁠ ⁠${\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}>0}$の場合は、x値を減分します。⁠ ⁠の場合は、 ${\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0}$x値を同じに保ちます。ここでも、これらの点をすべての八分円に反映させることで、完全な円が得られます。

この決定式の値と前のステップの値の差分のみを計算することで、計算を減らすことができます。まず、⁠ ⁠ を${\displaystyle E}$⁠ ⁠での式の初期値である⁠ ⁠${\displaystyle 3-2r}$として割り当て、次に各ステップで ⁠ ⁠の場合は上記のように⁠ ⁠として更新し(そしてX を減分します)、それ以外の場合は⁠ ⁠から通常どおり Y を増分します。${\displaystyle (x_{0},y_{0})=(r,0)}$${\displaystyle E>0}$${\displaystyle E=E+2(5-2x+2y)}$${\displaystyle E=E+2(3+2y)}$

アルゴリズムについては既に大部分説明されていますが、さらに最適化が行われます。

新しく発表された方法^[4]は、ステップごとに 5 つの算術演算 (8 ピクセル) のみで実行できるため、低パフォーマンスのシステムに最適です。「if」演算では、符号 (正か負か) のみがチェックされ、変数の割り当てがありますが、これも算術演算とは見なされません。最初の行の初期化 (4 ビット右にシフト) は、見た目のためだけのものであり、実際には必要ありません。

したがって、メインループ内では可算な操作が実行されます。

1. 比較 x >= y (減算としてカウントされます: x - y >= 0)
2. y=y+1 [y++]
3. t1 + y
4. t1 - x

   比較 t2 >= 0 は、実際の演算が行われないためカウントされません。変数の 2 の補数表現では、符号ビットのみをチェックする必要があります。

5. 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

        

上記の実装では、常に完全な八分円または円のみが描画されます。角度 から角度 までの特定の円弧のみを描画するには、アルゴリズムで最初にこれらの端点のと座標を計算する必要があります。この計算には、三角法または平方根の計算を使用する必要があります (平方根の計算方法を参照)。次に、Bresenham アルゴリズムを完全な八分円または円に対して実行し、必要な間隔内にあるピクセルのみを設定します。この円弧を描画した後、アルゴリズムを途中で終了できます。 ${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle x}$${\displaystyle y}$

角度が傾きとして与えられている場合は、三角法や平方根は必要ありません。 が目的の傾きの間にあることを確認するだけです。 ${\displaystyle y/x}$

同じ概念を使用して、放物線、楕円、またはその他の2次元曲線をラスタライズすることも可能です。^[5]

• 円を描く - シンプルなスキームから効率的なスキームまでを解説した円の描き方に関する記事
• いくつかのプログラミング言語における中点円アルゴリズム