Quickly creating voronoi texture

Hello, my goal is to create a texture with voronoi seeds that have assigned colors. Now, I go over each pixel (about 2 millions of them) and I look up which seed is closest and give pixel the color of the seed. Problem is that I have thousand seeds and this take some time (about 2 minutes) - is there something that could help me optimize this texture creation?

This of course is not 1000 seeds (about 50 in reality) but this is what I want to create.

Use a Quadtree.

If you have some time and you’re looking for a simple explanation and an example I can recommend this CodingTrain video.

Microsoft has a reference implementation over here, however the code is not allowed to be used in any project that is intended to be published anywhere since it’s under a reference only license. However there are other implementations like this one. This framework also seems to have a QuadTree under an MIT license. Though I haven’t used them myself.

Going pixel by pixel could by really slow if you have lot of seeds. When I was facing similar problem I iterate throught every seed in loop and set pixels near seed center. First loop - distance 1, second loop distance 2 etc. Make some class that you use for save data for pixel. Put there current region that this pixel belongs and distance from region center (needed only if want use euclidean distance). If region when expanding own border hit pixel that belong to other region, check distance and if it’s shorter, replace data. End when there was 0 changes in loop (0 new pixels added, and 0 pixels region parent changes).

Here’s mine example:

    using System.Collections;
    using System.Collections.Generic;
    using System.IO;
    using UnityEditor;
    using UnityEngine;
    
    public class VoronoiDiagram : MonoBehaviour {
    
    	public int seed;
    	public string saveFileName = "SavedTexture";
    	public bool distanceCorrection = true;
    
    	bool bType = false;
    
    	public int size = 1024;
    	public int regions = 10;
    	public Color[] regionsColors;
    
    	const int centerDrawSize = 5;
    	Color centerColor = Color.black;
    
    	Texture2D texture;
    
    	List<Vector2> regionCenter;
    	List<Region> currentRegions;
    	Cell[,] cells;
    	float startTime;
    
    	public class Region {
    		public Vector2 center;
    		public Color color;
    		public List<Region> neighbours;
    	}
    
    	public class Cell {
    		public Region region;
    		public float distance;
    	}
    
    	[ContextMenu("Generate")]
    	public void Generate() {
    
    		startTime = Time.realtimeSinceStartup;
    		Random.InitState(seed);
    
    		if (size < regions) {								//	protection for long loop when searching for region centers
    			Debug.LogError("Size too small");
    			return;
    		}
    
    		string path = Application.dataPath + "/" + saveFileName + ".png";
    		texture = new Texture2D(size, size, TextureFormat.RGB24, false);
    
    		for (int y = 0; y < size; y++) {
    			for (int x = 0; x < size; x++) {
    				texture.SetPixel(x, y, Color.white);
    			}
    		}
    
    		cells = new Cell[size, size];
    
    		GenerateCenters();
    
    		if (!bType) {
    			FillRegions();
    		} else {
    			FillRegions2();
    		}
    
    		DrawCenters();
    
    		File.WriteAllBytes(path, texture.EncodeToPNG());
    		AssetDatabase.Refresh();
    		Debug.Log("Voronoi finished, time: " + (Time.realtimeSinceStartup - startTime));
    	}
    
    	private void DrawCenters() {
    		for (int i = 0; i < regionCenter.Count; i++) {
    			for (int y = -centerDrawSize; y <= centerDrawSize; y++) {
    				for (int x = -centerDrawSize; x <= centerDrawSize; x++) {
    					TrySetPixel((int)regionCenter_.x + x, (int)regionCenter*.y + y, centerColor);*_

* }*
* }*
* }*
* }*

* private void FillRegions() {*
* bool changed = false;*
* int currentSize = 0;*

* do {*

* changed = false;*

* for (int i = 0; i < regionCenter.Count; i++) {*

* for (int x = -currentSize; x <= currentSize; x++) {*
if (TrySetCell((int)regionCenter.x + x, (int)regionCenter_.y + currentSize, currentRegions*)) {
changed = true;
}
}*_

* for (int x = -currentSize; x <= currentSize; x++) {*
if (TrySetCell((int)regionCenter.x + x, (int)regionCenter_.y - currentSize, currentRegions*)) {
changed = true;
}
}*_

* for (int y = -currentSize + 1; y <= currentSize - 1; y++) {*
if (TrySetCell((int)regionCenter.x + currentSize, (int)regionCenter_.y + y, currentRegions*)) {
changed = true;
}
}*_

* for (int y = -currentSize + 1; y <= currentSize - 1; y++) {*
if (TrySetCell((int)regionCenter.x - currentSize, (int)regionCenter_.y + y, currentRegions*)) {
changed = true;
}
}*_

* }*

* currentSize++;*

* } while (changed);*
* }*

* private void FillRegions2() {*
* for (int y = 0; y < size; y++) {*
* for (int x = 0; x < size; x++) {*
* TrySetCell(x, y, ClosestRegion(x, y));*
* }*
* }*
* }*

* Region ClosestRegion(int x, int y) {*
* Region closest = null;*
* float minDistance = float.MaxValue;*
* Vector2 pos = new Vector2(x, y);*

* for (int i = 0; i < regions; i++) {*
_ float checkDistance = Vector2.Distance(currentRegions*.center, pos);
if (checkDistance < minDistance) {
closest = currentRegions;
minDistance = checkDistance;
}
}*_

* return closest;*
* }*

* private bool TrySetPixel(int x, int y, Color color) {*
* bool retVal = false;*

* if (x >= 0 && x < size && y >= 0 && y < size) {*
* retVal = true;*
* texture.SetPixel(x, y, color);*
* }*

* return retVal;*
* }*

* private bool TrySetCell(int x, int y, Region region) {*
* bool retVal = false;*
* bool newCell = false;*

* if (x >= 0 && x < size && y >= 0 && y < size) {*

* if (cells[x, y] == null) {*
* cells[x, y] = new Cell();*
* newCell = true;*
* }*

* float distance = Vector2.Distance(new Vector2(x, y), region.center);*

* if (newCell || (distanceCorrection && distance < cells[x, y].distance)) {*
* cells[x, y].distance = distance;*
* cells[x, y].region = region;*
* retVal = TrySetPixel(x, y, region.color);*
* }*

* }*

* return retVal;*
* }*

* private void GenerateCenters() {*
* currentRegions = new List();*
* regionCenter = new List();*

* for (int i = 0; i < regions; i++) {*
* currentRegions.Add(new Region());*
* Vector2 newRegionCenter;*

* do {*
_ newRegionCenter = new Vector2((int)(Random.value * size), (int)(Random.value * size));
* } while (regionCenter.Contains(newRegionCenter));*_

* regionCenter.Add(newRegionCenter);*
_ currentRegions*.center = newRegionCenter;
currentRegions.color = regionsColors[(int)(Random.value * regionsColors.Length)];
}
}
}*_