気まぐれな戯れ言 バックナンバー9


気まぐれな戯れ言バックナンバーです。全体の一覧はこちら

04/05/28 多角形の交差判定編−2
04/05/18 多角形の交差判定編−1
04/05/06 最適なアルゴリズムの苦悩編
04/03/31 CodecをつかったMP3のデコード・再生編−3

04/05/28 多角形の交差判定編−2(点の内外判定) [★★◎◎◎]
実際に動くプログラムは、その46−多角形交差判定サンプルにあります。


前回説明不足だった点もあるので、「直線」「線分」「半直線」の定義をあらかじめ確認しておきます。
(特に、「直線」と「線分」は使い分けてるので注意)



「直線」は無限に続きます。
「直線AB」はABを通り無限に(AやBの外側も)続きます。
「半直線」は1つだけ端があり、片方は無限に続きます。
「線分」は2つ端があり、有限です。
「線分AB」はAとBの間だけを指します。

「直線AB」と「線分AB」はABの外側も含むか含まないかが異なるので注意する必要があります。



前回は多角形同士の交差判定の概要と、線分同士の交差判定を行いました。
残るは、「小さい方(A)が完全に大きい方(B)に含まれる(A⊆B) → Aの各頂点がBに含まれる」の判定のみです。
実際はAの各頂点がBに含まれることをチェックしなくても1つでOKです。
1つの頂点が含まれてるなら他も全部Bに含まれてるはずなので。
(もしBに含まれないAの頂点がある場合、その頂点と内部の頂点を結ぶ線分がBの辺と交差するため、辺の交差判定の段階でチェック可能)
同様に、1つが外にあると全部外にあることになります。

まぁどちらにしても「ある点が多角形に含まれるかどうか?」を判定する必要があります。
ここでは、計算の手間と利用可能な条件の異なる3つの方法を紹介します。
先に3つの手法の違いを表にしときます。

手法の概要計算速度利用可能な条件
手法1各辺の内側にあることを判定 高速凸多角形のみ
手法2点を通る半直線と境界の交差判定 中速(点の配置によって低速)特になし
手法3多角形の点と成す角の和の判定 低速特になし

各辺の内側判定による内外判定

前回の所で、外積を用いて直線の左側・右側を判定する手法を紹介しました。
これを利用して点の内外判定を行います。
例えば、下のような例を考えるとわかりやすいかと思います。


左の三角形の辺を、AB、BC、CAと右回りになるように辺を見ていきます。
三角形の中の点Pは、各辺の常に右側にあることがわかります。
点QはBC、CAの右側になってはいますが、ABの左側にあります。
逆にAC、CB、BAと左向きに回ったときは点Pは常に左側にあります。

要は、「辺をぐるっと回った時、常に点が同じ側にある→多角形の内側にある」と言うことが出来ます。
左の図の例では、点Pは右回りに辺を回った時常に右側にあります。


右回りに回った時に常に左側にある、と言う事はありえません。
上の図を見て、右回りに回った時常に左側に来るという領域は存在しない事がわかります。
そのため、実際は辺を左回りに辿ったか右回りに辿ったかは必要ありません。
常に同じ側にある、と言うことだけが重要です。

前回の外積を用いた左右判定を用いると、上の例では、(P-A)×(B-A)と(P-B)×(C-B)と(P-C)×(A-C)の符号が一致すればいい事になります。
0の場合は直線状にあると言うことなのでこれもOKです。
三角形でなく、四角形、五角形・・・となったときも判定する数が増えるだけです。

この手法は、引き算・掛け算・符号の判定だけで済むので非常に簡単です。
ただ、問題点として凸な図形にしか使えない点があります。


左の例では、太くなっている緑の辺の左右判定をした時、辺の両側に図形が存在します。
凸な場合は、常に同じ側で判定できましたが、凹な図形ではこの手法は使えません。
この場合は、図形をいくつかの凸な図形に分解するか、他の手法を使う必要があります。
この手法は他の手法に比べかなり計算が楽なので、凸な図形ならできるだけこの手法で行きたいところです。



境界との交差回数による内外判定

突然変な話ですが、団子に串を刺すことを考えてみます。
このとき各団子に対して串は「団子に入る・出る・入る・出る・・・」という順で刺さっていきます。
これと同じように、「点から半直線を伸ばし、多角形の境界との交差回数を調べる」という手法で判定が行えます。



左側の図では「の」の字の近辺にある点A、Bが「の」の内側にあるかどうかを判定します。
A・Bの左側から串を刺したと想定します。(すなわち、点Aから左側に伸びた半直線と「の」の境界の交差回数を調べる。点Bから伸びる半直線についても同様。)
Aに到達する前には2回境界と交差します。Bの場合は5回ですね。
要は、「境界と奇数回交差しているならば内側」といえます。

「の」の例では求める点の左側での交差回数を調べましたが、別に右でも縦でも斜めでも構いません。
右の「9」の近辺にある点Cの例では上は4回、右と下は2回、左は0回交差していますが、いずれも偶数回=外側と判定されます。

上の図では「の」「9」と曲線の例を用いましたが、多角形の場合では多角形の各辺が(求めたい点から伸ばした)半直線と交差する回数を求める事になります。
ここで、別に斜めに延ばした線と各辺の交差判定をしても言いのですが、まぁ上下左右のいずれかだと判定がラクでしょう。

例えば、辺ABが求める点Pの左側に引いた半直線と交差するかどうかは以下の判定を順に行う事で簡単に求める事が出来ます。

  • 点A及びBのY座標が共にPのY座標より大きい、または小さい場合は明らかに交差しない。(辺はPの上、もしくは下側に来る)
  • 点A及びBのX座標が共にPのX座標より大きい、または小さい場合は明らかに交差しない。(辺はPの右側)
  • (上記2つの条件をクリアした段階で、AとBのY座標は片方がPより小さく、片方は大きくなっている。また、少なくとも片方のX座標はPより小さい。)
  • 点A及びBのX座標が両方ともPのX座標より小さいなら明らかに交差する。
  • 点A及びBのX座標が片方Pより小さく、片方Pより大きいなら実際にPから左に伸ばした半直線との交点を求める必要がある。(Y座標の内分で簡単に求める事ができる)

文字で書くとわかりにくいですが、図を書いてみたりプログラム上で不等式を重い浮かべるとそれほどややこしい話ではありません。
線分(辺)と半直線(点まで刺した串)の交差判定だけだと簡単で済むのですが、残念ながらそうは行かない場合があります。
例えば、線分の両端のうち片方が半直線に重なったりすると下の図のようなことが発生します。

