yasuokaの日記： Z80における「手抜き」回転行列

ネットサーフィンしていたところ、このtweetで35年ほど前の悪行がバラされてしまっていたので、当時の記憶を辿りつつ、ざっと書いてみようと思う。

　┌　cosθ -sinθ　┐　　┌　x　┐
　└　sinθ  cosθ　┘　　└　y　┘

画面中心を(0,0)とするxy座標系において、適当な微小角度θで回転をおこないたい。θの値は、まあ何でも良くて、とにかく見た目が「回って」いる雰囲気を出したい。ただ、対象とするCPUがZ80なので、乗算は自分で実装するしかなく、そのあたりの「手抜き」を考える。

微小角度θにおいてcosθは1に近い値なので、ここの実装を簡単にすべく、とりあえずcosθ＝1－2^-kとしてみる。そうすると、sin²θ＝2^(1-k)－2^-2kとなるので、小さい方の項を捨てれば、だいたいsinθ≒2^(1-k)/2。つまり、kが奇数なら実装が簡単となり、たとえばk＝7なら、cosθ＝127/128, sinθ≒1/8となる。

HLレジスタのHレジスタに符号付整数、Lレジスタに256を分母とする分数が入っているとすると、1/8の乗算は単純に

7D      LD A,L
CB 2C  SRA H
1F     RRA
CB 2C  SRA H
1F     RRA
CB 2C  SRA H
1F     RRA
6F      LD L,A

で済む。一方、127/128の乗算は、私(安岡孝一)の記憶が正しければ

7C      LD A,H
2F     CPL
07    RLCA
5F      LD E,A
9F     SBC A,A
57      LD D,A
19     ADD HL,DE

と手を抜いた覚えがある。RLCAのところは、本来はLレジスタのトップビットを反転して持ってくるべきなのだが、それをAレジスタの符号ビットのコピーで誤魔化していて、少しだけ127/128からズレているわけだ。さて、今なら、どう書くかなぁ…。

計算誤差の対処法はありますか？

[annoymouse coward (11178)]

おもしろいですね．

この行列で繰り返しベクトルを変換し続けると
ベクトルは回転するだけじゃなくて
だんだんその長さも変化していくと思います．
画像だと回転しつつ
だんだんその大きさも変化していくとはずです．

この点はなにか対策をとられたのでしょうか？
良い対処方法をご存じでしたら是非おしえてください．

Re:計算誤差の対処法はありますか？

[yasuoka (21275)]

190回で1%ほどベクトルが長くなるのですけど、特に対処してなかったと思うのです。私(安岡孝一)の今日の日記 [srad.jp]にちょっとだけ書いてみたので、よければ御覧ください。

Re:計算誤差の対処法はありますか？

[kurema (42872)]

例えばx,y座標のどちらかが本来の半径を(例えば16/15倍)超えた時に両辺を縮小(15/16倍)すればいいのでは？
数字は適宜調整。
おおざっぱな方法だけど二乗和が不要で、その内x,y軸近くを通過するはず。

あるいは単純に一定回数毎なり定数を掛けるという方法でも対処できる。
何倍大きくなるかはわかっているわけだし。

掛け算ができないからビットシフトで代用ってのはプログラマブルシェーダーでも見かけた記憶があります。
あと、PS3のCellプログラミングでも記事で読んだような。
計算量が段違いなので今でも似たような手法は使える場面はあるはずです。

Re:計算誤差の対処法はありますか？

[annoymouse coward (11178)]

> 例えばx,y座標のどちらかが本来の半径を(例えば16/15倍)超えた時に両辺を縮小(15/16倍)すればいいのでは？

ブレゼンハムのアルゴリズムを使えば整数演算だけで実現できそうですね