KiCad PCB EDA Suite
mortoncodes.cpp File Reference

Implements Morton Codes base on the implementation of Fabian “ryg” Giesen https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/. More...

#include "mortoncodes.h"

Go to the source code of this file.

Functions

uint32_t Part1By1 (uint32_t x)
 
uint32_t Part1By2 (uint32_t x)
 
uint32_t Compact1By1 (uint32_t x)
 
uint32_t Compact1By2 (uint32_t x)
 
uint32_t EncodeMorton2 (uint32_t x, uint32_t y)
 
uint32_t EncodeMorton3 (uint32_t x, uint32_t y, uint32_t z)
 
uint32_t DecodeMorton2X (uint32_t code)
 
uint32_t DecodeMorton2Y (uint32_t code)
 
uint32_t DecodeMorton3X (uint32_t code)
 
uint32_t DecodeMorton3Y (uint32_t code)
 
uint32_t DecodeMorton3Z (uint32_t code)
 

Detailed Description

Implements Morton Codes base on the implementation of Fabian “ryg” Giesen https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/.

Definition in file mortoncodes.cpp.

Function Documentation

◆ Compact1By1()

uint32_t Compact1By1 ( uint32_t  x)

Definition at line 61 of file mortoncodes.cpp.

62{
63 x &= 0x55555555; // x = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
64 x = ( x ^ ( x >> 1 ) ) & 0x33333333; // x = --fe --dc --ba --98 --76 --54 --32 --10
65 x = ( x ^ ( x >> 2 ) ) & 0x0f0f0f0f; // x = ---- fedc ---- ba98 ---- 7654 ---- 3210
66 x = ( x ^ ( x >> 4 ) ) & 0x00ff00ff; // x = ---- ---- fedc ba98 ---- ---- 7654 3210
67 x = ( x ^ ( x >> 8 ) ) & 0x0000ffff; // x = ---- ---- ---- ---- fedc ba98 7654 3210
68
69 return x;
70}

Referenced by DecodeMorton2X(), and DecodeMorton2Y().

◆ Compact1By2()

uint32_t Compact1By2 ( uint32_t  x)

Definition at line 74 of file mortoncodes.cpp.

75{
76 x &= 0x09249249; // x = ---- 9--8 --7- -6-- 5--4 --3- -2-- 1--0
77 x = ( x ^ ( x >> 2 ) ) & 0x030c30c3; // x = ---- --98 ---- 76-- --54 ---- 32-- --10
78 x = ( x ^ ( x >> 4 ) ) & 0x0300f00f; // x = ---- --98 ---- ---- 7654 ---- ---- 3210
79 x = ( x ^ ( x >> 8 ) ) & 0xff0000ff; // x = ---- --98 ---- ---- ---- ---- 7654 3210
80 x = ( x ^ ( x >> 16 ) ) & 0x000003ff; // x = ---- ---- ---- ---- ---- --98 7654 3210
81
82 return x;
83}

Referenced by DecodeMorton3X(), DecodeMorton3Y(), and DecodeMorton3Z().

◆ DecodeMorton2X()

uint32_t DecodeMorton2X ( uint32_t  code)

Definition at line 98 of file mortoncodes.cpp.

99{
100 return Compact1By1( code >> 0 );
101}
uint32_t Compact1By1(uint32_t x)
Definition: mortoncodes.cpp:61

References Compact1By1().

Referenced by RENDER_3D_RAYTRACE::initializeBlockPositions().

◆ DecodeMorton2Y()

uint32_t DecodeMorton2Y ( uint32_t  code)

Definition at line 104 of file mortoncodes.cpp.

105{
106 return Compact1By1( code >> 1 );
107}

References Compact1By1().

Referenced by RENDER_3D_RAYTRACE::initializeBlockPositions().

◆ DecodeMorton3X()

uint32_t DecodeMorton3X ( uint32_t  code)

Definition at line 110 of file mortoncodes.cpp.

111{
112 return Compact1By2( code >> 0 );
113}
uint32_t Compact1By2(uint32_t x)
Definition: mortoncodes.cpp:74

References Compact1By2().

◆ DecodeMorton3Y()

uint32_t DecodeMorton3Y ( uint32_t  code)

Definition at line 116 of file mortoncodes.cpp.

117{
118 return Compact1By2( code >> 1 );
119}

References Compact1By2().

◆ DecodeMorton3Z()

uint32_t DecodeMorton3Z ( uint32_t  code)

Definition at line 122 of file mortoncodes.cpp.

123{
124 return Compact1By2( code >> 2 );
125}

References Compact1By2().

◆ EncodeMorton2()

uint32_t EncodeMorton2 ( uint32_t  x,
uint32_t  y 
)

Definition at line 86 of file mortoncodes.cpp.

87{
88 return ( Part1By1( y ) << 1 ) + Part1By1( x );
89}
uint32_t Part1By1(uint32_t x)
Definition: mortoncodes.cpp:35

References Part1By1().

◆ EncodeMorton3()

uint32_t EncodeMorton3 ( uint32_t  x,
uint32_t  y,
uint32_t  z 
)

Definition at line 92 of file mortoncodes.cpp.

93{
94 return ( Part1By2( z ) << 2 ) + ( Part1By2( y ) << 1 ) + Part1By2( x );
95}
uint32_t Part1By2(uint32_t x)
Definition: mortoncodes.cpp:48

References Part1By2().

◆ Part1By1()

uint32_t Part1By1 ( uint32_t  x)

Definition at line 35 of file mortoncodes.cpp.

36{
37 x &= 0x0000ffff; // x = ---- ---- ---- ---- fedc ba98 7654 3210
38 x = ( x ^ ( x << 8 ) ) & 0x00ff00ff; // x = ---- ---- fedc ba98 ---- ---- 7654 3210
39 x = ( x ^ ( x << 4 ) ) & 0x0f0f0f0f; // x = ---- fedc ---- ba98 ---- 7654 ---- 3210
40 x = ( x ^ ( x << 2 ) ) & 0x33333333; // x = --fe --dc --ba --98 --76 --54 --32 --10
41 x = ( x ^ ( x << 1 ) ) & 0x55555555; // x = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
42
43 return x;
44}

Referenced by EncodeMorton2().

◆ Part1By2()

uint32_t Part1By2 ( uint32_t  x)

Definition at line 48 of file mortoncodes.cpp.

49{
50 x &= 0x000003ff; // x = ---- ---- ---- ---- ---- --98 7654 3210
51 x = ( x ^ ( x << 16 ) ) & 0xff0000ff; // x = ---- --98 ---- ---- ---- ---- 7654 3210
52 x = ( x ^ ( x << 8 ) ) & 0x0300f00f; // x = ---- --98 ---- ---- 7654 ---- ---- 3210
53 x = ( x ^ ( x << 4 ) ) & 0x030c30c3; // x = ---- --98 ---- 76-- --54 ---- 32-- --10
54 x = ( x ^ ( x << 2 ) ) & 0x09249249; // x = ---- 9--8 --7- -6-- 5--4 --3- -2-- 1--0
55
56 return x;
57}

Referenced by EncodeMorton3().