高速化のテクニック

質問

プログラムを高速化するためのテクニック集を探していますがサイト、書籍ともなかなか見つかりません。特に図形のレンダリング（直線や曲線をイメージデータとして生成する）の高速アルゴリズムを探しています。ちなみに、Bresenham程度なら知っています。他にも乗算や割り算を高速化するための方法とかでもいいので、高速化するためのテクニックが載っているサイト、書籍をご存知でしたら教えてください。

回答No.1

amru05 · ベストアンサー

以下のサイトはなかなか優れものですね。非常に参考になるのではと、思います。

http://www2.starcat.ne.jp/~fussy/algo/index.htm

本では、
１）GAME PROGRAMMING
に、「テンプレートメタプログラミングを使った高速数値演算」「3角関数の多項式近似」が有ります。
２）GAME PROGRAMMING２
　　に「不動少数点トリック：ＩＥＥＥ不動書数点でのパーフォマンス向上」が有ります。
３）GAME PROGRAMMING３
　　に「さらなる3角関数近似」があります
４）高速３Ｄグラフィックス
　　に「3次元数学の魔術」があります。

大体、以下のような方針で高速化するのが常套手段？
１）三角関数などは級数展開や、テーブルを使用して近似計算で代用する
２）場合わけをして簡単な計算をなるべく使用する
　　水平、垂直の場合は簡単に処理する
　　斜め45度も簡単に、それ以外は通常の計算。。など
３）割り算のかわりに掛け算を使用する。
４）必要な精度がとれるなら固定小数点計算を使用する
５）無駄な方変換を行わない（整数、実数の混在はＸ）
６）CPUの特性に応じた計算を行う
　。。。。
＝＝＞
　「ゲーム」関係の本に「高速化」の話が良く出ているように感じます。「ゲーム」で検索してみるのも良いかも知れません。

お礼

まさに私の探していたサイトです。
直線を両端からかくとか、目から鱗がとれました。
教えていただいた高速化手法も参考にさせていただきます。
確かにリアルタイム性が要求されるゲームプログラムは高速化
技術が必須になりますね。
でも高速化のテクニックは重要なノウハウだからか、なかなか書籍
とかで公表されてないようです。
ちなみに私がよく使う・知っている方法は
・演算結果をテーブルとして持っておく
・ループの中身を展開する
・除算は行わず1/xを2^n倍した整数テーブルとの掛け算＋シフトで行う
・水平垂直方向の線分描画は座標計算行わず単純なforループで行う
・Bresenhamによる直線楕円描画アルゴリズム
・double,floatは使わず固定小数点演算で代用する
・無駄なメモリアクセスは削減する。
・ADD計算を減らすため*ptr++;の乱用は避ける（ptr[base_index+offset]で置き換え）

ぐらいです。
型変換は意識したことありませんでしたが、確かに無駄な処理が
増えそうですね。特に理由がなければintで統一していたほうが
いいのでしょうね。
ありがとうございました。