Morton ordering

morton.go

package main

import "fmt"

// A Morton code (aka z-order) interleaves the individual bits of X & Y
// coordinates. Below are routines that show how to generate a Morton
// code from X & Y integer coordinates in range [0,31) and do the reverse.
// The goal of these routines is to be educational (primarily me) and
// are not optimal. A diagram showing how Morton codes cover a 2D space
// would be nice...

// Recover X & Y components from the Morton code
func xyFromMortonCode(code int) (int, int) {
	//        000000yxyxyxyxyx
	// x mask 0000000101010101 = 0x155
	//        000000000000000x = 0000000x0x0x0x0x & 0x001
	//        000000000000000x = 000000000000000x >> 0
	//        0000000000000x00 = 0000000x0x0x0x0x & 0x004
	//        00000000000000x0 = 0000000000000x00 >> 1
	//        00000000000x0000 = 0000000x0x0x0x0x & 0x010
	//        0000000000000x00 = 00000000000x0000 >> 2
	//        000000000x000000 = 0000000x0x0x0x0x & 0x040
	//        000000000000x000 = 000000000x000000 >> 3
	//        0000000x00000000 = 0000000x0x0x0x0x & 0x100
	//        00000000000x0000 = 0000000x00000000 >> 4
	xBits := code & 0x155
	x := (xBits&0x001)>>0 |
		(xBits&0x004)>>1 |
		(xBits&0x010)>>2 |
		(xBits&0x040)>>3 |
		(xBits&0x100)>>4

	//        000000yxyxyxyxyx
	// y mask 0000001010101010 = 0x2AA
	//        00000000000000y0 = 000000y0y0y0y0y0 & 0x002
	//        000000000000000y = 00000000000000y0 >> 1
	//        000000000000y000 = 000000y0y0y0y0y0 & 0x008
	//        00000000000000y0 = 000000000000y000 >> 2
	//        0000000000y00000 = 000000y0y0y0y0y0 & 0x020
	//        0000000000000y00 = 0000000000y00000 >> 3
	//        00000000y0000000 = 000000y0y0y0y0y0 & 0x080
	//        000000000000y000 = 00000000y0000000 >> 4
	//        000000y000000000 = 000000y0y0y0y0y0 & 0x200
	//        00000000000y0000 = 000000y000000000 >> 5
	yBits := code & 0x2AA
	y := (yBits&0x002)>>1 |
		(yBits&0x008)>>2 |
		(yBits&0x020)>>3 |
		(yBits&0x080)>>4 |
		(yBits&0x200)>>5

	return x, y
}

// Generate the Morton code for the co-ordinate pair
func mortonCodeFromXY(x, y int) int {
	// Input
	//        00000000000xxxxx
	//        00000000000yyyyy
	// Output
	//        000000yxyxyxyxyx

	// 00000000000xxxxx
	// 000000000000000x = 00000000000xxxxx & 0x001
	// 000000000000000x = 000000000000000x << 0
	// 00000000000000x0 = 00000000000xxxxx & 0x002
	// 0000000000000x00 = 00000000000000x0 << 1
	// 0000000000000x00 = 00000000000xxxxx & 0x004
	// 00000000000x0000 = 0000000000000x00 << 2
	// 000000000000x000 = 00000000000xxxxx & 0x008
	// 000000000x000000 = 000000000000x000 << 3
	// 00000000000x0000 = 00000000000xxxxx & 0x010
	// 0000000x00000000 = 00000000000x0000 << 4
	xBits := (x&0x001)<<0 |
		(x&0x002)<<1 |
		(x&0x004)<<2 |
		(x&0x008)<<3 |
		(x&0x010)<<4

	// 00000000000yyyyy
	// 000000000000000y = 00000000000yyyyy & 0x001
	// 00000000000000y0 = 000000000000000y << 1
	// 00000000000000y0 = 00000000000yyyyy & 0x002
	// 000000000000y000 = 00000000000000y0 << 2
	// 0000000000000y00 = 00000000000yyyyy & 0x004
	// 0000000000y00000 = 0000000000000y00 << 3
	// 000000000000y000 = 00000000000yyyyy & 0x008
	// 00000000y0000000 = 000000000000y000 << 4
	// 00000000000y0000 = 00000000000yyyyy & 0x010
	// 000000y000000000 = 00000000000y0000 << 5
	yBits := (y&0x001)<<1 |
		(y&0x002)<<2 |
		(y&0x004)<<3 |
		(y&0x008)<<4 |
		(y&0x010)<<5

	return xBits | yBits
}

func main() {
	for i := 0; i < 50; i++ {
		morton := i + 400

		//        000000yxyxyxyxyx
		x, y := xyFromMortonCode(morton)
		fmt.Printf("morton %04d (0b%012b): x = %02d (0b%012b), y = %02d (0b%012b)\n", morton, morton, x, x, y, y)
		morton2 := mortonCodeFromXY(x, y)
		fmt.Printf("morton %04d (0b%012b): morton2 %04d (0b%012b)\n", morton, morton, morton2, morton2)
	}
}