<p><a href="http://www.cs.sandia.gov/~samitch/papers/vor_final.pdf" rel="nofollow">http://www.cs.sandia.gov/~samitch/papers/vor_final.pdf</a> There isn't the computer algorithm in any programming languague, but u should be able to replicate it easily with some Plane Reflections and the algorithms from the above link.</p>

CC BY-SA 3.0
2016-10-13T21:22:11.790Z
Welcome to ComputerGraphics.SE! It's normally a good idea to make answers on Stack Exchange self contained (e.g. in case links go down and also in general so that people don't have to follow links to be able to tell if an answer is useful to them). You might want to improve your answer by including a short summary of the contents of the paper.
Martin Ender
CC BY-SA 3.0
2016-09-28T22:25:13.647Z
2016-09-28T22:25:13.647Z
Zeitaku Enjin
<p>I would like to implement a Maya plugin (this question is independent from Maya) to create 3D Voronoi patterns, Something like </p>

<p><a href="https://i.sstatic.net/8RYgU.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8RYgU.jpg" alt="enter image description here"></a></p>

<p>I just know that I have to start from point sampling (I implemented the adaptive poisson sampling algorithm described in <a href="http://link.springer.com/article/10.1007%2Fs11432-011-4322-8#/page-1" rel="nofollow noreferrer">this paper</a>). </p>

<p>I thought that, from those points, I should create the 3D wire of the mesh applying Voronoi (I tried to use (Python) scipy.spatial.Voronoi but the result was something different from what I expected).</p>

<p>I am missing something? Can anyone suggest the proper pipeline and algorithms I have to implement to create such patterns?</p>

<p>[EDIT] Here are a few example of what I get handling the result i get from scipy.spatial.Voronoi like this (as suggested <a href="https://stackoverflow.com/questions/23658776/voronoi-diagram-edges-how-to-get-edges-in-the-form-point1-point2-from-a-scip">here</a>):</p>

<pre><code>vor = Voronoi(points)
for vpair in vor.ridge_vertices:
    for i in range(len(vpair) - 1):
        if all(x &gt;= 0 for x in vpair):
            v0 = vor.vertices[vpair[i]]
            v1 = vor.vertices[vpair[i+1]]
            create_line(v0.tolist(), v1.tolist())
</code></pre>

<p>The grey vertices are the sampled points (the original shape was a simple sphere):
<a href="https://i.sstatic.net/gz8hD.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/gz8hD.png" alt="enter image description here"></a></p>

<p>Here is a more complex shape (an arm)
<a href="https://i.sstatic.net/mCkPm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/mCkPm.png" alt="enter image description here"></a></p>

