#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Hilbert curve

Posts: 9,106

Here’s some code to draw a Hilbert curve. You can use the sliders to change the screen size and the order number. The higher the order number, the more intricate the curve. Increasing the order by one increases the curve complexity by 4. After changing the order number, press the process box. This displays the FPS, so the higher the order, the slower the FPS. Best viewed in landscape orientation.

``````--- Hilbert curve

viewer.mode=STANDARD

function setup()
parameter.watch("fps")
s=require("socket")
stroke(255)
strokeWidth(2)
positions={=vec2(0,0),vec2(0,1),vec2(1,1),vec2(1,0)}
parameter.integer("size",1,50,25)
parameter.integer("order",1,12)
parameter.action("process",process)
process()
end

function process()
tab={}
N=2^order
st=s:gettime()
for i=0,N*N do
hindex2xy(i,N)
end
en=s:gettime()
output.clear()
print("Order  "..order)
print("Number of points  "..#tab)
print("Time  "..en-st)
end

function draw()
fps=1/DeltaTime
background(0)
for z=1,#tab-1 do
if z>1 then
line(tab[z].x*size+10,tab[z].y*size+50,curr.x*size+10,curr.y*size+50)
end
curr=tab[z]
end
end

function hindex2xy(hindex,N)
tmp=positions[hindex&3]
x=tmp.x
y=tmp.y
hindex=hindex//4
n=4
while n<=N do
n2=n/2
ss=hindex&3
if ss==0 then
tmp=x
x=y
y=tmp
elseif ss==1 then
y=y+n2
elseif ss==2 then
x=x+n2;
y=y+n2;
elseif ss==3 then
tmp=y
y=(n2-1)-x
x=(n2-1)-tmp
x=x+n2
end
hindex=hindex//4
n=n*2
end
table.insert(tab,vec2(x,y))
end
``````

• Posts: 5,586

Interesting use of bitwise and binary operators. I made a small modification to animate the drawing of the curve

``````--- Hilbert curve

viewer.mode=STANDARD

function setup()
parameter.watch("fps")
s=require("socket")
stroke(255)
strokeWidth(2)
positions={=vec2(0,0),vec2(0,1),vec2(1,1),vec2(1,0)}
parameter.integer("size",1,50,25)
parameter.integer("order",1,12)
parameter.action("process",process)
currentIndex = 1
process()
end

function process()
tab={}
N=2^order
st=s:gettime()
for i=0,N*N do
hindex2xy(i,N)
end
en=s:gettime()
output.clear()
print("Order  "..order)
print("Number of points  "..#tab)
print("Time  "..en-st)
end

function draw()
fps=1/DeltaTime
background(0)
for z=1,currentIndex do
if z>1 then
line(tab[z].x*size+10,tab[z].y*size+50,curr.x*size+10,curr.y*size+50)
end
curr=tab[z]
end

currentIndex = currentIndex + 1
if currentIndex > (#tab-1) then
currentIndex = 1
end
end

function hindex2xy(hindex,N)
tmp=positions[hindex&3]
x=tmp.x
y=tmp.y
hindex=hindex//4
n=4
while n<=N do
n2=n/2
ss=hindex&3
if ss==0 then
tmp=x
x=y
y=tmp
elseif ss==1 then
y=y+n2
elseif ss==2 then
x=x+n2;
y=y+n2;
elseif ss==3 then
tmp=y
y=(n2-1)-x
x=(n2-1)-tmp
x=x+n2
end
hindex=hindex//4
n=n*2
end
table.insert(tab,vec2(x,y))
end
``````
• Posts: 9,106

@Simeon I have an animated version, but didn’t post it. I guess I don’t need to now. I was surprised when I searched for Hilbert code and didn’t find any here, I was looking thru the Rosetta link which had code in a bunch of different languages, but some didn’t make any sense and others that I understood were too long and complicated.

• Posts: 9,106

@Simeon I thought I’d post my animated version anyways. Adjust the size to fit the screen. It’s kind of interesting to shrink the image so there’s no spaces between the lines.

``````-- Hilbert curve

viewer.mode=STANDARD

function setup()
parameter.watch("fps")
s=require("socket")
stroke(255)
strokeWidth(5)
positions={=vec2(0,0),vec2(0,1),vec2(1,1),vec2(1,0)}
parameter.integer("size",1,50,25)
parameter.integer("order",1,12)
parameter.action("process",process)
process()
end

function process()
tab={}
tab1={}
N=2^order
for i=0,N*N do
table.insert(tab1,color(math.random(255),math.random(255),math.random(255)))
end
output.clear()
print("Order  "..order)
i=0
tab={}
end

function draw()
fps=1/DeltaTime
background(0)
hindex2xy(i,N)
for z=1,#tab do
if z>1 then
stroke(tab1[z])
line(tab[z].x*size+10,tab[z].y*size+50,curr.x*size+10,curr.y*size+50)
end
curr=tab[z]
end
end

function hindex2xy(hindex,N)
if i>=N*N then
return
end
tmp=positions[hindex&3]
x=tmp.x
y=tmp.y
hindex=hindex//4
n=4
while n<=N do
n2=n/2
ss=hindex&3
if ss==0 then
tmp=x
x=y
y=tmp
elseif ss==1 then
y=y+n2
elseif ss==2 then
x=x+n2;
y=y+n2;
elseif ss==3 then
tmp=y
y=(n2-1)-x
x=(n2-1)-tmp
x=x+n2
end
hindex=hindex//4
n=n*2
end
table.insert(tab,vec2(x,y))
i=i+1
end
``````
• Posts: 9,106

Here’s code for a 3D Hilbert curve using Craft. You can rotate it to get a better view. Change the order variable to increase/decrease the density. Going higher and it gets to dense.

@Simeon Is there a way to increase the thickness of the debug line command.

``````-- 3D Hilbert curve

viewer.mode=STANDARD

function setup()
s=require("socket")
assert(craft, "Please include Craft as a dependency")
assert(OrbitViewer, "Please include Cameras (not Camera) as a dependency")
scene = craft.scene()
v.rx=25
v.ry=30
v.rz=0
size=5
count=0
tab={}
order=3
st=s:gettime()
hilbertC(2^order,0,0,0,1,0,0,0,1,0,0,0,1)
en=s:gettime()
print("3D Hilbert curve")
print("Order  ",order)
print("Number of lines  "..count-1)
print("Time ",en-st)
end

function hilbertC(s, x, y, z, dx, dy, dz, dx2, dy2, dz2, dx3, dy3, dz3)
if s==1 then
table.insert(tab,vec3(x,y,z))
count=count+1
else
s=s/2
if dx<0 then x=x-s*dx end
if dy<0 then y=y-s*dy end
if dz<0 then z=z-s*dz end
if dx2<0 then x=x-s*dx2 end
if dy2<0 then y=y-s*dy2 end
if dz2<0 then z=z-s*dz2 end
if dx3<0 then x=x-s*dx3 end
if dy3<0 then y=y-s*dy3 end
if dz3<0 then z=z-s*dz3 end
hilbertC(s, x, y, z, dx2, dy2, dz2, dx3, dy3, dz3, dx, dy, dz)
hilbertC(s, x+s*dx, y+s*dy, z+s*dz, dx3, dy3, dz3, dx, dy, dz, dx2, dy2, dz2)
hilbertC(s, x+s*dx+s*dx2, y+s*dy+s*dy2, z+s*dz+s*dz2, dx3, dy3, dz3, dx, dy, dz, dx2, dy2, dz2)
hilbertC(s, x+s*dx2, y+s*dy2, z+s*dz2, -dx, -dy, -dz, -dx2, -dy2, -dz2, dx3, dy3, dz3)
hilbertC(s, x+s*dx2+s*dx3, y+s*dy2+s*dy3, z+s*dz2+s*dz3, -dx, -dy, -dz, -dx2, -dy2, -dz2, dx3, dy3, dz3)
hilbertC(s, x+s*dx+s*dx2+s*dx3, y+s*dy+s*dy2+s*dy3, z+s*dz+s*dz2+s*dz3, -dx3, -dy3, -dz3, dx, dy, dz, -dx2, -dy2, -dz2)
hilbertC(s, x+s*dx+s*dx3, y+s*dy+s*dy3, z+s*dz+s*dz3, -dx3, -dy3, -dz3, dx, dy, dz, -dx2, -dy2, -dz2)
hilbertC(s, x+s*dx3, y+s*dy3, z+s*dz3, dx2, dy2, dz2, -dx3, -dy3, -dz3, -dx, -dy, -dz)
end
end

function draw()
update(DeltaTime)
scene:draw()
for a,b in pairs(tab) do
if a>1 then
scene.debug:line(vec3(b.x*size,b.y*size,b.z*size),
vec3(c.x*size,c.y*size,c.z*size),color(255))
end
c=b
end
end

function update(dt)
scene:update(dt)
end
``````
• edited March 25 Posts: 9,106

Here’s an animated 3D Hilbert curve. You can zoom in / out or rotate it. You can reduce the value of the “order” variable to see a smaller curve.

``````-- 3D Hilbert curve animated

viewer.mode=STANDARD

function setup()
s=require("socket")
assert(craft, "Please include Craft as a dependency")
assert(OrbitViewer, "Please include Cameras (not Camera) as a dependency")
scene = craft.scene()
v.rx=25
v.ry=30
v.rz=0
size=5
count=0
tab={}
order=6
hilbertC(2^order,0,0,0,1,0,0,0,1,0,0,0,1)
print("3D Hilbert curve")
print("Order  ",order)
print("Number of lines  "..count-1)
xx=1
end

function hilbertC(s, x, y, z, dx, dy, dz, dx2, dy2, dz2, dx3, dy3, dz3)
if s==1 then
table.insert(tab,vec3(x,y,z))
count=count+1
else
s=s/2
if dx<0 then x=x-s*dx end
if dy<0 then y=y-s*dy end
if dz<0 then z=z-s*dz end
if dx2<0 then x=x-s*dx2 end
if dy2<0 then y=y-s*dy2 end
if dz2<0 then z=z-s*dz2 end
if dx3<0 then x=x-s*dx3 end
if dy3<0 then y=y-s*dy3 end
if dz3<0 then z=z-s*dz3 end
hilbertC(s, x, y, z, dx2, dy2, dz2, dx3, dy3, dz3, dx, dy, dz)
hilbertC(s, x+s*dx, y+s*dy, z+s*dz, dx3, dy3, dz3, dx, dy, dz, dx2, dy2, dz2)
hilbertC(s, x+s*dx+s*dx2, y+s*dy+s*dy2, z+s*dz+s*dz2, dx3, dy3, dz3, dx, dy, dz, dx2, dy2, dz2)
hilbertC(s, x+s*dx2, y+s*dy2, z+s*dz2, -dx, -dy, -dz, -dx2, -dy2, -dz2, dx3, dy3, dz3)
hilbertC(s, x+s*dx2+s*dx3, y+s*dy2+s*dy3, z+s*dz2+s*dz3, -dx, -dy, -dz, -dx2, -dy2, -dz2, dx3, dy3, dz3)
hilbertC(s, x+s*dx+s*dx2+s*dx3, y+s*dy+s*dy2+s*dy3, z+s*dz+s*dz2+s*dz3, -dx3, -dy3, -dz3, dx, dy, dz, -dx2, -dy2, -dz2)
hilbertC(s, x+s*dx+s*dx3, y+s*dy+s*dy3, z+s*dz+s*dz3, -dx3, -dy3, -dz3, dx, dy, dz, -dx2, -dy2, -dz2)
hilbertC(s, x+s*dx3, y+s*dy3, z+s*dz3, dx2, dy2, dz2, -dx3, -dy3, -dz3, -dx, -dy, -dz)
end
end

function draw()
update(DeltaTime)
scene:draw()
c=tab
for t=2,xx do
scene.debug:line(vec3(tab[t].x*size,tab[t].y*size,tab[t].z*size),
vec3(c.x*size,c.y*size,c.z*size),color(255))
c=tab[t]
end
if xx<#tab then
xx=xx+1
end
end

function update(dt)
scene:update(dt)
end
``````
• Posts: 965

You guys amaze me.