Godot: Implement Voronoi Fracture?

[TritiatedWater]

It would be nice for godot to support Voronoi fracture.
I know bullet physics does.

[akien-mga]

CC @AndreaCatania @reduz

[AndreaCatania]

This is one of the thing that I've to implement, but right now I'm not able to tell you when I can start to work on it. I let you know :grinning:

[Ashafix]

I wrote a Godot plugin using the C++ interface for Qhull (http://www.qhull.org/). It works for 2D rectangles and 3D boxes returning a number of defined fragments.

Left corner: Voronoi cells with random colors and alpha overlaid on sprite.
Main scene: A body which is replaced with Voronoi fragments upon impact.

What would be needed to integrate it into the Godot engine?

Usage

2D

voro = Voronoi.new()
voro.voronoi2d(100)
Calculates 100 2D Voronoi points inside a square

voro.get_vertexes()
Returns a dictionary where the vertex index is the key and the value is a Vector2

voro.get_faces()
Returns an array of arrays where the inner array contains all vertex indexes for a face

3D
voro.voronoi3d(25)
Calculates 25 3D Voronoi points inside a cube

voro.get_faces()
Returns an array of arrays which contain the triangles to generate the mesh for the Voronoi fragment.

Performance

2D

Windows: i5-2500, Windows 10, compiled with standard settings using Visual Studio 2017
Ubuntu: i5-2520M, compiled using g++ 5.4

| points | Windows [msec] | Ubuntu [msec] |
| --- | --- | --- |
| 10 | 6 | 2 |
| 25 | 11 | 3 |
| 50 | 22 | 5 |
| 250 | 104 | 29 |
| 1000 | 419 | 114 |

3D

| points | Windows [msec] | Ubuntu [msec] |
| --- | --- | --- |
|10 | 24 | 7 |
| 25 | 68 | 20 |
| 50 | 147 | 70 |
| 250 | 838 | 287 |
| 1000 | 3732 | 1167 |

[AndreaCatania]

Awesome Job.
Would be useful try it in order to understand it and then discuss how to integrate it inside the editor.

Do you think is it possible test it?

Also the fracturing is not 100% correct, it has a kind of teleport but I think it can be fixed easily.

[Ashafix]

@AndreaCatania an example project is attached
voro_test.zip

If you check out the voronoi branch from my Godot fork (https://github.com/Ashafix/godot/tree/voronoi), the attached project should work (tested on Windows 10 and Ubuntu 16.04).

The teleport effect is due to the fact that the edges of the box are of length 2 while the Voronoi box has a length of 1. It obviously needs some more work.

[AndreaCatania]

The teleport effect is due to the fact that the edges of the box are of length 2 while the Voronoi box has a length of 1. It obviously needs some more work.

To be merged we require that you implement it properly. Let us know when it's done

[Jollyblu]

Hello, there is any chance this will be implemented in Godot 3.2? Also with Lloyd’s Relaxation? It is really useful for procedural generation not just for fragment a mesh like in the image above.
This is an example of implementation in procedural map generation to separate biomes in a more consistent way:
http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/
I know that now we have OpenSimplexNoise in Godot 3.1 but alone is not enough.

[CyanBlob]

I would love for Voronoi and Lloyd's Relaxation to be native to the engine! They're crucial to an upcoming project of mine and implementing them seems like a huge pain. If I get a good grasp of the algorithms I'll start working on adding them to the engine! I only personally care about the 2d implementation, but if it seems easy to extend to higher dimensions I can give that a go as well

[Ashafix]

@CyanBlob I implemented qHull in Godot but didn't find the time to really finish it. Feel free to check my Godot and send me an email if you want to collaborate on it.

[Wapit1]

@Ashafix how is the feature going ? I would love to use it in my VR game :)

[Calinou]

Feature and improvement proposals for the Godot Engine are now being discussed and reviewed in a dedicated Godot Improvement Proposals (GIP) (godotengine/godot-proposals) issue tracker. The GIP tracker has a detailed issue template designed so that proposals include all the relevant information to start a productive discussion and help the community assess the validity of the proposal for the engine.

The main (godotengine/godot) tracker is now solely dedicated to bug reports and Pull Requests, enabling contributors to have a better focus on bug fixing work. Therefore, we are now closing all older feature proposals on the main issue tracker.

If you are interested in this feature proposal, please open a new proposal on the GIP tracker following the given issue template (after checking that it doesn't exist already). Be sure to reference this closed issue if it includes any relevant discussion (which you are also encouraged to summarize in the new proposal). Thanks in advance!