Skip to content

Instantly share code, notes, and snippets.

@StagPoint
Last active May 6, 2024 15:45
Show Gist options
  • Save StagPoint/98847aabd9b1ef70ad17e9a34dda84f7 to your computer and use it in GitHub Desktop.
Save StagPoint/98847aabd9b1ef70ad17e9a34dda84f7 to your computer and use it in GitHub Desktop.
Represents 2D Morton Codes by interleaving two 16-bit unsigned integer values into a 32-bit unsigned integer.
// **************************************************
// EXAMPLE USAGE:
//
// // Returns a single value with arguments x and y interleaved
// var code = MortonCode2D.Interleave( 123, 456 );
//
// // Extracts the interleaved values (123 and 456) into integer variables x and y
// MortonCode2D.Deinterleave( code, out int x, out int y )
//
// **************************************************
// See this link for more information: https://en.wikipedia.org/wiki/Z-order_curve
public static class MortonCode2D
{
/// <summary>
/// Returns a Morton code interleaving the component-wise difference of the X and Y values from two encodings.
/// </summary>
/// <param name="z">A Morton code interleaving a 16-bit unsigned X and Y value</param>
/// <param name="w">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint TesseralSubtract( uint z, uint w )
{
uint xdiff = ( z & 0x55555555 ) - ( w & 0x55555555 );
uint ydiff = ( z & 0xAAAAAAAA ) - ( w & 0xAAAAAAAA );
return ( xdiff & 0x55555555 ) | ( ydiff & 0xAAAAAAAA );
}
/// <summary>
/// Returns a Morton code interleaving the component-wise sum of the X and Y values from two encodings.
/// </summary>
/// <param name="z">A Morton code interleaving a 16-bit unsigned X and Y value</param>
/// <param name="w">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint ComponentwiseAdd( uint z, uint w )
{
uint xsum = ( z | 0xAAAAAAAA ) + ( w & 0x55555555 );
uint ysum = ( z | 0x55555555 ) + ( w & 0xAAAAAAAA );
return ( xsum & 0x55555555 ) | ( ysum & 0xAAAAAAAA );
}
/// <summary>
/// Returns a Morton code interleaving the component-wise minimum of the X and Y values from two encodings.
/// </summary>
/// <param name="z">A Morton code interleaving a 16-bit unsigned X and Y value</param>
/// <param name="w">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint ComponentwiseMin( uint z, uint w )
{
uint xdiff = ( z & 0x55555555 ) - ( w & 0x55555555 );
uint ydiff = ( z >> 1 & 0x55555555 ) - ( w >> 1 & 0x55555555 );
uint maskx = (uint)( (int)xdiff >> 31 );
uint masky = (uint)( (int)ydiff >> 31 );
uint xmin = ( maskx & z ) | ( ~maskx & w );
uint ymin = ( masky & z ) | ( ~masky & w );
return ( xmin & 0x55555555 ) | ( ymin & 0xAAAAAAAA );
}
/// <summary>
/// Returns a Morton code interleaving the component-wise maximum of the X and Y values from two encodings.
/// </summary>
/// <param name="z">A Morton code interleaving a 16-bit unsigned X and Y value</param>
/// <param name="w">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint ComponentwiseMax( uint z, uint w )
{
uint xdiff = ( z & 0x55555555 ) - ( w & 0x55555555 );
uint ydiff = ( z >> 1 & 0x55555555 ) - ( w >> 1 & 0x55555555 );
uint maskx = (uint)( (int)xdiff >> 31 );
uint masky = (uint)( (int)ydiff >> 31 );
uint xmin = ( ~maskx & z ) | ( maskx & w );
uint ymin = ( ~masky & z ) | ( masky & w );
return ( xmin & 0x55555555 ) | ( ymin & 0xAAAAAAAA );
}
/// <summary>
/// Increments the X value in the interleaved Morton code, clamped to <paramref name="maxValue"/>
/// </summary>
/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint IncrementX_Clamped( uint code, uint maxValue )
{
uint xsum = ( ( code | 0xAAAAAAAA ) + 1 ) & 0x55555555;
uint xdiff = xsum - maxValue;
uint maskx = (uint)( (int)xdiff << 1 >> 31 );
uint xsat = ( maskx & xsum ) | ( ~maskx & maxValue );
return xsat | ( code & 0xAAAAAAAA );
}
/// <summary>
/// Increments the Y value in the interleaved Morton code, clamped to <paramref name="maxValue"/>
/// </summary>
/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint IncrementY_Clamped( uint code, uint maxValue )
{
uint ysum = ( ( code | 0x55555555 ) + 2 ) & 0xAAAAAAAA;
uint ydiff = ysum - maxValue;
uint masky = (uint)( (int)ydiff >> 31 );
uint ysat = ( masky & ysum ) | ( ~masky & maxValue );
return ysat | ( code & 0x55555555 );
}
/// <summary>
/// Decrements the X value in the interleaved Morton code, clamped to <paramref name="minValue"/>
/// </summary>
/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint DecrementX_Clamped( uint code, uint minValue )
{
uint xsum = ( ( code & 0x55555555 ) - 1 ) & 0x55555555;
uint xdiff = xsum - minValue;
uint maskx = (uint)( (int)xdiff << 1 >> 31 );
uint xsat = ( ~maskx & xsum ) | ( maskx & minValue );
return xsat | ( code & 0xAAAAAAAA );
}
/// <summary>
/// Decrements the Y value in the interleaved Morton code, clamped to <paramref name="minValue"/>
/// </summary>
/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint DecrementY_Clamped( uint code, uint minValue )
{
uint ysum = ( ( code & 0xAAAAAAAA ) - 2 ) & 0xAAAAAAAA;
uint ydiff = ysum - minValue;
uint masky = (uint)( (int)ydiff >> 31 );
uint ysat = ( ~masky & ysum ) | ( masky & minValue );
return ysat | ( code & 0x55555555 );
}
/// <summary>
/// Increments the X value in the interleaved Morton code
/// </summary>
/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint IncrementX( uint code )
{
uint xsum = ( code | 0xAAAAAAAA ) + 1;
return ( xsum & 0x55555555 ) | ( code & 0xAAAAAAAA );
}
/// <summary>
/// Increments the Y value in the interleaved Morton code
/// </summary>
/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint IncrementY( uint code )
{
uint ysum = ( code | 0x55555555 ) + 2;
return ( ysum & 0xAAAAAAAA ) | ( code & 0x55555555 );
}
/// <summary>
/// Decrements the X value in the interleaved Morton code
/// </summary>
/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint DecrementX( uint code )
{
uint xsum = ( code & 0x55555555 ) - 1;
return ( xsum & 0x55555555 ) | ( code & 0xAAAAAAAA );
}
/// <summary>
/// Decrements the Y value in the interleaved Morton code
/// </summary>
/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
public static uint DecrementY( uint code )
{
uint ysum = ( code & 0xAAAAAAAA ) - 2;
return ( ysum & 0xAAAAAAAA ) | ( code & 0x55555555 );
}
/// <summary>
/// Returns the interleaved values stored in both the odd and even bits of <paramref name="code"/>.
/// </summary>
/// <param name="code">An interleaved value, presumably returned from a prior call to <see cref="Interleave(int, int)"/></param>
/// <param name="x">Will contain the value stored in the odd bits of the interleaved value</param>
/// <param name="y">Will contain the value stored in the even bits of the interleaved value</param>
public static void Deinterleave( uint code, out uint x, out uint y )
{
x = Deinterleave( code );
y = Deinterleave( code >> 1 );
}
/// <summary>
/// Deinterleave the interleaved value and return the value stored in the odd bits.
/// Call this function with (code >> 1) to return the value stored in the even bits.
/// </summary>
/// <param name="code"></param>
/// <returns>Returns the value stored in the odd bits of <paramref name="code"/></returns>
public static uint Deinterleave( uint code )
{
// http://stackoverflow.com/questions/4909263/how-to-efficiently-de-interleave-bits-inverse-morton
code = code & 0x55555555;
code = ( code | ( code >> 1 ) ) & 0x33333333;
code = ( code | ( code >> 2 ) ) & 0x0F0F0F0F;
code = ( code | ( code >> 4 ) ) & 0x00FF00FF;
code = ( code | ( code >> 8 ) ) & 0x0000FFFF;
return code;
}
/// <summary>
/// Interleave lower 16 bits of x and y, so the bits of x are in the even positions and bits from y in the odd.
/// </summary>
/// <param name="x">A positive integer value between 0 and 65536</param>
/// <param name="y">A positive integer value between 0 and 65536</param>
/// <returns>A Morton Code with the values of X and Y interleaved into a single Integer value.</returns>
public static uint Interleave( uint x, uint y )
{
// http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
// See this post for interleaving 32-bit numbers into 64-bit result, and interesting comparisons with SIMD versions
// https://lemire.me/blog/2018/01/08/how-fast-can-you-bit-interleave-32-bit-integers/
x = ( x | ( x << 8 ) ) & 0x00FF00FF;
x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
x = ( x | ( x << 2 ) ) & 0x33333333;
x = ( x | ( x << 1 ) ) & 0x55555555;
y = ( y | ( y << 8 ) ) & 0x00FF00FF;
y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
y = ( y | ( y << 2 ) ) & 0x33333333;
y = ( y | ( y << 1 ) ) & 0x55555555;
uint z = x | ( y << 1 );
return z;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment