DDA(Digital Differential Analyzer)
線分を描画するためのアルゴリズム。
単純ではあるが除算が入ってしまう。ここから除算やfloat演算を取り除いたものがブレセンハム。
dxとdyを比較して、長い方でステップする。
例えばdxの方が長いなら、xを1ずつ増やしてステップする。
yは1以下であり、累積する。
つまりy座標はxに応じて1増えるかそのままかの2択である。
dxとdyを比較して、短い方でステップすると、この単純な2択が使えない。
例えばdxの方が短い場合、
線分は途切れるか、あるいは同一のxに対して複数回yをプロットする羽目になる。
あくまで第一象限の傾き$${m\leq1}$$の範囲内であるならば
$$
\Delta x = x_1-x_0\\
\Delta y = y_1-y_0\\
m=\frac{\Delta y}{\Delta x}
$$
$${x_0}$$から$${x_1}$$まで$${x}$$を1ずつステップしていき、
$${y}$$は$${y=y_0}$$を基準として、以降$${y+=m}$$となる。
つど
$$
(x_i, Round(y_i))
$$
がプロットされる。
ただし線分の進行方向は4つの象限に各2エリア、計8方向あるため、それに応じた処理が必要となる。
以下ChatGPT
DDAアルゴリズム(Digital Differential Analyzer、デジタル差分分析器)は、コンピュータグラフィックスにおいて線分を描画するためのアルゴリズムです。このアルゴリズムは、与えられた二点間に線分を描画する際に、始点から終点にかけての各ピクセル位置を計算することにより、直線を描画します。
DDAアルゴリズムの基本的な考え方は、線分の傾きとステップサイズを利用して、線分上の次の点を計算することです。ここでいうステップとはピクセルが1つ進むことです。傾きが1以下の場合は、水平方向に1ピクセルずつ進みながら垂直方向の位置を調整します。傾きが1より大きい場合は、垂直方向に1ピクセルずつ進みながら水平方向の位置を調整します。このプロセスを繰り返すことにより、線分が描画されます。
始点と終点を決定する:描画したい線分の始点 $${(x_0, y_0)}$$ と終点 $${(x_1, y_1)}$$ を決定します。
差分とステップ数の計算:始点と終点の差$${\Delta x = x_1 - x_0}$$、$${\Delta y = y_1 - y_0}$$を計算し、大きい方の差分を基にステップ数を決定します。コード上ではステップ数分ループを回します。小さい方を基準にすると、ステップ毎に複数の出力を決定する必要が生まれます。複数出力しないなら直線は途切れます。
増分の計算:ステップ数に基づき、水平方向$${\delta x}$$と垂直方向$${\delta y}$$の増分を計算します。これは、$${\Delta x}$$と$${\Delta y}$$をステップ数で割ることにより求めます。どちらかの増分の総和はステップ数と一致し、ステップの進行方向の増分は理論上とういか実装上は整数になり、$${x}$$か$${y}$$について$${+1}$$か$${-1}$$です。ステップに応じる方の増分は1以下で、$${m=\frac{Delta y}{Delta x}}$$です。
4つの進行方向と、それに応じたプラスマイナスの増分により、8つのエリアのどれかに向かって直線が伸びます。線分の描画:始点に対して、計算された増分を加算していき、各ステップでピクセルを描画します。このプロセスをステップ数だけ繰り返します。
DDAアルゴリズムはそのシンプルさから初期のコンピュータグラフィックスで広く使用されましたが、計算誤差の蓄積や浮動小数点演算のコストのため、より効率的なアルゴリズム(例えば、ブレゼンハムのアルゴリズム)が好まれる場合もあります。しかし、DDAアルゴリズムの原理はグラフィックス理論の理解に役立つ重要な基礎となります。
p5.jsの場合
function setup() {
createCanvas(400, 400);
background(220);
// 線分の始点と終点
let x0 = 50, y0 = 50, x1 = 350, y1 = 350;
drawLineDDA(x0, y0, x1, y1);
}
function drawLineDDA(x0, y0, x1, y1) {
// 差分を計算
let dx = x1 - x0;
let dy = y1 - y0;
// ステップ数を決定
let steps = Math.abs(dx) > Math.abs(dy) ? Math.abs(dx) : Math.abs(dy);
// 増分を計算
let xIncrement = dx / steps;
let yIncrement = dy / steps;
// 最初の点をプロット
let x = x0;
let y = y0;
for(let i = 0; i <= steps; i++) {
point(Math.round(x), Math.round(y)); // 点を描画
x += xIncrement; // 次のx座標
y += yIncrement; // 次のy座標
}
}
function draw() {
// draw関数はここでは使用しない
}
この記事が気に入ったらサポートをしてみませんか?