   How to calculate the Hilbert value of a point?
  How does one actually calculate the Hilbert value of a 3d point? The Hilbert value the points distance along a Hilbert curve? I know it has something to do with bitwise operations but can't find anything that explains the actual computations and operations involved. So far I'm either greeted by incredibly complex theories (which I cannot understand at all) or given a mountain of source code to try to dig through. So can anyone give me the pseudo code that can take a 3d point as input and output its Hilbert value?   
  Are you talking about the 3D version of the Hilbert space-filling curve?   ;  Yup, though actually just knowing how to find the Hilbert value of a 2d point would be helpful.   ;  I can't remember the author, but there is a book called, I think, Space-Filling Curves that, I think, has code for doing this, but definitely only in the 2D case. It's one of the those math books published by Springer Verlag with the yellow covers. Actually it might just have code in the other direction i.e. distance along the curve -> 2D point. Anyway, I'm working right now but as soon as I start doing a big build I'll go try to dig out that book.   ;  Thanksbtw is this the book your talking about?http://www.amazon.com/Space-Filling-Curves-Universitext-Hans-Sagan/dp/0387942653   ;  Yeah, that's it. I just found it but it only has code in the dist. along curve -> 2D point case and it's in BASIC :)But I think I understand it enough to write the 2D case in the other direction. Basically you output the answer as a fraction in base-4 and each digit of the fraction is specifying which quadrant the point falls in at a particular level of the hilbert curve, ordering the quadrants from 0 to 3 according to the order in which the Hilbert curve will pass through them. The hitch is that although the Hilbert curve is self-similar in the quadrants of the unit square it is rotated by 90 degrees and negative 90 degrees in the two bottom quadrants.Anyway I think that the following is correct (at least it agrees with the book in that the book shows that .203 in base-4 yields the point (5/8,3/4) and if you run the following on (5/8,3/4) you'll get 2 0 3 in the output vector):void GetHilbertValueAux(double x, double y, double dim, int max_digits, std::vector<int>& output) {    if (output.size() == max_digits) {   return;    }    // find which quadrant (x,y) is in and recurse, shrinking and rotating the square    // appropriately...    double half_dim = dim / 2.0;    double new_x, new_y;    if (x <= half_dim && y <= half_dim) {   // we're in the lower left quadrant   output.push_back(0);   new_x = y;   new_y = x;    } else if (x <= half_dim && y > half_dim) {   // we're in the upper left quadrant   output.push_back(1);   new_x = x;   new_y = y - half_dim;    } else if (x > half_dim && y > half_dim) {   // we're in the upper right quadrant   output.push_back(2);   new_x = x - half_dim;   new_y = y - half_dim;    } else if (x > half_dim && y <= half_dim) {   // we're in the lower right quadrant   output.push_back(3);   new_x = y;   new_y = dim - x;    }    GetHilbertValueAux(new_x, new_y, half_dim, max_digits, output);}void GetHilbertValue(double x, double y, int max_digits, std::vector<int>& output) {    GetHilbertValueAux(x, y, 1.0, max_digits, output);}int main() {    std::vector<int> quarternary_digits;    GetHilbertValue(5.0/8.0, 3.0/4.0, 3, quarternary_digits);}Also, the number that this thing returns may be (or may not be) correct, but it isn't unique. For any number between 0 and 1 there is exactly one (x,y) point corresponding to it on the Hilbert curve, but there is a one-to-many mapping in the other direction.[Edited by - jwezorek on May 14, 2010 1:23:09 AM];  Thank you very much. It might not be perfect but at least I have something to work with now.   ;  Out of curiosity, what are you working on?   ;  I'm trying to make a way to hash objects based on their location in 3d space. This would make collision testing much more efficient since instead of an object testing itself against every other object in the game it would only have to test itself against objects in its hash group.Btw what exactly does output.push_back and output.size do. I'm assuming output.size returns how 'long' output value is (ie if output == 354 then output.size() would return 3).I'm not sure what push_back does though. Does it just set the output value to that number? So output.push_back(3) is setting output = 3?o wait, output is a list/array/vector isn't it? So is push_back adding a value to the end/start of the list/array/vector?   ;Quote:Original post by 1101o wait, output is a list/array/vector isn't it?A vector, as can be seen in the parameter list for the function:Quote:std::vector<int>& outputArrays in C++ do not have member functions.Quote:So is push_back adding a value to the [end] of the [vector]?Yes. It's called push_back because it pushes (in the stack sense) on the back side (i.e. the end).   