横方向の薄い灰色の線が半直線、太い黒線が多角形の一部と考えてください。(4つのパターンが書いてある図です)



まず、左の2つはちょうど半直線と多角形の点Qが重なった場合です。
この例では、点Qの近辺で多角形の境界と半直線が交差しているか判断する事ができません。
次の点RがPと同じ側にあるか反対側にあるかを判定する必要があります。
一番左側のように点Pが上にある時、Qの次の点Rも上にあると、半直線と多角形は交差していないと考えられます。
2番目の例のようにRが下に来た場合は交差したと判定できます。

右の2つは半直線と辺QRが重なった場合です。
この場合は、PQが交差するか判定する場合Rまで見てもまだ交差するかしないか判定できません。
最終的に半直線から出る点Sまで調べる必要があります。

今回は、連続した辺が一直線に並んでないと仮定しています。(QRとRSは一直線に並ばない)
もし一直線に並ぶ可能性がある場合、R、Sと座標を見てもまだ交差するかどうかわからないので、さらに先の点を見る必要があります。
(さらに、当然QRが求める点の左側にあることを判定する必要があります。)
なお、「内外を求める点が辺QRの中に入っちゃったらどうするの?」という事が考えられますが、この場合は既に「辺同士の交差判定」の段階で判定されるので大丈夫です。

この手法は計算はそれほど大変ではないですが、このように図形の形によって多少余分な処理が入ります。
この手法はドーナツ型みたいに穴の空いた形でも利用可能です。

角度の和による内外判定



上の図で、調べたい点Pから多角形の点ABCDを順に見ていくとします。
この場合、A・B・C・D・Aと順に右回りに1周していることがわかると思います。

右の図では点Qに対して同じ事をやっていますが、こちらはA・B・Cと右に行った後、Dで左に戻り、また最後Aに戻る時に右に行ってます。
右向いて左向いて戻ってるだけで1周はしていません。

つまり、求めたい点Pに対して角度を∠APB+∠BPC+∠CPD+・・・と足した場合、内部にあれば1周するので360度(もしくは-360度)となり、外部にあれば0度になります。
(角度は符号付き、すなわち左回りと右回りは正負が異なると考える)

この手法は凸な図形でなくても使えるため、アルゴリズムとしてはわかりやすいです。
(凹な図形の場合、右回りの途中で少し左回りに戻ったりする事があるが、全体としては1周する)

もし点Pが辺AB上にのっていたりすると、∠APBが+180度なのか-180度なのか面倒なことが起こります。
しかしこの場合は、辺同士の交差判定の段階で交差しているとみなされるので、この処理を行う前に交差と判断されるので考える必要がありません。
(点Pが多角形の頂点に重なる場合も同様)

さて、あとは点A・B・Pがあったときに∠APBを符号も考えて求める方法がわかればいいということになります。
角度を求めるにはVBからはATan関数を使うしかないわけですが、そのためにはTan(∠APB)を求める必要があります。

その前に、VBのATan関数を拡張しておきます。
ATan関数はTanの値だけで判断するので、例えばTanθ=1となる場合でもθ=45度(第1象限)か225度(もしくは-135度、第3象限)か判断できない場合があります。
そのため、それも含めて値を返すATan2関数を定義しておきます。
定数0.001とか使ってるあたり適当ですが。
(C言語やJavaだと標準ライブラリでatan2があるんですけどね・・・)

Function Atan2(ByVal y As Double, ByVal x As Double) As Double
'-PI〜PIの間の値を返す
Dim t As Double

If Abs(x) > 0.001 Then
  t = Atn(y / x)
  If x < 0 Then t = t + PI
  If t > PI Then t = t - 2 * PI

Else
  If y > 0 Then t = PI / 2
  If y < 0 Then t = -PI / 2
End If

上の関数はyとxの値を入力するので第何象限にあるかも判断してくれます。
で、このyとxに対応する値を点A・B・Pからどう得るかという事になります。
このATan2を見ると、結局ATan2に入力しているのは、y=C sinθ、x=C cosθと結局sinとcosの値を入力しているに過ぎません。

で、sinとcosをどう求めるか・・・ですが、これはここまで出てきた話で解決できます。
ベクトルの外積でsin、内積でcosを求められます。
まとめると以下のようになります。


A' = A - P
B' = B - P
cos = A' ・ B' (内積)
sin = A' × B' (外積)

∠APB = ATan2(sin,cos)

内積や外積はいずれも直接cosやsinを求めるわけではなく、ベクトルの長さ|A'||B'|をかけた値が得られます。
ただ、ATan2でTanの値を一時的に計算する際に結局tan = sin / cosの計算をするので|A'||B'|は結局上下で打ち消し会うのでATan2に入れる前にベクトルの長さは考慮する必要はありません。

この角度計算を∠APB、∠BPC、∠CPD、・・・と行って足して行けば求められます。
この手法は図形が凹でも使えるし、上の手法みたく図形の形に依存しないのですが、ATanを使う事もあって結構計算量がかかるのが難点です。

また、この手法はそのままでは穴の空いた形には適用できません。
例えばドーナツ型の場合は外側の輪郭と内側の輪郭それぞれについて計算を行い、「外側の輪郭の内側で、かつ内側の輪郭の外側なら図形の内部」と判定する事になります。
プログラム側が「2つの輪郭からなる図形である」ということを知っていなければ行けません。

まとめ

前回は辺の交差判定、今回は点の内外判定についてまとめてみました。

辺の交差にしても点の内外判定にしても両方図形の点の数の積に比例した時間がかかります。
複雑な図形を直接判定するよりは、簡単な図形いくつかに分割した方がいいかも。
サンプルの方では一番最後の手法で実装しています。


今回は2次元での交差を扱いましたが、(具体的なアルゴリズムはともかく)アプローチは3次元(もしくはそれ以上)でも適用できます。
まず、辺同士の交差判定は言いかえれば境界同士が交差するかどうかの判定なので、3次元では面同士の交差判定をする事に相当します。
点の内外判定においても、
  • 各点が各辺の内側にある→各点が各面の内側にある(ベクトル演算で計算可能)
  • 点まで串を刺して辺との交差回数を計算→面との交差回数を計算
  • 点を順に見てったとき1周するか計算→立体角で全方位分になるか(これはめんどうですね)
と考えることができます。

