Wednesday 30 July 2008

Procedural graphics: science or art ?

Scientists credo seems to be: all hypotheses must be supported by the data. It's resonable. Typical scientific discovery recipe: gather a lot of data, use statistics, formulate "rules", falsify.

Statistics is math. Linear regression is a kind of curve fitting is a kind of approximation technique. Regularities (low-order curves) are common: planet bodies, planet orbits or pendulum oscillation. But so are irregularities: rocks, coastlines, clouds, fixational eye movement.

And here is the discovery that influenced my interests and research topic a lot: fractal geometry. Fractals provide sort of evidence that irregular "things" can be described as simply as regular. But there is a small twist here!
For example take some long sequence of random (white noise) data. How to approximate those date ? Is there any simple recursive or any other equation that can describe this sequence or at least fit to it with a small error ?
Unfortunately, in general, it's almost impossible to find a short one. To give you more clue - white noise doesn't compress easily (just try JPG or ZIP on it).
But we can do something else with it. We change the way we think about approximation! Instead of trying to fit all the data, we can just try to reproduce their "general characteristics". Why not "approximate" white noise just by any other white noise, i.e. generated using simple LCG? If our application is audio-visual, we will not see much difference. This kind of reasoning was succesfully used in speech synthesisers or synthetic terrain/rocks generators. And taken to the extreme (applied to vast variety of signals) define what is called: procedural art.
A procedural technique researcher is trying to find methods (a set of rules, algorithms or equations) that can be used to generate very complicated signals that has the same "general characteristic" as modeled signals, while procedural artist is trying to "paint" with those methods.
I did several procedural works in my life, i.e. a movie inside weird caves and 64k intro, introducing my own procedural techniques.
More works like this can be found in so called demoscene archives, most recommended are some Inigo Quilez works. Another prominient researcher (not related to demoscene) is Dmytry Lavrov.
With a demoscene you have to be careful though: not all those little creations are fitting my procedural art definition. Some of them just use standard approximation techniques to describe regular "things" using subdivision surfaces, quantization, wavelet compression, etc... To put it straight, this creations have lower artistic value for me (but I'm not claiming they have no value at all).

Monday 14 July 2008

Closures and boundaries

Today, I was working on some technical report (an internal publication for the university) for my PhD. I was dealing with topology of sets in metric spaces, which is a special case of general topology, well suited just for my needs, a computer graphics field.
I had minor troubles with a definition of a set boundary, but I think I finally got it right and actually some things surprised me a bit - that's why I'm sharing it here!
At first I was saying about boundary of the set A without mentioning about the metric space X that contains it. Usually I'm operating in R^n euclidean space, and all of my sets was subsets of R^n. But this time, I was dealing with a space constructed from a subset of R^n, specifically, a unitary box: [0..1]^n, further called I^n space, I={x|0<=x<=1}, where x is a real number. Let Y be a continuously deformed ball that is a subset of I^n . I was "intuitively" (by analogy to R^n space) thinking that the boundary of Y should be always connected (or even simply-connected). You can not imagine a ball that has disconnected boundary, right ?
As usual, it all depends on the definition on the boundary.
In topology, the boundary can be defined several ways that are equivalent for metric spaces. We can for example say, that a boundary of a set Y included by a metric space X is a set of points in X for which any open ball (with radius > 0) contains points both inside Y and outside Y.
To define an open ball in X you surely need to define a metrics of X. If it is euclidean R^n space, a ball "looks" like a ball = it is a sphere, if not, it can be almost "anything". But stick to the euclidean first. The I^n set has a boundary in R^n. It is an "empty" box. But any open ball in euclidean I^n space will not always be an open sphere - near the boundary of I^n in R^n, it will be just a part of a sphere cut by the walls of I^n box. Now, if we take any connected subset Y of I^n that touches the walls of I^n box, the set of points at the walls of I^n box will be not a part of boundary of Y! This is why we can construct Y that will have a disconnected boundary in I^n, an example provided below:


In the figure above, a boundary is denoted as a thicker line. Note that any open ball co-centered with "a" and smaller than "a" will contain only points inside Y, thus the center of "a" is not a part of the boundary of Y. We can also clearly see that the center of "b" lies on the boundary of Y (any ball around it contains point both inside and outside Y). Obviously the boundary of Y' in R^n is connected.