補間について少し書いてみます。間を補うと書いて補間。点と点の間を繋ぐ。私がプログラムを書き始めた頃は、直線描画のハードあるいはコードで作っていた。
ｏ点とｐ点を繋ぐ。
Ｘ方向に３、Ｙ方向に５進む。
-
●
●
●
●
●
●
多分上の図が望まれる。
除算機能のないＣＰＵがまれになった現在では、増分（Ｙ／Ｘ、あるいはＸ／Ｙ）を
求めておいて、累積させれば求まる。
上の例で言うと、増分は３／５（＝Ｙ／Ｘ）となる。
累積の結果１を超えた場合は上と右へ、超えない場合は右のみへ進める。
|
Ｙの累積値 |
Ｘの座標 |
Ｙの座標 |
Ｙの目標値 |
誤差 |
|
|
始点 |
０ |
０ |
０ |
０ |
０ |
|
１回補間後 |
３／５ |
１ |
０ |
３／５ |
－３／５ |
|
２回補間後 |
６／５－＞１／５ |
2 |
１ |
６／５ |
－１／５ |
|
３回補間後 |
４／５ |
3 |
1 |
９／５ |
－４／５ |
|
４回補間後 |
７／５－＞２／５ |
4 |
2 |
１２／５ |
－２／５ |
|
４回補間後 |
５／５－＞０／５ |
５ |
３ |
１５／５ |
０ |
-
●
●
●
●
●
●
となる。
少し変ですね。
これは丸め処理(四捨五入）が入ってないためです。
丸め処理を入れる。
累積結果に１／２を加えて判定すればよい。累積の初期値を１／２とする。
|
Ｙの累積値 |
Ｘの座標 |
Ｙの座標 |
Ｙの目標値 |
誤差 |
|
|
始点 |
１／２（初期値） |
０ |
０ |
０ |
０ |
|
１回補間後 |
１／２＋３／５－＞１／１０＋１ |
１ |
1 |
３／５ |
＋２／５ |
|
２回補間後 |
１／１０＋３／５－＞７／１０＋０ |
2 |
１ |
６／５ |
－１／５ |
|
３回補間後 |
７／１０＋３／５－＞３／１０＋１ |
3 |
2 |
９／５ |
＋１／５ |
|
４回補間後 |
３／１０＋３／５－＞９／１０＋０ |
4 |
2 |
１２／５ |
－２／５ |
|
４回補間後 |
９／１０＋３／５－＞０／１０＋０ |
５ |
３ |
１５／５ |
０ |
-
●
●
●
●
●
●
となる。
さてコードだが、右へｒ、上へｕ進ませる場合（２点間の距離が［ｒ、ｕ］）、増分ｕ／ｒを求める必要がある。
ｒ／ｕの性質上Ｒｅａｌ（ｆｌｏａｔ，ｄｏｕｂｌｅ）を使いたくなるが、整数演算で間に合わす。
補間の距離に依存するが、２の１６乗未満の画素数なら、１６ビットのｕｎｓｉｇｎｅｄで足りる。
増分は１６ビットの下駄を履かせて演算する。
ａ=６５５３６×ｕ／ｒ
こうすると、Ｍｓｂ（最上位ビット）が１／２となる。
同様に初期値１／２は３２７６８となる。
この初期値にａを累積させ、Ｘを１画素進めた時にＹを増加させるかをキャリーで判定する。
しかし、キャリービットを検知する言語でない場合、累積値の減少を判定する。
ｓａｍｐｌｅ ｃｏｄｅ
void LineInterpolation( Cpoint p0, CPoint p1)
{
CPoint d= p1 – p0;
if ( d.x == 0 && d.y == 0 ) { return; }
unsigned short a= 65536 * d.y / d.x; // １６ビットの下駄を履かせて増分算出
unsigned short ds= 0×8000; // 初期値を１／２に
Cpoint p;
for( p= p0; p != p1; p.x++ ) { // Ｘ方向歩進
// ここに補間点ｐに対する処理を入れる。
If ( ds + a < ds ) { p.y++; } // キャリー判定とＹ方向歩進
ds += a; // 誤差の更新
}
}
これはモデルであり、使えるのは
r>=0 && u>=0 && |r|>=|u|、すなわち０～４５度の区間に限る。
老婆心ながら付け加えると、４５～９０度の区間はＸ座標とＹ座標を入れ替えればよい。
更に、－４５度～０度の区間であれば、Ｙの符号を反転しＹ方向の増分を－１とする。
他の区間も同様で、Ｘ，Ｙの入れ替えと増分の符号反転で対応すればよい。
お気づきかもしれないが、このコードでは終点は描画されない。
これは、Ｏｎ ｐｕｒｐｏｓｅ！
ちょっとした意味があります。
次回、円弧補間を書くつもりですのでその時に。