Creativity and Simplicity

www.lactamme.polytechnique.fr

jean-francois.colonna@polytechnique.edu CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641, École polytechnique, Institut Polytechnique de Paris, CNRS, 91120 Palaiseau, France france telecom, France Telecom R&D

[Site Map, Help and Search [Plan du Site, Aide et Recherche]]
[The Y2K Bug [Le bug de l'an 2000]]
[Do you believe that Real Numbers exist for a computer and that floating point computations are safe? [Croyez-vous que les Nombres Réels existent dans un ordinateur et que les calculs flottants sont sûrs?]]
[Please, visit A Virtual Machine for Exploring Space-Time and Beyond, the place where you can find thousands of pictures and animations between Art and Science]
(CMAP28 WWW site: this page was created on 06/07/1995 and last updated on 04/16/2023 20:53:34 -CEST-)

(published in The Visual Computer, Volume 11, Number 8, 11/1995)

Abstract: The human intelligence and in particular its creative potential seems to be, for many scientists, made of processes that cannot be automated by the means of a computer. This WWW page tries to show, as already exhibited with the fractal geometry, that the iteration and the combination of very elementary operations can give very complex behaviours and shapes. It will give some practical examples in order to encourage reader involvement and new experiments in particular during classroom settings.

Keywords: accumulation, brain, chaos, conformal mapping, convolution, creativity, Fast Fourier Transform, fractal geometry.

Contents:

Whether the human brain is a machine or not is one of the oldest questions posed by human beings. Two answers are given: yes and no, neither being scientifically justified. My personal view about this question is that the brain is a machine that constantly receives external data (by the means, for example, of the visual system), transforms, processes and memorizes it, and then produces output at the muscular level (to walk, to talk,...). Creativity could then be the "simple" result of numerous combinations and transformations of former memorized data thus giving birth, from time to time, to very surprising new data...

I should like to illustrate this personal point of view by means of an analogy using very simple computer graphics algorithms.

Genetic algorithms [1], the fractal geometry and the deterministic chaos [2][3][4] have already exhibited the fact that iteration and combination of operations can result in very complex behaviours and shapes. The main goal of this WWW page is to show this remains true even with the most elementary operations. Moreover, it should be noticed that most chaotic processes are sensitive to rounding-off errors (see [5] and one of the author's WWW pages); the consequence is that their results may depend on many extra-parameters:
• the way parentheses are used,
• the system release (in particular the compiler's one),
• the compiling options,
• the instruction scheduling,
• the floating point processor,
• etc...

Then, the user could be faced with impossibilities: for example, to reproduce results obtained before upgrading his or her computer.

As suggested above, let us describe a few simple tools for false color pictures (the extension to true color pictures is obvious); figure "Four tool pictures" displays four very simple "seed" pictures useful for our demonstration.

1-GENERALIZED PRODUCT (GP):

1.1-Generalized multiplication table:

It is a square array M(i,j) of integer values defined as:
```                    Nmin <= i <= Nmax
Nmin <= j <= Nmax
Nmin <= T(i,j) <= Nmax ∀ i,j.
```
The generalized product Pg = P1 x P2 of two pictures P1 and P2 is then defined as:
```                    (1): Pg(x,y) = M(P2(x,y),P1(x,y)) ∀ x,y.
```
In the most general case, this generalized multiplication table is not symmetrical, ie:
```                    M(i,j) # M(j,i),
```
hence the generalized product is not commutative:
```                    P1 x P2 # P2 x P1
```
As examples, we are going to define two 3D effects as 2D postprocessings. For this purpose we shall assume that 3D pictures are generated by means of the Z-Buffer technique [11], and that the content of the Z-Buffer is available after visualization. The description will be given for grey level pictures (the extension toward true colors is straightforward). In this context a picture is an array of integer values; P(x,y) and Z(x,y) will denote respectively the pixel value and the depth value (the third coordinate) at the location (x,y). The following conditions are required:
```                    Xmin <= x <= Xmax
Ymin <= y <= Ymax
Nmin <= P(x,y) <= Nmax ∀ x,y.
```
Thus Xmax-Xmin+1 and Ymin-Ymax+1 define the dimension of pictures, when Nmax-Nmin+1 defines the number of available grey levels. We shall consider the Z-Buffer Z(x,y) as a particular picture; we shall assume that the values of the third coordinate have been casted to integers and scaled within [Nmin,Nmax] where Nmin will denote the foreground and Nmax the background (this approach is devised with the aim of being implemented in hardware).

1.1.1-fog effect:

Let's define the generalized multiplication table as:
```                    (2): M(i,j) = (1-L).j + L.Nmax
```
with:
```                          i - Nmin
L = -------------
Nmax - Nmin
```
Then the generalized product:
```                    Pg(x,y) = M(Z(x,y),P(x,y))
```
is a good visual approximation of the fog effect (see figure "Mountains and fog"). From (2) we see that the pixel values P(x,y) are transformed into Pg(x,y) in the following way:
```                    (3): Pg(x,y) = (1-L).P(x,y) + L.Nmax
```
with:
```                         Z(x,y) - Nmin
L = ---------------
Nmax - Nmin
```
When the point (x,y) is close to the foreground (low values of Z(x,y)):
```                    L << 1
```
and from (3) we see that:
```                    Pg(x,y) ~ P(x,y)
```
The new value Pg(x,y) will differ only slightly from the old one P(x,y); hence, the pixel values for the points close to the foreground almost do not change. When the point (x,y) is close to the background (high values of Z(x,y)):
```                    L ~ 1
```
and from (3) we see that:
```                    Pg(x,y) ~ Nmax
```
The old value P(x,y) will be changed into a new one, very close to Nmax; hence, the pixel values for the points close to the background are of the same order than Nmax, thus appearing very bright. In the particular case where:
```                    Nmax = 0
Nmax = 255
```
(3) can be simplified and written:
```                    (3): Pg(x,y) = (1-L).P(x,y) + 255.L
```
with:
```                         Z(x,y)
L = --------
255
```
The following figures displays sixteen views of an evolution of a form, before ("Cauliflowers, seaweeds, shells,...") and after ("Cauliflowers, seaweeds, shells,... with fog") this processing; the fog is far from being just an artistic effect: in this case it gives a better understanding of the depth of the objects visualized without compromising the brightness of the picture.

1.1.2-depth cueing effect [12]:

It is defined as the generalized multiplication table:
```                                                      Nmax - i
(4) : M(i,j) = Nmin + (j - Nmin)-------------
Nmax - Nmin
```
then the generalized product:
```                    Pg(x,y) = M(Z(x,y),P(x,y))
```
is a good visual approximation of a depth cueing effect. In fact, this formula is transforming the pixel values P(x,y) into Pg(x,y) in the following way:
```                                                           Nmax - Z(x,y)
(5) : Pg(x,y) = Nmin + (P(x,y) - Nmin)---------------
Nmax - Nmin
```
It is obvious that this function decreases when the depth value Z(x,y) increases; thus the closest to the background the pixels are, the dimmer they appear. In the particular case where:
```                    Nmax = 0
Nmax = 255
```
(5) can be simplified and written:
```                                     255 - Z(x,y)
Pg(x,y) = P(x,y)--------------
255
```
It is noticeable that in both cases (ie. fog and depth cueing effects), T(Z(x,y)) (with T denoting an arbitrary function) could be used instead of Z(x,y) thus allowing the "tuning" of the effect; for example in the preceding example one can choose to use:
```                                 Z(x,y)
T(Z(x,y)) = --------
2
```
thus giving a brighter background. The function T could be implemented as a Look-Up Table.

1.1.3-nota:

The generalized multiplication table can be very useful in many other circumstances. For example figure "The Generalized Product" shows an animation of a texture [13] obtained from the variable generalized product of two much more simple pictures. In this case, the generalized multiplication table is a moving [Nmin,Nmax]x[Nmin,Nmax] subset of a given third picture (its periodical motion gives a periodical animation).

1.2-Convolution with a variable length kernel:

In general convolutions are defined with 3x3 kernels [14]. Here we are defining a variable length kernel: let K(i) and I(i) be respectively a coefficient vector and an inhibition vector (it defines which points are to be taken into account and thus allows kernels of any shape, something very useful for morphological applications); their commune length is L(x,y)+1 where L is a function of the point (x,y). To simplify the following presentation we shall assume that neither points are inhibited: thus we shall ignore the vector I(i) for the sake of simplicity. The neighborhood of each point (x,y) is defined by means of a L(x,y)-point "square" spiral; we denote h(x,y,i) and v(x,y,i) respectively the abscissa and ordinate of the i-th point of the spiral with center (x,y). At each point (x,y) of the picture P we compute the value:
```                                   i=L(x,y)
------
\
/      K(i).P(h(x,y,i),v(x,y,i))
------
i=0
(6) : C(x,y) = ---------------------------------
i=L(x,y)
------
\
/      K(i)
------
i=0
```
Let us describe now one application of the variable length kernel convolution.

depth of field effect [15]:

it suffices to define L(x,y) as:
```                    (7): L(x,y) = k.(Z(x,y) - Nmin)
```
(where k is an optional scaling factor) and to choose for example:
```                    K(i) = 1.0 ∀ i
```
to obtain a good visual approximation of the depth of field effect with the foreground being in focus (see figure "Depth of field effect"). In the particular case where:
```                    Nmax = 0
Nmax = 255
```
(5) can be simplified and written:
```                    L(x,y) = k.Z(x,y).
```
To change the focus on the picture it is enough to use T(Z(x,y)) instead of Z(x,y) in the above formula, with T an appropriate function (see the paragraph 1.2). For example, to focus on the center of the tridimensional scene, it suffices to define T as the function:
```                                               |          Nmax + Nmin |
(8) : T(Z(x,y)) = Nmin + 2.|Z(x,y) - -------------|
|               2      |
```
hence:
```                    T(Nmin) = T(Nmax) = Nmax

Nmin + Nmax
T(-------------) = Nmin
2
```
Thus L(x,y) will be minimal at the center of the scene (that implies no convolution at all) and maximal whitin the foreground (Nmin) and background (Nmax) planes respectively.

1.3-Conclusion:

The purpose of this chapter was to devise 2D post-processing tools with the aim of improving the appearance of 3D pictures (and only appearance, it does not pretend in anyway to be a physical model). It has shown that very straightforward methods are able to simulate visually 3D effects and consequently make these pictures more easily readable; these methods could be implemented in hardware without difficulties (see the reference [16] for an example of a hardware implementation of a powerful simple idea). It is noticeable these tools are "pipable" allowing for example the display of depth cueing effects simultaneously with depth of field (see again figure "Depth of field effect")... Moreover, they are not limited to these effects and for example, the generalized multiplication table allows arithmetic operations between pictures or again masking, when the variable length kernel convolution allows variable filtering. At last they are fully compatible with animations (changing of the view point for example) as well as with stereoscopic displays.

2-EXTENDED LIFE GAME (ELG):

The life game was initially defined by Conway [6]. It uses an empty square mesh with all vertices turned off (the problem of the boundary conditions will be discussed later); at time t=0 some vertices are turned on (this is the initial state). To go from the time t to the time t+1, it suffices to count for each vertex M(x,y) the number N of its 8-neighbours, and then to possibly change the state of M according to the following bidimensional automata rules:
```                    [R1 = birth]        ((M(t).IS.off).AND.(N == 3)) ==> M(t+1) on
[R2 = death]        ((M(t).IS.on).AND.((N < 2).OR.(N > 3))) ==> M(t+1) off
[R3]                other cases ==> M(t+1)=M(t)
```
with N taking its value within [0,8], the preceding rules can be "normalized" in the following way:
```                                                             N      3
[R1 = birth]        ((M(t).IS.off).AND.(--- == ---)) ==> M(t+1) on
8      8

N     2        N     3
[R2 = death]        ((M(t).IS.on).AND.((--- < ---).OR.(--- > ---))) ==> M(t+1) off
8     8        8     8

[R3]                other cases ==> M(t+1)=M(t)
```
The set {M(x,y)} can be seen as a binary picture. This definition can be generalized in the following way: let P(t) be an arbitrary picture (displaying the state of the extended game at the time t). For each point {x,y} the following value is computed:
```                                i=L
-----
\
/     W(i).(P (h(x,y,i),v(x,y,i)) - Nmin)
-----        t
i=0
C (x,y) = -------------------------------------------
t                        i=L(x,y)
-----
\
/     W(i)
-----
i=0
```
where h(x,y,i) and v(x,y,i) define the abscissa and ordinate of the i-th point of a spiral with center {x,y} respectively and W(i) is a weighting vector of length L+1 (see the paragraph 1.2, where the notion of inhibition vector is introduced in order to allow the study of neighbourhoods of arbitrary shapes). When chosing:
```                    L=8
W(0)=0,
W(i)=1 ∀ i ∈ [1,L],
```
and a binary picture:
```                    Nmin=0 (off state)
Nmax=1 (on state),
```
the value:
```                                   i=L
C (x,y)    -----           C (x,y)
t         \                t
------------- /     W(i) = -------------.L
Nmax - Nmin  -----         Nmax - Nmin
i=0
```
gives us the former number N of 8-neighbours of the point {x,y}. In the most general definition of the extended life game, the picture P(t+1) is computed in the following way:
```                                               |   C (x,y)         |2
|    t            3 |
- |------------- - ---|
| Nmax - Nmin     8 |
P   (x,y) = Nmin + Nmax.e                        ∀ x,y
t+1
```
where the constant 3/8 is chosen according to the rules R'1 and R'2; the maximum of this function is obtained for:
```                       C (x,y)
t            3
------------- = ---
Nmax - Nmin     8
```
The boundary conditions chosen have a very important impact on the pictures produced; many options are available, for example:

• giving a Nmin value to all the points outside the picture boundary,
• defining the picture space as a bidimensional torus,
• defining the picture as a window inside an infinite space.

The figure "Extended life game" gives an example of this process with P(0)=GRID (see figure "Four tool pictures").

3-WALL-PAPER (WPB and WPF):

Let us define two exclusive or operators Beor and Feor. Beor is the binary one, when Feor is the fuzzy one defined as:
```                                          _      _
Feor(a,b) = max(min(a,b),min(a,b)) ∀ a,b ∈ R
```
in our specific case where a and b denote grey levels, it can be defined as:
```                    Feor(a,b) = Nmin + max(min(a-Nmin,Nmax-b),min(Nmax-a,b-Nmin)) ∀ a,b ∈ [Nmin,Nmax]
```
The wall-paper procedure WP [7] transforms the picture P(t) into the picture P(t+1) and works as follows:
```                    P   (x,y) = eor(P (x,y),P ((x+tx)                 ,(y+ty)                 )) ∀ x,y
t+1             t       t       modulo Xdimension       modulo Ydimension
```
where the eor operator is either Beor or Feor, Xdimension and Ydimension denotes the dimensions of X and Y axes respectively, and finally tx and ty are two arbitrary translations within the picture plane (see figure "The wall-paper process" with P(0)=STAR (see figure "Four tool pictures")).

4-SIMPLE CONFORMAL MAPPING (SCM1 and SCM2):

(with the word simple just indicating that no antialiasing process is involved here...) Let us define the two following picture transformations:
```                             1                             x                              -y
[SCM  : ---]        P(x,y) = P1((k1---------)                  ,(k2---------))                  ∀ x,y
1    z                           2    2  modulo Xdimension       2    2   modulo Ydimension
x  + y                          x  + y

2                           2    2
[SCM  : z ]         P(x,y) = P1(k1.(x  - y )                  ,k2.2.x.y)                  ∀ x,y
2                                       modulo Xdimension           modulo Ydimension
```
where k1 and k2 denote two arbitrary constants.

5-GENERALIZED FILTERING (GF):

Let fft and fft-1 denote the complex Fourier transform and its inverse respectively [8]. With K being an arbitrary picture (K stands here for kernel), the generalized filtering transforms the picture P1 into the picture P as follows:
```                                      -1
P = GF(P1,K) = fft  (complex(K)*fft(P1))
```
where complex denotes a function converting a picture into a complex matrix, and '*' is the product "point by point" of the two complex matrices (M=M1*M2: M(x,y)=M1(x,y)M2(x,y) x,y). For example, if K is a centered gaussian field (see the GAUSS picture of figure "Four tool pictures"), the picture P will only display the low spatial frequencies of the picture P1. What is of great interest for our purpose here is not to use only one kernel-picture, but several obtained, for example, by the incremental rotation of an initial anisotropic one (see figure "Texture animation by means of the generalized Fourier filtering process").

6-FOURIER INTERPOLATION (FI):

Starting with three pictures P1, P2 and K (the "interpolation Kernel"), the Fourier interpolation computes a fourth picture P "between" P1 and P2 as follows:
```                                         -1
P = FI(P1,P2,K) = fft  ((complex(K)*fft(P1))+(complex(complementary(K))*fft(P2)))
```
where:
```                    complementary(GreyLevel) = Nmin + (Nmax-GreyLevel).
```
For example:
```                    FI(P1,P2,WHITE) = P1
```
(see the caption of figure "Four tool pictures" for the definition of the picture WHITE). Figures "Texture animation by means of Fourier interpolation" and "Texture animation by means of Fourier interpolation" give examples of this process.

7-ACCUMULATION (A):

When a set of related pictures {P(t) | t [0,T-1]} is available (and obtained, for example, with one of the previous processes), it is sometimes interesting to accumulate them together [9]. The easiest way to do that is to compute:
```                              t=T-1
-----
\
/     W(t).P (x,y)
-----       t
t=0
P(x,y) = --------------------
t=T-1
-----
\
/     W(t)
-----
t=0
```
where W(t) denotes a weighting vector. Another possibility is to consider each picture P(t) as a 2D slice inside a 3D object, and to reconstitute this last one allowing some of the grey levels to be transparent (see figure "Synthesis of tridimensional textures"; it displays the accumulation of 128 bidimensional frames generated with the process "Texture animation by means of the generalized Fourier filtering process" -the step then equals pi/256-).

8-TRIDIMENSIONAL BUMPING (B):

The last process I shall introduce here is 3D visualization of a 2D scalar field (a grey level picture, but as mentioned earlier, the extension of this process to true color pictures is obvious). The idea is far from new and consists of translating the grey levels of a picture into height data [10]. It gives, for example, an easy way to exhibit correlations between two 2D scalar fields (the first one being displayed as a 3D surface and the second one being a texture mapped on the former surface). Both for the sake of simplicity and in order to display here only simple pictures, I shall only use here a process giving bird's-eye view bumping (including shadowing). Taking a height field H and a texture T, it produces the picture P:
```                    P = B(H,T) = bumping(H,T)
```
and then give body to a flat picture.

Once again, my purpose here is not to exhibit very new and complex algorithms, but only to remind the reader that simple processes, when iterated and combined together, can give birth to very complex and unpredictable shapes (in the computer graphics realm) and behaviours. The figure "Synthesis of tridimensional stained-glass window" displays four frames from an animation produced using almost all the preceding processes. It can be described as:
```                    G(0)   = GRID
P(t)   = B(GF(GP(GF(SCM1(G(t)),GAUSS),GF(SCM2(G(t)),GAUSS),STAR),GAUSS),WHITE)
G(t+1) = ELG(G(t))

with t ∈ [0,127]
```
(when in fact it is a little more complicated for it is a true color one). The shapes then obtained surprised me, even though the computer did nothing more than to execute my requests; as stated earlier, the combinations and the iterations of simple processes (using simple "seed" pictures) give birth to very surprising pictures (I dare not say beautiful), some of which are even "biological". This must be a lesson for us: simplicity can produce complexity, and then surprises for the observer. My surmise is that when an artist creates such pictures ("by hand"), they are only the result of numerous combinations and transformations of preexisting elements stored in his memory (each coming either from his five senses or from former "computations") and nothing more.

The algorithms described in this WWW page are elementary and then easy to implement by novice programmers, when the starting pictures "Four tool pictures" (WHITE, GAUSS, STAR and GRID) suggested here are very simple. I should like to encourage reader involvement, in particular in classroom settings, with experiments (about starting pictures, kernel pictures, parameters,...) giving birth to the huge variety of shapes and textures needed for our future virtual worlds...

• [1] "Artificial Evolution for Computer Graphics", Karl Simms, Computer Graphics, Volume 25:319-328, Number 4, August 1991, SIGGRAPH'91.
• [2] "Scientific Visualization, Chaos and Art", Jean-François Colonna, the Visual Computer, Volume 10, Number 6, 1994.
• [3] "Symmetry in Chaos", Michael Field and Martin Golubitsky, Oxford University Press, 1992.
• [4] "Images du Virtuel", Jean-François Colonna, Addison-Wesley France, 1994.
• [5] "The subjectivity of computers", Jean-François Colonna, Technical Correspondence, Communications of the ACM, volume 36, numero 8, page 15-18, 08/1993.
• [6] "Winning Ways for your Mathematical Plays", Elwyn R. Berlekamp, John H. Conway, Richard K. Guy, London, New York, Paris, 1982, volume 2:817-850.
• [7] "Un système informatique au service de la communication", Jean-François Colonna, these d'Etat, INPG, Grenoble, 1985.
• [8] "Digital Picture Processing", Azriel Rosenfeld and Avinash C. Kak, Academic Press, 1976.
• [9] "The Accumulation Buffer": Hardware Support for High-Quality Rendering", Paul Haerberli, Kurt Akeley, Computer Graphics, Volume 24:309-318, Number 4, August 1990, SIGGRAPH'90.
• [10] "Scientific Display: a Means of Reconciling Artists and Scientists", Jean-François Colonna, "Frontiers of Scientific Visualization", Clifford A. Pickover and Stuart K. Tewksbury editors, Wiley InterScience, John Wiley and sons, 1994.
• [11] "Computer Graphics, Principles and Practice", page 668, James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes, Addison-Wesley Publishing Company, 1990.
• [12] "Computer Graphics, Principles and Practice", page 727, James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes, Addison-Wesley Publishing Company, 1990.
• [13] "Artificial Evolution for Computer Graphics", Karl Sims, Computer Graphics, Volume 25, Number 4, July 1991, SIGGRAPH'91.
• [14] "Digital Picture Processing", Azriel Rosenfeld, Avinash C. Kak, Academic Press, 1976.
• [15] "Computer Graphics, Principles and Practice", page 774, James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes, Addison-Wesley Publishing Company, 1990.
• [16] "The Accumulation Buffer": Hardware Support for High-Quality Rendering", Paul Haerberli, Kurt Akeley, Computer Graphics, Volume 24, Number 4, August 1990, SIGGRAPH'90.