04/05/18 多角形の交差判定編−1(概要と辺の交差判定) [★★◎◎◎]
実際に動くプログラムは、その46−多角形交差判定サンプルにあります。

通常、2Dのゲームなどでは衝突判定を長方形同士や円・楕円同士で行う事が多いようです。
これらは衝突判定が非常に単純であり、その分高速であることを考えると有効な手法であると言えます。
ただ、大きいキャラなどを出現させる場合、衝突判定などを長方形や楕円だけで行うのはあまりに大雑把過ぎる事になります。
そこで、衝突判定を多角形を使って行う事を考えてみます。

ここでは、物理シミュレーションの衝突判定のように複雑なものではなく、単に多角形同士が交差している(共通部分を持つ)かどうかを判定するアルゴリズムを考えてみます。

(・・・とアルゴリズムとかを考えていたら隠れ線表示(授業のレジュメっぽいです)というサイトが見つかりました。まぁこちらは具体的な交点を求めるので、その分計算量が増える部分もあります。とりあえず基本的な考えかたは一緒なので安心)
まずは、多角形が交差している場合には、どのような条件を満たしているか考えてみます。
ぱっと考えて一番最初に思いつくのは、「片方の多角形のいずれかの頂点がもう片方の多角形に含まれる」あたりかと思います。
しかしこれは少し考えるとうまく行かないことがわかります。

 

左の図は交差はしていますが、各頂点はお互いの図形には含まれていません。
ただ、この図を見ていると、気付くのが、「交差するんなら辺同士が交わるんじゃない?」ということです。
図で言うと緑の小さな○が付いてるのが辺同士の交点ですが、これが1つでもあれば交差していると考えられそうです。

逆に右の図では辺の交わりでは判定できません。
ただ、「片方の多角形のいずれかの頂点がもう片方の多角形に含まれる」の考えを適用してみると、中の四角形の頂点はいずれも大きな三角形に含まれています。

まとめてみると、大体以下の感じで判定できそうです。
  • 互いに含まれない領域がある(A−B≠Φ、B−A≠Φ) → AとBの各辺で交わるものがある
  • 小さい方(A)が完全に大きい方(B)に含まれる(A⊆B) → Aの各頂点がBに含まれる
上記のことを考えた上で、「辺の交差判定」「点の内外(包含)判定」を行います。

先に断っておくこととして、「境界同士が重なっている場合は交差・包含されていると判定する」とします。
(不等号で表すと、 < じゃなくて ≦ のように境界自体も多角形の一部であると考える)
境界そのものを多角形の一部と考えない場合、以下のような図形で処理が面倒になります。



左の2つの図ではともに明るい緑色の部分で辺が重なっています。
ここで、境界が多角形の一部であるとすると、辺が重なる→辺が交差すると考えられるので、どちらも多角形が交差していると考えられます。
境界は多角形の一部でないとすると、また別の手法で上の例と下の例を判断する事になり、処理が煩雑になります。

右の図では、内側の図形の各頂点が外側の図形の辺に重なっています。
この場合も境界を多角形の一部でないとすると点の内外判定が行えず、別の手法で判定する事になります。(例えば、その点を通る辺の内外判定をするなど)

これらの手間を省くため、境界同士が重なった場合はその時点で「辺が交差している」「点が包含されている」と判断する事にします。


bounding box

ちょっとわき道にそれますが、先にbounding boxについて説明しておきます。
名前だけ聞くと大げさですが、中身は単純です。(なお、同じ手法でも名前は色々あるようなのでここでは一例としてbounding boxという名称を使います。)

実際は複雑な多角形の交差判定は結構計算に手間がかかります。
これを毎回まともにやっていては非常に無駄が多くなります。



上の図を見るとわかるかもしれませんが、要は対象となる図形を簡単な図形で囲い、まずその図形同士で衝突判定をするという手法です。
例えば、左側は2つの多角形がありますが、それぞれを囲う長方形は明らかに交差しないですし、その交差判定は非常に簡単です。
この段階で細かい交差判定を止めることができ、かなり計算量の削減に役立ちます。

右側のように対象となる図形が多角形でなくても適用できます。
右側は2線分の交差判定を行いたい場合ですが、とりあえず長方形が交差しているのでこの場合はもっとしっかり計算する必要がありそうです。

この囲う図形をbounding boxと言います。(上にも書いた通り色んな言いかたがあると思います)
囲う図形は別に長方形である必要はなく、円や楕円でもOKですし、3次元なら直方体や楕円体を使うのもOKです。
とにかく大雑把な判定で計算量を減らすのが目的です。

辺の交差判定

辺の交差判定を行うには、両多角形から1つずつ辺を選び、それを交差しているかどうか判定すると言うのを全辺について行います。
計算量としては(片方の図形の辺の数)×(もう片方の図形の辺の数)となります。
交差判定は乗算がいくつか絡んで面倒なので、先にbounding boxの交差判定で大雑把に判定しておきましょう。

では、平面上での2線分の交差判定をしてみます。
先ほどの隠れ線表示のサイトでは具体的に交点を求め、それが両線分上にあることを求めています。
この作業は交点が欲しい時には必要ですが、割り算が必要になるなど、多少面倒です。
単に交差してるかどうかがわかればいい時はもっと簡単に行う事ができます。

線分ABとCDが交差してるかどうかを調べる場合、以下の様に考える事が出来ます。
「ABとCDが交差するなら、CDは線分ABを通るはずだ(もちろんその逆も)」
言いかえると、以下の様に表現できます。



「AからBを見た時、CとDはどちらかが左側、どちらかが右側にくる」(A・BをC・Dと入れ替えてもOK)
左の例では、AからBを見た時、Cは左側、Dは右側に来ています。
同様に、CからDを見た時、Bは左側、Aは右側に来ています。
右の例では、確かにCDはABをまたいでいますが、ABはCDをまたいでいません。
CからDを見た時、AもBも右側にあります。

で、「AからBを見た時、CとDはどちらかが左側、どちらかが右側にくる」をどう求めるかと言う話になります。
能書きはいいから必要な計算式だけ見たいというかたはこちら。
∠CABと∠DABを求める必要がありそうですが、もっと簡単な方法があります。
sinはθ=0〜180°までなら正の値を返し、-180°〜0までなら負の値を返します。(まぁ0もあるがとりあえずおいておいて)
これは、いわゆる数学のXY座標(コンピュータとはY軸の向きが上下逆なのに注意)で言うと、原点からX軸の正の向きを見た時、sinは左側(赤い部分)なら正、右側(青い部分)なら負の値を返すと言えます。



