Space-Filling Curves - Numberphile
Вставка
- Опубліковано 9 вер 2024
- Henry Segerman shows us some 3D-printed space-filling curves, including the Hilbert Curve and Dragon Curve.
More links & stuff in full description below ↓↓↓
Check Henry's book about 3D printing math: amzn.to/2cWhY3R
More Henry videos: bit.ly/Segerman...
Dragon Curve videos: bit.ly/Dragon_C...
A little snippet we cut from this video: • Infinite Staircase - N...
A paper on this topic by Henry Segerman and Geoffrey Irving: bit.ly/Fractal_...
Leave a comment about this video on Brady's subreddit: redd.it/54k7h6
THANKS TO THESE SUPPORTERS ON PATREON:
Jeff Straathof
Today I Found Out
Peggy Youell
Christian Cooper
Dr Jubal John
Ken Baron
John Buchan
Bill Shillito
Erik Alexander Nordlund
Thomas Buckingham
Ole Kristian Merli
Thomas J.
BADER ALGHAMDI
Ayliean MacDonald
Tyler O'Connor
Jon Padden
Emme Nye
Stan Ciprian
Vali Dobrota
Arnas
Ian George Walker
Paul Bates
Tracy Parry
George Greene
Kristian Joensen
Tryggve Johannesson
Alfred Wallace
Mark Klamerus
Support us on Patreon: / numberphile
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
Videos by Brady Haran
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile T-Shirts: teespring.com/...
Other merchandise: store.dftba.co...
"it gets more squiggly" is the best way i've ever heard anyone describe space-filling curves
how many description have you heard before? lol
I think that's the official scientific term for it. (Or at least it shoul be.) 😂
I was going to 3D print a space-filling curve/gasket... but the cost of an infinite amount of filament put me off.
Dustin Rodriguez if you will make it 1/3 of the height for every next step you will finish it with finite filament
sergey technically, if the ratio of the size of the next level down is between 0.999 and 0.001 times smaller then he’d only need an finite filament.
@@pixiedust1383 Technically, if the ratio of the size of the next level down is between 0 and 1 times smaller then he’d only need an finite filament.
@@pixiedust1383 technically if he doesn’t build the next layer he would only need a finite amount of filament
When I was choosing a dissertation project in university, space-filling curves were an option, and the handbook had a little explanation of the project, including the diagram:
■
6:12 "Do you recognize this shape?"
Well, of course I do, that's the Tri Force.
You're a Tri Force Hero.
yeah, i was like "...the triforce? uhm... but why?" then he continued on.
That tri-force has cancer or something...
There's always someone in the comments who says this
The Tri-Force is just the step n = 1 of the Sierpinski triangle, not the Sierpinski triangle itself. But yeah, close enough.
Video could also be titled 'How Ramen Noodles Are Packed'
I cut out a step of the Hilbert curve on a laser cutter, with the cut being the curve. It ended up being very springy as well, but rather than one big connected noodle it was a bunch of interlocking leaves.
Protip for anyone laser cutting a Hilbert curve: turn up the power higher than you normally would for your material, especially if you're cutting wood. It's a very long cut for the size of the material (obviously, lol). If there are any incomplete cuts, you'll have to go back and sever them yourself. This is a big problem with something like wood, where lots of individual fibers may stay connected.
Where are the 3D models for those 3D prints? I'd love to print them out myself!
I used Hilbert curves in one of my terrain renderers to accelerate node lookup in a quad tree that has varying sub-divisions. Thanks to the mathematical properties of the curve I could find a node in memory (a straight line mathematically speaking) without the need to include every single node, just each sub-divided level. It was amazing just how well it's maps into memory even when certain quadrants of the curve are at a different complexity than the ones around it. Made lookups so fast that I could rebuild the tree every frame at 500FPS on a core 2 quad and so small that it fit within the CPU cache. The only downside was that it was mathematically complex to perform all the required functions of a very advanced terrain renderer that could support collision detection as well.
Wow! Nice work. I'd like to see a video if you made one! I love hearing about people making neat things like that. Keep it up! :P
dude what?
I didnt fully understand your comment, but I know it turned me on.
Alan Hunter I read the first sentence as a long string of math words. The rest I could about half understand
You can summarize this video with, "It gets more squiggly".
And it's getting squigglier
*AND IT'S GETTING SQUIGGLIER*
Back in the 1980s I saw a demonstration of an experimental TV system that scanned the screen in a Hilbert curve. The idea was that you could switch between resolutions, or show film of the "wrong" resolution on a different screen, quite easily. I worked out that it would be nearly impossible to adapt to colour. I have never managed to track down any other references to it. Has anyone else heard of this?
I need to find this
Any luck?
3b1b has a similar video on this
Anyone?
I found a paper from 1982 that is possibly related. The paper is "Using peano curves for bilevel display of continuous tone images", written by Ian H. Witten and Radford M. Neal.
"We need to get into the squiglly zone" -ViHart
my first thought too XD
finally someone rational :v:
+
squiggly squooty
Shrooms
These three-dimensional extrusions remind me of corals and brain folds.
This never boggled my mind until one of uni profs gave us a long lecture on how weird it is that a filled in square is/can be a curve and, therefore, that curves are not what we think that they are and can even be a bit tricky to define. This was part of a larher harangue on how every definition admits pathologies.
"And you were surprised by that?"
OWWW SASS LEVEL UP
I'd like to see some buildings shaped like space filling curves dragged through time. I think they look cool!
The way he draws grids with fractal crosses instead of continuous lines makes me irrationally mad.
How dare he make a fractal grid in a video, that has fractal-like curves in it! Scandal! Okay, actually it bugged me too.
That last squiggly thing reminded me of a brain. So that got me thinking about neuromorphic computing. Maybe neuromorphic chips could be modeled after space-filling curves?
Thought of the same thing
Chips aren't a single linear string of components, there are many things going on in parallel, and many components that need to be connected to multiple things at the same time.
Newer designs tend to make better use of three dimensions (ex., having some functional components serving as links between layers, instead of just having a bunch of stacked layers with passive connections between them), but they are fundamentally different from a linear space-filling curve.
You can't deny that mathematicians are hella passionate with their craft. You can see it in their eyes.
The squiggly curve reminds me of the brain, are cranial folds similar to space filling curves?
Yes. It is a nearly space filling surface. The surface of the brain has some desirable property, so the brain folds to create as much surface as possible. There is something about this somewhere in Mandelbrot's "The Fractal Geometry of Nature", a book I admit I have never finished.
I read something a log time ago about this. I believe it said that reptiles and fish tend to have smoother brains, while the smarter mammals tend to have foldings on the surface.
Yeah, once he showed us the pink model, that gave me the same feeling.
The main reason our brains are folded is that we can have more surface area in our brain, but the volume doesn't grow in our head.
Folds create greater surface area per volume. You can see this phenomenon in several parts of our bodies, e.g. our intestines to increase absorption, in our brain to increase the amount of gray substance (the actual nerve cells are at the surface of our brain and the inside is filled with axons) and mitochondria also have folds in their inner membrane to increase sites for ATP (energy) production.
It's an interesting observation, maybe the nerve cell layout follows a space filling curve since the actual filling in the brain are mostly axons.
It is amazing to see how mathematics with just "simple" rules can create something mindboggeling as this.
6:10 "Recognize this?"
Oh yeah that's the trifo-
"NOPE IT'S A SIERPINSKI TRIANGLE!!"
k then...
Two types of nerds...
I was just going to comment that!
never played Zelda but had same thoughts
you're missing out on one of the best Gaming Franchise in my opinion
Disappointment.
The audio editing for the sped-up drawing section near the start is incredible.
3Blue1Brown!
Yep.
+Aaron Cruz The one and only!
3:53 is also a nice part of 3Blue1Brown. The "hearing-pictures" video.
How does this video relate to 3Blue1Brown at all?
he released a video a while back illustrating space filling curves and a pretty cool use for them
A better way to describe a space-filling curve, than to say “If you go infinitely far, it suddenly fills space”, is to say “Each iteration makes the curve longer, so its limit after indefinitely many steps goes through every possible point”
This seems right but it’s not! Even though it’s length diverges, it doesn’t mean it will hit every point. If you think about all the points in the rational number space (Q^2) then an infinitely long curve could hit all of the points (because there are infinitely many rationals) but still miss infinitely many irrational points!
I'm noticing a pattern here. At some point in like every 5th numberphile video in recent memory, whoever Brady's filming will just pull out several 3d printed models of what they're talking about. Something tells me that around 6 months ago, the math department got a 3d printer and that behind the scenes, everyone is still super excited about it. I bet if you watch all of these videos in the order they were released, you'll see those models slowly get more and more intricate as the professors get better at using 3d CAD software.
Reminds me of how brains are so densely packed in skull, props nature for figuring space filling curves out without UA-cam!
"If you enjoy Henry's videos here on Numberphile, you're really gonna love his new book about visualizing mathematics with 3D printing."
Ooh, sounds interesting! Let's see that link:
"Kindle: $45.52, Hardcover: $63.06"
Never mind...
Yeah, I wish it were less expensive - the publisher's decision, not mine.
Trash is cheap as it is available in masses, but quality is rare and has it's price in order to get it at all.
Quick question: can I order a kind of uncomfortable bracelet somewhere?
Henry Segerman
Whoa, thanks for the quick reply.
Is it possible to get the link? I cannot see Henry's comment (might have been erased?).
Hilbert curves are available as an algorithmic auto fill option on most 3d printing slicing software, as well
This reminds me a lot of one of Vihart's videos about doodling
Up a squiggle, down a squiggle, Up a squiggle, down a squiggleUp a squiggle, down a squiggle.
Up a squiggle, down a squiggle, up a squiggle, down. Woop!
not related but: snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek snek
+zoranhacker 🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍🐍💕
+Elliot Grey
you forgot 6 snek-s.
Here they are: 🐍🐍🐍🐍🐍🐍 !
Can you post links to the 3D models so we can print / view them ourselves? Or is that accessible in the book or something?
Can you fill space in the 4th dimension? is it possible to create a Hilbert curve or Peano curve in 4D? if possible please make a vid of this!!!!
Yes it is possible
How will the animation look like?
That also means you can map every single point in space and time on a 1d line, even accounting for the expansion of spacetime.
+crnobijeli13 That makes no sense.
Stop trying to look intelligent.
You can't animate it, but there is a map between a line and every n-th dimensional space.
I really don't have the entry knowledge required for some of these less intuitive more formulated ways of expressing mathematical concepts but I still enjoy these videos as it is like I'm using what I see to solve what was coming 5 seconds ago if that makes sense.
Windows XP screen saver, REDISCOVERED.
3Blue1Brown has an amazing video on this!
Gorgeous models.
Henry: "Recognize this shape? that would be the Stravinsky Triangle."
Me: "Eh no mate, that's the Triforce."
if we learned something like this in school, math classes would have been much more enjoyable
Yay, fractals again! \o/ One of my favourite maths topics.
Extra credit (5 points divided by number of terms in the solution): Compute the lowest spring stiffness across a long diagonal of the Nth iteration of a Hilbert curve in M dimensions with filament bending stiffness k.
These things would make great heatsinks
Lol, a Menger Sponge heatsink would look cool! Very... space filling though ;)
Would that even work? I mean, you are pushing air over an infinite amount of surface area.
it's a very interesting idea! but i could imagine 2 reason why it would be a bad heat sink.
1) long conduction path. heat needs to conduct through solid before it gets to the surface touching cold air on "the other side". and since this curve fills space locally first, the solid path to get to "the other side" is a lot further than it could be.
2) from engineering point of view it would be harder to produce than simpler shape.
Two solutions: a) As mentioned you can tune the relative thickness of the elements as they leave the heat source; b) You can use selective laser sintering technology to build the parts quickly, with as much intricacy as needed.
Other than this in my opinion the problems will be more: Optimal shape for airflow, and overall compactness of design. I think that grille-type radiators could use the Peano space-filling curve, for instance.
I don't know what I'm talking about, but if the copper from a CPU heatsink is at around 60-90°C, there's a lot of heat that can be transferred to air (through larger surface area) even if it takes longer to "travel through the heatsink", right? (also, would heat radiation, as in the one that still happens in vacuum, begin to play a role?)
Reminds me of 3Blue1Brown's video
Funny how I had a course on this in my computer science class only two days ago. We had a recursive, beautifully made, solution for the Dragon Curve in Python using Turtle Graphics.
"Recognize this shape?"
Ooo, the triforce!
"It's the sepinski triangle."
...
The Sierpinski triangle is the triforce for a brief second step. In fact, Zelda 1 introduces only separate pieces of triforce (wisdom and power), Sierpinski triangle at step 1. Zelda 2 introduced the triforce of courage, but it took until Zelda 3 (a link to the past) for the pieces to appear as a Sierpinski triangle at step 2. Sadly, there has yet to be a game that goes for another iteration, maybe 9 pieces is a bit much to handle.
this reminds me of the wooden puzzles that are 1 string of smaller cubes connected at 90 degrees or 180 and you have to rotate them around to fit back into a cube
Looks like a beautiful corals reef.
I appreciate the fact that sometimes in mathematics it's cool to take a step back and just say "hey look, it's a clone trooper", or "oh wow. It's wiggly", and forget all the math stuff for a moment. I really like he that.
0:16 we're gonna build a curve, and Mexico's gonna pay for it
Any chance we could get a link to a the code Henry Segerman is using to generate those models?
Yeah that would be great, so maybe people could print their own model :D
Yeah, it's called Rhino.
Rhino is a 3D modelling application. You can create the curves in just about any major 3D package, either manually (by drawing the layers and then connecting them with one of the lofting tools) or using their built-in scripting languages. The shapes are well-known enough that you might even find ready-made plug-ins (just search for [name of your favourite 3D software] + [name of the curve]).
I highly suspect Henry is using some scripting tools on top of Rhino to build these. He probably goes into that in his book I guess.
If I were to try and model these things with Rhino I would probably start with the Grasshopper plug-in and if that fails then straight to Python.
You could model these by hand in Rhino, but I would recommend against it.
The string maybe infinitely small, but the impressionable media of which is the defined memory is going to have some size and scale. Therefore for these infinite strings to be meaningful and usable they have to be impressed with some distortional capacity and this is where the use is implied. You have to understand the infinitely small strings are just the ideal impressionable capacity to store information, but they need to be impressed and therefore stored into some complex wave function as opposed to the ideal sine.
Interesting timing considering I was watching all sorts of videos about the subject the past weekend.
Imagining these objects to be buildings, would be so awesome :D
Some of Frank Gehry's buildings come pretty close...
...?...
***** They're curvy but not like this ;)
Reminds me of this one pipe screensaver I had on an old Windows computer :^)
So many applications and yet he only talks about them for a few seconds. They're so much more than just visually interesting shapes.
I'm used to being confused by Numberphile videos, but I was legitimately scratching my head as soon as he explained the premise of this one. I guess I'll just "woosh" myself here.
woosh
the infinite hilbery curve can also be represented by taking a number in binary, and then all the even bits make up the x coordinate and all the odd bits make up the y coordinate.
If I undertood it correclty, the premise is, that if you "fold" the curve to infinity, it will cover all the space the shape "occupies"
@@ChristopherKing288 oh woah that's really cool.
Fractals are really weird. I mean, there's this thing called Menger's sponge, and it's like Sierpiński's triangle, but with squares and actually in three dimensions, so not really squares, but cubes. And what amazes me about it is that with every step, the surface area increases and the volume decreases. So at the limit it will have infinite surface area and absolutely no volume? I'm very fond of fractals and I'm a programmer, so I've been playing around with a few of them for some time. It was really fun. In the end, I think, I never fully understood them.
I saw (and met) this guy at the Museum of Math in New York. He was giving a talk about 4 dimensional shadows.
Matters Computational is a book and it is free. For example it shows you how to construct Hilbert curves in code/
Fractals? Finally!
Fractals are my childhood.
The tactile senses tell us more than the math show.
A simple and maybe non-obvious space filling fractal is: express all the points between 0 and 1 as a decimal fraction, and then take every second digit as an x-coordiate and the other digits as a y-coordinate. The result is broken up into disconnected segments (obviously), but it fills the square and has a fractal structure.
But is it actually a curve? A curve is a continuous map from [0,1]. It's definitely a map from 0,1 to the square but there are lots of those! The thing in the video is a curve.
Not a curve, I guess, but is a fractal. That is - it is self-similar when you scale it.
I wonder if all maps from the interval to the square must have fractal structure.
I designed some 3D models like this in Blender some months ago. Didn't know all the math behind it back then.
Circles, spirals and curves fill this world. Wonder of worlds with other geometry and order, after all...
These curve-objects would be some nice stamps..
The infinity limit of the curve in the Hilbert curve is composed of countably many finite curves or does it have uncountable many finite curve. In other words how many steps (countably infinite or uncountable infinite) are required to hit all the points?
Spaaaaaace-Filling Curves - Numberphile - thanks to XKCD
what he said at 3:46 is not exactly wrong, but misleading. I calaculated distances orthogonally in a Level 2 Hilbert curve vs. Classic snaking, and found:
Hilbert curve = for every unit you travel in the image, you travel an average of 3.0092592592592592 units in the data stream.
Snake Pattern = for every unit you travel in the image, you travel an average of 2.8645838645836845 units in the data stream.
So the regular back and forth pattern is actually more efficient in those terms. However, there was a lot of variation in the hilburt curve, so sometimes the path was much shorter, but there were plenty of times when the path was much longer, as well.
It's interesting that there are so many points that it could never hit. For instance it could only ever approach the center point of the main square with infinite recursion.
2:00 that sound editing tho
So smooth
Wow, yeah, the best editing is the one you don't notice.
What is there to notice ? :/
What are equation of extra dimensions. The powers of random numbers when multiplied by wave functions gives shape as it splits. And that takes various regular form as it progresses with sheets of partial structures.
Those are also called fractal curves. So, brady asked how a line can fill space, if it actually has no thickness. The thing is, we're in mathematics, where the definition of a line is to be indefinitely thin, but it get's interesting, if we go into physics. In physics, we know that everything is quantized or "not continuous", which basically means that there is a minimum difference in energy between the smallest particles when they move the smallest distances. Just like you can only zoom into a picture until you see every single pixel, there are actually particles that are so small, that they can't be split, because they're literally just a spike of energy, squeezed into a virtual particle for better understanding. So what that means is, that everything is made of a finite number of ingredients and carries a finite amount of information and if there is only a finite number of particles or units of distance in a volume, then you can only iterate a fractal curves so many times until it touches every last of the smallest possible areas in this finite volume of space. Those are btw called a Planck Quantum, defined as the smallest possible amount of anything. So if you were to draw line that touches each and every Quantum of Space in a volume, meaning that at any one point on the line the distance to the next portion of the line is not more than one Quantum, you actually filled up the volume, because nothing else can exist between the lines, as the area between any two neighbouring quanta is simply not defined.
7:22 It looks like a cubey brain
it does, it does.. wouldn't it be interesting to draw the conclusion that our brains are also "looped" in that same way, hmm? :)
I was thinking the very same thing
Our brains look similar to maximise surface area, which is where the grey matter is.
The comparison to a single strand might be why some people mention a person's noodle.
hahaha, noodleloop
Minecraft?
It's things like the sculptures in this video that make me want a 3D-printer.
So much to learn
this video is so Parker squared!
How so? Didn't see many mistakes in this one.
A "complete" Hilbert curve (drawn to infinite "resolution") fills the space of the square region it's drawn in, but seems like it _doesn't_ include every point in the region. If you look at the way the levels are iterated, you'll see that you'll end up with "seams" along the boundaries between the subregions (i.e. along the blue lines) which are infinitely thin (approached from both sides by the curve), but are crossed by the curve only a _finite_ number of times. If the curve is drawn in the square region (0,0) to (1,1), the seams occur where either coordinate equals a/(2^b), where a and b are integers, b>0, and 0
It is true that the vertices (corners) of the curve always have rational coordinates. The complete Hilbert curve is DENSE in R^2, but does not comprise
all of R^2?
I need to make this... telling my STEM class about this tomorrow
The Dragon Curve is printed at the start of every chapter of one of the Jurassic Park books, can't recall now if it's the original or The Lost World
Incredible.
This is so awesome!
love this channel keep up the good work!
The Gilbert curve! Yay geometry!
These mathematical principals create such natural seeming objects. Like they could form patterns in animals fur or in the grouping of skin cells or even the configuration of galaxies. I wish I was smart enough to understand any of it. Yeah mathematicians.
Just Imagine that in a 1000 years this Videos as exciting as it is right here right now will be considered boring basic math by most of people as they learn it in preschool
Ahhh i want/need to print those curves
My favourite space-filling curve is the Sierpiński Curve, a bit sad that it didn't get shown.
Never thought a cube could be made form a single curve
I think it's because the infinitesimal thickness cancels with the infinite steps.
Have an awesome day!
And if you keep zooming out, you'll see all the tightly packed curly hairs that make up the coolest fro you've ever seen.
Those 3D printouts would make awesome stamps.
My favorite is the Flowsnake
Can someone tell me what's the best approach to model in such amazing 3d shapes? how do you connect the iterations?
7:18 "We are Borg. Resistance is futile. You will be assimilated."
The main proof for these being space filling curves is the line would have to go to zero thickness to stop it from hitting the same points twice, which is the same way as saying the curve hits every point in the area.
4:34 this looks like De Sitter space! Prof. Susskind talked about it on several videos!
2:15 those crosses seemed tempting for my Garand
3d printing is badass
The space is being filled by discrete, or countable steps, whereas the space itself is made of continuous, thus uncountable, points. How does a countable infinity ever fill an uncountable infinity?
OMG! Please give us 3D models of those objects!
Henry Segerman has a really nice voice
7:26 i'd like to see the (electro-)magnetic field of that thing. Could you cast that out of magnetic material or make an electric circuit like that?
WOW! Amazing work...
How to make a space-filling curve:
1) take a regular curve;
2) get more squiggly;
3) repeat Step 2 to infinity;
4) it's springy!