Point Distribution

News from my research. Right now, we have a very good tool to create textures. But because we are not artists, we have to develop algorithms that use that tool to create textures automatically. To create textures with our tool, we have to place points and orientations on the plane, therefore, the main purpose of our algorithms is to place these points.

To create interesting textures, we have to find methods to place the points. One of the most popular method consists of selecting a minimal distance d and then, for each new potential point, test with the previous point if the minimal distance is at least d. If it is, the point is added to the set, otherwise, it's rejected. To determine how this process terminates, you can either put a maximal number of points or a maximal number of consecutive failure. For more information, you can take a look at Poisson Disk Sampling for more information and for the description of a more efficient algorithm to produce the point set.

But, while investigating those process, we noticed that our tool, with the points and orientations, can be used to determined the distance between two points. We use the orientation to create different distance functions and the minimal distance is considered according to these functions. So, we end up sometimes with pair of points closer than the minimal distance, but not according to the distance function.

Here's some point distribution with the orientation parallel to the z-axis. In this case, it creates a point distribution similar to the Poisson Disk Sampling described above.

But, if we start changing the orientations randomly, we have point distributions that are much less regular:

With this method, we can see that creating a random night sky is not that difficult.

It's also possible to manage point distribution with clusters. A basic method to do clusters is first to place clusters centers, just like distributing points (by choosing an orientation and a distance function), but without any minimal distance (but it's possible to have one). Then, for each point that you want to add to the point set, you first look for the closest center. Just like before, you test that new point with all the previous points already in the point set. If the point can be added, you assign a minimal distance to that point using the distance between that point and its center. The minimal distance can be the distance itself, but for better result, you can use the square or the square root of that distance.

Here's some result of cluster point distribution:

So now that we have methods to distribute points that also use our tool, we are now able to generate textures. We plan to first use these point distribution to create textures such as caustics, clouds and random abstract images.

Learn to code | Codecademy

Today's post is about a website I planned to talk about, bu totally forgot! It's called Codecademy and it's actually a very nice tutorial to teach kids, from 7 to 77, how to handle basic principles in source code.

It shows how to code in Javascript. And in the last years, mostly with HTML5, Javascript is getting even more important. And there's a rule on the Internet about Javascript: If something can be done in Javascript, eventually, someone will do it. And it's actually true. Just take a look at Google Docs. Also, by choosing Javascript, you don't have to think about compilers or on which OS you are. You can jump directly in the fun part.

The tutorial starts by asking your name and you just have to write it as a string like "Widgg". Then, gradually, you are introduce to various concepts like variables, conditions, loops and so on. The only problem that I had with the tutorial is that the syntax in Javascript requires semicolons at the end of each statement, but that was not explicitly mentioned in the tutorial. Or I just did not find it.

I did that tutorial a while ago, so maybe they corrected it. But even with that small problem, it's actually a really good starts for anyone who want to start programming or are just curious.

Paper Review: Alan Turing and the Origins of Complexity

It's the first time I'm doing a post like this one. I don't really know how to approach this paper review or even if it should be considered a paper review. So, first here's the basic information about that paper.

Abstract:

The 75th anniversary of Turing's seminal paper and his centennial year anniversary occur in 2011 and 2012, respectively. It is natural to review and assess Turing's contributions in diverse fields in the light of new developments that his thoughts has triggered in many scientific communities. Here, the main idea is to discuss how the work of Turing allows us to change our views on the foundations of Mathematics, much like quantum mechanics changed our conception of the world of Physics. Basic notions like computability and universality are discussed in a broad context, making special emphasis on how the notion of complexity can be given a precise meaning after Turing, i.e., not just qualitative but also quantitative. Turing's work is given some historical perspective with respect to some of his precursors, contemporaries and mathematicians who took up his ideas farther.

Author:

Dr. Miguel Angel Martín-Delgado

Link:

Alan Turing and the Origins of Complexity

