News for hackers. Stuff that matters.
Re:Voronoi Diagrams on the GPU by Rhapso on Wednesday April 13, 2016 @08:37PM (#11493517)
aha, finally a chance to post my only meaningful contribution to computer science:

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=tru...

draft here (because I can't give away the final version): https://github.com/BrendanBenshoof/pyVHASH/raw/master/Paper/...

Nifty because it is distributed, works in any metric space where voronoi regions make sense (XOR and non-euclidian ones as a start!) and easy to make into an online algorithim that updates as nodes join and exit.

basically:

   given a center point $center$
   given a list of candidate points $candidate$
   to output a list $peers$
   
   sort $candidates$ by distance from $center$
   remove the closest candidate and add to $peers$ (it will always be a delaunay peer)
   for $c$ in candidates:
      if any member of $peers$ is closer to $c$ than $center$ then reject $c$
      else add $c$ to $peers$
essentially this generates most of a delaunay triangulation, and you can quickly find the voronoi generator of a given point by greedily traversing the resulting graph.
Re:Voronoi Diagrams on the GPU by faitswulff on Thursday April 14, 2016 @12:04AM (#11494220)
Sorry if this is only tangential to your comment and naive to boot, but why is it that you can't give away the final version of your paper?
Re:Voronoi Diagrams on the GPU by Rhapso on Thursday April 14, 2016 @08:47AM (#11496164)
Essentially to get published you have to give away all the publishing rights for the work you submitted. I'd prefer open access journals, but the people who decide if I get my phd don't value those like I do.
Re:Voronoi Diagrams on the GPU by bobdo on Thursday April 14, 2016 @09:54AM (#11496662)
The IEEE actually has a reasonable policy https://www.ieee.org/documents/author_faq.pdf(see section 2). Essentially authors are allowed to post the version of the paper that they submitted for final publication.
Re:Voronoi Diagrams on the GPU by cinquemb on Thursday April 14, 2016 @12:28AM (#11494308)
Re:Voronoi Diagrams on the GPU by Rhapso on Thursday April 14, 2016 @08:47AM (#11496168)
awesome!
Re:Voronoi Diagrams on the GPU by eru on Thursday April 14, 2016 @12:08AM (#11494236)
Probably some copyright shenanigans with the journal published in.
Re:Voronoi Diagrams on the GPU by gregschlom on Wednesday April 13, 2016 @08:25PM (#11493465)
I love Voronoi diagrams, and especially Centroidal Voronoi Tesselations. They relate to many natural phenomena such as honeycombs and soap bubbles. I used that as the basis for an art installation I did for Burning Man: http://www.flowandwonder.com.

Another technique for computing them on the GPU, not sure how related it is to OP's technique: http://www.iquilezles.org/www/articles/voronoilines/voronoil...

Edit: shadertoy link: https://www.shadertoy.com/view/ldl3W8

Re:Voronoi Diagrams on the GPU by adriand on Wednesday April 13, 2016 @10:10PM (#11493871)
That is wild! Wow, what an incredible installation! Do you have video of this at night? It looks fantastic.
Re:Voronoi Diagrams on the GPU by runeb on Thursday April 14, 2016 @07:51AM (#11495832)
Great project! Would also love to see a video of this.
Re:Voronoi Diagrams on the GPU by bladecatcher on Wednesday April 13, 2016 @11:58PM (#11494202)
That's an inspiring project. Thanks for sharing
Re:Voronoi Diagrams on the GPU by exDM69 on Thursday April 14, 2016 @04:07AM (#11495008)
There's a much faster O(n) method for doing Voronoi diagrams on the GPU by taking advantage of the depth buffer. It's so simple that it gives you one of those "why didn't I think of this earlier" moments. I learned it from the old school demoscene guys at work...

    0. Set up orthographic projection
    1. Enable depth testing
    2. For each "seed" point, draw an "infinite" cone all the way from the near to the far clipping plane
    3. Shade with solid colors.
That's it.

The depth testing will only leave fragments of the cone that the corresponding pixel is closest to. If you need better precision, draw the "cone" by making a full screen quad and use the fragment shader to set depth (gl_FragDepth) according to distance from seed point (or just use enough vertices in the cones).

If you change the circular cone to a rectangular-based pyramid shape, you'll get Voronoi-type diagrams but with a different metric (manhattan distance?). Turn the rectangle 45 degrees to make a diamond shaped base and you have yet another metric.

Re:Voronoi Diagrams on the GPU by mrec on Thursday April 14, 2016 @07:42AM (#11495786)
Heh, I remember this technique from the OpenGL Red Book, at least 15-20 years ago.

http://www.glprogramming.com/red/chapter14.html#name19

Re:Voronoi Diagrams on the GPU by exDM69 on Thursday April 14, 2016 @08:25AM (#11496032)
Cool! I've of course read the Redbook back in the day (I think I still have it printed out in my shelf) but for some reason I've missed that chapter.

I didn't quite get what you need the stencil buffer for in that technique.

Re:Voronoi Diagrams on the GPU by mrec on Thursday April 14, 2016 @09:39AM (#11496555)
The stencil buffer provides a boolean mask for the regions you care about, making it easy to draw them in flat color with a subsequent pass. I can't see a way to do that easily with depth information only.

(Plus, it was traditional to combine 24-bit depth with 8-bit stencil in the same buffer, so stencil writes were basically free if you're writing depth anyway.)

Re:Voronoi Diagrams on the GPU by exDM69 on Thursday April 14, 2016 @02:16PM (#11499149)
Yeah, that's pretty similar to the stenil-then-cover technique used in vector graphics.

But what advantage does a two pass stencil technique have over just writing to the color buffer in the first pass?

Re:Voronoi Diagrams on the GPU by mrec on Thursday April 14, 2016 @07:02PM (#11500943)
Oh, I see what you mean. Good question. I suppose it might have been more efficient to avoid multiple colour buffer overdraws (since you're drawing a fullscreen quad for each seed point, albeit a depth-tested one). And you could render the depth+stencil buffer once then reuse it to highlight different regions, e.g. on mouseover.

But you're right, it doesn't sound massively compelling. And the traditional 24depth+8stencil buffer format would limit you to a maximum of 256 regions, which could easily cramp your style.

Re:Voronoi Diagrams on the GPU by shultays on Thursday April 14, 2016 @10:02AM (#11496748)
Article just does logn (n is dimension of input texture) passes on the render target and that is it. complexity is independent of number of seeds.
Re:Voronoi Diagrams on the GPU by nraynaud on Thursday April 14, 2016 @04:16AM (#11495037)
well, if you're doing that, then just use the distance function, at least you've got a perfectly circular cone, and you don't get tricked by the maximum distance of the cone.

the complexity is num pixels*num entities.

implementation here: https://github.com/nraynaud/webgcode/blob/gh-pages/webapp/sh...

I would gladly show the result here: http://nraynaud.github.io/webgcode/various_tests/test_vorono... but it looks like Chrome removed PathSegList that the SVG library was using internally

edit: it still works in firefox, it extracts the voronoi diagram, the medial axis, then does a subtraction on the medial axis (internal offset of the original polygon), then a minimum threshold (mickey ears for pocketting in milling), then a reconstruction of the polygon from the altered medial axis.

Re:Voronoi Diagrams on the GPU by exDM69 on Thursday April 14, 2016 @06:25AM (#11495470)
Your pixel shader implementation is quite clean and simple. But the method I described doesn't rely on shaders at all, it uses the fixed function triangle rasterization and depth testing. It has different performance characteristics. That method is also of historical interest because it works (and is fast) also on pre-shader graphics accelerators.
Re:Voronoi Diagrams on the GPU by 33a on Wednesday April 13, 2016 @09:20PM (#11493679)
This isn't actually a voronoi diagram, it is an (approximate) distance transform - though it is still pretty cool!

If you are working on a grid, there are lots of ways to compute distance transforms exactly. An exact and optimal serial algorithm which works for any metric is due to Meijster, and it runs in O(n) time in the number of pixels:

http://parmanoir.com/distance/

Distance transforms are a special kind of (max, +) convolution, and have lots of interesting algebraic properties

Re:Voronoi Diagrams on the GPU by vanderZwan on Thursday April 14, 2016 @03:22AM (#11494860)
The linked paper specifically says "Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform," so are you sure it's not both in this case?
Re:Voronoi Diagrams on the GPU by 33a on Thursday April 14, 2016 @10:42AM (#11497096)
To compute a voronoi diagram, you also need to reconstruct the boundary and topology of all the cells, which is not being done here. Also most algorithms for computing voronoi diagrams do not snap the vertices to integer lattice coordinates.
Re:Voronoi Diagrams on the GPU by vanderZwan on Friday April 15, 2016 @08:42AM (#11503785)
Would it be fair to say this is a fast rasterization algorithm?
Re:Voronoi Diagrams on the GPU by nathancahill on Wednesday April 13, 2016 @09:05PM (#11493626)
Any good resources for getting started with WebGL? I'm going to start transitioning a large amount of slow <canvas> drawing to WebGL, and I'd love any pointers for someone getting started without any experience in graphics and gaming (which seems to be the starting point most tutorials use).
Re:Voronoi Diagrams on the GPU by rjkaplan on Wednesday April 13, 2016 @09:18PM (#11493670)
I recently got started with WebGL so I hope that others post more/better resources, but...

- I found this to be a good starting point for WebGL as a whole: https://webglfundamentals.org/

- This is a great resource for learning about GLSL and shaders (writing code that runs on the GPU): http://patriciogonzalezvivo.com/2015/thebookofshaders/

- As a starting point for implementing the Jump Flood Algorithm (which is what I used to implement the Voronoi Diagram demos) I found it helpful to read Chris Wellon's articles on GPGPU programming. Here's the first one: http://nullprogram.com/blog/2014/06/10/

Re:Voronoi Diagrams on the GPU by mattdesl on Wednesday April 13, 2016 @10:25PM (#11493924)
Re:Voronoi Diagrams on the GPU by Zecc on Thursday April 14, 2016 @10:57AM (#11497217)
Re:Voronoi Diagrams on the GPU by riebschlager on Wednesday April 13, 2016 @10:01PM (#11493831)
Ryan! Thanks for writing this post. I had messed around with Voronoi diagrams in Processing and D3 without really understanding the intricacies behind it. This is a great explanation of what's going on.

I'd love to see more stuff like this on HN.

Re:Voronoi Diagrams on the GPU by rjkaplan on Wednesday April 13, 2016 @10:06PM (#11493851)
Thanks - I'm glad you found it interesting!
Re:Voronoi Diagrams on the GPU by ewencp on Wednesday April 13, 2016 @10:45PM (#11493989)
It's not particularly efficient, but probably the easiest way to draw Voronoi diagrams on the GPU doesn't require a shader at all. Instead, use an orthographic projection and draw cones for each vertex with the cone's apex at the vertex and its axis oriented into the screen. Then the GPU's z-buffer takes care of choosing which vertex is closes to the given pixel.
Re:Voronoi Diagrams on the GPU by rjkaplan on Wednesday April 13, 2016 @10:56PM (#11494027)
Yeah! It's a pretty big omission in my post that I don't talk about other methods of generating Voronoi diagrams, but I wanted to keep it relatively short.

Chris Wellons has a great article on the method that you mention: http://nullprogram.com/blog/2014/06/01/

It's also mentioned in the OpenGL red book: http://www.glprogramming.com/red/chapter14.html#name19

Re:Voronoi Diagrams on the GPU by lmeyerov on Thursday April 14, 2016 @09:55AM (#11496676)
Yes, this is similar to what I and others described! Underneath, similar stuff going on in the HW :)
Re:Voronoi Diagrams on the GPU by lmeyerov on Wednesday April 13, 2016 @07:58PM (#11493343)
We use a weak approximation of this for hit testing. So awesome!
Re:Voronoi Diagrams on the GPU by rjkaplan on Wednesday April 13, 2016 @08:03PM (#11493373)
Cool! If you're willing to share, I'm interested to hear how your approximation works. Do you just do fewer rounds? Do you use bigger step sizes?
Re:Voronoi Diagrams on the GPU by lmeyerov on Wednesday April 13, 2016 @09:18PM (#11493671)
It's point picking for ~svg, where we draw a wider region than the actual elements and just go with that. The goal is not having to precisley click on small objects in a big scene. This generates a reverse index for knowing which element each pixel fuzzily refers to, and if far, if better described as blankspace. So, just 1 step, and we can cover a huge scene :)
Re:Voronoi Diagrams on the GPU by flashman on Wednesday April 13, 2016 @09:05PM (#11493625)
If you use a grid of regularly-spaced points, you end up with a pixelated/mosaic image. Here's a (sadly Flash based) tool for applying a quadrilateral/triangular/hexagonal mosaic effect to a photo: http://damienclarke.me/code/mosaic-maker
Re:Voronoi Diagrams on the GPU by Franciscouzo on Thursday April 14, 2016 @10:24AM (#11496953)
Can't see your link because I don't have flash, but I made a similar thing with HTML5 https://franciscouzo.github.io/voronoi/
Re:Voronoi Diagrams on the GPU by bhickey on Thursday April 14, 2016 @07:55AM (#11495855)
Here's an implementation of 2d Worley noise using a hexagonal grid with one-point per cell: https://www.shadertoy.com/view/ltjXz1

This version may still have artifacts when the points fall too close to a cell boundary.

Re:Voronoi Diagrams on the GPU by swayvil on Thursday April 14, 2016 @01:04AM (#11494405)
This guy is all about voronoi diagram based animation.

https://vimeo.com/159319784

Also this guy, maybe more so. (There seems to be a connection).

https://vimeo.com/155733402

Re:Voronoi Diagrams on the GPU by boredatnight12 on Wednesday April 13, 2016 @11:30PM (#11494114)
http://mappable.com made an incredible music product out of these kinds of layouts. Pity more people don't know about it.
Re:Voronoi Diagrams on the GPU by raverbashing on Wednesday April 13, 2016 @09:43PM (#11493766)
Worked on my mobile browser, apparently without major issues
Re:Voronoi Diagrams on the GPU by desdiv on Wednesday April 13, 2016 @10:13PM (#11493881)
Ironically, it's not working on my desktop browser.

I'm getting "DEMO DISABLED. COULDN'T START WEBGL." on my Chrome on Windows 10 on Intel integrated graphics setup, literally the most common browser on the most common OS on the most common graphics stack.

Re:Voronoi Diagrams on the GPU by rjkaplan on Wednesday April 13, 2016 @10:23PM (#11493917)
I'm sorry that you're running into issues - I just got started with WebGL and I don't have a Windows machine to test on. I'd be interested to know if other WebGL demos work on your machine. Do you see a triangle and square when you visit this page? http://learningwebgl.com/lessons/lesson01/index.html
Re:Voronoi Diagrams on the GPU by desdiv on Wednesday April 13, 2016 @11:17PM (#11494083)
Yep, the demo is working fine on both Firefox 45.0.2 and Chrome 49.0.2623.112. Both browsers are failing on your site for some reason.
Re:Voronoi Diagrams on the GPU by rjkaplan on Wednesday April 13, 2016 @11:47PM (#11494164)
I fixed an issue that I was able to repro on a Windows machine. It'd be great if you could try again and let me know if it now works for you!
Re:Voronoi Diagrams on the GPU by desdiv on Thursday April 14, 2016 @02:42AM (#11494711)
It's working perfectly now. Thanks!
Re:Voronoi Diagrams on the GPU by Schwolop on Wednesday April 13, 2016 @11:21PM (#11494089)
I have the same issue, and yes, that other page works.
Re:Voronoi Diagrams on the GPU by rjkaplan on Thursday April 14, 2016 @12:47AM (#11494359)
Thanks for the report - I reproduced and fixed an issue on a Windows machine. It'd be great if you could let me know if it now works for you!
Re:Voronoi Diagrams on the GPU by Schwolop on Friday April 15, 2016 @02:38AM (#11502614)
Yep, works now. Cheers
Re:Voronoi Diagrams on the GPU by uptownfunk on Wednesday April 13, 2016 @08:25PM (#11493463)
What are these used for?
Re:Voronoi Diagrams on the GPU by privong on Wednesday April 13, 2016 @08:52PM (#11493575)
In astrophysics, voronoi tessellation is used for adaptively smoothing data to reach a desired signal-to-noise ratio while trying to preserve as much spatial/angular resolution as possible [0]. It is also used in numerical hydrodynamic simulations to dynamically construct the mesh of cells for the hydro calculations[1, 2].

[0] http://www-astro.physics.ox.ac.uk/~mxc/software/#binning

[1] http://wwwmpa.mpa-garching.mpg.de/~volker/arepo/

[2] http://www.tapir.caltech.edu/~phopkins/Site/GIZMO.html

Re:Voronoi Diagrams on the GPU by flashman on Wednesday April 13, 2016 @09:08PM (#11493636)
A little bit non-standard, but I used them to generate a map of the nearest vehicle spawn points for the game DayZ: http://i.imgur.com/GryW1fz.jpg

In the attached map, the red dots indicate a place where a truck might spawn. The polygons show the places nearest each truck. If a player wants to obtain a truck to drive, this map shows them which direction to run.

This was more a proof of concept than anything else, and is sadly outdated. In any case, it never took into account the steepness of terrain, which influences player running speed.

Re:Voronoi Diagrams on the GPU by rjkaplan on Wednesday April 13, 2016 @08:44PM (#11493541)
I mostly just think they look cool :)

In the post there's a demo on how to use the same algorithm that generates Voronoi diagrams to render 2D drop shadows with a spread radius.

You may also be interested in Alan Zucconi's article on Voronoi diagrams where he outlines a few use-cases in games: http://www.alanzucconi.com/2015/02/24/to-voronoi-and-beyond/...

Re:Voronoi Diagrams on the GPU by Jack000 on Wednesday April 13, 2016 @11:40PM (#11494145)
http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html

when generalized to line segments, voronoi diagrams can be used to efficiently compute offset contours.

Offsets are used for CNC operations, slicing 3d print models, robotic path planning etc.

Re:Voronoi Diagrams on the GPU by fvargas on Thursday April 14, 2016 @12:07AM (#11494234)
One use is in AI path planning algorithms. When you have a continuous space with obstacles, you can discretize the space by constructing a Voronoi diagram where the nodes are at the maximal distance away from obstacles.
Re:Voronoi Diagrams on the GPU by tribe on Wednesday April 13, 2016 @11:03PM (#11494039)
I have used Voronoi diagrams (and their corresponding Delaunay triangulations) for interpolation routines.
Re:Voronoi Diagrams on the GPU by a3n on Wednesday April 13, 2016 @08:40PM (#11493528)
Re:Voronoi Diagrams on the GPU by a3n on Wednesday April 13, 2016 @09:05PM (#11493627)
The wikipedia page has a nice section on what these are used for.