!!!独り言日記 !!ベジェの性質（2007/08/30） まずはベジェってどのようなものなんだろう、ということをメモ。 {{ref_image bezier_20070830.png}} Wikipediaに分かりやすい解説が書いているのでそちらを参考にするのがよいかも。 http://ja.wikipedia.org/wiki/%E3%83%99%E3%82%B8%E3%82%A7%E6%9B%B2%E7%B7%9A 上の図はベジェ曲線上に点Qを追加したときのハンドルのイメージです（適当に書いてますので、比率などはあってません）。 p0-p1-p2-p3で構成される点があり、p0とp3は曲線が通っています。 p1とp2は曲線が通っていません。 p0-p1を「t:1-t」に分割するとします。tは0.0〜1.0の間の値です。 同様にp1-p2とp2-3をそれぞれ「t:1-t」の割合になるように分割します。 で、緑色の線ができますので、これをさらに「t:1-t」で分割します。 曲線上のちょうど接線としてこれも「t:1-t」の直線ができます。これをここでは Qとしています。このとき「inQ-Q:Q-outQ」も「t:1-t」となります。 つまりは、このQが曲線上における新しい制御点となります。ハンドルもできてますね。 tを0.0〜1.0の間で細かく区切ることで、p0-p1-p2-p3が与えられたときの曲線を生成することができます。 そのときの計算式は {{mimetex b1=(1-t)^3 \\b2=3*t*(1-t)^2\\b3=3*t^2*(1-t)\\b4=t^3\\\\fx = b1 * p0.x + b2 * p1.x + b3 * p2.x + b4 * p3.x\\fy = b1 * p0.y + b2 * p1.y + b3 * p2.y + b4 * p3.y}} となり、 tを0.0、0.2、0.4、0.6、0.8、1.0のように変化させて(fx, fy)を打っていくと曲線になります。もっと分割を細かくするとより滑らかになります。 このとき、Qを追加した場合の接線のインハンドル・アウトハンドルの比率がt:1-tとなる、というのがミソです。 つまり、これはそのまま曲線上の点Qを削除することにもつながります。 これからの説明内容は、「曲線を構成する制御点から点を削除していって、できるだけもとの曲線を生かしつつリダクションする」です。 !!ベジェ近似もうちと最適化（2007/08/29） {{ref_image bezier_20070829.png}} 誤差の許容範囲を1.5Pixel以下になるように縛りを設けました。後、気になった部分を最適化。図は回転はいってしまいましたね（回転かけて保存してしまった・・・）。 見た目ほぼ同じなんですが、円の部分は真円（をつぶして楕円にした）っぽくみえないかも。 しかし、1ピクセルずれるだけで「おや、なんか違う・・・」と判断できるのは 人間の目って不思議ですね。 でも、これくらいになるとベジェ化する意味がないような(^_^;;。 ということで、線分からベジェ変換はだいたい勉強も実装もほぼ完了しましたので、 ちょくちょく解説を入れていきます。 !!mimetexテスト（2007/08/29） {{mimetex \LARGE f(x,y,z)=a x2 + 2 b x y + c y2 }} {{mimetex \LARGE f(x,y,z)=a x2 + 2 b x y + c y2 }} {{mimetex f(x)=\int_{-\infty}^xe^{-t^2}dt }} {{mimetex f(x)=\int_{-\infty}^xe^{-t^2}dt }} {{mimetex x=\frac{-b\pm\sqrt{b^2-4ac} }{2a} }} {{mimetex x=\frac{-b\pm\sqrt{b^2-4ac} }{2a} }} 途中で「｝｝」の表記を入れると、FreeStyleWikiのプラグイン閉じと勘違いしてしまうため、「｝　｝」のように間にスペースを入れて回避してます。 FreeStyleWikiのソースを修正するのは面倒なのでとりあえず。 書式についてはWikipediaの http://meta.wikimedia.org/wiki/Help:Formula が参考になります。 !!ベジェ化 - 最適化（2007/08/28） ポイントは思ったよりも増えてしまいますが、点の集まりから線で結んでベジェに変換は一通りできました。 赤い線・点がオリジナルの線情報。青い点がベジェの制御点を検出したもの。緑の線がベジェとして描画したもの。下画像のはベジェのみ描画したもの。 {{ref_image bezier_20070828.png}} もっとサンプリングを絞り込むことでより実際のポイントに近づけることができるのですが、行き着く先はオリジナルのポイントになってしまうのでこのへんで止めておきます。 でも、隣接しているベジェ制御点とかまだ最適化できそうですね。 で、今までのまとめとして数式で説明入れようと思ってたのですが、FreeStyleWikiのご本家サイトにつながらない・・・。どうやら「mimetex」というので数式を入れることができそうなのですが、、、。 !!ベジェ化（2007/08/27） 線分の集まりをベジェ化。 {{ref_image bezier_20070827.png}} 緑の線がベジェとして描画したものです（元は赤い点の集まり）。 やはりというか、ずれがありますね。補正は再分割でなんとかなりそうです（制御点が増えるのですが）。 ベジェ曲線を扱うのに一から勉強するようにしてみました（数式は前から使っていたのですが理論は理解してなかった）。 このへんで数式を逆変換してインハンドル・アウトハンドルを求めたりしてたのですが、なるほど〜、これはきれいに計算できますね（といってもかなり長い計算式になるのですが）。 ところで上記キャプチャ、何のソフトで描画しているか分かりますでしょうか。 実はFlashなんです。このへんのベクトルデータをテスト（ビュワー）するのはやりやすいですね（ただ、ベジェを扱うのはFlashではちと面倒なのでShadeから出してたりします）。 FreeStyleWikiで数式を扱いたいなぁと思ってるので、それ用のプラグインがあるか探してきます。このベジェ曲線の計算については自分でまとめる意味もこめて解説していければと思ってます（数式とはずっと格闘中・・・）。 !!線分のキーとなる点をとらえてみる（2007/08/24） 頭フル回転で疲れてしまいました・・・。メール等は明日レスしますです。 {{ref_image curve_point_20070824.png}} 複数の制御点を結んで曲線か直線かよく分からない線が引かれた場合に（これは単なる直線の集まりで、ベジェとしては扱っていないもの）、 いわゆるベジェの必ず通るであろう制御点を検出するプログラムを 書いてました。赤い点が本来の制御点です。青い点がベジェで使用する制御点を自動検出したもの。 いろいろ組み合わせてるんですが、まだ甘いですね。一部ベジェ化できそうにない部分もあるなぁ。 後は、この隣り合う青２点からベジェのインハンドル・アウトハンドルを伸ばして いかにそれっぽく曲線を作るか、ということでなんとか目的の実装はできそうです。 真ん中の円を見て分かるように、緩やかな制御点が多い部分はベジェ化することで結構な圧縮率になりそうではあります。 !!検索の効率化（2007/08/23） 最近は、「みなぎってきた！」な気分なんでノってるときにどんどん開発を進めてます。 つい最近掘っている曲線のものもそうなんですが、UniformGridによる検索を結構いろんなところで使ってます。レイトレの交差判定では使ってないですが、たとえば頂点法線を計算するとき（同一頂点の判定）とか、近接するオブジェクトの検索とか。 使う使わないで速度が100倍速とかざらなので（そして、空間構築時間はほどんどかからない）大量のデータを扱う検索を行う場合はぜひご利用を。 しかし、過去の自分はおろかなもんで、それを塗り替えるために作り直し、とかよくやってます。なんだかんだで覚えることや考えることに終わりはないなぁ。 最近はそのへんの「考えるプロセス」はショートカットすべきでない、と思ったりしてます。積み重ねが大事、かも。 今回作ってるプロジェクトはちょっと自信があったりします。 また時がきたらどっかで公開されるでしょう・・・。 !!曲線変換（2007/08/21） 最近、２つの三角形が交わる場合の交差する場所に出来る直線を求める、ってのに取り組んだのですが半日以上かかってしまった・・・・。ソースコードも長くなったけど、もっとスマートに行きそうな気がする・・。高校の代数幾何の証明問題を思い出しました（たしか、平面同士の交差はあったような）。平方根と割り算の多様は避けたいところ。 で、これをとりあえず解決したら今度は新しい課題が、、、と飽きることはないですね(^_^;;。 ということで、メモ。 B-スプラインからベジェ変換 http://www.infogoaround.org/JBook/bstobez.html 今取り組んでいるのは複数の頂点（曲線上の制御点）が与えられた場合に、できるだけ少ない制御点でベジェ曲線化したい（曲線にて近似したい）、というお題です。 逆は簡単なんですが、、、なんとなく反復させると求まりそうだなぁ。でも、速度は犠牲にしたくない、ということで勉強中です。 最近は数式と格闘してばっかり（kd-treeの最適化も平行して）・・・。 !!kd-tree視覚化（2007/08/19） チェックついでに、ツリーノードにて三角形が存在する部分を視覚化。 {{ref_image fuka_test_21.jpg}} {{ref_image fuka_test_20.jpg}} 赤いボクセルほど三角形が密集している部分です。 個々のティーポットを構成する三角形は2248個。なので、表示から見て1ボクセルに最大2250個の三角形が入っているのはだいたい計算があってますね。 ただ、何かずれてる部分がある気がする・・・。 !!kd-treeの苦手なシーン（2007/08/19） UniformGridでもそうですが、kd-treeの苦手シーンでどこまで遅くなるのか負荷テスト。 512 x 512 pixelにて、1ピクセル1レイ（アンチエイリアスなし）、Celeron 1GHz/Mem 512MBのVAIO noteで試してみました。 何かわからんですが、一枚のでかい平面上に物体を配置。 {{ref_image fuka_test03_20070819.jpg}} 中央に机っぽいものを配置して、大小のサイズの違うティーポットを複数配置してます。 *オブジェクト数 : 33 *三角形数合計 : 38278 *空間分割 : kd-tree(special-median) *空間分割の再帰の最大の深さ : 24（ = 2^(24/3) = 256より、256 x 256 x 256 ボクセルのUGに相当） *空間分割の最小の三角形数 : 30（1ノードにて、これ以下の三角形数になると再帰を打ち切り） 拡大していくと以下のようになります。 {{ref_image fuka_test02_20070819.jpg}} レンダリング時間 26 sec {{ref_image fuka_test01_20070819.jpg}} レンダリング時間 138 sec ということで時間かかりすぎです(^_^;;。 原因ははっきりしていて、kd-treeのノードに含まれる三角形数が2250くらいのものが存在する部分。UGで言えば、256x256x256の分割数よりも小さい部分にまだ分割し切れていない物体が存在する(単純に言えばティーポット1個分がまるごとノード1つに入ってしまっている)、という状態です。 ちなみに三角形数が2250も含まれるノードは、一番末端です（ここで設定した再帰の最大の深さ=24を超えてしまい、再帰を打ち切ったところ）。 再帰の最大の深さをもっと大きくすれば、というのはすぐに思いつきますが、 今度はメモリが際限なく消費されてしまいます。後、じゃあもっと大きな地面を配置したとすれば・・・結局はいたちごっこのようです。 また、全体的に同じ割合で三角形がちらばっているシーンの場合（空間分割時には、ノードにほぼ均等に三角形が割り振られている）は、メモリ消費はUniformGridのときと同じになり、再帰の最大数を大きくすればするほど不利になります。 大きな三角形が含まれれば分割すればいい、というのもでっかいシーンにちっさいオブジェクト、の場合は通用しないですね。 ということでこのへんなんとかしよう・・・。実用的となるとやっぱりBVHかな？ !!goto 永田町（2007/08/18） 本日は涼しかったので散歩をしてました。とにかく直進、行き止まりになったらランダムに方向転換、などとやっていたら道が分からなくなりまして、気がついたら国会議事堂にたどりついてました。 家からでも国会までいけることが発覚、いい収穫になりました（３時間は歩いたけど・・・）。前はこれで六本木ヒルズにたどりついたのですが、、、おっかしいなぁ、また迷ったか・・・。東京を南から横断して真ん中あたりに来たことになります。 体力は有り余ってたので、もうちょっと無理をすると東京外にいけるかもしれないですね。 で、国会議事堂前にナイスな公園っぽいのがありまして「国会前庭」というそうです。 入っていいのか分からなかったのですが、公園好きにとってはこれは絶好の機会。 「無料」って書いてましたので入ってみました（門は半開きだったのですが気にしない！！）。 {{ref_image kokkai_01.jpg}} 写りはよくないのですが、いつもの携帯写真のページに。 http://ft-lab.ne.jp/photo/kokkai.html しかし、誰も人がいない・・・。おかげさまで自由に前庭内を散歩できました。 横に長いのですが落ち着くにはいい雰囲気です。 しかし、永田町界隈を散歩してきましたが、人が少なかったです。 バリケードをはってる警備の方がポイントごとにいらっしゃいましたが。 皇居の周りはまだ行ってないので、また行ってみることにしよう（迷ってたどり着いたので、歩いていけるかというとその自信はありません(^_^;;）。 このあたりは、東京メトロの永田町または国会議事堂前で降りるとすぐです。 帰りは電車で帰りました。東京は迷っても少しすると電車が見つかるので便利ですね。 なので、わざと迷って遊んでます(^_^;;。 !!コミック（2007/08/14） ケロロ軍曹のコミックにて購入してないのを数冊買ったら14巻がだぶってしまった・・・。一度買ったのを再び購入してしまうのはたまにやっちゃいますね〜〜。 昔は店頭でも中身を見ることができたので確認はできたのですが、今はほとんどパラ見もできないので、このへんのミスに陥りやすいです(^_^;;。 （中身みても間違えるもんは間違えるんですけど・・・） 後、もう出ないかと思っていた「月姫」の5巻が出ていたので買ってきました。 内容がなかなか進展しないので、、、ゲーム買おうかなぁ。というか、TYPE-MOONのはどこで売ってるんでしょう・・・（コミケはのぞいて）。 と、ひさびさの書き込みでどうでもいい話から入ったのですが、 （仕事では割り切るのでいいのですが）モノを造ることを最近してないなぁという焦りがあります。 仕事の都合上、いろいろ情報公開できないのもあるのですけどそれ以外で行動するための自身のキャパがないのがなんとも。 !!kd-treeでの深さ（2007/08/02） 速いから、と思って深さの制限を上げたら構築時間はそんな変わらないのですがメモリを某大に消費。 約120万ポリゴン（実際はポリゴンではないのですが）で再帰の深さの最大を18くらいにしたら、80MBくらい使ってるじゃないですか。でも、これで構築は8秒ほど（Celeron 1GHzのノートPCにて）。ここで深さを最大14にしたらレンダリング時間が4倍に膨れ上がりました・・・。ただ、メモリ消費は約半分に。 速度を取るかメモリを取るか以前に、無駄に再帰を繰り返している部分もあるかな、もうちょっと再帰から抜けるアルゴリズムを考えたほうがいいか・・・。というか、再帰を使わずに独自スタックで実装したほうが利口かなぁ、展開はできますよね。後、ツリーノード自身も結構メモリ消費の原因になってる予感。1000万ポリくらいを512MB以内のメモリ上で扱いたいもんです。まだファイルキャッシュに逃げるのは早い（苦笑）、ということで最適化中。その前に仕様に沿った部分をまず実装しないと＜自分。