Simple Voronoi diagram generator. I was trying to see if I could get a speed boost from writing pixel values directly to the video RAM, but regardless the fill walking through all the pixels is still very slow. Any ideas on how I could speed things up?

--voronoi diagram --by hypothete points={} function makepoints() for i=1,16 do e=rnd(128) f=rnd(128) add(points,{ x=e, y=f, c=rnd(255) }) end end function jitter() for i=1,#points do p=points[i] p.x+=rnd(2)-1 p.y+=rnd(2)-1 end end function near(pts,b) nt=nil --nearest pt nd=4096--dist to nt for i=1,#pts do a=pts[i] nl=(b.x-a.x)^2 + (b.y-a.y)^2 --dist leaving off sqrt if(nl<nd)then nd=nl nt=a end end return nt end function drawvoro() for i=0,63 do for j=0,127 do k=i+64*j --x+y*w = 1d position z={x=i*2,y=j} np=near(points,z) if(np) then memset(0x6000+k,np.c,0x1) end end end end function _init() makepoints() drawvoro() end function _update() if(btnp(5)) then jitter() drawvoro() end end |

Not sure how much faster it'll make it, but I've heard using the ^ operator is slower than using a multiplication. So instead of (b.x - a.x) ^ 2 is slower than (b.x - a.x) * (b.x - a.x)

I can thing of a couple ideas.

The easiest seems to be fairly popular in Pico8 demos. Randomly choose which pixels to update each frame instead of using a for loop. The finished image will converge fairly quickly.

Another idea is algorithmic. You might want to google around, but I remember there being a algorithm that goes something like this: Find the closest two points and the difference of their distances. Advance that many pixels and then evaluate the closest two points again. You might be able to reduce the number of sorts using a hilbert curve or a recursive structure (that would be very rectfill friendly).

min2 version using circles and randomization also works pretty good. Converges quickly while minimizing edge artifacts.

Ok. I'm sort of having fun with this... Min2 version that skips along the x and interleaves scanlines:

A bit slower. Might try a recursive one that works by subdividing 8x8 blocks.

Here's an image showing pixels instead of drawing lines with lineskip.

So the only really interesting thing in all of these is the modified near function:

function near2(pts, x, y) local p1, p2 = nil local d1, d2 = 0x7fff, 0x7fff for i = 1, #pts do local p0 = pts[i] local dx, dy = (x - p0.x)/16, (y - p0.y)/16 local d0 = dx*dx + dy*dy if d0 < d1 then p2, d2 = p1, d1 p1, d1 = p0, d0 elseif d0 < d2 then p2, d2 = p0, d0 end end return 8*(sqrt(d2) - sqrt(d1)), p1.c end |

It returns the nearest point, and the minimum distance you can go before it could possible swap with the next closest point.

Ok. Here's the code for all my experiments. Left and right change the algorithm, while up and down change the quality. The near2 monte carlo version is my favorite. It converges quickly, and is sort of a neat effect.

function jitter(points) for i = 1, #points do p = points[i] p.x += rnd(2) - 1 p.y += rnd(2) - 1 end end function near(x, y, points) local p1 local d1 = 0x7fff for i = 1, #points do local p0 = points[i] local dx, dy = (x - p0.x)/16, (y - p0.y)/16 local d0 = dx*dx + dy*dy if d0 < d1 then p1, d1 = p0, d0 end end return p1.c end function near2(x, y, points) local p1, p2 local d1, d2 = 0x7fff, 0x7fff for i = 1, #points do local p0 = points[i] local dx, dy = (x - p0.x)/16, (y - p0.y)/16 local d0 = dx*dx + dy*dy if d0 < d1 then p2, d2 = p1, d1 p1, d1 = p0, d0 elseif d0 < d2 then p2, d2 = p0, d0 end end return 8*(sqrt(d2) - sqrt(d1)), p1.c end function brute(points, res) for y = 0, 128 do for x = 0, 128 do local c = near(x, y, points) pset(x, y, c) end end return "brute" end function vorocell(s, cx, cy, points, res) local x0, y0 = s*cx, s*cy if s <= res then local c = near(x0 + 0.5, y0 + 0.5, points) rectfill(x0, y0, x0 + s, y0 + s, c) else local s2 = s/2 local rl, c = near2(x0 + s2, y0 + s2, points) if rl > s2*1.41 then rectfill(x0, y0, x0 + s, y0 + s, c) else local cx2 = cx*2 local cy2 = cy*2 vorocell(s2, cx2 + 0, cy2 + 0, points, res) vorocell(s2, cx2 + 1, cy2 + 0, points, res) vorocell(s2, cx2 + 0, cy2 + 1, points, res) vorocell(s2, cx2 + 1, cy2 + 1, points, res) end end end function subdivide(points, res) vorocell(128, 0, 0, points, shl(1, res - 1)) return "subdivide" end function runlength(points, res, frame) for y = frame%res, 128, res do local x = 0 while x < 128 do local rl, c = near2(x, y, points) -- Clamp the run length to 1. -- Rounding helps remove aliasing. rl = max(1, flr(rl + 0.5)) line(x, y, x + rl, y, c) x += rl end end return "runlength" end function montecarlo(points, res) for i = 0, res*50 do local x, y = rnd(128), rnd(128) local rl, c = near2(x, y, points) circfill(x, y, rl, c) end return "montecarlo" end local points = {} local res = 1 local frame = 0 local rendermethod = 1 local rendermethods = { brute, subdivide, runlength, montecarlo } function _init() for i = 0, 15 do add(points, {x = rnd(128), y = rnd(128), c = i}) end end function _update() res -= (btnp(2) and 1 or 0) res += (btnp(3) and 1 or 0) res = max(res, 1) rendermethod += (btnp(1) and 1 or 0) rendermethod -= (btnp(0) and 1 or 0) rendermethod %= #rendermethods end function _draw() printh(rendermethod) local render = rendermethods[rendermethod + 1] local name = render(points, res, frame) rectfill(0, 0, #name*4, 5, 0) print(name, 0, 0, 7) local fps = "fps: "..(30/stat(1)) rectfill(0, 6, #fps*4, 11, 0) print(fps, 0, 6, 7) frame += 1 jitter(points) end |

slembcke, these are remarkable, thanks for sharing! I'm going to try out line skip and your mixed shapes approach. Great idea on using monte carlo methods.

Ok. Last one I think. Near2 accelerated monte carlo with 32 regions and a jitter function that avoids clumping:

[Please log in to post a comment]