これを応用すると、具体的に∠CABと∠DABを求める必要はなく、sin(∠CAB)とsin(∠DAB)を求めればいい事になります。
これらの値が片方が正で片方が負ならCとDは直線(線分ではない)ABをまたいでいると言えます。

sinの求めかたですが、これはベクトルの外積を用いて求める事が出来ます。
ベクトルの外積は本来3次元空間上で定義されるものですが、ここではz=0であると考える事で次の様に考える事が出来ます。
ベクトルV・Wの外積V×WとVおよびWの成す角θについて次の式が成り立ちます。(|V|はベクトルVの長さ)
本当はベクトルの外積もベクトルで表現されますが、ここではその長さについての関係を表しているので| |で囲んでいます。

|V×W| = V.x*W.y - V.y*W.x = |V||W|sinθ

sinの値を取りたい場合|V|、|W|が邪魔なので|V|や|W|で割るか、あらかじめV、Wの長さが1になるようにベクトルを正規化(長さを1にする事、x及びyの値をベクトルの長さ√(x^2+y^2)で割ればよい)する必要があります。
ただ、今回の場合は欲しいのはsinの正負だけです。
|V|や|W|はベクトルの長さなのでどのみち0以上なので、結局(V.x*W.y - V.y*W.x)の符号を直接利用する事が出来ます。



最終的な計算方法

さて、これをCDがABをまたぐかどうかの計算に利用すると、以下の計算を行う事になります。

「((C-A)×(B-A)) ・ ((D-A)×(B-A)) が 0以下ならCDがABをまたぐ」(「・」は普通の乗算)
(もちろん、ABがCDをまたがるかどうかの判定も同様に((A-C)×(D-C)) ・ ((B-C)×(D-C))の符号をチェックすることで行う必要がある)

式の解説をしていきます。



