• 1-GENERALIZED PRODUCT (GP):
• 1.1-Generalized multiplication table:
• 1.1.1-fog effect:
• 1.1.2-depth cueing effect [12]:
• 1.1.3-nota:
• 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):

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

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 [06]. 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 [07] 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 [08]. 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 [09]. 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.

                    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]

• [01] "Artificial Evolution for Computer Graphics", Karl Simms, Computer Graphics, Volume 25:319-328, Number 4, August 1991, SIGGRAPH'91.
• [02] "Scientific Visualization, Chaos and Art", Jean-François COLONNA, the Visual Computer, Volume 10, Number 6, 1994.
• [03] "Symmetry in Chaos", Michael Field and Martin Golubitsky, Oxford University Press, 1992.
• [04] "Images du Virtuel", Jean-François COLONNA, Addison-Wesley France, 1994.
• [05] "The subjectivity of computers", Jean-François COLONNA, Technical Correspondence, Communications of the ACM, volume 36, numero 8, page 15-18, 08/1993.
• [06] "Winning Ways for your Mathematical Plays", Elwyn R. Berlekamp, John H. Conway, Richard K. Guy, London, New York, Paris, 1982, volume 2:817-850.
• [07] "Un système informatique au service de la communication", Jean-François COLONNA, these d'Etat, INPG, Grenoble, 1985.
• [08] "Digital Picture Processing", Azriel Rosenfeld and Avinash C. Kak, Academic Press, 1976.
• [09] "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.