{"id":149,"date":"2016-09-18T08:46:37","date_gmt":"2016-09-18T08:46:37","guid":{"rendered":"http:\/\/threadlocalmutex.com\/?p=149"},"modified":"2016-09-18T08:46:37","modified_gmt":"2016-09-18T08:46:37","slug":"lut-based-3d-hilbert-curves","status":"publish","type":"post","link":"https:\/\/threadlocalmutex.com\/?p=149","title":{"rendered":"LUT-based 3D Hilbert curves"},"content":{"rendered":"<p>As referenced in my earlier post about <a href=\"http:\/\/threadlocalmutex.com\/?p=126\">Hilbert curves<\/a>, it&#8217;s possible to map between $$d$$-dimensional Euclidean coordinates and the offset along the Hilbert curve in $$O(n)$$ time by direct application of the transformation group at each recursion level of the curve. The following applies this to the 3D case:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\nstatic const uint8_t mortonToHilbertTable&#x5B;] = {\r\n\t48, 33, 27, 34, 47, 78, 28, 77,\r\n\t66, 29, 51, 52, 65, 30, 72, 63,\r\n\t76, 95, 75, 24, 53, 54, 82, 81,\r\n\t18,  3, 17, 80, 61,  4, 62, 15,\r\n\t 0, 59, 71, 60, 49, 50, 86, 85,\r\n\t84, 83,  5, 90, 79, 56,  6, 89,\r\n\t32, 23,  1, 94, 11, 12,  2, 93,\r\n\t42, 41, 13, 14, 35, 88, 36, 31,\r\n\t92, 37, 87, 38, 91, 74,  8, 73,\r\n\t46, 45,  9, 10,  7, 20, 64, 19,\r\n\t70, 25, 39, 16, 69, 26, 44, 43,\r\n\t22, 55, 21, 68, 57, 40, 58, 67,\r\n};\r\n\r\nstatic const uint8_t hilbertToMortonTable&#x5B;] = {\r\n\t48, 33, 35, 26, 30, 79, 77, 44,\r\n\t78, 68, 64, 50, 51, 25, 29, 63,\r\n\t27, 87, 86, 74, 72, 52, 53, 89,\r\n\t83, 18, 16,  1,  5, 60, 62, 15,\r\n\t 0, 52, 53, 57, 59, 87, 86, 66,\r\n\t61, 95, 91, 81, 80,  2,  6, 76,\r\n\t32,  2,  6, 12, 13, 95, 91, 17,\r\n\t93, 41, 40, 36, 38, 10, 11, 31,\r\n\t14, 79, 77, 92, 88, 33, 35, 82,\r\n\t70, 10, 11, 23, 21, 41, 40,  4,\r\n\t19, 25, 29, 47, 46, 68, 64, 34,\r\n\t45, 60, 62, 71, 67, 18, 16, 49,\r\n};\r\n\r\nuint32_t transformCurve(uint32_t in, uint32_t bits, const uint8_t* lookupTable)\r\n{\r\n\tuint32_t transform = 0;\r\n\tuint32_t out = 0;\r\n\r\n\tfor (int32_t i = 3 * (bits - 1); i &gt;= 0; i -= 3) {\r\n\t\ttransform = lookupTable&#x5B;transform | ((in &gt;&gt; i) &amp; 7)];\r\n\t\tout = (out &lt;&lt; 3) | (transform &amp; 7);\r\n\t\ttransform &amp;= ~7;\r\n\t}\r\n\r\n\treturn out;\r\n}\r\n\r\nuint32_t mortonToHilbert3D(uint32_t mortonIndex, uint32_t bits)\r\n{\r\n\treturn transformCurve(mortonIndex, bits, mortonToHilbertTable);\r\n}\r\n\r\nuint32_t hilbertToMorton3D(uint32_t hilbertIndex, uint32_t bits)\r\n{\r\n\treturn transformCurve(hilbertIndex, bits, hilbertToMortonTable);\r\n}\r\n<\/pre>\n<p>The 3D Hilbert curve transforms under the group A4, which has 12 elements. However as there are only 8 transformations that can appear on the left-hand side of each multiplications, only an 8&#215;12 subset of the multiplication table is required. By folding the the index <=> octant mapping function into this table and additionally storing each index respectively octant into the lower 3 bits of each entry, we end up with a compact 96 byte LUT for each function.<\/p>\n<p>These functions can be used as drop-in replacement for the algorithm provided by <a href=\"http:\/\/and-what-happened.blogspot.de\/2011\/08\/fast-2d-and-3d-hilbert-curves-and.html\" target=\"_blank\">Fast 2D and 3D Hilbert curves and Morton codes<\/a>, but are faster by a factor of roughly 2.5 on my machine.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>As referenced in my earlier post about Hilbert curves, it&#8217;s possible to map between $$d$$-dimensional Euclidean coordinates and the offset along the Hilbert curve in $$O(n)$$ time by direct application of the transformation group at each recursion level of the curve. The following applies this to the 3D case: static const uint8_t mortonToHilbertTable&#x5B;] = { <a class=\"read-more\" href=\"https:\/\/threadlocalmutex.com\/?p=149\">[&hellip;]<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,7],"tags":[],"class_list":["post-149","post","type-post","status-publish","format-standard","hentry","category-general","category-hilbert-curves"],"_links":{"self":[{"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/posts\/149","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=149"}],"version-history":[{"count":1,"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/posts\/149\/revisions"}],"predecessor-version":[{"id":150,"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=\/wp\/v2\/posts\/149\/revisions\/150"}],"wp:attachment":[{"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/threadlocalmutex.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}