I decided to talk about that paper because it's about the work of a great man, Alan Turing, without whom, the world would be so different, at so many levels that it's hard to understand the impact he had. As mention in the abstract, he gave us a better understanding of complicated Mathematical concepts. In WWII, he helped breaking the naval Enigma machine used by Nazis to communicate.

But the main reason that I decided to write a post about this paper is that it covers subjects that most computer scientists should be aware of. It doesn't matter if the proofs are not understood, but it's very important to get the foundation of computer science and to know what are the limitations of computers. Even if you already know this material, it's always good to read it again. Particularly if it's been a while.

First, Alan Turing introduce what he called the "a-machine" for automatic machine. That machine is now called a Turing machine. To know what a Turing machine is, take a look at this video:

It might be hard to understand, but a machine like this can reproduce everything a computer can do. Here, we're not talking about speed, but the capacity to compute the same result. The most important Turing machine is a Universal Turing machine, i.e. a machine that can simulate any other Turing machine. Such a machine requires two inputs: a program and input data. Then the machine follow the instruction of the program, according to the input data, and produce an output.

This is exactly like a computer. You have the hardware (the machine), when it starts, it loads an operating system (the program) and you start typing on your keyboard, moving the mouse, receiving data from an internet connection (the input data). And in exchange, you get outputs in the form of images shown on your screen, data sent to a server or a document printed (an output).

Turing also showed the limitation of his machine. For example, that machine would not be able to compute the square root of two because the computation would never stop. If the machine cannot stop, it's considered non-computable. But, if we put a limit to the computation such as a maximum number of decimals, then it's computable because the machine will know when it's done.

Then, if something can be computed, how hard is it to compute it ? How much time and how much space ? Time, so given an input of size N, how much steps a Turing machine will need to solve it. Space, how much place on the tape (see the video above) is needed. On a Turing machine, the tape is considered as "infinite" but in practice, computers don't have infinite space and it takes time to do any operations. The paper covers the common complexity classes and problems related to these, specially the well know P vs. NP.

The paper also talk about the famous Halting Problem, i.e. there's no way to find whether a computer will eventually halt. A proof of the Halting Problem is given in the paper by using Cantor's diagonal method. That method can be used to show that even if there's an infinite number of natural numbers N, the cardinality (the size) of the set of real numbers R is greater than the cardinality of N. A concept that is weird the first time you read about it (I remember how surprised I was when I saw a proof for that) but very important to understand the foundation of Mathematics.

Have fun reading this paper!

more smoke

So, yesterday I presented some smoke textures that I created. I continued to work on it and after altering some values, I managed to create some new interesting smoke textures. These textures look cleaner than those made yesterday. I made sure that the background would be closer to black and it helps to see the curves made by the smoke.

Here's some of these outputs:

When the process would be easier to control, with well defined functions to distribute the points, I will be able to generate as much smoke textures as I want. Might put a package of a hundred of them on Renderosity.

smoke textures

Back on creating textures. First, I finished the first version of that new renderer. Might still have some bug, but in general, it's done.

One of the objectives that we had with this new tool that we created was to create some smoke. A bit similar to this one:

The picture above is called Smoke Art, so creating images using smoke. This one is not generated by any computer. Other Smoke Art are listed there: http://www.bablotech.com/2008/12/14/20-amazing-smoke-art-pictures/, and some of them are really amazing.

With our new method, we try to reproduce such piece of art, but completely random. We don't try to recreate a scene or anything. Just create random smoke effects.

There's many ways to do such images, the most popular is probably with particles. You use thousands or millions of points and let them behave like smoke. But this approach is heavy to run and it's mostly for animation. For static images like ours, it's not very interesting to manage that amount of points to finally find the right image.

Our method still consists of placing points and some information of associated with points on the plane to partition it. We are still using the layers to create the effects and it works really well with smoke. So here's some of my favorite that I created today:

We still have some work to do to really control that new technique. And also some experimentation to be sure that the behavior is more stable. One thing that we might try is adding a bit of color to it instead of working in gray. But not drastic colors like red or green. Little variation from gray, but enough to see that there's more.

Please leave any comment or question that you have about these textures.