KiCad PCB EDA Suite
mortoncodes.cpp File Reference

Implementes 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

Implementes 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

uint32_t Compact1By1 ( uint32_t  x)

Definition at line 61 of file mortoncodes.cpp.

Referenced by DecodeMorton2X(), and DecodeMorton2Y().

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 }
uint32_t Compact1By2 ( uint32_t  x)

Definition at line 74 of file mortoncodes.cpp.

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

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 }
uint32_t DecodeMorton2X ( uint32_t  code)

Definition at line 98 of file mortoncodes.cpp.

References Compact1By1().

Referenced by C3D_RENDER_RAYTRACING::initialize_block_positions().

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

Definition at line 104 of file mortoncodes.cpp.

References Compact1By1().

Referenced by C3D_RENDER_RAYTRACING::initialize_block_positions().

105 {
106  return Compact1By1( code >> 1 );
107 }
uint32_t Compact1By1(uint32_t x)
Definition: mortoncodes.cpp:61
uint32_t DecodeMorton3X ( uint32_t  code)

Definition at line 110 of file mortoncodes.cpp.

References Compact1By2().

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

Definition at line 116 of file mortoncodes.cpp.

References Compact1By2().

117 {
118  return Compact1By2( code >> 1 );
119 }
uint32_t Compact1By2(uint32_t x)
Definition: mortoncodes.cpp:74
uint32_t DecodeMorton3Z ( uint32_t  code)

Definition at line 122 of file mortoncodes.cpp.

References Compact1By2().

123 {
124  return Compact1By2( code >> 2 );
125 }
uint32_t Compact1By2(uint32_t x)
Definition: mortoncodes.cpp:74
uint32_t EncodeMorton2 ( uint32_t  x,
uint32_t  y 
)

Definition at line 86 of file mortoncodes.cpp.

References Part1By1().

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

Definition at line 92 of file mortoncodes.cpp.

References Part1By2().

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

Definition at line 35 of file mortoncodes.cpp.

Referenced by EncodeMorton2().

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 }
uint32_t Part1By2 ( uint32_t  x)

Definition at line 48 of file mortoncodes.cpp.

Referenced by EncodeMorton3().

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 }