Hello,

For the past week or so, I have familiarized myself with Voronoi/Worley Noise, so as a conclusion to learning about and writing a program for Voronoi I have decided to share what I have learned as a pseudo-tutorial about the subject. I know it is not much, but I hope it helps someone. Now with out further delay I present what I have learned.


What is Voronoi/Worley Noise?
Well in the simplest sense, it is a different representation of points in space, but rather than showing the points themselves they are visualized by the pixels around them. So,
as you will see in the pictures below the further the pixel is away from the point the brighter it will be. This of course can be inverted. With this gradients can be formed from the point going outwards in all directions .
For more info go here

Ways to Measure Distance?
All of these make the assumptions that:
delta(x) = x1 - x2
delta(y) = y1 - y2
a = delta(x)
b = delta(y)
**
Note: All the pictures use the same same settings other than the distance type
size = 100
fValue = 1
blockSize = 10
**

Linear
This is the good old Pythagorean theorem.


Equation:
distance^2 = a^2 + b^2 or
distance = sqrt(a^2+b^2)


Linear Squared
This is the same as before except you do not take the square root of the ending total. This in turn saves some computation time.


Equation:
distance = a^2 + b^2


Manhattan
This method of computing distances is based off of how one would travel in a city. So in this is the shortest distance that could be traveled with no diagonal lines. The main thing here is that the delta(x) and delta(y) must be positive. (Self error note: This was a problem when I first started in that I would have these perfect diagonal gradients on the screen.
Also if you do not take the absolute value of any of it you will get some weird results.)


Equation:
distance = abs(a) + abs(b)


Chebyshev (sometimes seen as chebychev)
This way is similar to the Manhattan method in that it goes based of individual changes in x or y. The only thing different here is that it includes diagonals. This comes from this methods is based off how a king can move in chess. By adding the diagonal it adds the possibility of traveling both to a and b at the same time. This causes the value to be which ever number is lower.


Equation:
if abs(a) == abs(b) or abs(a) < abs(b)
distance = abs(a)
if abs(a) > abs(b)
distance = abs(b)


Quadratic
The quadratic method is simple in that it is all the values multiplied together then added up just like a quadratic equation. ex. (x^2 + xy + y^2)


Equation:
distance = (a*a + a*b + b*b)


Minkowski
Minkowski is a little odd in that, from what I have observed, it is controlled by an exponential, and based on that number the results go from being the same as Manhattan (MinkowskiNumber=1) to being more and more square as the number increases leading eventually to look like the Chebyshev. If anyone knows any more about this feel free to correct me. I personally would like to know a little more about this one.


MinkowskiNumber=1

MinkowskiNumber=3

MinkowskiNumber=5
Equation:
distance = (abs(a)^MinkowskiNumber + abs(b)^MinkowskiNumber) ^ (1 / MinkowskiNumber)


Voronoi Math
Just like any other type of image these can easily be manipulated to render very different results.
The most common types of math with these are taking different fValues of the same seed and adding or subtracting them.
With this different patterns can be created by use of variations of the same points.

fValues
fValues are what determine how many (and to which points) the induvidaul pixels will calculate distance to. F1 for example is the absolute closest point to said pixel. F2 would be the second closest, and so on and so forth. (Self error note: the fValues are only for that point. They are not cumulative! This will result in some wonky math later on ie (F2 - F1 = the real F2)(F3 - F2 = real F3) ect. When I first wrote the code I had it set up this way and was wondering why it did not work right. I don't know whether it was me being dumb or some of the other sites explainations of the subject being weird. Either way I hope that this will stop anyoe else from falling into my mistake.)

Octaves
Just like in other noise octaves define how many iterations of the same variables other than the blockSize. This is changed to allow for more detail in the image. By shrinking the blockSize more and more layers of noise are overlayed on each other. By doing this with some modification, this code could create fractals based off of an ever decreasing blockSize.


1 Octave

2 Octaves

3 Octaves

4 Octaves


Other Stuff
Plated/ Solid Cell Results
Plated/ Solid Cells can be seen if you set the var plated to True.

Original Voronoi Results
You can get the original Voronoi results if you turn on plated and platedLines

Using the Code
If you run the VController.py the minimum input
is:

somename = Voronoi(Somesize)
ex: thing = Voronoi(100)
thing.draw() will then display the Voronoi


blockSize=None
This sets up the block size for each octave. This must be in list form with every octave that you are going to do accounted for.

Examples
blockSize=[10] would make octave 1 have a block size of 10
blockSize=[20, 5] would make octave 1 have a block size of 20 and octave 2 would have a block size of 5.
blockSize=[0, 10] would make skip octave 1 and octave 2 would have a block size of 10.
**Note the size of you image must be dividable by the block sizes. Also you must match the block sizes with your selection of octaves**

octave=None
This sets up which octaves will be done. This also must be in list form.

Examples
octave=[1] would have one octave and it would have a 1x multiplier in relation to the final image.
octave=[1, .5] would have two octaves with the first having a 1x multiplier and the second octave would have a .5x making it to where it is less visible.
Octave=[2, 0, .2] would make the first octave have a 2x multiplier and then give the third octave a .3x multiplier.
**Note octave must match up with blockSize in the location of all non-zero numbers**

fValue=None
This works in the same sort of way as the octave and blockSize. The only difference here is that this is your voronoi math spots. So for example for F1 - F2 you would put fValue=[1,-1].

Other Examples
fValue=[1] this is the basic voronoi. A value of -1 would invert the coloring of the image.
fValue=[2, 1] this would add F1 and F2 together, but F1 would have a 2x multiplier.
fValue=[-1, 0, 2] this is that same as saying 2(F3) - F1 = end picture.

clip=0
This does not quite work right but basically it clips the top how ever much you set clip to off the image resulting in more areas of pure white. I am currently tring to make it to where it will clip from the bottom as well.

seed=None
This sets the seed of the entire thing so that you have the ability to create the same image over and over.

distType="Linear"
This sets how distances are determined. These correspond to the descriptions from above.
Options include:
"Linear"
"SqLen"
"Manhattan"
"Chebyshev"
"Quadratic"
"Minkowski"
**Note if you use "Minkowski" you need to set the minkowskiNumber as well.**

plated=False
This sets whether or not you want to just see the plated view which makes it pixel the color of the cell rather than showing how far pixels are from the cells.

platedColor=True
This sets whether you want the cells to be in color or greyscale.

platedLines=False
If you turn this on then it will return normal Voronoi

minkowskiNumber=4
Use this to set the number for Minkowski

Explanation of code coming soon...

Well I guess that is it for now, I have been typing this up for about two hours now so there are probably lots of errors and some things are not done yet, but I hope it helps all the same.

Also Feel free to use anything on this page for whatever you want. I am going to keep this under a "Learners Rights License" Trademark of Chris_0076 =), so if you have read anything on this page you are free to use it in any way you like, claim it as your own, mutilate it, make millions off it, or what have you. My concern is not to be a copyright troll, but rather help others learn something new... and of course hope they pass along something in the same sort of manor because knowledge is wasted if you keep it a secret.

