Howdy, Stranger!

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

Hilbert curve

dave1707dave1707 Mod
in Code Sharing Posts: 9,429

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

Comments

  • SimeonSimeon Admin Mod
    Posts: 5,705

    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
    
  • dave1707dave1707 Mod
    Posts: 9,429

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

  • dave1707dave1707 Mod
    Posts: 9,429

    @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
    
  • dave1707dave1707 Mod
    Posts: 9,429

    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
    
  • dave1707dave1707 Mod
    edited March 25 Posts: 9,429

    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
    
  • Posts: 1,284

    You guys amaze me.

Sign In or Register to comment.