Hilbert curve

dave1707

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={[0]=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

Simeon

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={[0]=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

dave1707

@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.

dave1707

@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={[0]=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

dave1707

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=scene.camera:add(OrbitViewer, vec3(0,25,0), 60, 0, 1000)
    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

dave1707

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=scene.camera:add(OrbitViewer, vec3(0,25,0), 400, 0, 1000)
    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[1]
    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

UberGoober

You guys amaze me.