Voronoi Diagrams

Community Community & Industry Discussion
1

I stumbled across Voronoi Diagrams the other day and thought they were really cool. I made a plugin implementation for Unreal. Hope someone can find it useful!

This repository contains code that can generate a Voronoi Diagram by using an implementation of Fortune’s Algorithm.

To use, clone the code into a directory named ‘VoronoiDiagram’ in your Unreal project’s plugin directory. Don’t forget to add a public dependency to your project for the plugin, or else your Unreal project will not be able to find it.

The following code:



#include"VoronoiDiagram.h"

UTexture2D* MyTexture;
    
FVoronoiDiagram VoronoiDiagram(FIntRect(0, 0, 512, 512));
TArray<FIntPoint> Points;

for(int32 i = 0; i < 100; ++i)
{
    Points.AddUnique(FIntPoint(FMath::RandRange(0, 511), FMath::RandRange(0, 511)));
}
VoronoiDiagram.AddPoints(Points);

FVoronoiDiagramHelper::GenerateTexture(VoronoiDiagram, MyTexture);

Will create a texture similar to:
capture.png

Citations:

Fortune’s Algorithm as outlined in:
Steve J. Fortune (1987). “A Sweepline Algorithm for Voronoi Diagrams”. Algorithmica 2, 153-174.

Bresenham’s line algorithm as outlined in:
Bresenham, J. E. (1 January 1965). “Algorithm for computer control of a digital plotter”. IBM Systems Journal 4 (1): 25–30

Based off of:

as3delaunay

2

Sorry to dig up this thread, but is there any way of approaching this via blueprints only?

3

I didn’t set it up that way, but it probably could be pretty easily.

4

This is interesting. What could you use this for, exactly?

5

I’ve seen people use Voronoi for terrain generation; procedural areas/rooms, etc, anything that requires a nice randomizing pattern.

6

Voronoi is awesome. It’s one of the essential procedural base fractals. Heck, if you can generate the co-ordinates in 3D space with a gradient in each tile you get a great volumetric randomiser. Nice work fuzzy!

7

Just pointing out that Unreal is using this algorithm for destructibility generation on static meshes.

(I’ve added it to my plugin collection)

8

My maps use multiple layers of Voronoi.

9

Okay, I’m trying to include the plugin on my code project. I’ve got the plugin installed and its recognized by the engine, but my source code doesn’t recognize include “VoronoiDiagram.h”

I’ve never installed or run a third party plugin before, so all of this is new to me. I think I’m missing something small but critical: Telling the project about the plugin dependency. I just don’t know where or how to do that, even after looking through all of the documentation. Do I right click on my project in visual studio and add a build dependency? If so, I don’t see the plugin listed.
There’s also an “external dependencies” filter, but it also don’t include VoronoiDiagram.h, or anything like that, and if this is where it goes, I don’t know how to add external dependencies here.
I also build my project and look at the plugins section. The Voronoi plugin shows up and its checked as being enabled for the project.

I’m at a loss. Where and how do I add a “public dependency” to my existing code project?

10

Hey… sry when Im digging this post out, but I find this plugin really cool :smiley:

and I have a question: can I generate the edgePoints for the Voronoi cells? When yes how?

I need It for a City creation.