|
The basic idea of cell noise is to spread a varying number of feature points in space and calculate the distances to these points from every possible point in space. This can then with success be used to simulate, among many things, cell-like structures. As a complement to this basic idea, Worley describes ways to connect each feature point with a unique ID number. This number can be used to generate a surface with solid colored areas, looking a lot like military canvas or glass mosaic, depending on the coloring function.
The figure above describes a space with feature points scattered across the plane. For a position on the plane, the x in the figure, there is always a closest feature point. There is a second closest as well as a third and so on. The algoritm searches the plane to find them and returns the distance, the relative position and the ID number of each feature point.
Shown in the figure are also the integer lines of the plane, that is where the positions are integers in any dimension. The integer squares (cubes in three dimensions) are central in the algoritm. When we want to know the distance to the two feature points closest to the point (3.6, 5.7) we start by looking at the integer square (3, 5) and compare its feature points to each other to find the closest. Let’s say that the point (3.6, 5.7) is the x in the figure. It’s obvius that the two feature points in that square aren’t the two closest. One of them is, but the second closest belongs to the integer square (3, 6).
This is no problem using the algorithm by Worley. Having found the two feature points in square (3, 5) the algorithm goes on to compare the position with its integer borders, to determine if it’s even possible that there is a closer feature point in the adjacent squares. As seen in the figure, where the distances to the two points of the center square are marked, it’s only possible to find closer feature points in the squares (4, 5), (3, 6) and (4, 6). Only these squares have to be searched. The benefit of this is efficiency. The integer line comparison is extremely fast compared to the in-square search.
Since the number of feature points to search for is variable, the number of squares having to be searched varies. The number of feature points in each square is set in the algorithm to be between none and five, and average to 2.5.
|