Cellular Automaton Shading for Building Envelopes - Cellular Automata in Image Processing and Geometry - page 217

further investigations including totalistic triangular cellular automata (tTCA) and
the stabilization process see [25].

11.4.2 Cellular Automata on Triangulated Free-Form Surfaces

The application of stTCA on a free-form surface has been demonstrated in [63].
However, general rules have potential of allowing more direct control over the CASS
mesh than totalistic and semi-totalistic rules. For a corresponding demonstration
see [60]. Figure 11.19 shows three arbitrarily selected 2D2C TCAs: 9622, 44862,
65534 and applied on the BE shown in Fig. 11.1. For an interactive demonstration
illustrating the application of those TCAs on a free-form surface with voids see [64].

11.5 Application of Evolutionary Algorithms for Optimization

of CA Shading

As mentioned in Sect. 11.2.1, the sequence of initial conditions (SIC) is besides the
local transition rules (TR) the second most fundamental factor determining the per-
formance of CASS. Finding optimal SIC is much more straightforward than finding
an automaton for CASS, nevertheless it is a NP-problem: the number of all possible
SICs grows as factorial of the width of a shading array. Since it is impossible to
exhaustively explore the entire search space, it is natural to use an meta-heuristics
for finding, if not perfect, at least good or competitive solutions. Evolutionary al-
gorithms (EAs) are a well established methodology in this field which has been
successfully applied for a number of CA-related problems, e.g.: automated design
of CA-based complex systems [54], evolving a non-uniform CA where each cell
in the lattice does not use the same rule set [14]; finding Wolfram class IV, that is
complex rules [7]; density classification task [38] and the parity problem [58] [35];
discovering and designing cell-state transition functions, where CA are designed
to satisfy certain global conditions [15], etc. The application of EA for optimiza-
tion of SIC for a 100 100 cell CASS has been presented in [67]. In that pa-

per the objective is to minimize grayness monotonicity and pattern distribution
error (GDE), which is called there the cost function (CF). The core parts of the

×

Fig. 11.17 The history of evolution from Fig. 11.16 shown as a single diagram. The shaded
part after 29 th time step indicates stabilization of the state of the mesh. White, gray and white
indicate transparent facets, voids in the mesh and opaque facets, respectively.