myara CG blog

CG Design Blog. Thoughts, experiments and experiences.

SI | Find Double Edges

今日の作業にダブルエッジを探すツールが欲しかったですけど、ないですね。

確かに一ヶ月前ごろにTweeterでLand_Yさんがダブルエッジのスクリプトについてつぶやいていたことを思い出しました。
ん~ハードディスクの中を探ってみても・・・ない!!

でもググったら出てきました。よかった ( ̄▽ ̄)

Land_Yさんが言ってたスクリプトはこれです:
https://groups.google.com/group/xsi_list/browse_thread/thread/1e34cc42e5b87de9

確かに、ダブルエッジを見つけてくれるんですけど、ハイポリで使うとめちゃめちゃ遅い!
作者もそれで悩んでいたそうです。

3914ポリのキューブで 3914ミリ秒

なんとかならないか~と思って、色々考えながらていじってみました。

話を短くすると

3914ミリ秒 から 49ミリ秒 に タイミングが減らせました !

良かったら

DOWNLOAD




スクリプト解説

元のスクリプトの仕組み:

・オブジェクトのエッジを取得
・エッジのポイントを1つずつ他のエッジと比べて、同じポイントを持っていたら→ダブルエッジ発見!
・発見したダブルエッジをコレクションにまとめる


実験のキューブは:
3584ポリ ・ 3616エッジ ・ 1810ポイント

普通のキューブにサブディブジョンをかけて、1面を切り離してマージしただけです。


このキューブのエッジとエッジを比べると、3616エッジを3615と比べることになるので 13071840 周 もループしているということですね。

これじゃ、遅いですね。


エッジとエッジを比べるしかないと思いますが、予めに怪しいエッジだけをとっておいて、このエッジだけを比べたら速くなるんじゃない?!


でもどうやって・・・?


少し考えてみると、普通のポイントにエッジ3本ぐらいしかありません。
一方、ダブルエッジの場合は、ポイントに最低でも5本があります。

これでいけるんじゃない?


ポイントでループして、ポイントの隣に5エッジ以上がある場合、そのエッジをコレクションに入れておきます。
これで1810周ループして、怪しいエッジのコレクションの出来上がりです。


この実験のキューブの場合は 83エッジ まで絞れました。
その後、83エッジを82エッジと比べるので、6806周です。
合計 8616周 です。


まぁ、単純な計算ではないけど、これでなんとなく分かりやすいじゃないかな。


うん、これで良い。ただし、このキューブを全部三角形にすると、最初のエッジフィルターでほとんどのエッジが引っかかってしまう為大した差が出ないかもしれません。

では、実験:

元のスクリプト:8715ミリ秒
俺のバージョン:6616ミリ秒

25%ぐらい速いから結構良い結果だと思うけど、四角形の結果と比べたらね…。

でも、遅くなってはいないからOKです。


因みに、元のスクリプトのforループのlengthを変数にとっておくと多少速くなります。


元のスクリプト:
実験のキューブで: 3914ミリ秒 から 3454ミリ秒
三角形化された後: 8715ミリ秒 カラ 7680ミリ秒

やっぱり、変わりますね。


はい、以上!
仕事に戻りま~す。


今日の作業には遅いスクリプトで十分だったんですけどね・・・ついに。