Chris



... I guess I can not attach the code. So I have hosted it on pasteall for the time being.
"VController.py"
"VoronoiFaster.py"


EDIT
Made some fixes. And hopefully the code should be here:
http://www.mediafire.com/?26x93wv3i7cga14
*Note* it is a zip file with 2 files inside

[Edited by - Chris_0076 on July 27, 2010 8:24:22 PM]

Thanks very much for this post! I'm a big Voronoi fan, and I know something about the Minkowski numbers, but not the Worley.

I have some Voronoi-related posts on my blog at http://nodename.com/blog

I can't seem to access your sources on pasteall; are those words supposed to link to them? I'd love to check out your code.

-A

Quote:Original post by Chris_0076
Minkowski
Minkowski is a little odd in that, from what I have observed, it is controlled by an exponential, and based on that number the results go from being the same as Manhattan (MinkowskiNumber=1) to being more and more square as the number increases leading eventually to look like the Chebyshev. If anyone knows any more about this feel free to correct me. I personally would like to know a little more about this one.

Your observation is correct: the Minkowski norm is a generalized form of both the Manhattan, the Euclidean and the Chebyshev norm.

First off, the word "norm": this just means "some measure of the length of a vector". If you have points (x1, y1) and (x2, y2), the "distance" between them (according to some norm) is the norm of the difference of the points, (x1-x2, y1-y2). So we don't really need two points, we just work with one vector, which simplifies the notation a bit. (We can also use the reverse difference, (x2-x1, y2-y1). By definition, norms don't care.)

Then, the Minkowski norm of a vector (x, y) is defined as:
(|x|^p + |y|^p) ^ 1/p

Fill in p = 1, and we get:
(|x|^1 + |y|^1) ^ 1/1 = |x| + |y|
This is the Manhattan norm.

Fill in p = 2, and we get:
(|x|^2 + |y|^2) ^ 1/2 = (x^2 + y^2) ^ 1/2 = sqrt(x^2 + y^2)
That's the Euclidean norm.

Fill in p = infinity, and we get:
(|x|^inf + |y|^inf) ^ 1/inf = ???
Mathematically, this is nonsense; you cannot use infinity in this way. The best you can do is to take the limit, when p goes to infinity. You'll have to take my word for it that
lim_p->inf (|x|^p + |y|^p) ^ 1/p = max(|x|, |y|)
which is the Chebyshev norm. You said that you saw this happen: the larger you choose p, the more it looks like the Chebyshev result. So this is why.

Another intuitive way of understanding this is, that if x > y, then x^p will eventually begin to "dominate" y^p for large enough p. In the limit of p to infinity, only the larger of the two will remain. Let's say x is larger:
lim_p->inf (|x|^p + |y|^p) ^ 1/p = lim_p->inf (|x|^p) ^ 1/p = lim_p->inf |x| = |x|
If y is larger, the result will be y. So this is why the "max" function appears.

Awesome thread guys! Thanks for the info.

Yeah, cool thread. It seems that the images for Manhattan and Chebyshev got mixed up though. At least they contradict with what is said in the Minkowski part. In any case, nice work!

Wow, I thought this thread was long gone and useless...

Ok, I have hosted the code at MediaFire. It is in a .zip folder with two files inside. The VController.py and then the VoronoiFaster.py.

Use the VController.py for the instructions that are in the post above. Look at the VoronoiFaster.py. If you want to see what is actually going on(If you can read my code).

It should be at this link: http://www.mediafire.com/?26x93wv3i7cga14



Now that that is out of the way....

nodename - Cool site. Ya, the code linking did not quite work out, and I guess my mind slipped because I did not even check it.

thomastc - Thanks for the explanation. I was on the right track, sort of.

kloffy - Hmmm... don't know what happened there, other than my image names were almost the same on those two XD, I just goofed up when I put them in order.

Thanks for the comments guys, hope I fixed some of the problems.

Chris