03/06/29 | ベジェ曲線の長さ編[★★◎◎◎◎] | |||||||||||
とあるメーリングリストで出てきた話題なのでここで取り上げて見る。 ベジェ曲線はグラフィックの分野以外にもCADでも使われているらしい。 グラフィックならともかく、CADで使うとなるとその長さを求めてみたくもなるが単純な円弧でもないしどうやって曲線の長さを求めればいいんだ?という話。 一応数学的な部分についてはHK WORLDで述べられているので、これでわかる人はもうプログラムを組めるはず。 ただ、このサイトには実際のプログラムがないので一応ここでだらだら書いてみる。 とりあえずベジェ曲線そのものについて。 ベジェ曲線はn次ベジェ曲線と言われて制御点の数で色々なものが有るが、一般的に使われるベジェ曲線は3次ベジェ曲線である。 これは、始点・制御点1・制御点2・終点の4点からなる曲線で、終点を次の曲線の始点とすることで連結させると複雑な曲線も書く事が出来る。 Illustratorなんかのツールだと、ある始点の制御点として、その前の曲線の制御点2と、これから書く曲線の制御点1がくっついた形になっているものが多いと思う。 (始点から滑らかさを示す接線っぽい奴が伸びてるというか・・・) 前の曲線の制御点2、終点(=次の曲線の始点)、次の曲線の制御点1を1直線に並べれば連結部分も滑らかに繋がるし、Illustratorとかで適当に線を引くとそんな感じで制御点が取られる。 んで、実際のベジェ曲線の数学的表現について。 3次ベジェ曲線は、始点・制御点1・制御点2・終点をP0,P1,P2,P3とすると、媒介変数tを用いて以下のように表す事が出来る。
上の式をx、y(3次元ならzも)についてt=0〜1で変化させていって得られるP(t)をドットで打って行けばよい。 ここでとりあえず特徴として、P(0)=P0、P(1)=P3、すなわち始点及び終点は名前の通り必ず通り、始点と終点となることがわかる。 一方制御点は必ず通るとは限らない。(というか4点を直線上に配置でもしないとそうそう通らない。別に通ったからって何の問題もないと思うけど) ↑の式のままだと扱いにくいので、tの次数で並べ替えてみると、
上の式は、x,yそれぞれについて成り立つので、2次元ならA,B,C,Dもx,yの2値のベクトルになるし、3次元なら3つになる。 つまり、2次元ならばA,B,Cをそれぞれx,yについて求めたものを構造体風にA.x,A.y,B.x,B.y,C.x,C.yの様に書くとして、
のような感じで求めればよい。 上の式は単なる3次式なので、後は高校の時習った曲線の長さの公式が使える。 媒介変数を使った場合の曲線の長さLの式は、t=a〜bとすると、
となる。(式が見づらい場合は上のHK WORLDで。) 3次元、4次元・・・ならルートの中に(dz/dt)2でも(dw/dt)2でもどんどん付け加えて行けばよい。 要は何をやっているかといえば、dtだけ変化した場合のP(t)とP(t+dt)の2点間の直線距離を採っているだけですね・・・ じゃあ、上記の積分計算をどのように行うか。 とりあえずP(t)を微分して、さらに二乗してみると、
となる。上の式はx,yそれぞれに対して成り立つので、P(t)のx成分をP(t).xと表現するのであればd(P(t).x)/dt=P'(t).xと書くことが出来る。 P'(t)にはDが出てこないのでA,B,Cだけ求めればいいわけだが、(dx/dt)2=(P'(t).x)2なので、
上の式は見てのとおりそれぞれx、yについて対称。3次元になったら(dz/dt)2も同じ様に計算すればよい。 ここで積分すべき関数をQ(t)とおくと、
まぁみてわかるとおり.xが由来の項と.yが由来の項が足し算になっているだけなので、3次元でも.zの部分を同じように足せば大丈夫。 このQ(t)の中身は√の中に4次式が出てきていることになる。 これの不定積分ができるとありがたいのですが、どうなるかわからないので数値積分をしてみる。 数値積分には色々方法があるが、ここでは一番簡単な前進オイラー法を用いる。 一応前進オイラー法について解説。 先ほどの曲線の長さの式で、tの積分区間を0〜1にして計算すればいいが、ここであえて0〜sとおいて
とおくと、R(1)が求めるベジェ曲線の長さである。 しかし、Q(t)の不定積分が直接わからないので、Δsずつ刻んで求める。
ここで、前の項の∫0s Q(t)dt=R(s)である。 一方後ろの項に関してはΔsが十分小さいなら∫ss+Δs Q(t)dt ≒ Q(s)*Δsと近似できるので、結局
とすることでR(s+Δs)を近似的に求める事ができる。 あくまで近似なうえ、Δsを十分に小さく取らないと誤差が大きくなる。 幸い今回はQ(t)が単なる2次以下(4次式が√の中なので)の式なのでそこまでΔsを小さくしなくても0.001ぐらいに取ればよい。 ここまで聞くと難しく思えるかもしれないが、ゲームで「落下の加速度が1フレーム0.1ピクセルだから毎フレーム落下速度を0.1足して、今のy座標に落下速度を足す」なんてことをしてる人は多いと思う。 ほんとは加速度とか使うんならy座標は時間に対して正確に二次的に増やさなきゃいけないけど、そこまで せず毎フレーム0.1を足すだけ、速度を足すだけだと思う。 「60FPSでは加速度秒間6ピクセル(6/60=0.1)」と考えれば上の計算は「加速度を積分して速度を求める」「速度を積分して座標を求める」と言うことを前進オイラー法で求めている事になる。 ちなみに、より精度が高く、発散しにくい数値積分の方法としてルンゲ・クッタ法などがあるので興味がある人は調べてみるといいかもしれない。 積分がからむような物理シミュレーションなどで広く使われているはず。 まぁごたくはいいとして、上記の計算を実際にプログラムに起こしてみるとこんな感じ。
上記のプログラムは、引数p()にp(0)〜p(3)に始点・制御点1・制御点2・終点が入るようなPOINTAPI構造体、divに分割数(=1/Δs、デフォルトでNUM_DIV=1000)を入れるとベジェ曲線の長さを求める。 これはPOINTAPI構造体を渡すんで整数かつ2次元だけど、3次元や浮動小数にするのは簡単だと思います。 分割数は10とかだと少ないけど、100以上ならそれなりな値が出るはず。 100〜10000だと1%程度の誤差だった。 みてわかるとおり数値積分が単純なので、ここをルンゲ・クッタ法とかにすればさらに精度が上がるかな? そのうちVB講座で動くプログラムとして公開します。 しかし思ったより文章長くなったなぁ・・・ HTMLは数式打ちづらい。TeXコードIncludeとかできないかな^^; |
03/06/14 | 立体視できる3次元物体編[★★★◎◎] |
ゲームネタがパクリっぽいSTGとオリジナルと思われるパズル系でいくつかあるがあんまり作る気が起きないなぁ・・・ 今回戯れ言一覧とか作ったら年々記事数が減ってきてるのが気になる。 まぁその分最近のは1回分の文章量が多いってのはあるけど。 小ネタでもいいからちょくちょく書かないとな。 卒論のときOpenGL使ってたけど、OpenGL+GLUTだとちょっとした3Dのプログラム組む時便利だね。 初期化の手間もDirectXとかに比べればそんなにかかんないし、別にゲームとかに使うわけでもないならほんとに最低限の部分だけ初期化すればいい。 まぁそうは言ってもゲームに使う気は起きないな・・・ 少なくともGLUTの機能だけでは不満。 テクスチャとかもintやcharやfloatなど色んなデータで入力できるけど変換とかで遅そうだし。 というわけで、OpenGLでちょっとしたプログラムを書いてみる事に。 近年3次元ディスプレイなるものが色々研究されてきてるらしい。 子供の頃に、少しずれた赤い線と青い線で書かれた絵を赤と青のフィルムが貼ってあるメガネを使う事で3次元に見えるという体験をした人もいるかもね。 あとは、最近でも書店などで見かけるのは、ノイズが載ってるだけのような絵を寄り目などで焦点をずらす事で奥行きのある模様が見えるという奴ね。 (そう言えばVirtualBoyはこの手法使ってるのかな?それとも単にディスプレイが多層になってるのかな?) なぜこれらの手法で奥行きが感じられるかを考えてみる。 心理学的な要素としては、物が3次元に見える原因として物の影(影の位置やかかりぐあいで前後関係がわかる)や模様(模様がだんだん小さくなる→だんだん遠くの面になる)などがある(らしい)。 これらは別に目が2つでなくても奥行きが感じられる原因となる(らしい)。 片目つぶると遠近感が少しわかりにくくなるが、先入観などもあって小さいものや動くもので無ければそれほど遠近感に狂いが出ないのはこれらのせいなんでしょう。 で、さらに光学的に考えれば奥行きがわかるのは正に目が二つあるからであるといえる。 目が二つ別々の位置にあるので(まぁ「二つ」と言うくせに同じ場所にあるわけは無いが)当然二つの目には少し位置のずれた画像が入る事になる。 そこで脳が自動的に(←これ結構すごいと思う。2点からのステレオ画像生成をコンピュータで行うのは結構難しい。まぁ目で見る場合はそれほど正確な奥行きを求めてるわけではないんだろうけど。)そのずれから奥行きを計算してると考えられる。 んで、なんでいわゆる(ノイズから絵が浮かぶ系の)ステレオグラムが立体的に見えるか考えてみる。 (以下、個人的な想像であり解釈であるので間違ってるかもしれないです。) ステレオグラムは単なるノイズであるが、当然ながら左右の画像のノイズは基本的に重なるように出来ている。 ただ、一部奥や手前に持っていきたい部分は少しだけ左右の距離が周りとずれている事になる。 (寄り目じゃなくて普通に画像を見ると、へこんだり浮かんだりする部分の境目がよく見るとノイズがその形に線が入ったりして区切れてるのがわかる。) 例えば、2つの同じような画像が左右に10cm離れていて、それを20cm遠くから見ているとする。 交差法では、大抵この左右の画像が重なるように寄り目で焦点を合わせようとするだろう。 そこで、画像の一部分だけ10cmでなく9.9cmだけしかずれていなかったらどうなるか。 寄り目をしたときに周りの部分はぴったり重なるが、一部分だけは1mmだけずれて見える事になる。 この時、単に2つの同じ画像が1mmずれて見えるというわけではなく、脳がその1mmの誤差を修正するために 「この領域は少し手前にあるからずれが小さいんだ」 と見ることで、この領域は10:9.9≒20.2:20で2mm奥にあるように見える事になる。 (↑ここの計算が間違ってるかも知れないけど、まぁこんな感じで手前にあるように見えるという事で。) 遠くに見える時も同様に10cm以上の距離がある部分は手前にあるように見える。 まぁ考えかたとしては、 「周りよりずれが大きい→手前にあるからだ」 「周りよりずれが小さい→奥にあるからだ」 となります。 ずれが数cmと大きくなると、もはや脳は両者は重ねる事が出来ず、別々の模様と考えるので絵は重ならなくなります。 んで。 別にノイズから模様が見える必要はなくて、この手法は普通の物体を3次元に見えるようにも応用できます。 というわけで、2つの目から見た物体を描画してみる。 まぁ色々書いたけどプログラムとしては大した事ない。 (OpenGL+GLUTで作成) 大きさ1のティーポットが距離5の位置にある場合、0.4離れた二つのカメラから見た状態の絵を描いて見る。 横に並べると、下のようになった。 ティーポットの取っ手の部分が少し手前にあるように見えないだろうか? 作成したプログラムは、プログラム実験部屋に置いてある。 ティーポットが回転するだけであるが、(寄り目で見つづけるのはちょっと大変かもしれないが)ティーポットの奥行きが感じられて面白いと思う。 ちなみに、この技術はVirtual Realityや3次元モデルの直感的理解のため、3次元ディスプレイ等の分野で応用が考えられているらしい。 ずっと寄り目で物体を見るわけにも行かないので、両目に別々の画像を表示すればいい事になる。 最初に書いた赤と青のフィルムを貼ると言うのが一番簡単な方法だと思われるが、この手法だと色が表現できない。 手っ取り早いのはヘッドマウントディスプレイ(HMD)で両目に別々の画像を映せば簡単である。 この方法は全員がHMDをつける必要があるので、大勢に見せたい時は頭が重いし値段が高い。 赤と青のフィルムの応用として、光の偏光を利用する方法がある。 ディスプレイからは左目用と右目用でそれぞれ縦と横に光の偏光の向きを揃えて表示する。 両目のレンズはそれぞれ縦と横に偏光した光だけを通す事で、色の問題も解決できるし、見る側はメガネをつけるだけでいいので負担も少ない。 ただ、偏光するとなると現在だと液晶を利用する事になるのかな? 液晶ディスプレイの大型化は技術的にもかなり難しいらしい。 将来漫画やSF小説であるような空間上に表示でききるような立体ホログラム装置とかできるのかな・・・ 今回あんまりプログラムに関しては細かいこと書いてないな。。。ごたくばっかりだ。 03/06/28補足 音についてもやはり2つ耳があるというのは大きいらしい。 ただ、画像の場合と違い、通常音は鼓膜の振動という情報しか耳に入らないわけで、単に二つの耳に違う場所からの音が入るから場所がわかるというわけでもない。 とりあえず2つの耳は異なる場所にあるので、目同様に音の聞こえるタイミングの遅れや、音量差で距離がわかるとか。 ただ、両耳から距離がわかったところで、それぞれの耳からある大きさの球を考えればその交差部分は大抵円になるわけでまだ1次元分(円自体は2次元だが円周部しかないので)の自由度が残ってる事になる。 んで。 どうやら、マネキンの両耳にマイクをつけて録音したのを聞くと、かなり位置がわかるらしい。 単に二つのマイクからステレオの音声を採っただけだとだめなんだけどね。 と言うのも、頭自身で音が遮られて音が回折して耳に入るのを脳が自動的に計算しているんだそうな。 人間の脳って凄いね。。。 脳の計算といえば、化粧やらメガネやらしていて、表情がコロコロ変わってもそう他人と間違える事はないが、これをコンピュータで計算でやらせるのはかなり難しい。 |
03/04/02 | CodecをつかったMP3のデコード・再生編−1(ファイルからの必要なデータの取得)[★★★◎◎] | |||
以前からちょくちょく挑戦していたCodecのMP3デコードです。 あと、waveOut系関数をつかって任意の音声をストリーム再生する方法も知りたかったので色々調査。 ところでCodecってCOder-DECoderの略だとか。MOdulator-DEModulatorみたいだな。 まずはMP3のデコードについて。 最近はフリーウェアですらMP3をBGMにつかってるゲームがちょくちょくある。 一応Codecが入っているとMP3形式のwavはmciSendSoundで"play filename.wav"で充分再生出来るんだけど・・・ まぁBGMとしてつかえるか微妙だしDirectSoundに応用できなさそうなんで、とりあえずデコードだけをしたいと。 で、大抵はデコードルーチン自体をプログラムが持ってるか、デコード用のDLLとかを利用している事が多い気がする。 ただ、せっかくOSがAudio用Codecを持っているので、それを利用する事を考えてみます。 個々のCodecを統一的に利用するために、マルチメディア系関数としてAudio Compression Manager系関数acmXxxxが色々と定義されてます。 midiOutXxxxとかwaveOutXxxxと同様にwinmm.dllで定義されているらしく、wavOutXxxxとかと関連する構造体も多いようです。 特に変換の場合はacmStreamXxxxを使うことになります。 これをつかうとCodecさえあればこの一連の関数だけでエンコード・デコードできて結構オトクだと思います。 この部分はプログラム中にデコーダのコードを持つとか個別のDLLをつかうとは別の有利な点でしょう。 一応先に書いておくと、acmStreamXxxxをつかうためにはWAVEFORMATを拡張したWAVEFORMATEXと言うものが必要です。 特にMP3の場合にはWAVEFORMATEXをさらに拡張したMPEGLAYER3WAVEFORMATが必要。 ちなみにこの構造体はVC6ではmmreg.h内で宣言されています。 少なくともVB5のAPIビューアーにはありませんでした。(まぁVB5は97年に出たしな・・・) 逆に、変換元と変換先のWAVEFORMATEXを取得できればあとはacmStreamXxxxが勝手にコンバートしてくれると言うありがたい仕組み。 とりあえずacmStreamXxxxの前に、WAV形式のMP3データにしろMP3ファイルにしろ名前のウェーブデータ部分だけをまずファイルから取り出す必要があります。 まず、WAVファイルのヘッダは以下の通り。 (4byte)'RIFF' - 4バイトのヘッダ (4byte)これ以降のファイルサイズ - ファイルサイズ-8の値 (4byte)'WAVE' - waveファイルであることを示す 以下は、 (4byte)タグ名 (4byte)タグの長さ (nbyte)上記タグの長さ分のデータ が入ります。タグは複数ありますが、タグ数などは記述されてなくて、ファイルの終端に来たら終わりと言う事っぽいです。 ここで、waveファイルで重要なタグは'fmt 'と'data'です。 通常'fmt 'は'WAVE'と連続して、その後に'data'が入りますね。 拡張して別のタグを入れて歌詞や曲の情報を入れるフォーマットもあるみたいですが、とりあえず再生する音だけに関しては'fmt 'と'WAVE'で十分です。 'fmt 'チャンクには、APIなどにそのまま放りこめるPCMWAVEFORMAT構造体が入っています。 非圧縮の普通のWAVファイルであれば、以下の16バイトでしょう。
PCMWAVEFORMATではwBitsPerSampleまででしたが、ちょうど拡張部分のサイズがcbSizeにはいり、残りのデータがMPEGLAYER3WAVEFORMATのwID以降に入ります。 実際に身近なWAV形式MP3を見ると、'fmt 'チャンクのサイズは0x1Eとなっており、MPEGLAYER3WAVEFORMAT構造体のサイズと一致します。 acmStreamXxxxを使う場合は必要に応じて拡張部分を含むWAVEFORMAT(つまりMP3の場合ならMPEGLAYER3WAVEFORMAT)が必要なのですが、これがWAVファイルそのものから得られるのでラクです。 あとは、'data'チャンクの内容がちょうど変換すべきデータにあたるのでごっそりバッファかなんかに読みこんでおきましょう。 (別にちょびちょびファイルから読みこんでもいいけどさ) で。 メンドイのがMP3ファイル。 MPEGLAYER3WAVEFORMAT構造体に相当するものをファイルからパパっと取り出せればいいのですが、そうもいかないようです。 そもそもMP3ファイルは、フレーム単位のデータが繋がっているだけで、複数のフレーム全体を取り囲むようなヘッダやフッタは基本的には存在しません。 そこで、個々のフレームデータからMPEGLAYER3WAVEFORMATを取得する事を考えます。 (VBR(可変ビットレート)については未調査。) ただしその前に。 MP3ファイルにはID3v1、ID3v2のような曲名やジャンルなどを入力する項目があります。 これは少なくとも再生のことだけを考えれば全く邪魔なのであらかじめ取り除くことを考えます。 ID3v1及びID3v2の細かい内容は現在主流っぽいMP3タグ情報フォーマットまとめなどに掲載されているので、具体的にこの部分を書き換えたいとか思っている方は参照するといいでしょう。 ここではとりあえず取っ払う方法だけ考えます。 ID3v1は非常に簡単です。 ID3v1はMP3ファイルの最後尾128byteとサイズが決まっています。 そのため、後ろから128byteの位置のデータが'TAG'であればID3v1が存在するとして128byte削って終了です。 ID3v1は128byte固定で文字列フィールドも最長30byteと長い曲名などを格納できないため、ID3v2が考えられたようです。 ID3v2はファイルの先頭にあるため、ファイルの先頭3byteが'ID3'であればID3v2タグがあると考えられます。 ID3v2にはバージョンが存在し、これを書いてる時点ではv2.4.0まで来ているようです。 まぁ下位互換性はあると思われるのでとりあえずこれをサポートすれば現状ではOKでしょう。 (しかし「考えられる」「思われる」「とりあえず」って適当だなぁ・・・) ID3v2の構造は先ほどのリンク先からたどればわかりますが、最初の10バイトがヘッダになっています。 そのうち最後の4バイトにID3v2全体のサイズからヘッダの10byteをひいた物が格納されています。 ただし、MidiのSMF形式のように、最上位ビットは使用せず、各バイトに対し残り7bitを用いた計28bitのデータが実際に利用されます。 また、ヘッダの6バイト目にはいくつかのフラグがありますが、下から5番目のビットが1である場合、フッタが存在するとしてもう10バイト長いタグと計算されます。 作成したプログラムでは以下のような計算でID3v2の長さを計算しています。
これでID3v1もID3v2も取っ払い、生のウェーブデータの圧縮部が取れました。 この圧縮部はWAV形式のMP3でもMP3ファイルでも同じです。 ただ、WAV形式の場合と違いMP3ファイルに関してはフレームのヘッダからMPEGLAYER3WAVEFORMATを設定する必要があります。 次回はMP3のフレームデータからMPEGLAYER3WAVEFORMATを設定する方法について触れ、実際にデコードを行う予定です。 |
03/03/14 | 簡易OSを作ろう編−3(ブートセクタの解析)[★★★◎] | |||||||||||||||||||||||||||||||||||||
と、いうわけで、FDのブートセクタを逆アセンブル・解析してみました。 って解析したのは去年の7月だったんだけど・・・更新ネタがちょっと尽きてきたかな・・・ んで。 ぱっとみてわかるのは、86系の比較的初期の命令しかつかって無いと言うところです。 掛け算すらないし、そもそも16bitコードです。 基本的に除算もないのですが、なぜか1箇所だけあったり。 余りが6バイトしかないからなぁ・・・ 起動時はFDの先頭セクタ512バイトを0000:7C00-7DFFに読みこみ、7C00からスタートします。 全体の目的は、ルートディレクトリ中のIO.SYSというファイルを読みこみ、実行する事です。
HDDの場合は、パーティションテーブルを読みこんで、アクティブなパーティションの先頭セクタに制御を移すコードが入ります。 色々やってますが、結局IO.SYSを読みこむだけ(^^;) 次回はようやくアセンブラでコードを書こうかと思います。 と言ってもファイルシステムがどうとかマルチスレッドがとか簡単にできるわけがないので、BIOSの命令を使って簡単なプログラムを作ってみたいと思います。 単なるプログラムではOSとは言えないので、intの割りこみ命令を定義する予定です。 |