and

Simplicity

Jean-François COLONNA

jean-francois.colonna@polytechnique.edu

CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641, Ecole Polytechnique, CNRS, 91128 Palaiseau Cedex, France

france telecom, France Telecom R&D

[

[

[

(CMAP28 WWW site: this page was created on 06/07/1995 and last updated on 01/28/2014 15:08:45 -CET-)

(published in

- 1-GENERALIZED PRODUCT (GP):
- 1.1-Generalized multiplication table:
- 1.2-Convolution with a variable length kernel:
- 1.3-Conclusion:
- 2-EXTENDED LIFE GAME (ELG):
- 3-WALL-PAPER (WPB and WPF):
- 4-SIMPLE CONFORMAL MAPPING (SCM1 and SCM2):
- 5-GENERALIZED FILTERING (GF):
- 6-FOURIER INTERPOLATION (FI):
- 7-ACCUMULATION (A):
- 8-TRIDIMENSIONAL BUMPING (B):

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.

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 P1As 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).

(2): M(i,j) = (1-L).j + L.Nmaxwith:

i - Nmin L = ------------- Nmax - NminThen 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.Nmaxwith:

Z(x,y) - Nmin L = --------------- Nmax - NminWhen the point (x,y) is close to the foreground (low values of Z(x,y)):

L << 1and 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 ~ 1and from (3) we see that:

Pg(x,y) ~ NmaxThe 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.Lwith:

Z(x,y) L = -------- 255The 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.

Nmax - i (4) : M(i,j) = Nmin + (j - Nmin)------------- Nmax - Nminthen 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 - NminIt 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)-------------- 255It 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)) = -------- 2thus giving a brighter background. The function T could be implemented as a Look-Up Table.

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=0Let us describe now one application of the variable length kernel convolution.

(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 \-/ ito 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) = NmaxThus 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.

Nmin + Nmax T(-------------) = Nmin 2

[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 8The 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:

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)

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=0where 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 E [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=0gives 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+1where 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 8The 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").

_ _ Feor(a,b) = max(min(a,b),min(a,b)) \-/ a,b E Rin 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 E [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 Ydimensionwhere the eor operator is either

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 + ywhere k1 and k2 denote two arbitrary constants.

2 2 2 [SCM : z ] P(x,y) = P1(k1.(x - y ) ,k2.2.x.y) \-/ x,y 2 modulo Xdimension modulo Ydimension

-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").

-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.

t=T-1 ----- \ / W(t).P (x,y) ----- t t=0 P(x,y) = -------------------- t=T-1 ----- \ / W(t) ----- t=0where 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-).

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))(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.

with t E [0,127]

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.

Copyright (c) France Telecom R&D and CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / Ecole Polytechnique, 1995-2014.