5

与えられた横軸xにある線上の点の縦座標yを計算しています。線は、その2つの端点座標（x0、y0）（x1、y1）によって定義されます。終点の座標は浮動小数点数であり、GPUで使用するには、計算を浮動小数点精度で実行する必要があります。

数学、したがって素朴な実装は簡単です。

t =（x-x0）/（x1-x0）とすると、y =（1-t）* y0 + t * y1 = y0 + t *（y1-y0）となります。

問題は、x1-x0が小さい場合です。その結果、キャンセルエラーが発生します。x-x0のいずれかと組み合わせると、除算でtに重大なエラーが発生すると予想されます。

問題は、より正確にyを決定する別の方法があるかどうかです。

つまり、最初に（x --x0）*（y1 --y0）を計算し、その後（x1 --x0）で除算する必要がありますか？

y1-y0の差は常に大きくなります。

4

8 に答える 8

3

大部分は、根本的な問題が根本的なものです。(x1-x0) が小さい場合、x1 と x0 の仮数部に異なるビットが数ビットしかないことを意味します。さらに、x0 と x1 の間の float の数は限られています。たとえば、仮数の下位 4 ビットのみが異なる場合、それらの間に最大 14 の値があります。

あなたの最良のアルゴリズムでは、t用語はこれらの下位ビットを表します。さらに、たとえば、x0 と x1 が 4 ビット異なる場合、t も 16 個の値しか取りません。これらの可能な値の計算はかなり堅牢です。3E0/14E0 と 3E-12/14E-12 のどちらを計算しても、結果は 3/14 の数値に近くなります。

式には、0 <= t <= 1 であるため、y0 <= y <= y1 であるという追加の利点があります。

(float 表現について十分に理解していると仮定しているため、「(x1-x0) が小さい」というのは、「x1 と x0 自体の値に比べて小さい」という意味です。x0 の場合、1E-1 の差は小さいです。 =1E3 でも x0=1E-6 の場合は大きい)

于 2009-05-22T08:52:57.653 に答える
2

Qt の "QLine" (私の記憶が正しければ) のソースを参照してください。彼らは、「Graphics Gems」の本の 1 つから取られた交差決定アルゴリズムを実装しました (参照はコード コメントにある必要があります。この本は数年前に EDonkey にありました)。指定されたビット幅で計算が実行される場合の指定された画面解像度（私が間違っていなければ、固定小数点演算を使用します）。

于 2009-05-22T10:11:08.260 に答える
1

それを行う可能性がある場合は、abs（x1-x0）<abs（y1-y0）に応じて、計算に2つのケースを導入できます。垂直の場合、abs（x1-x0）<abs（y1-y0）の場合、xからyを計算するのではなく、yからxを計算します。

編集。別の可能性は、二分検索の変形を使用してビットごとに結果を取得することです。これは遅くなりますが、極端な場合には結果が改善される可能性があります。

// Input is X
xmin = min(x0,x1);
xmax = max(x0,x1);
ymin = min(y0,y1);
ymax = max(y0,y1);
for (int i=0;i<20;i++) // get 20 bits in result
{
  xmid = (xmin+xmax)*0.5;
  ymid = (ymin+ymax)*0.5;
  if ( x < xmid ) { xmax = xmid; ymax = ymid; } // first half
  else { xmin = xmid; ymin = ymid; } // second half
}
// Output is some value in [ymin,ymax]
Y = ymin;
于 2009-05-22T08:10:02.980 に答える
0

x0とx1の間の距離が小さいかどうか、つまりfabs（x1-x0）<epsかどうかを確認します。次に、線は座標系のy軸に平行になります。つまり、xに応じてその線のy値を計算することはできません。y値は無限にあるため、このケースを別の方法で処理する必要があります。

于 2009-05-22T08:20:30.213 に答える
0

ソースデータがすでに浮動小数点数である場合、根本的な不正確さがあります。

さらに説明するために、これをグラフィカルに行っていると想像してください。方眼紙の 2D シートがあり、2 つの点がマークされています。

ケース 1: これらのポイントは非常に正確で、非常に鋭い鉛筆でマークされています。それらを結ぶ線を引くのは簡単で、x から y を取得するのは簡単です (またはその逆)。

ケース 2: これらのポイントは、ビンゴ マーカーのような大きな太いフェルト ペンでマークされています。明らかに、あなたが描く線はあまり正確ではありません。スポットの中心を通りますか？上端？下端？一方の上、他方の下？明らかに、多くの異なるオプションがあります。2 つの点が互いに接近している場合、変動はさらに大きくなります。

浮動小数点数には、数値を表す方法が原因で、特定のレベルの不正確さが内在しています。そのため、ケース 1 よりもケース 2 に対応します (これは、任意精度のライブラリを使用することと同等であると示唆できます)。世界中のどのアルゴリズムもそれを補うことができません。不正確なデータ入力、不正確なデータ出力

于 2009-05-22T08:13:19.837 に答える
0

MSalters が言ったように、問題は既に元のデータにあります。

内挿/外挿には傾きが必要ですが、特定の条件ではすでに精度が低いです (原点から離れた非常に短い線分では最悪です)。

アルゴリズムを選択しても、この精度の低下を取り戻すことはできません。私の直感では、誤差は除算ではなく減算によって導入されるため、異なる評価順序で物事が変わることはありません。

アイデア:
線が生成されたときにより正確なデータがある場合は、表現を ((x0, y0), (x1, y1)) から (x0,y0, 角度, 長さ) に変更できます。角度または勾配を保存できます。勾配には極がありますが、角度には三角関数が必要です...醜いです。

もちろん、エンドポイントが頻繁に必要であり、追加のデータを保存できないほど多くの行がある場合、それは機能しません。私にはわかりません。しかし、あなたのニーズに合った別の表現があるかもしれません。

double はほとんどの状況で十分な解像度を持っていますが、ワーキング セットも 2 倍になります。

于 2009-05-22T11:22:51.267 に答える
0

次のようなものを計算するのはどうですか：

t = sign * power2 ( sqrt (abs(x - x0))/ sqrt (abs(x1 - x0)))

アイデアは、低い (x1-x0) の影響が少ない数学的な同等の式を使用することです。（私が書いたものがこの基準に一致するかどうかはわかりません）

于 2009-05-22T09:22:49.370 に答える