1

私は八分木を実装しようとしています。そのためには、高速なAABB線交差アルゴリズムが必要です。いくつか検索した後、私はそれを提供しているように見えるこの論文に出くわしました。ここで入手できるソースコードから、pluecker_cls_cff関数を次のようにC＃に変換しました。

public bool Intersect_2(ref RayPluecker r)
{
  switch (r.Classification)
  {

    // 7 same-ish cases snipped

    case Classification.PPP:

      return !((r.Position.X > this.Max.X) || (r.Position.Y > this.Max.Y) || (r.Position.Z > this.Max.Z) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Max.Y - r.Direction.Y * this.Min.X < 0) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Min.Y - r.Direction.Y * this.Max.X > 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Min.Z - r.Direction.Z * this.Max.X > 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Max.Z - r.Direction.Z * this.Min.X < 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Min.Y + r.Direction.Y * this.Max.Z < 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Max.Y + r.Direction.Y * this.Min.Z > 0));
  }

  return false;
}

これは問題なく機能しているように見えますが、私にはかなり遅いように見えたので（1,000万回の交差を行うには250ミリ秒）、さまざまな種類のマイクロベンチマークを試しました。return1つは、ステートメントの直後にある否定を削除し、すべての比較を逆>にしました（<またはその逆）。

雪が降る：

case Classification.PPP:

      return ((r.Position.X < this.Max.X) || (r.Position.Y < this.Max.Y) || (r.Position.Z < this.Max.Z) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Max.Y - r.Direction.Y * this.Min.X > 0) ||
        (r.PlueckerCoefficient.X + r.Direction.X * this.Min.Y - r.Direction.Y * this.Max.X < 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Min.Z - r.Direction.Z * this.Max.X < 0) ||
        (r.PlueckerCoefficient.Y + r.Direction.X * this.Max.Z - r.Direction.Z * this.Min.X > 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Min.Y + r.Direction.Y * this.Max.Z > 0) ||
        (r.PlueckerCoefficient.Z - r.Direction.Z * this.Max.Y + r.Direction.Y * this.Min.Z < 0));

これでも同じ結果になるはずですよね？いくつかのテストケースを含む否定バージョンと同じ結果が返されるため、そう見えました。ただし、ベンチマークでは、5倍高速でした（1,000万回の交差を実行するには50ミリ秒）。最適化されていなかったと確信しています。私のベンチマークは次のようになります。

for (int i = 0; i < 10000000; i++)
{
  if (!box.Intersect_3(ref ray))
  {
    throw new Exception();
  }
}

この大きな違いを説明できるのは何ですか？x86で.NET4.0を実行しています。

4

2 に答える 2

5

2番目のコードは最初のコードと同じことをしません。

すでに行った変更に加えて、すべてのORをANDに変換する必要があります。（ド・モルガンの法則を参照してください。）

修正を行った後、2つのバージョンが同じ速度で実行されることは間違いありません。

于 2010-09-16T23:02:04.777 に答える
0

特にパフォーマンスに関連して、2番目のケースでは最初のケースよりもreturnステートメントが早く短絡しているに違いありません。いくつかが他よりも真である可能性が高い場合は、比較の順序を変更することを試みる価値があるかもしれません。||の代わりに&&を使用して計算を同等に変更した場合 2番目のケースでは、偽である可能性が最も高いものを最初に配置する必要があります。

于 2010-09-16T23:23:26.630 に答える