((C-A)×(B-A))はAからBへのベクトルとAからCへのベクトルの外積を取っています。
同様に((D-A)×(B-A))はAからBへのベクトルとAからDへのベクトルの外積を取っています。
この2つの積が片方正、片方負になればいいわけですが、掛け算して負になればどっちかが正、もう片方が負の判定を一度に行う事が出来ます。
VB風に書けばこんな感じでしょう。(「'」なんて使っちゃ行けないんだけど。)
C'.x = C.x - A.x
C'.y = C.y - A.y
B'.x = B.x - A.x
B'.y = B.y - A.y
D'.x = D.x - A.x
D'.y = D.y - A.y

intersect =  ( (C'.x * B'.y - C'.y * B'.x) * (D'.x * B'.y - D'.y * B'.x) <= 0)

例外処理

計算する式は((C-A)×(B-A)) ・ ((D-A)×(B-A))ですが、(C-A)×(B-A)および(D-A)×(B-A)がどちらも0でない時は問題ありません。
両方正か両方負ならまたがず、符号が異なればまたがることになります。
ただし、上の式では「< 0」ではなく「<= 0」と0も含んでいます。

この掛け算が0になるには(C-A)×(B-A)および(D-A)×(B-A)のどちらか及び片方が0になる必要があります。
この値が0と言うのは何を表すかを考えてみます。
(なお、多角形の辺を取ってくるという前提なので点Aと点Bは重ならない、すなわちB-Aは0にならないと仮定します。)

「(C-A)×(B-A)=0」となる条件は、以下のいずれかになります。(B-Aは上記の通り0にならない)
  • C-A=0、すなわちCとAが重なってる
  • Cが直線ABの左右どちら側でもない、すなわち点Cは直線AB上にある
    (外積の計算ではsinθが含まれますが、sinθ=0となるのはθ=0度か180度、すなわちベクトルABとACの成す角が0度か180度と言うことはCがAB上に乗っていると考えられる)
ここで、前者の条件「CとAが重なっている」は後者の「CがAB上にある」に含まれます。
結局「(C-A)×(B-A)=0」と「CがAB上にある」が同じ意味になります。
ここで、CがAB上にあっても(D-A)×(B-A)≠0、すなわちDはAB上にない、下の図の左側みたいな状態ならまぁ交差してると考えていいでしょう。



さて、(C-A)×(B-A)=0 かつ (D-A)×(B-A)=0と両方0の時を考えてみます。
これはCもDもAB上、すなわちABとCDが同一直線上にあることになります。
この場合、必ずしもABとCDが重なるとは限りません。
上の図の右側では、上の例では確かにABとCDが重なっています。
ただし、下の例では重なっていませんが、計算の値は0となってしまって重なっていると判断されてしまいます。

これを解決するには、既に図に書いてありますが、bounding boxの重なりを判定すればOKです。
と言うか、ここに書いた通り、そもそも外積の計算の前にbounding boxが交差しなければ線分同士も交差しないと判定されます。
おかげでここで再度bounding boxの交差判定をする必要がなくなりますね。

結局、bounding boxの交差判定を通過している以上は、計算値が0であれば交差すると判定する事ができます。


まとめ

というわけで、外積の計算を用いた辺の交差判定をしてみました。
この計算ではbounding boxの交差判定及び外積の符号判定であるため、大小比較・引き算・掛け算だけで交差判定を行う事が出来ました。
実際に交点を求めたい場合は、隠れ線表示のところにあるように連立方程式を解く必要があります。
これは割り算が関わるため0で割らないように気をつける必要があるし、そもそも計算量も多くなります。
必要な時だけ交点を求めればよいでしょう。


長くなってしまったので分割。
次回は点の内外判定のための計算量・条件の異なる3つの手法について触れて行きたいと思います。

04/05/06 最適なアルゴリズムの苦悩編(テーブルアート)[★★◎◎◎◎]
実際に作成したソフトはミニミニソフトその52にあります。

最近ちらほらテーブルアートと言うものを聞くようになりました。
テーブルアートとは何かというと、<TABLE>タグを用いて絵を表現しようというものです。

例えば、下の絵は16x16の絵を5倍に拡大したものですが、ソースを見ると<TABLE>やら<TD>やらで構成されています。

↓みたいな感じ。
<table width="80" height="80" border=0 cellpadding=0 cellspacing=0>
<tr><td bgcolor=#C0C0C0 colspan=14></td><td bgcolor=#C0C0C0 colspan=2 rowspan=9></td></tr>
<tr><td bgcolor=#C0C0C0 colspan=5></td><td bgcolor=#000000 colspan=4></td><td bgcolor=#C0C0C0 colspan=5></td></tr>
<tr><td bgcolor=#C0C0C0></td><td bgcolor=#000000 colspan=5></td><td bgcolor=#FFFF00 colspan=2></td><td bgcolor=#000000 colspan=5></td><td bgcolor=#C0C0C0></td></tr>
<tr><td bgcolor=#000000 rowspan=10></td><td bgcolor=#808000></td><td bgcolor=#808080 rowspan=3></td><td bgcolor=#808000></td><td bgcolor=#000000></td><td bgcolor=#FFFF00></td><td bgcolor=#000000 colspan=2></td><td bgcolor=#FFFF00></td><td bgcolor=#000000></td><td bgcolor=#808080></td><td bgcolor=#808000></td><td bgcolor=#808080></td><td bgcolor=#000000 rowspan=5></td></tr>

(中略)

<tr><td bgcolor=#C0C0C0></td><td bgcolor=#000000 colspan=5></td><td bgcolor=#FFFFFF colspan=8></td></tr>
<tr><td bgcolor=#C0C0C0 colspan=6></td><td bgcolor=#000080 colspan=10></td></tr>
<tr><td bgcolor=#C0C0C0 colspan=16></td></tr>
</table>


んで。
プログラムを組める人はこれを見ると自動で変換するプログラムを組みたくなるでしょう(^^;

・・・と同じことを考える人は多いらしく、BMPやJPEGをHTMLに変換するプログラムはいくつか存在します。
(というか、GIMPまでHTML出力をしているとは(^^;)

ここで問題となるのは、生成されるHTMLのサイズです。
例えばフルカラーのBMPだと1ピクセルに4バイトで済むわけですが、HTMLに変換すると「"」を省略しても
<TD BGCOLOR=RRGGBB></TD>
24バイトにもなってしまいます。
単なるフルカラーBMPでもサイズがでかいのに、さらに<TR>とかもつくことを考えるとその6倍以上になることになります。
(色によっては000000→black、0000FF→blueとかで多少文字数が減らせますが・・・)

ここで、サイズを減らすためには、TDタグで利用できるcolspan、rowspanを用いることが考えられます。
(colspan、rowspanについてはとほほのWWW入門(TABLEタグ)等を参照するといいでしょう)
colspan、rowspanを使うとセルを複数連結させることが出来ます。
これにより、同じ色のピクセルが連続した場合は1つのTDタグでまとめて記述し、サイズを減らそうという考えです。

例えば、同じ色が3ピクセル続いた場合は
<TD BGCOLOR=RRGGBB colspan=3></TD>
で34バイトで3ピクセル表せることになります。

上の図は赤でborderを入れてみると、実は下のように分割されています。
ボード部はよく見ると市松模様のように色が変化しているので、それぞれ1ピクセル=1セルになっています。
一方ボードの手前の書類(?)の中の白い部分の方や、全体の右上のあたりはいくつか連結した長方形からなっています。


で、このように長方形で分割するのは難しいのかどうなのか。

検索して見つけたいくつかのテーブルアート生成プログラムを実行してみると、colspanを使うものはありましたが、両方を使うものはありませんでした。(多くはcolspanもrowspanも使わず1セル=1ピクセル)
通常画像をHTMLに変換しようとする場合、TABLEタグは上から下に行単位でTRタグで記述し、各行は左から右にTDタグで記述して行くので、その通りに画像も走査していくことになります。
なので、各行で左から右に調べて行く際、数ピクセル同じ色が続けばその部分をまとめてcolspanを使って1つのセルで表せます。
ただ、rowspanも用いて縦方向の連結も行おうとすると、途中で別の行を走査したりするなどプログラム上の手間もかかるし、変換の処理にも時間がかかるようになります。
そのためかどうなのか、横方向連結を使ったものはあっても、縦方向連結も用いた長方形分割をしているものはありませんでした。


というわけで、じゃあ長方形で分割してみようということで考えてみます。

少し考えてみると、常に最適な分割(=少ない長方形で分割)するのは非常に難しいことが分かります。
手順としては、以下のような感じになるのではないでしょうか。

  1. 適当な長方形を選ぶ
  2. 選んだ長方形の分を図形から削除
  3. まだ図形が残ってたら1に戻る。全部終わってたら↓に進む
  4. 分割した長方形の数が最小かどうかチェック。リセットして別の選びかたでまた1から繰り返し。

って文章で書くと非常に簡単そうですが、そうも行かないです。
例えば、以下のような4x4の図形があり、とりあえず黒い部分を長方形で分割するとします。

↑のような図形から、まず1つ長方形を取り出すには、どんな取りかたが考えられるか。
colspanやrowspanは右何マス分、下何マス分連結するかを指定するので、長方形のうち左上の点が代表となることになります。

等々考えられます。(青い点が代表点)
具体的に挙げると、
  • 1x1の長方形:10通り
  • 2x1の長方形:6通り
  • 1x2の長方形:6通り
  • 3x1の長方形:2通り
  • 1x3の長方形:2通り
  • 2x2の長方形:3通り
でまず29通りあります。
一番左のパターンの左上の2x2マスを取った場合、残った図形からまた1つ長方形を選ぶのは15通りあります。

・・・こんなやり方をしていては分岐が膨大な数になってしまいます。
同じ色が固まってる領域が小さければいいですが、ゲームなどアニメ風画像等同じ色の領域が固まってる画像ではいつまでたっても計算が終わらないことになります。
(個人的にはNP完全レベルの計算量があるのではと思ってますが・・・どうなんだろう。)

とりあえず、本当に最適な解を見つけるのはかなり手間がかかりそうです。
(もちろんもっと高速な方法はあるのかもしれませんし、そもそも上に書いた手法も改善の余地は色々ある)
そこで、近似的にそれなりに良さそうな解を見つける方法を考えてみます。

で、とりあえず思いつくのは
「大きく取れそうな長方形から取って行けば?」
というものです。

理屈は単純明快です。
これが最適でない解を出すような図形は存在しますが、とりあえず今回作成したプログラムはこれでやってみました。

ちなみに、最適でない解は以下のような図形を分割する際に現れます。
こんな図形を変換すると・・・
最適な分け方
大きいものを先に取る
最適な解のためには先に横棒を確保した方がいい(6個に分割)のですが、先に大きいからと縦棒を取ってしまうと、10個に分割されてしまいます。

まぁ上の話は置いておいて、とりあえず
「大きな長方形から取って行く」
ということで考えて行きます。(最適解は得られないにしても時間の割に近い値が得られるということで。)

「同じ大きさの長方形があったらどっちを優先するの?」という問題はありますが、それを除けばこの時点で元の画像から生成される分割のしかたは決定されることになります。

「大きい順にとっていくなら、とりあえず取れる可能性のある長方形を全部列挙して大きさ順にソートすれば?」
というと事はそう単純でもないことになります。
先ほどの例を考えます。


上の例を見る限り、4マスの長方形や3マスの長方形を取る方法はいくつかありそうです。
ただ、例えばここで4マスの長方形が最大なので、2番目の取りかたで真中の正方形をまず1つ分抜くとします。
こうなると、元々4マスや3マスの長方形が何通りも取る方法があったにも関わらず、次に大きい長方形は2マスのものしか取れません。
要は、最大の長方形を選択したとすると、その選択によって残りの図形の中からの最大の長方形が変化するということが問題になります。
するとまた残りの図形の全ピクセルを走査して最大の長方形を探す・・・ということになります。
最初これをやったらWin95や98にある「雲.bmp」では5分でも終わらなそうな感じでした。(最終的に作ったものは75秒)

これをより高速化するために、以下のような処理を施してみました。
  • 同じ色のものだけ処理
    最大の長方形を1つ抜き取ると、残りの図形の長方形の選びかたに影響を与えます。
    とはいえ、それは抜き取った領域と同じ色のところだけです。
    と言うことで、未出の色を見つけたらまず画像内の全同色のピクセルを処理してしまうことにします。
    ある色を処理している間は他の色のピクセルのことを考えなくていいので処理対象がだいぶ絞れます。

  • 抜き取る長方形と関係のある部分だけ更新
    最大の長方形を1つ抜き出したとして、残りの図形(の同色のピクセルの部分)全てについてまた長方形のリストを取得するのはめんどいです。
    そこで、抜き取った長方形と関係のある部分だけ再度長方形の候補を挙げて行きます。
    具体的には、「リスト内の長方形のうち最大の長方形とintersectする場合」「抜き取った最大の長方形の真下及び右のピクセルのみ再度走査」しています。

  • 明らかに最大にならない取りかたは排除する
    例えば、左の取りかたがある場合は右側は明らかに無駄です。
    すなわち、長方形のリスト中に片方が片方を完全に含む取りかたがある場合、含まれる方は不用です。

  • 1x1のピクセルは個別に処理
    ある代表点から右下方向に面積が大きくなるような長方形を探して行くわけですが、これが1x1の結果になった場合、このピクセルは完全に孤立していると考えられます。
    (もし、対象の代表点の上や左に同色のピクセルがある場合、上の「明らかに最大にならない取りかたは排除する」のルールのためこの代表点はそもそも候補になりません)
    孤立した点は明らかに周りに影響を与えないですし、そこは単独で長方形として抜き取っていいことになります。
とまぁグダグダと書いてみました。
多分文章だけ見てもよくわからないと思います。
プログラムを組んでみようとすると分かるかも。

あと、サイズを減らすインチキ(?)として、最も登場頻度の高い色はTABLE全体のBGCOLORに指定してしまい、TDの中で毎回指定しないようにしています。

結果、雲.bmpではcolspan・rowspanを用いない場合にTDタグだけで640*480*24=7.3MBかかることになりますが、5.5MB程度のサイズに圧縮できました。
上の貼り付けボタンの絵は16*16*24=6144バイトのところを、TRタグやTABLEタグをつけても2563バイトになっています。
雲は見れば分かると思いますが、かなり色の変化が激しいためあまりcolspanやrowspanの恩恵がありません。
まぁアニメ風画像や色数の少なめなドット絵など、同じ色が連続すると影響が大きいです。
(GIFがそういう画像の圧縮に強いのと大体同じ理由かと。)

さらに細かい圧縮方法では、「bgcolor=#000000 → bgcolor=black」みたく一部の色で6文字以下の名前がついている場合それに置き換えることでしょうか。
どっちにしても写真風など色の変化が激しい場合は名前のついている色にぴったり合うピクセルは少なそうなので影響は少ないと思いますが。

で、もし「もっといいアルゴリズムがあるぞ〜」と言う人がいたら主に以下のどのレイヤーになるかを考えつつ教えてもらえるとありがたいです。
  • まずは、最適な解を出せる効率的(現実的)な方法がある
  • (最適ではないが、)大きい順に抜き取るよりは(速度または分割の)効率のいい方法がある
  • (大きい順に抜き取るという手法は同じだが、)もっと(速度面で)効率的に処理できる方法がある
高速化そのものとしては、「VBじゃなくてCで書けばいいんじゃない?」「動的なメモリ確保を押さえれば」「関数呼出を減らせば」等と色々考えられますが、それ以上にアルゴリズム的な改善案があれば聞いてみたいです。
(自分の手法が最高とは限らないし、もっといいの有りそうだし)
というわけで、今回はアルゴリズムを考える話をしてみました。

色々APIを使いこなして凄い使い勝手のいいインターフェースを作るのも面白いし、ハードの力をフルに利用して派手なゲームを作るのもプログラムを組む人の楽しみの1つであると思います。
ただ、中でもアルゴリズムはプログラムを組む面白さの最たるものではないかと思います。
用意されたAPIや人の作ったライブラリを借りるわけではなく、問題解決は全て自分の考えだけで行うわけですし。

こういう問題を解くにはVBは速度的にも言語仕様的にも向いてないですけどね・・・

あと、プログラムで画像をテーブルアートに変換できてしまうと、手作業のテーブルアートが何だか無駄な作業に思うかもしれません。
ただ、絵柄中の★印をあえて文字の「★」を入れることで表現するなど、まだまだ人間ならではの手法が介在する余地があると思います。
そういう意味ではテーブルアート職人の方がいるのであれば、頑張って欲しいです。
(なんか3Dのキャラを縮小するよりドット絵職人の方の絵の方がキャラが際立つのと同じ感じですね。写真があれば本物そっくりな絵がいらなくなるというわけでもないし。)

04/03/31 CodecをつかったMP3のデコード・再生編−3(デコード、再生)[★★★◎◎]
前回前々回でMP3データの余分なタグを削除し、WAVEFORMATEXを初期化する事ができました。
ということでようやくデコードです。
まぁCODECというかacmの使い方の紹介みたくなってしまいますが・・・

大まかな使い方は以下の通りです。

acmFormatSuggestで出力形式を指定
      ↓
acmStreamOpenでACMストリームオープン
      ↓
acmStreamSizeで出力サイズを取得
      ↓
acmStreamPrepareHeaderで出力用の構造体を準備
      ↓
acmStreamConvertで変換
      ↓
acmStreamUnprepareHeaderで出力用の構造体を破棄
      ↓
acmStreamCloseでACMストリームをクローズ

Windows APIのほかのオブジェクト同様に開始・終了はOpen-Closeで対になっています。
また、他のMCI系API同様にPrepareHeader-UnprepareHeaderは対になっています。
acmStreamSizeとacmPrepareHeaderの順番は逆でも構わないようです。

こまごま説明するより、ソースを見たほうが分かりやすいと思うので載せておきます。

まず、前々回の知識を用いるとMP3ファイルやWAV形式のMP3ファイルからMP3の生データだけ取得する事ができます。
さらに前回のGetMP3FormatFromBuffer関数でフレームヘッダからWAVEFORMATEX(今回はMPEGLAYER3WAVEFORMAT)を取得する事ができます。

で、下の関数で変換できます。
あまり細かいエラー処理をしていないですが、とりあえず動くコードということで。

Public Function DecodeToPCM(ByRef smw As MPEGLAYER3WAVEFORMAT, ByRef sbuf() As Byte, _
ByRef dmw As MPEGLAYER3WAVEFORMAT, ByRef dbuf() As Byte) As Long
'圧縮WAVを無圧縮WAVに変換
Dim slen&, dlen& '長さ
Dim has As Long, ash As ACMSTREAMHEADER 'ハンドルなど
Dim b As Boolean, i&, j&


'推奨変換先取得
i = acmFormatSuggest(0, smw, dmw, Len(dmw), _
  ACM_FORMATSUGGESTF_WFORMATTAG Or ACM_FORMATSUGGESTF_NCHANNELS Or _
  ACM_FORMATSUGGESTF_NSAMPLESPERSEC Or ACM_FORMATSUGGESTF_WBITSPERSAMPLE)

If i <> 0 Then Exit Function
  
i = acmStreamOpen(has, 0, smw, dmw, 0, 0, 0, ACM_STREAMOPENF_NONREALTIME)
If i <> 0 Then Exit Function

slen = UBound(sbuf) + 1

'展開後のサイズ取得
Call acmStreamSize(has, slen, dlen, ACM_STREAMSIZEF_SOURCE)
ReDim dbuf(dlen - 1) As Byte

'構造体初期化
With ash
  .cbStruct = Len(ash)
  .cbSrcLength = slen
  .pbSrc = VarPtr(sbuf(0))
  .cbDstLength = dlen
  .pbDst = VarPtr(dbuf(0))
End With

Call acmStreamPrepareHeader(has, ash, 0)

'変換開始
Call acmStreamConvert(has, ash, &H30)
'変換終了
Call acmStreamUnprepareHeader(has, ash, 0)

b = (ash.cbDstLengthUsed > 0)
If b Then ReDim Preserve dbuf(ash.cbDstLengthUsed - 1) As Byte

Call acmStreamClose(has, 0)

DecodeToPCM = b

End Function

まず、この関数の4つの引数は以下の意味を持っています。
smw : 変換元(MP3データ)の形式を示すMPEGLAYER3FORMAT構造体、GetMP3FormatFromBuffer関数で得られる。
sbuf : 変換元のMP3データの入ったバイト配列。
dmw : 変換先(非圧縮WAVデータ)の形式を示すMPEGLAYER3FORMAT構造体。
dbuf : 変換後のデータの入るバイト配列。

変換先のdmwはMPEGLAYER3FORMAT構造体のうち、WAVEOFORMATの分だけ埋めれば大丈夫のようです。
下みたいな感じ。

'出力するPCMの設定
With dmw.wfx
  .wFormatTag = WAVE_FORMAT_PCM
  .nChannels = IIf(IsStereo, 2, 1)
  .nSamplesPerSec = SamplingRate
  .wBitsPerSample = SamplingBit
  .nBlockAlign = SamplingBit * .nChannels \ 8
End With

WAVE_FORMAT_PCMはAPIの定数で1。
nChannelはチャンネル数。ステレオなら2、モノラルなら1。
↑の例ではBoolean型のIsStereo=Trueなら2になる。
SamplingRateは44100とか22050とか11025が入ります。
元のMP3データにもよりますが、44100Hz指定のMP3データを8000Hzで出力しようとしたらうちの環境(Win98)ではエラーが出ました。
約数である11025だとうまく行きました。
SamplingBitは16か8ですね。


各関数の追跡

で、上のコードを一つずつ追って行きます。
まずacmFormatSuggestです。
上のコードから該当部分を抜き出すと以下のようになります。
i = acmFormatSuggest(0, smw, dmw, Len(dmw), _
 ACM_FORMATSUGGESTF_WFORMATTAG Or ACM_FORMATSUGGESTF_NCHANNELS Or _
 ACM_FORMATSUGGESTF_NSAMPLESPERSEC Or ACM_FORMATSUGGESTF_WBITSPERSAMPLE)

If i <> 0 Then Exit Function
これは、Codecが出力先のフォーマットを利用できるかどうかをチェックします。
もしくは、Codec側からちょうどいいフォーマットを教えてもらう事もできます。
5つの引数がありますが、1つ目は呼出元インスタンスですがこれは0でも大丈夫です。
2・3つ目はそれぞれ変換元、変換先のWAVEFORMATEXです。
MPEGLAYER3FORMATはWAVEOFORMATEXの種類の1つなのでそのまま突っ込めばいいのですが、APIビューアの定義ではこの関数はWAVEFORMATEXを受け取るようになっているので、関数の宣言As AnyとかAs MPEGLAYER3FORMATに変える必要があります。
WAVEFORMATEXは実際はさまざまな長さの構造体となるため、4つ目の引数で出力先の構造体のサイズを指定します。
5つ目は色々定数のORを取っていますが、これは各項目を「ユーザーが指定する」「Codecに教えてもらう」のどちらかにするかの指定です。
上の例ではフォーマット、チャンネル、サンプリングレート、サンプリングビット数を示す4つの定数のORをとっていますが、この場合dmwに指定したフォーマットを利用できるか尋ねることになります。
一方、ACM_FORMATSUGGESTF_WFORMATTAGだけ指定したりすると、dmwのチャンネル・サンプリングレート・サンプリングビット数を埋めて返してくれます。
今回はいずれもユーザーが指定する形をとっていますが、特に形式にこだわらない場合はCodecの指定するフォーマットでもいいかも知れませんね。
利用できないフォーマットを指定するとエラーが返ります。
例えば、44100HzのMP3データに対して出力を8000Hzにするとここでこけます。


次に、acmStreamOpenでストリームをオープンしています。
i = acmStreamOpen(has, 0, smw, dmw, 0, 0, 0, ACM_STREAMOPENF_NONREALTIME)
If i <> 0 Then Exit Function
返り値ではなく、第1引数の引数にハンドルが返ってきます。
2つ目はCodecの指定のようですが、0で構いません。
3・4つ目は上と同様に変換元、変換先の指定ということでsmw、dmw。
5つ目はフィルタを通す場合そのデータが入りますが、今回は使用しないので0。
6つ目はコールバック関数のアドレスだが、最後の引数にACM_STREAMOPENF_NONREALTIMEを指定した場合は関係ない。
7つ目はインスタンスですが、やはり0で大丈夫。
8つ目はオープン完了を待つか待たないかです。
待つ場合は上の通りACM_STREAMOPENF_NONREALTIMEを指定します。
待ちたくない場合はACM_STREAMOPENF_ASYNCを指定すると、オープンが完了する前にプログラムは先に進みます。
この場合オープンが完了すると6番目に指定したコールバックが呼ばれますが、今回は特にその必要性もないので指定しません。

やはり失敗するとエラーで負の値が返ります。


次に、展開後のサイズを取得します。

slen = UBound(sbuf) + 1

'展開後のサイズ取得
Call acmStreamSize(has, slen, dlen, ACM_STREAMSIZEF_SOURCE)

acmStreamSizeは変換元のサイズを指定して変換後のサイズを取得したり、その逆ができます。
上はACM_STREAMSIZEF_SOURCEとあるように、ソース側のサイズから変換後のサイズを取得しています。
ここで注意なのが、acmStreamSizeは実際の値より大きい値を返すことがあるようです。
(手元の環境では1フレーム=1152サンプル=4608バイト大きくなった)
まぁ実際に変換しないと細かいサイズは分からないと言うことでしょうか・・・?

次にACMSTREAMHEADER構造体の初期化です。
ReDim dbuf(dlen - 1) As Byte

'構造体初期化
With ash
  .cbStruct = Len(ash)
  .cbSrcLength = slen
  .pbSrc = VarPtr(sbuf(0))
  .cbDstLength = dlen
  .pbDst = VarPtr(dbuf(0))
End With

上を見ると大体想像がつくかもしれませんが、変換元のサイズとデータの先頭位置のポインタを指定し、変換後のサイズとデータを指定するだけです。
最初に構造体の長さをセットしているぐらいで大した事はないですね。
そして変換処理です。

Call acmStreamPrepareHeader(has, ash, 0)

'変換開始
Call acmStreamConvert(has, ash, &H30)
'変換終了
Call acmStreamUnprepareHeader(has, ash, 0)

まぁ返り値のチェックとかはしていませんが・・・
前後のPrepareHeader、UnprepareHeaderはMCI系の関数ではお約束で、waveOutXxxxやmidiOutXxxxでも使いますね。
具体的に何をやっているかは分かりませんが、とりあえずストリームのハンドルと上で初期化したACMSTREAMHEADER構造体を突っ込んどく事になります。
間のacmStreamConvertで実際に変換をしています。
最後の&H30はACM_STREAMCONVERTF_STARTとACM_STREAMCONVERTF_ENDの和なんですが、別に0でも大丈夫みたいです。
変換の形式によっては必要なのかもしれませんね。


残るのは無事変換が終了した後の後処理です。

b = (ash.cbDstLengthUsed > 0)
If b Then ReDim Preserve dbuf(ash.cbDstLengthUsed - 1) As Byte

Call acmStreamClose(has, 0)


変換が終わると変換後のサイズがcbDstLengthUsedに代入されます。
そこで配列のサイズを整えてます。
事前のacmStreamSizeと違うサイズが返ることがあるのがいやらしいですね。


再生

最後に今回展開したデータを再生する場合についてちょこっと。
別に非圧縮WAVの再生にしてもそうですが、展開後は44100Hz・16bit・ステレオのデータだと1秒で160KBものサイズになってしまいます。
1分10MBと言うことで、何分もの曲を全部メモリに読みこんだり展開すると数10MBになるので不可能ではないにしろあまり好ましいサイズではないです。

そこで、少しずつファイルから読みこむとか、MP3データだけメモリに読みこんで少しずつ展開する事になると思います。
(WinAMP等もそうですね)

そこで、waveOutXxxx系のAPIを使う場合、1秒〜数秒程度の再生用バッファを準備しておき、それを無限回連続再生することで実装します。
(DirectSoundの場合もそう)
一応waveOutWriteは書きこんだデータをバッファリングしてくれるようですが、DirectSoundと近いインターフェースとして扱うには再生用バッファを準備する方がいいかも知れません。

例えば3秒のバッファを使っている場合、タイマーなどで再生状況をチェックして最初の1秒以内の位置を再生する時は2〜3秒の位置に相当するデータを展開して書きこみ、、1〜2秒の区間を再生している時は次のループで到達する0〜1秒の区間のデータを展開して書きこむという事でループ再生バッファを用いた再生ができます。
(最初の1秒以内を再生している場合1〜2秒の区間もデータを書きこんでもいいのですが、処理中に再生位置が1〜2秒の区間に入ってしまうとまずいので・・・)

できればこの再生バッファ管理用にスレッドを1つつくってマルチスレッドで扱う方がいいのかもしれませんが、まぁタイマーで定期的にチェックしても問題はなさそうです。
ここでは大雑把にしか書いていないのでソースはサンプルで。

注意しなければならないのは、少しずつフレームを展開して行く場合、acmStreamのハンドルは同じ物を使いつづけて、最初から順番に展開しなければならないということです。
途中のデータからいきなり展開しようとすると、(前のフレームからパラメータを引き継ぐらしく?)少しノイズが入ります。


最後再生については駆け足になりましたが、とりあえずここらへんでMP3のデコード・再生については終わりと言うことで。
OggVorbisはもっと使いやすそうなんだけどな・・・


一覧へ戻る