I haven't actually implemented the following, so may well have overlooked some snag; but must confess not understanding why connecting sub-paths of different recursion levels is problematic. Given: line segments in 2-space with endpoints (U,X) and (V,Y) , parallel to axes, and contained within disjoint quadtree boxes. Required: connect X and V by further segments (X,Z) and (Z,V) parallel to axes, disjoint from interiors of (U,X) and (V,Y) . Method: denote by (P,X,Q,V) the rectangle with sides parallel to axes and opposite corners X,V ; if P lies outside the interior of both (U,X) and (V,Y) , set Z = P ; else set Z = Q . When both boxes are at the same recursion level, the rectangle degenerates to line segment with P = X and Q = V . When both P,Q satisfy the criterion above, and join lines UX and VY are perpendicular, it may be preferable on aesthetic grounds to choose or to avoid setting Z = meet of UX, VY . The requisite geometric operations are fairly easy to implement simple- mindedly; however my preference would be to use general-purpose algorithms based on projective (homogeneous) coordinates. [OK, so I know you won't --- but at some point you may wish you had!] Fred Lunnon On 5/11/13, Neil Bickford <techie314@gmail.com> wrote:
WFL>And the program comprises a single Mma procedure call with ten parameters, each an obscure value of some appallingly recondite hypergeometric function ... No, that's http://www.wolframalpha.com/input/?i=tardar+sauce+curve .
Okay, so it may be a bit kludgish, but here's how we generated the Hilbert(Hilbert) picture, in case anyone's interested in the technique: We were originally inspired by Brian Wyvil's work, specifically his portrait of Bill Gosper using a flowsnake curve. He's apparently done quite a bit using fractals to indicate values in images, even going so far as to write a drawing program which automatically produces the curve and colors it in real-time. While his program doesn't have to deal with quite so many line segments, he did decide to use fractional iterations (i.e., interpolated between two levels) of the fractal, which was something we wanted to avoid.
If I remember correctly, Bill wanted to create a portrait of Hilbert using a Hilbert curve right away, but due to some technical problems (described below) we started out trying to create a portrait of Peano using a Peano curve. The technique for doing this is fairly simple: Starting with an initial, preferably square image (we used the one from http://en.wikipedia.org/wiki/Giuseppe_Peano ), and a level n curve, - For each edge, sample the image around the line and return the minimum value of the samples - If this value is less than the "expected brightness" of the current iteration depth (currently, naively computed as 1-n/maxDepth), subdivide that edge according to the current fractal system. Repeat this until the iteration depth meets the maximum depth, at which point the line segments will create an approximation to the original image.
Here's the result using this technique: http://neilbickford.com/assets/peano-frac-2.png (5.87 MB, try peano-frac-small.png if that's too large)
Aside from some noticeable problems, such as the clear difference in grays produced by only using 7 iterations, this technique works fairly well. However, Hilbert(Hilbert) involves some additional difficulties- specifically, the recursion always adds additional line segments, and the spacefilling path only begins and ends at 0 and 1 in the limit (that is, iteration n goes between (1+I)/2^n and 1-(1-I)/2^n). The source image we used for Hilbert ( http://en.wikipedia.org/wiki/File:Hilbert.jpg ) also doesn't have as many hard edges as the image for Peano, and there are many fine details, such as the hairs in his beard or his glasses, some of which aren't very clear in the final picture.
This means that not only did we have to modify the above algorithm to recurse on points, but also that we had to come up with some way of connecting parts of the curve that were in two different recursion depths using only orthogonal lines. Our original idea was to connect the pieces using parts of the Hilbert curve itself, and while we did have a sort of proof of concept (screenshot at http://neilbickford.com/assets/hilbinterpolation.png ), it was incredibly finicky to work with, and I eventually gave it up. (It's not impossible, though, and it'd be neat if someone came up with a version that actually followed the Hilbert curve)
Once we got the code working, we soon found out that it would be necessary to go down to level 9 to get a good result. This immediately led to the discovery of the memoization bug in Mathematica, which Gosper covered in an earlier email. Once <i>that</i> was fixed, we got an image which is at least passable: http://neilbickford.com/assets/hilbinterpolation.png (2.62 MB) Notice how in areas where the original image was textured, such as Hilbert's suit, almost all the lines are slanted.
However, you'll notice that the final image does have straight lines. Okay, I'll admit it: we cheated a bit. Bill suggested moving the vertices around until the the lines were straight, so I wrote out the coordinates to a file (available at http://neilbickford.com/assets/hilblines.zip ), then wrote a C#/XNA program to nudge everything around until it looked about right. Once that was finished, the program saved the image out to a file, which was what Bill posted at the top of this thread.
It should be noted that there was a lot of trial-and-error in finding the correct parameters to get a good image involved in this process- for example, the rendering program would sometimes round off the corners too much and actually reduce the number of iterations in the curve, or wind up with intersecting edges. Typical failures looked like Ulysses S. Grant with a hat; at worst, Bill compared the resulting image to Freddy Kreuger. One interesting result was that a black background worked best; not only did it provide high contrast with the edge of Hilbert's face, but it also set the minimum recursion level to a high enough value that smaller details are visible.
Lastly, some things about the final picture could be improved. I didn't let the rendering program run for long enough, and so intersecting and even slightly slanted lines can still be seen, although they're not very visible.
Anyways, I hope this answers some of the questions that have been raised, and I also hope WFL forgives me for using his comment to document how the subject image was made.
Thanks for all the enthusiasm, --Neil Bickford
On Thu, May 9, 2013 at 6:00 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
And the program comprises a single Mma procedure call with ten parameters, each an obscure value of some appallingly recondite hypergeometric function ...
WFL
On 5/9/13, Bill Gosper <billgosper@gmail.com> wrote:
Tonight, after a couple of weeks of work, Neil produced http://gosper.org/hilbert.png . This is *way* harder that Peano(Peano) or Gosper(Gosper). --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun