1

I'm hoping to create a Voronoi landscape in Unity in C#. I looked at a number of Unity Project files, but they all implement Fortune's algorithm, which is completely over my head. Are there any other methods of generating Voronoi diagram (that is easier to understand)? Slow performance is completely fine with me. Much appreciated!

Sidenote: Since I'm working in Unity and need to generate 2D/3D mesh from Voronoi diagram, per-pixel distance check won't work :,( On second thought, maybe I could use a 2D array of Vector2s instead of pixels, that are 1.0 unit spaced apart in x and z axis.

Komm
  • 331
  • 2
  • 13
  • So do you actually need the geometrically exact Voronoi diagram or is an pixel approximation fine, as you mention "landscape"? – gue Jul 27 '17 at 06:29
  • An approximation is absolutely fine. Although it would be nice to have vertex or edge data, so I can use them to generate a mesh. Thank you gue! – Komm Jul 27 '17 at 06:44
  • Possible duplicate of [Easiest algorithm of Voronoi diagram to implement?](https://stackoverflow.com/questions/973094/easiest-algorithm-of-voronoi-diagram-to-implement) – Micromega Jul 27 '17 at 07:19

2 Answers2

3

There is a very simple way to create an approximated Voronoi diagram VD. For every Site s that should define a cell in the VD (2D-plane) you center a cone at s with constant slope and a certain height. Then you look from above onto that landscape of cones (where all the spikes are visible). The boundary where the different cones meet (projected to the 2D-plane) is the (approximated) Voronoi diagram.

enter image description here

(Image Source)

As you requested in the comments, to get the actual edge data seems not so easy. But there could be some graphical routines to generate them by intersecting the cones.

An alternative is to compute a Delaunay triangulation of the given point set. There are some implementation referenced in this related post (also simple approximations are mentioned). Then you compute the dual graph of your triangulation and you have the Voronoi diagram. (Dual graph means that for every for every edge AB in the triangulation there exists an edge in the VD bisecting the space between the two vertices A and B, and for every triangle there exists a vertex in the VD where the dual edges meet.) Othwerwise there are also many C# Voronoi implementations around: Unity-delaunay, but as you mentioned using the Fortune approach.

If you want to code everything yourself you may compute a triangulation of the points with brute force for n points in O(n^2) time. Then apply in-circle tests and edge flips. That is, for every triangle t(abc) create a circle C defined by the three vertices of t. Then check if there lies another point d of your point set inside C. If so, then flip the edge that is in t as well as forms an edge in the triangle with d. This flipping is done until all triangles fulfil the empty circle property (Delaunay condition). Again with brute force will take O(n^2) time. Then you can compute the dual graph as mentioned above.

enter image description here

(Image Source)

gue
  • 1,868
  • 1
  • 16
  • 21
  • @gui: You are a PhD? Woah! – Micromega Jul 27 '17 at 08:01
  • The idea is to just place the cones without actually intersecting them. Then you can use any ray tracer like Blender and look from the top and immediately "see" (with human eyes) the VD, as it is formed by the valleys between the cones. From below you would only see a flat surface then. To get the actual VD from this graphical representation is not so simple. – gue Jul 27 '17 at 10:49
3

"Easiest? That's the brute-force approach: For each pixel in your output, iterate through all points, compute distance, use the closest. Slow as can be, but very simple. If performance isn't important, it does the job."

[1] Easiest algorithm of Voronoi diagram to implement?

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • 1
    The referenced algorithm is Bowyer-Watson which has nothing to do with the pixel approximation you describe in the answer. – gue Jul 27 '17 at 07:41
  • I am not a phd. I see the mistake, the ref you used is not the one you quote, you quote (https://stackoverflow.com/a/10848478/4462067) but referenced (https://stackoverflow.com/questions/973094/easiest-algorithm-of-voronoi-diagram-to-implement/18084287#18084287). That is where my confusion came from. – gue Jul 27 '17 at 08:07
  • @gue: I am sorry, fixed. – Micromega Jul 27 '17 at 08:11