CC BY-SA 3.0
2015-10-20T15:55:23.550Z
Thank you for the reply. I am going to replicate what I did and post a screen as suggested. Anyway the final intent of this question isn't to debug my code, but to understand if what I am doing is right or there are others steps that I am missing in between!
Jiloc
CC BY-SA 3.0
2015-10-21T11:38:50.710Z
added examples as suggested!
Jiloc
CC BY-SA 3.0
2015-10-21T20:10:46.213Z
The points from the poisson sampling are right. The algorithm that generates them is fully unit tested and the ones you see in the screens are spheres with the center in the sampled point which i programmatically created before calling Voronoi(points)! I am worried that I am not following the proper path or I am handling the Voronoi result in a wrong way
Jiloc
CC BY-SA 3.0
2015-10-22T03:57:12.260Z
The images you show have done the voronoi on the 2d function.
joojaa
CC BY-SA 3.0
2015-10-22T10:07:57.903Z
@joojaa From the example images I expected that the Voronoi cell edges on the 2D surface were what was required (to give a collection of line segments connecting points on the sphere surface, rather than the collection of plane sections that would be given in 3D). However, [scipy.spatial.Voronoi](http://scipy.github.io/devdocs/generated/scipy.spatial.Voronoi.html) seems to be designed for N dimensional spaces rather than surfaces embedded in them. I can't immediately see how it would be used for 3D points constrained to a 2D surface.
trichoplax is on Codidact now
CC BY-SA 3.0
2015-10-22T10:20:03.673Z
Is not a problem to me if I have to change library or to write my own implementation.  If you can suggest any source I need to look at I will be happy to do it!
Jiloc
CC BY-SA 3.0
2015-10-22T14:29:47.847Z
I'm guessing you would need to implement a distance function for two points on a surface. On the sphere you can get away with just using the 3D Euclidean distance but for arbitrary shapes you'll need something more specific otherwise points that are near to each other in 3D due to folds in the surface will appear nearer to each other than to points between them.
trichoplax is on Codidact now
CC BY-SA 3.0
2015-10-22T14:36:31.333Z
Do you mean to sample points? I am using isotopic distance to accomplish this. Anyway as you see, my problem is with the Voronoi computation, not the initial sampling procedure, but maybe I didn't understand what you were saying!
Jiloc
CC BY-SA 3.0
2015-10-22T20:37:01.267Z
No I meant the Voronoi step - converting cell centres (the Poisson sampled points) into cell edges. This also requires a length calculation in order to determine which line is equidistant from a given two points.
trichoplax is on Codidact now
CC BY-SA 3.0
2015-10-26T03:19:08.577Z
These articles look relevant to what you are trying to achieve:
http://meshlabstuff.blogspot.com/2009/03/creating-voronoi-sphere.html
http://meshlabstuff.blogspot.com/2009/04/creating-voronoi-sphere-2.html
Julien Guertault
<3d><geometry><mesh><polygon>
Pipeline to create Voronoi Meshes
Jiloc
# Pipeline to create Voronoi Meshes

(Asked by: username_0 on 2015-10-20)

I would like to implement a Maya plugin (this question is independent from Maya) to create 3D Voronoi patterns, Something like

[![enter image description here](https://i.sstatic.net/8RYgU.jpg)](https://i.sstatic.net/8RYgU.jpg)

I just know that I have to start from point sampling (I implemented the adaptive poisson sampling algorithm described in [this paper](http://link.springer.com/article/10.1007%2Fs11432-011-4322-8#/page-1)).

I thought that, from those points, I should create the 3D wire of the mesh applying Voronoi (I tried to use (Python) scipy.spatial.Voronoi but the result was something different from what I expected).

I am missing something? Can anyone suggest the proper pipeline and algorithms I have to implement to create such patterns?

[EDIT] Here are a few example of what I get handling the result i get from scipy.spatial.Voronoi like this (as suggested [here](https://stackoverflow.com/questions/23658776/voronoi-diagram-edges-how-to-get-edges-in-the-form-point1-point2-from-a-scip)):

```
vor = Voronoi(points)
for vpair in vor.ridge_vertices:
    for i in range(len(vpair) - 1):
        if all(x >= 0 for x in vpair):
            v0 = vor.vertices[vpair[i]]
            v1 = vor.vertices[vpair[i+1]]
            create_line(v0.tolist(), v1.tolist())

```

The grey vertices are the sampled points (the original shape was a simple sphere):
[![enter image description here](https://i.sstatic.net/gz8hD.png)](https://i.sstatic.net/gz8hD.png)

Here is a more complex shape (an arm)
[![enter image description here](https://i.sstatic.net/mCkPm.png)](https://i.sstatic.net/mCkPm.png)

**Tags:** 3d, geometry, mesh, polygon

> **Comments:**
> **username_0**: Thank you for the reply. I am going to replicate what I did and post a screen as suggested. Anyway the final intent of this question isn't to debug my code, but to understand if what I am doing is right or there are others steps that I am missing in between!  
> **username_0**: added examples as suggested!  
> **username_0**: The points from the poisson sampling are right. The algorithm that generates them is fully unit tested and the ones you see in the screens are spheres with the center in the sampled point which i programmatically created before calling Voronoi(points)! I am worried that I am not following the proper path or I am handling the Voronoi result in a wrong way  
> **username_1**: The images you show have done the voronoi on the 2d function.  
> **username_2**: @username_1 From the example images I expected that the Voronoi cell edges on the 2D surface were what was required (to give a collection of line segments connecting points on the sphere surface, rather than the collection of plane sections that would be given in 3D). However, [scipy.spatial.Voronoi](http://scipy.github.io/devdocs/generated/scipy.spatial.Voronoi.html) seems to be designed for N dimensional spaces rather than surfaces embedded in them. I can't immediately see how it would be used for 3D points constrained to a 2D surface.  
> **username_0**: Is not a problem to me if I have to change library or to write my own implementation.  If you can suggest any source I need to look at I will be happy to do it!  
> **username_2**: I'm guessing you would need to implement a distance function for two points on a surface. On the sphere you can get away with just using the 3D Euclidean distance but for arbitrary shapes you'll need something more specific otherwise points that are near to each other in 3D due to folds in the surface will appear nearer to each other than to points between them.  
> **username_0**: Do you mean to sample points? I am using isotopic distance to accomplish this. Anyway as you see, my problem is with the Voronoi computation, not the initial sampling procedure, but maybe I didn't understand what you were saying!  
> **username_2**: No I meant the Voronoi step - converting cell centres (the Poisson sampled points) into cell edges. This also requires a length calculation in order to determine which line is equidistant from a given two points.  
> **username_3**: These articles look relevant to what you are trying to achieve: http://meshlabstuff.blogspot.com/2009/03/creating-voronoi-sphere.html http://meshlabstuff.blogspot.com/2009/04/creating-voronoi-sphere-2.html  

---

## 1 answers

### Answer by username_4 on 2016-09-28. Score: 1

<http://www.cs.sandia.gov/~samitch/papers/vor_final.pdf> There isn't the computer algorithm in any programming languague, but u should be able to replicate it easily with some Plane Reflections and the algorithms from the above link.

> **Comments:**
> **username_5**: Welcome to ComputerGraphics.SE! It's normally a good idea to make answers on Stack Exchange self contained (e.g. in case links go down and also in general so that people don't have to follow links to be able to tell if an answer is useful to them). You might want to improve your answer by including a short summary of the contents of the paper.  

---

