Sunday, May 22, 2011

Hello Worley

If you are into procedural things you probably heard about Perlin noise. This noise function can be used to recreate many of the patterns you find in nature, like clouds, large mountain ranges, marble. While it is not the only way to produce them, it is probably the most efficient way to achieve very good looking results.

There is another type of noise that is as useful as Perlin noise: Worley noise, which is also called cellular noise. Here you can see how it looks like, compared to Perlin:

Perlin is great for phenomena that originated from mixing different entities, like how moisture permeates a wall or mold grows on a tree. Worley is best for self-organizing patterns, things that break down into clear boundaries like cells, pebbles and even man-made objects like a stone wall.

The idea behind this noise function is simple. The function field is scattered with random points, then for any point in space the function determines how this point relates to the nearby random points.

Unlike Perlin's function, which you may take as a magical black box, it helps to learn the implementation details of the Worley function. Many interesting effects can be achieved by using different criteria. One example would be to return the distance to the closest random point. This is the used in the image before. As you can see it outputs the Voronoi diagram for the field.

I had delayed including Worley noise in my terrain generator for too long. All the screenshots and videos I had posted so far were produced using only some form of Perlin-like noise. It was a long weekend, so while the wife and twins were taking a nap I pulled out the holy book for procedural content and went straight to Worley's chapter.

It only took a few hours to have his noise ported to OpenCL. Here are screenshots of a large rock formation out of Worley noise:


Here it can be seen in more detail:



Worley's algorithm is perfectly suited for parallelization. I only changed the criteria on which neighbor cells are visited. For a CPU implementation, Worley goes into an elaborate scheme to avoid testing points inside a cell if it can be early discarded. My parallel superstitious instinct told me this type of optimization would not carry well into OpenCL. If at least one of the points in the current wavefront hits the worst case scenario, then it was as if all the points were worst case scenario too. So I removed all conditions and went with the brute force approach. I do not have any numbers to back this up, however. I could be wrong.

Now I have this new toy and I keep thinking of shiny things I could build. It is that warm feeling a new noise function will give you.

7 comments:

  1. I was fine with you writing this blog until you mentioned you have twins. Now I'm like 'where do you get the time?'...

    ReplyDelete
  2. @Andrew: The key to handling twins is parallelization. Be aware of bandwidth and coalescence issues, ready their input beforehand and take care of their output in a single shot.

    You get double the cuteness with almost the same effort as a single baby system.

    ReplyDelete
  3. Hello! I'm keebus from Italy and I follow you every day. Keep up the great work I'm extremely interested on the topics you cover. Hope to see some ludic result soon :)

    ReplyDelete
  4. had to chime in, this stuff looks quite interesting. i was curious did you go with svo or warped voxels for this? also you have curious mesh errors all over the place i was wondering how those came about specificially. unbelievably the weird mesh errors give your engine More character not less :)

    so keep going and keep updating this thing!

    -planaria

    ReplyDelete
  5. @Planaria: SVO and voxel warps are not exclusive. You can warp the octree cells and get the best of the two worlds. I use both, but it is mostly SVO for adaptive contouring. I did not go very far with warping. It is noticeable to the eye. There is something about non-euclidian spaces that must have frighten our primitive ancestors.

    Not sure what you mean by mesh errors. If you point them to me I should be able to explain how they got there. You can email an image to my gmail account, same username you see here just add gmail.com

    ReplyDelete
    Replies
    1. Hmmm, I think he means some less smooth parts of the terrain, like here http://puu.sh/3Bv5I.jpg or here http://puu.sh/3Bv8u.jpg

      Delete
  6. (Comment on the vote) Actually, I would like to use this technology in my own game, so i don't have to re-invent your wheel. But i guess, something like that would be too much of a gift.

    sascha (weird email symbol here) heylik dot at

    ReplyDelete