パスワードを忘れた? アカウント作成
13742732 journal
日記

yasuokaの日記: Z80における「手抜き」回転行列のさらなる改良 2

日記 by yasuoka

昨日の日記の読者から、Alan W. Paethの「A Fast Algorithm for General Raster Rotation」(Proceedings Graphics Interface '86 / Vision Interface '86 (May 1986), pp.77-81)という論文をお教えいただいた。以下の3つの三角行列の積で回転行列をシミュレートする、という優れモノで、かなり速い上に誤差が小さい。

 ┌ 1 a ┐┌ 1 0 ┐┌ 1 a ┐ _ ┌ cosθ -sinθ ┐
 └ 0 1 ┘└ b 1 ┘└ 0 1 ┘  ̄ └ sinθ  cosθ ┘

式を解くと、b=sinθ, a=(cosθ-1)/sinθ=-tan(θ/2)である。ここで、三角行列を使うメリットは、aとbが多少不正確な値でも、行列式が常に1になるという点にある。たとえば、cosθ≒127/128, sinθ≒1/8に対しては、a=-1/16, b=1/8すなわち

 ┌ 1 -1/16 ┐┌  1  0 ┐┌ 1 -1/16 ┐ _ ┌ 127/128 -255/2048 ┐
 └ 0   1   ┘└ 1/8 1 ┘└ 0   1   ┘  ̄ └   1/8    127/128  ┘

という「回転行列」を計算することになるので、少し歪んでいるものの、確かに行列式が1となっている。

このPaethのアルゴリズムを元に、私(安岡孝一)の一昨日のプログラムを改良してみよう。対象とするCPUがZ80なので、IXレジスタにx座標(上位8ビットが符号付整数、下位8ビットが256を分母とする分数)を、IYレジスタにy座標を入れることにする。

FD E5   PUSH IY
21 01 00  LD HL,1
39       ADD HL,SP
7E        LD A,(HL)
07      RLCA
9F       SBC A,A
ED 67    RRD
2B       DEC HL
ED 67    RRD
EB        EX DE,HL
C1       POP BC
DD E5   PUSH IX
E1       POP HL
B7        OR A
ED 42    SBC HL,BC
44        LD B,H
7D        LD A,L
CB 28    SRA B
1F       RRA
CB 28    SRA B
1F       RRA
CB 28    SRA B
1F       RRA
4F        LD C,A
FD 09    ADD IY,BC
FD E5   PUSH IY
EB        EX DE,HL
23       INC HL
7E        LD A,(HL)
07      RLCA
9F       SBC A,A
ED 67    RRD
2B       DEC HL
ED 67    RRD
EB        EX DE,HL
C1       POP BC
B7        OR A
ED 42    SBC HL,BC
E5      PUSH HL
DD E1    POP IX
C9       RET

(100,0)すなわちIX=6400H, IY=0000Hから始めると、このプログラムは65536回よびだした後でもIX=C3C9H, IY=B010Hで、0.08%も誤差がない。うーむ、ここまで凄いとは。でも、当時の私は、この論文を知らなかったというか、論文まだ発表されてなかったんだよなぁ…。

この議論は、yasuoka (21275)によって「 ログインユーザだけ」として作成されている。 ログインしてから来てね。
typodupeerror

皆さんもソースを読むときに、行と行の間を読むような気持ちで見てほしい -- あるハッカー

読み込み中...