今回はブレゼンハムアルゴリズムで線を引いていきます
ソースここから
import pyxel
class VBresenham:
def __init__(self):
self.l_side = 0
self.s_side = 0
# horizonatial side is longer
self.b_long_hs = True
# Direction (1 or -1)
self.dct_x = 1
self.dct_y = 1
self.counter = 0
self.adder_x = 0
self.adder_y = 0
self.start_x = 0
self.start_y = 0
# start x,y terminus x,y
def setup(self,s_x,s_y,t_x,t_y):
self.b_long_hs = True
self.dct_x = 1
self.dct_y = 1
self.counter = 0
self.adder_x = 0
self.adder_y = 0
self.start_x = s_x
self.start_y = s_y
if (s_x > t_x):
self.l_side = s_x - t_x
self.dct_x = -1
else:
self.l_side = t_x - s_x
if (s_y > t_y):
self.s_side = s_y - t_y
self.dct_y = -1
else:
self.s_side = t_y - s_y
if (self.s_side > self.l_side):
# swap
self.s_side,self.l_side = self.l_side,self.s_side
self.b_long_hs = False
self.l_side += 1
self.s_side += 1
return self.l_side
def step(self):
self.counter += self.s_side
i = self.counter - self.l_side
ret_x = self.start_x+self.adder_x
ret_y = self.start_y+self.adder_y
if self.b_long_hs:
self.adder_x += self.dct_x
if i >= 0:
self.counter = i
self.adder_y += self.dct_y
else:
self.adder_y += self.dct_y
if i >= 0:
self.counter = i
self.adder_x += self.dct_x
return ret_x,ret_y
class App:
def __init__(self):
# 画面サイズ 160x120 で初期化
pyxel.init(160, 120, title="Line")
self.vbre = VBresenham()
pyxel.run(self.update, self.draw)
def update(self):
pass
def draw(self):
# 画面を黒（色番号0）でクリア
pyxel.cls(0)
reg = self.vbre.setup(80,60,pyxel.mouse_x,pyxel.mouse_y)
for i in range (reg):
x,y = self.vbre.step()
pyxel.pset(x,y,6)
App()
ソースここまで
※８／２９ ブレゼンハムのクラスを流用した際に暴走するので修正しました
マウスの動きに合わせて線を引くプログラムです。
…今回初めて複数の戻り値を持つ関数や、変数のスワップを使ったのですが、Python って便利な言語なんですね…言語の進化を感じます。
解説
- setup の最後でなぜ長辺と短辺に１を加算しているのか？
self.l_side += 1
self.s_side += 1
の部分ですね。コレ、前回もやっていたのですが、解説してませんでした…
前回の図を使うとこんな感じ…
ざっくり言うと、計算は「格子」の座標系、描画は「格子の中」としているから。
実は加算しなくても動作するのですが、どうしてそんな事をしているのか？
例えば、始点と終点が同一点だったら？短辺の値が同一（＝短辺が０だったら）？
これが３次元ポリゴンであったなら理屈上ポリゴンは厚みが無いので「描画しない」が正解になりますが、２次元の描画の場合は描画を行います。
つまり、最低限の描画を保障する為に加算しています。…あと、この方が描画が綺麗だったりするんですよね…。
- アセンブラで書くなら
前回に引き続き、setup 関数でループ回数を取得し、 step 関数をループ回数分実行する処理になっています。
…と言う事は当然中に書かれている
if self.b_long_hs:
の分岐処理はループ回数実行されますが…毎回結果は同じです。
これを毎回分岐処理するといろいろ勿体ないので、アセンブラで書く場合はジャンプ先を上書きしたりします。
Ｃ言語で書くなら
goto vs_longer
// Ｘ軸の方が長かった場合の処理
～
goto end
// Ｙ軸の方が長かった場合の処理
vs_longer:
～
// 以後最終処理
end:
のような記述をして、状況に応じて初期化時に goto vs_longer を書いたり消したりします。
アセンブラで変数として使用するレジスターは有限な上に数が少ないので使わないで済むならその方が良いですし、分岐処理が減ると数ステップ（クロック）処理が早くなります。線を引く際のドット数分全てにこの高速化がかかって来るのでバカにできません。
…まあ、現代のＣＰＵパワーでこんな事を気にしないといけない状況は皆無だと思いますが。
同様に
self.dct_x
self.dct_y
この二つの変数、ベクトルのＸとＹがどちらに進むのかを１、もしくは－１で保存して、step 関数内で加算しているのですが…
ほぼ全てのＣＰＵには１加算する Inc 命令と １減算する Dec 命令が存在し、大抵高速に動作します。
なので
self.adder_y += self.dct_y
や
self.adder_x += self.dct_x
にあたる処理部分を初期化時に Inc や Dec に書き換えればレジスターも節約できるし、処理も高速化できます。
ただし…
これらのプログラム自身が自分のプログラムを上書きする…と言う動作は昔のプログラムでは有効でしたが、現代ではセキュリティの関係からメモリを書き換え禁止で保護して不可能になっているかもしれません。
そもそも、プログラム実行中にプログラムが書き換わるのでデバッグのやり辛さが尋常ではありません。
それでも、これらの処理で高速化を積み重ねる事が有効だった時代があった（今でも有効ですが）のですよ…遥か昔のお話なんですけどね…。
今回直線のプログラムを書きましたし、次回は回転を構成するもう一つのパーツ、三角関数テーブルを作って線の回転を作ってみます。
