スキャンラインに沿って半径を計算する反復的な方法はありますか？

StackOverflow https://stackoverflow.com/questions/1423918

質問

すべてのY値は同じですが、X値が異なる一連のポイントを処理しています。 Xを1つ増やしてポイントを通過します。たとえば、Y = 50で、Xが-30〜30の整数である場合があります。アルゴリズムの一部には、各ポイントから原点までの距離を検出し、さらに処理することが含まれます。

プロファイリングの後、距離計算のsqrt呼び出しにかなりの時間がかかっていることがわかりました。距離を計算する反復的な方法はありますか？

言い換えれば：

効率的に計算したい：r[n] = sqrt(x[n]*x[n] + y*y))。前の反復からの情報を保存できます。各反復は、xをインクリメントすることにより変化するため、x[n] = x[n-1] + 1です。 sqrt関数またはtrig関数は、各スキャンラインの開始時を除いて遅すぎるため使用できません。

十分な精度（0.l％未満の誤差）であり、導入された誤差が滑らかである限り（近似の事前計算テーブルにビンできない）、近似を使用できます。

追加情報： xとyは常に-150〜150の整数です

明日いくつかのアイデアを試し、どちらが最も速いかに基づいてベストアンサーをマークします。

結果

タイミングを調整しました

  • 距離の式：16 ms /反復
  • Peteの相互ソリューション：8 ms /反復
  • wrang-wrang事前計算ソリューション：8ms /繰り返し

私は両方の答えが好きなので、テストが2つの間で決定することを望んでいました。メモリ使用量が少ないため、Pete'sを使用します。

役に立ちましたか？

解決

その感覚をつかむために、あなたの範囲y = 50に対して、x = 0はr = 50とy = 50を与え、x = +/- 30はr〜= 58.3を与えます。 +/- 0.1％または+/- 0.05絶対値に適した近似が必要です。これは、ほとんどのライブラリsqrtが行うよりもはるかに低い精度です。

2つの近似アプローチ-前の値からの補間に基づいてrを計算するか、適切なシリーズのいくつかの項を使用します。

前のrからの補間

r =（x 2 + y 2 ） 1/2

dr / dx = 1/2。 2x （x 2 + y 2 ） -1/2 = x / r 

    double r = 50;

    for ( int x = 0; x <= 30; ++x ) {

        double r_true = Math.sqrt ( 50*50 + x*x );

        System.out.printf ( "x: %d r_true: %f r_approx: %f error: %f%%\n", x, r, r_true, 100 * Math.abs ( r_true - r ) / r );

        r = r + ( x + 0.5 ) / r; 
    }

与える：

x: 0 r_true: 50.000000 r_approx: 50.000000 error: 0.000000%
x: 1 r_true: 50.010000 r_approx: 50.009999 error: 0.000002%
....
x: 29 r_true: 57.825065 r_approx: 57.801384 error: 0.040953%
x: 30 r_true: 58.335225 r_approx: 58.309519 error: 0.044065%

0.1％のエラーの要件を満たしていると思われるため、かなり多くの計算ステップが必要になるため、次のエラーをコーディングする必要はありませんでした。

切り捨てられたシリーズ

ゼロに近いxのsqrt（1 + x）のテイラー級数は

sqrt（1 + x）= 1 + 1/2 x-1/8 x 2 ... +（-1/2） n + 1 x n

r = y sqrt（1 +（x / y） 2 ）を使用して、用語t =（-1/2） n + 1 0.36 n （0.001未満、log（0.002）<！> gt; n log（0.18）またはn <！> gt; 3.6なので、x ^ 4に用語をとっても大丈夫です。

他のヒント

Y=10000
Y2=Y*Y
for x=0..Y2 do
  D[x]=sqrt(Y2+x*x)

norm(x,y)=
  if (y==0) x
  else if (x>y) norm(y,x) 
  else {
     s=Y/y
     D[round(x*s)]/s
  }

座標が滑らかな場合、アイデアは線形補間で拡張できます。より正確にするには、Yを増やします。

アイデアは、s *（x、y）がy = Yの線上にあり、距離を事前に計算したことです。距離を取得し、それをsで割ります。

あなたは本当にその正方形ではなく距離を必要とする と思います。

速度の精度を犠牲にする一般的なsqrt実装を見つけることもできますが、FPUの機能を破ることを想像するのは困難です。

線形補間により、D[round(x)]を次のように変更します：

f=floor(x)
a=x-f
D[f]*(1-a)+D[f+1]*a

これは実際にはあなたの質問には答えませんが、役立つかもしれません...

最初に尋ねる質問は次のとおりです。

  • <！> quot; sqrtは必要ですか？<！> quot;。
  • <！> quot;そうでない場合、どうすればsqrtsの数を減らすことができますか？<！> quot;
  • then yours：<！> quot;残りのsqrtsを賢い計算で置き換えることはできますか？<！> quot;

だから私は始めます：

  • 正確な半径が必要ですか、それとも半径の2乗が許容されますか？ sqrtには高速な近似がありますが、おそらく仕様に対して十分に正確ではありません。
  • ミラー化された象限または8分の1を使用して画像を処理できますか？バッチで同じ半径値のすべてのピクセルを処理することにより、計算の数を8倍減らすことができます。
  • 半径の値を事前に計算できますか？必要なのは、処理している画像のサイズの4分の1（または8分の1）のテーブルのみで、テーブルは一度だけ事前に計算して、アルゴリズムの多くの実行に再利用するだけで済みます。

したがって、賢い数学は最速の解決策ではないかもしれません。

さて、あなたのsqrtを常に最適化しようとしています。私が見た最速のものは、古いカーマック地震3 sqrtです：

http://betterexplained.com/articles/understanding- quakes-fast-inverse-square-root /

とはいえ、sqrtは非線形であるため、結果を得るために線に沿って単純な線形補間を行うことはできません。テーブルルックアップを使用することをお勧めします。これにより、データへの高速アクセスが可能になります。また、整数で繰り返し処理しているように見えるため、テーブル検索は非常に正確である必要があります。

さて、x = 0を中心にミラーリングして開始できます（n <！> gt; = 0を計算し、それらの結果を対応するn <！> lt; 0に複製するだけで済みます）。その後、sqrt（a ^ 2 + b ^ 2）（または対応するsin）の導関数を使用して定数dxを利用する方法を見ていきます。

それが十分に正確でない場合、これはSIMDにとって非常に良い仕事であり、SSEとVMX（およびシェーダーモデル2）の両方の逆数平方根演算を提供することを指摘できますか。

これは、 HAKMEMアイテムに関連しています。

  

ITEM 149（ミンスキー）：CIRCLE ALGORITHM   ここにほとんどを描くエレガントな方法があります   ポイントプロット表示上の円：

NEW X = OLD X - epsilon * OLD Y
NEW Y = OLD Y + epsilon * NEW(!) X
     

これは非常に丸い楕円を作ります   サイズと原点を中心に   初期点によって決定されます。   イプシロンは角度を決定します   循環点の速度、および   偏心にわずかに影響します。もし   イプシロンは2のべき乗です。   乗算も必要です   平方根、正弦、余弦！の   <！> quot; circle <！> quot;完全に安定します   ポイントがすぐになるため   定期的。

     

サークルアルゴリズムは、   保存しようとしたときの間違い   ディスプレイハックに登録してください！ベン・ガーリー   のみを使用して驚くべきディスプレイハックがありました   約6つか7つの指示、および   それは素晴らしい驚きでした。しかし、それは   基本的に行指向です。それが発生しました   わくわくする   曲線があり、私は取得しようとしていた   最小限の曲線表示ハック   手順。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top