c++ - フロートを使用した 2D ポイントからのモートン インデックス

Question

次のような 2D ポイントがあります。

class Point
{
    float m_x, m_y;

public:

    int mortonIndex()
    {
        // what would go here?
    }
};

整数をどうするかはわかっていますが、浮動小数点数を使用する必要があります。また、特定のグリッド サイズのスケーリングも避けたいと考えています。

ウィキペディアの関連ページ:

モートン インデックス、または Z オーダー カーブ

Answer 1

これには、次の 2 つの方法があります。

• 256 ビットの数値である「float」(または同様に、[ここ][1] で実装された 2100 ビットの数値としての「double」)。
• 奇妙な 32 ビット整数である「float」。

実装が簡単なので、後者を使用します。

このアプローチは、IEEEfloatがもともと古い整数のみのデータベース エンジンと互換性を持つように設計されているという事実を利用しており、浮動小数点数を 1 の補数の整数として扱うことができます。

より正確には、1 の補数の意味で、浮動小数点値の順序付けは、同じ幅の整数の順序付けを尊重します (実際、しゃれた浮動小数点数に直接 1 を追加すると、隣接する値の絶対値が大きくなります**)。

class Point
{
    float m_x, m_y;

    // This assert is not correct when the floating point model
    // is not IEEE-compliant, float is not 32-bit, or both.
    //
    // Such things are hard to find, so we'll just assume
    // mostly-sane hardware.
    //
    static_assert(
        (sizeof(int) == sizeof(float)) &&
        (sizeof(int)*CHAR_BIT == 32) &&
        (sizeof(long long)*CHAR_BIT == 64),
        "We need 32-bit ints and floats, and 64-bit long longs!"
        );

public:

    // So we don't lose any information, we need 2x the width.
    // After all, we're cramming two 32-bit numbers into a single value.
    // Lossiness here would mean a container would need to implement
    // a binning strategy.
    //
    // Higher dimensions would require an array, obviously.
    //
    // Also, we're not going to modify the point, so make this a const routine.
    //
    long long mortonIndex() const
    {
        // Pun the x and y coordinates as integers: Just re-interpret the bits.
        //
        auto ix = reinterpret_cast<const unsigned &>(this->m_x);
        auto iy = reinterpret_cast<const unsigned &>(this->m_y);

        // Since we're assuming 2s complement arithmetic (99.99% of hardware today),
        // we'll need to convert these raw integer-punned floats into
        // their corresponding integer "indices".

        // Smear their sign bits into these for twiddling below.
        //
        const auto ixs = static_cast<int>(ix) >> 31;
        const auto iys = static_cast<int>(iy) >> 31;

        // This is a combination of a fast absolute value and a bias.
        //
        // We need to adjust the values so -FLT_MAX is close to 0.
        //
        ix = (((ix & 0x7FFFFFFFL) ^ ixs) - ixs) + 0x7FFFFFFFL;
        iy = (((iy & 0x7FFFFFFFL) ^ iys) - iys) + 0x7FFFFFFFL;

        // Now we have -FLT_MAX close to 0, and FLT_MAX close to UINT_MAX,
        // with everything else in-between.
        //
        // To make this easy, we'll work with x and y as 64-bit integers.
        //
        long long xx = ix;
        long long yy = iy;

        // Dilate and combine as usual...

        xx = (xx | (xx << 16)) & 0x0000ffff0000ffffLL;
        yy = (yy | (yy << 16)) & 0x0000ffff0000ffffLL;

        xx = (xx | (xx <<  8)) & 0x00ff00ff00ff00ffLL;
        yy = (yy | (yy <<  8)) & 0x00ff00ff00ff00ffLL;

        xx = (xx | (xx <<  4)) & 0x0f0f0f0f0f0f0f0fLL;
        yy = (yy | (yy <<  4)) & 0x0f0f0f0f0f0f0f0fLL;

        xx = (xx | (xx <<  2)) & 0x3333333333333333LL;
        yy = (yy | (yy <<  2)) & 0x3333333333333333LL;

        xx = (xx | (xx <<  1)) & 0x5555555555555555LL;
        yy = (yy | (yy <<  1)) & 0x5555555555555555LL;

        return xx | (yy << 1);
    }
};

結果の曲線の頂点は、2D 浮動小数点空間の位置と同じ分布を持つことに注意してください。

これをディスク上の構造で使用する場合は、座標軸または原点の近くでクラスタリングを行うと、範囲クエリがそれらの近くの多数のボックスを横切る可能性があるため、問題になる可能性があります。それ以外の場合、IMO は、均一なインデックスを生成する (そしてブランチがない!) 代わりに、合理的にパフォーマンスの高い代替手段です。

**無限大と NaN には特別な処理が必要ですが、アイデアはわかります。