Home | Links | Applets | Papers | Class Plan | Team

I         Introduction

 A cellular automaton is an array of identically programmed automata, or "cells", which interact with one another. The arrays usually form either a 1-dimensional string of cells, a 2-D grid, or a 3-D solid. Most often the cells are arranged as a simple rectangular grid, but other arrangements, such as a honeycomb, are sometimes used. The essential features of a cellular automaton ("CA" for short) are:

•  Its State - a variable that takes a separate value for each cell. The state can be either a number or a   property.

•  Its Neighborhood - the set of cells that it interacts with. In a grid these are normally the cells physically  closest to the cell in question.

• Its Program  - the set of rules that defined how its state changes in response to its current state, and    that of its neighbors.

 Cellular Automata models are used to simulate the process of crystal growth and to generate various patterns that the crystals create in nature. Crystals form whenever a solid is formed from fluid. Crystals form from vapors, solutions or molten materials, and are built from repeating units. Crystals grow from the outside. Crystal formation is called crystallization. Crystallization means "become crystals". At a microscopic level, crystals consist of regular arrays of atoms laid out much like the cells in a cellular automaton. Crystals always start from a seed such as a grain of dust and then progressively adding more atoms to their surface. Some of the examples are: snowflakes formation from water vapor, rocks like felsite, and most non-living substances. This paper reports on some of the work done by researchers in simulating crystal growth using cellular automata models and describes the snow crystals in detail.

II        Description of Crystals

This section consists of the crystal history, how it came into existence, the different categories of crystals and description of snow crystals in detail.

1.                 History of Crystals 

'Crystal' comes from a Greek word meaning clear ice. In the late sixteenth century, Andreas Libavius, made the theory, which said, "Mineral salts could be identified by studying the shapes of the crystal grains." In 1669, Nicholas Steno observed that corresponding angles in two crystals of the same material were always the same. The first synthetic gemstones were made in the mid-1800s, and methods for making high-quality crystals of various materials have been developed over the course of the past century. Since the mid-1970s such crystals have been crucial to the semiconductor industry. Systematic studies of the symmetries of crystals with flat facets began in the 1700s, and the relationship to internal structure was confirmed by X-ray crystallography in the 1920s.

2.                 Different Categories of Crystals 

There are many different shapes and kinds of crystals. There are about 22 crystal shapes. Some of them are cubes, hexagonal and prisms. All crystals are not the same shapes. All perfect crystals have flat surfaces. There are also the kinds. For example, there is basalt, salt, sand, quartz, granite, obsidian, shale, marble, slate, petrified wood, diamonds, snowflakes, rhyolite and felsite, they are all crystals. 

Wolfram, in his book ‘A New Kind Of Science’ has categorized the crystals as follows:

i)        Hopper crystals

 When a pool of molten bismuth solidifies it tends to form crystals like the one shown in Figure 1. What seems to give these crystals their characteristic “hoppered “ shapes is that there is more rapid growth at the edges of each face than at the center. Hoppering has been noticed in many substances like galena, rose quartz, gold, calcite, salt and ice. 

Figure 1. Hopper Crystals

ii)      Polycrystalline Materials

A solid can be composed of many crystalline grains, not aligned with each other. It is called polycrystalline. In other words, composed of aggregates of crystals. When solids with complicated forms are seen, it has usually been assumed that they must be aggregates of many separate crystals with each crystal having a simple faceted shape. However, individual crystals can yield highly complex shapes. There will nevertheless be cases however where multiple crystals are involved. These can be modeled by having a cellular automaton in which one starts from several separated seeds. Polycrystalline materials consist of domains. The molecular/atomic order can vary from one domain to the next. The growth process for polycrystalline materials is shown in Figure 2. and can be imagined as follows. Consider a blank substrate placed inside a growth chamber. Crystals begin to grow at random locations with random orientation. Eventually the clusters meet somewhere on the substrate. Because the clusters have differing crystal orientations, the region where they meet cannot completely bond together. This results in the interstitial region

             

             Figure 2. A polycrystalline material showing two separate crystal phases separated by interstitial material.

iii)          Quasicrystals

The idea that crystals are periodically ordered was amazingly successful. Before the discovery of quasicrystals, it was known that crystals were solids composed of a periodic arrangement of identical unit cells. Among the most well known consequences of periodicity is the fact that the only rotational symmetries that are possible are 2-, 3-, 4-, and 6-fold rotations. Five-fold rotations (and any n-fold rotation for n>6) are incompatible with periodicity. However, on April 8^th 1982 Shechtman, while performing an electron diffraction experiment on an alloy of Aluminum and Manganese observed a new symmetry. By orienting the alloy in different directions he found that it had the symmetry of an icosahedron, containing six axes of 5-fold symmetry, along with ten axes of 3-fold symmetry and 15 axes of 2-fold symmetry. The crystal that Shechtman discovered was named as ‘quasi crystal’. Quasicrystals are very different from periodic crystals. They may possess rotational symmetry, which is incompatible with periodicity. To this date, quasicrystals have been found that have the symmetry of a tetrahedron, a cube, an icosahedron. Figure 3. shows some pictures of quasicrystals. 

   

 Figure 3. Some forms of quasicrystals.

iv)          Amorphous materials

These are the materials that do not have a well-ordered structure. They lack distinctive crystalline structure. When solidification occurs fairly slowly, atoms have time to arrange themselves in a regular crystalline way. But if the cooling is sufficiently rapid, amorphous solids such as glasses are often formed. Amorphous materials do not have any long-range order but they have varying degrees of short-range order.

Examples of amorphous materials include amorphous silicon, glasses and plastics. Amorphous silicon provides the   prototypical amorphous material for semiconductors. It has wide ranging and unique properties for use in solar cells and thin film transistors.

 Figure 4.  Amorphous crystals. Lacking distinctive shape.

v)                  Snow Crystals and Snowflakes

Snowflake is one of the well-known examples of crystal formation. Snowflakes are collections of snow crystals, loosely bound together into a puff-ball. These can grow to large sizes, up to about 10 cm across in some cases, when the snow is especially wet and sticky. Thus, snow crystals are individual, single ice crystals, often with six-fold symmetrical shapes. These grow directly from condensing water vapor in the air, usually around a nucleus of dust or some other foreign material. Typical sizes range from microscopic to at most a few millimeters in diameter. The structure of a given snowflake is determined by the temperature and humidity of the environment in which it grows, and the length of the time it spends there. Figure 5. shows some forms of snowflakes that are often seen in nature.

                

                     (1)                                  (2)                                (3)

          Figure 5. 1) Simple sectored plate; 2) Dendritic sectored plate; 3) Fern-like stellar dendrite

Six-fold symmetry of snow crystals

When water freezes into ice, the water molecules stack together to form a regular crystalline lattice, and the ice lattice has six-fold symmetry. It is this hexagonal crystal symmetry that ultimately determines the symmetry of snow crystals.

      Complex symmetrical shapes of snow crystals

The snow crystals form complex shapes because of their simple six-fold symmetry and also because they are both complex and symmetric, and it is this combination that gives them their special beauty.  To see how such fancy crystals come about, consider the history of a growing snow crystal in the atmosphere. The growth usually begins with a dust particle, which absorbs some water molecules that form a nucleus for the ice crystal.  Typically snow crystals need some kind of surface on which to get started.  Faceting then causes the newborn crystal to quickly grow into a tiny hexagonal prism. As the crystal grows larger, the corners often sprout tiny arms, since they stick out a bit further into the supersaturated air and thus grow a bit faster. The crystal growth rate strongly depends on the temperature. If there are variations in the temperature, the snow crystal encounters different growth conditions, growing into an intricate shape. Thus, we see such a rich diversity in the shapes of snow crystals in nature. When a snow crystal grows from air supersaturated with water vapor, there are two dominant mechanisms that govern the growth rate. The first is diffusion -- the way water molecules must diffuse through the air to reach the crystal surface. The second involves the surface physics of ice -- the efficiency with which water molecules attach themselves to the ice crystal lattice.  

Cellular automata applied to snowflakes

CA’s do quite easily reproduce the basic feature of the overall behavior that occurs in real snowflakes. Snowflakes can be modeled with the help of cellular automata to produce simple faceted forms, needle-like forms, tree-like or dendritic forms, as well as rounded forms.

One of the ways to create real snowflake patterns is to use two-dimensional cellular automata displaying 3-state seven sum totalistic rules on a hexagonal grid. Each cell has three states representing growth as a result of different temperature conditions. The state of a cell is updated based on the sum of its six neighbors and its current state.  Figure 6. shows some of the snowflake patterns generated after applying the totalistic rule.

                              

         Figure 6. Seven-sum totalistic rule showing intricate snowflake patterns.

III       Cellular Automata models

There has been a lot of research work done in the field of crystals, which make use of cellular automata models for simulation purposes. I describe below Packard’s cellular automaton model [1] and a 3-dimensional cellular automaton model of ‘free’ dendritic growth[8].

Packard’s Cellular Automaton Model

 Introduction

Crystal growth is an excellent example of a physical process that is microscopically very simple, but that displays a beautiful variety of macroscopic forms. Many local features are predicted from continuum theory, but global features may be analytically inaccessible. For this reason, computer simulation of idealized models for growth processes has become an indispensable tool in studying solidification. Packard presents a new class of models that represent solidification by sites on a lattice changing from zero to one according to a local deterministic rule. The strategy is to begin with very simple models that contain very few elements, and then to add physical elements gradually, with the goal of finding those aspects responsible for particular features of growth.

 Description of the model

The simplest deterministic lattice model for solidification is a 2D CA with two states per site to denote presence or absence of solid, and a nearest neighbor transition rule. Packard considers rules, which have the property that a site value of one remains one (no melting or sublimation). The rules also depend on neighboring site values only through their sum:

      =    f( )     with            =

The domain of f ranges from zero to number of neighbors; f takes on values of one to zero.

 These rules display four types of behavior for growth from small seeds:

1.  No growth at all. This happens for the rule that maps all values of σ to zero.

2. Growth into a plate structure with the shape of the plate reflecting the lattice structure

3. Growth of dendrite structure, with side branches growing along lattice directions; this type of rule is obtained by adding growth inhibitions to the previous rule. Physically growth inhibition occurs because of the combined effects of surface tension and radiation of heat of solidification.

4. Growth of an amorphous, asymptotically circular form. This form is obtained by adding even more growth inhibition. 

The two ingredients missing from the cellular automaton model are:

 i)                    Flow of heat

This may be modeled with the addition of a continuous variable at each lattice site to represent temperature.

ii)                   Effect of solidification on the temperature field

When solid is added to a growing seed, latent heat of solidification must be radiated away. This is modeled by causing an increment in the temperature field. 

Simulations

In these simulations, the temperature is set to a constant (high) value when new solid is added. This means that heat flows to nearby interface sites and inhibits their solidification.

 This model is a hybrid of discrete and continuum elements. The addition of solid happens in a discrete way, which can only be a very coarse approximation to solid deposition on molecular length scales. The use of continuum variable at each lattice site to represent temperature gives the model unique features lacking in a purely discrete cellular automaton model. The parameters used in the simulation are diffusion rate and amount of latent heat added upon solidification. Other parameters (call it λ) may characterize the local temperature threshold function. These parameters may be varied to obtain different macroscopic forms. Figures 7(a-c) shows a sequence of pictures when λ is varied from low to high values.

Figure 7a illustrates the case when λ is small so that more heat diffuses before a boundary site will solidify. Figure 7b illustrates the effect of raising λ. There is a rather chaotic network of tendrils that appear to grow in every direction, but still they show some tendency to grow along lattice directions. The tip splitting instability is apparent, preventing the formation of long dendrites with regular side branching. When λ is raised even further as shown in Figure 7c, the tips begin to stabilize, and the tip splitting instability gives away to the side branch instability.

 The macroscopic forms yielded by this model show remarkable similarity to experiments in pattern formation.

              

       (a)                                                  (b)

 

                         (c)

Figure 7.  Different growth patterns as parameters are varied in the deterministic growth rule: (a) Amorphous, isotropic fractal growth. (b) Tendril growth, dominated by tip splitting. Some anisotropy is evident. (c) A macroscopic form showing strong anisotropy, stable parabolic tip with side branching.

A 3D CA model of ‘Free’ Dendritic growth

Introduction

Dendrites are commonly observed in materials solidifying with low entropies of fusion. A dendrite is a branching structure that freezes such that dendrite arms grow in particular crystallographic directions. As a dendrite grows it is possible for additional arms to form behind the growing tip. The growth of dendritic crystals is of practical importance in metallic materials. Dendrites are termed ‘free’ dendrites when they form individually and grow in super-cooled liquid. As growth occurs the latent heat of fusion released flows into the supercooled liquid. Both pure materials and alloys can display free dendritic growth behavior. S. Brown and N. Bruce [8] present a 3D CA model of a growing ‘free’ dendrite. This simple model has been able to simulate changes in dendrite morphology as a function of liquid supercooling that are similar to some of those observed experimentally.

The Cellular Automaton Model

In this model, a one million element grid is used with an initial nucleus of 3x3x3 elements placed at the center. Each of these is set to a value of 1 (i.e. solid).  All other elements are set to 0. (i.e. liquid). For each simulation the temperatures of all sites are set to an initial predetermined value representing supercooling. Opposite faces of the cubic 100x100x100 computational domain were treated as periodic, as if in contact with one another. Details of the simulation procedure are described below assuming that the dendrites are thermal in nature.

 The following rules and conditions are assumed:

1. A liquid site may transform to a solid site only if c_x >= 3 and/or c_y >=3 and/or c_z >=3 (where c_x, c_y, and c_z    are the number of solid sites present in the surrounding eight nearest neighbors taken in each of the principal x, y, and z planes respectively).

2. Growth can occur only if the temperature of the liquid site is less than a critical temperature T _crit.

3.  T _crit  =  - γ ( f(c_x) + f(c_y) + f(c_z) )                                                                                                                                                   where f(c_i) = 1/ c_i   c_i >= 1                                                                                                                                                                     f(c_i) = 0   c_i <  1   and  γ is a constant representing the solid/liquid interfacial energy.

4. If a liquid element transforms to a solid element then the temperature of the element is raised to a fixed value to simulate the release of latent heat.

5. Conductive heat transfer is modeled by updating the temperature of each element at each time step. The average temperature of the six nearest neighbor elements is computed and the temperature of the central element is moved towards this average by an amount governed by an assumed heat transfer constant.

For all simulations, γ is set to a value of 20. In each step of the simulation all liquid sites are tested to determine whether growth will occur. All sites are then updated simultaneously to their new states of liquid or solid. Liquid sites that have transformed to solid have their temperature raised to a fixed value. The process is then repeated.

Despite the simple nature of the cellular automaton model, it is possible with judicious choice of parameters, to simulate the growth of highly complex 3-D dendritic morphologies that exhibit many of the features observed in real dendrites.

Results and Observations

A series of simulations are performed using initial liquid supercoolings ranging from –60 to –32. Different dendritic shapes are produced. In these cases, the structures are allowed to grow until the number of solid sites grown from the center of the 100x100x100 grid towards the edge along any of the principal axes was 45. 

For larger initial supercoolings, compact structures with large volumes fractions of solid were produced. As the amount of supercooling was reduced there was a transistion to plate-like growth. When the initial supercooling was decreased further the growth pattern became more spherical with noticeable tip-splitting.Considering the simplicity of the model, the results show remarkable similarity to experimentally observed free dendrites. But, it should be noted that the simulated dendrites produced in this model all evolved from a single nucleus whereas the experimentally observed growth patterns often comprised several interpenetrating dendrites.  

IV      Hexlife

 Hexlife is a model of Conway’s Game of Life on a hexagonal grid. This classic game of life, a cellular automaton algorithm, was invented by British mathematician John Conway in 1970. Conway's Life plays on a rectangular grid. Each cell has eight neighbors and survives only if two or three of its neighbors are alive. If more than three of its neighbors are alive, it dies from overcrowding; less than two, it dies of 'loneliness'.

 In HexLife, a hexagonal grid is used. Each cell has six neighbors. These are called the first tier neighbors. The hexlife rule looks at twelve neighbors, six belonging to the first tier and remaining six belonging to the second tier. This is shown in Figure 8.

             

                                                           

                                                   

  Figure 8.  12 neighbors in HexLife. The first tier six neighbors are marked by ‘red’ color. The second tier six neighbors considered are marked by ‘blue’ color. The center white cell  is the current cell, whose state will be determined by the sum of these 12 neighbors.

 As in Conway's Life, whether a cell is born, dies, or survives to the next generation is determined by how many of these 12 neighboring spaces contain live cells. The live cells out of the twelve neighbors are added up each generation. However, live 2nd tier neighbors are only weighted as 0.3 in this sum whereas live 1st tier neighbors are weighted as 1.0. A cell becomes live if this sum falls within the range of 2.3 - 2.9, otherwise remains dead. A live cell survives to the next generation if this sum falls within the range of 2.0 - 3.3. Otherwise it dies (becomes an empty space).

 I have implemented the hexlife rule by David Ballinger. Each cell of the grid has three states It is dead, is born, or it survives. A dead cell is simply shown by an empty cell. A cell that is born is shown by blue color and a cell that survives (stays live) is shown by green color.  Various patterns such as gliders and reflection are observed. One could experiment by setting different initial population (set of live cells). The snapshot of a hexlife pattern is shown in Figure 9.

 Figure 9. A hexlife pattern, which resembles gliders. A cell that is born is shown by blue color and a cell that survives to the next generation is shown by green color.

IV      Class 4 Crystal Growth

Wolfram’s classification of the four classes is on the basis of asymptotic behavior of cellular automaton rule acting on a random initial condition. Under such circumstances the rules discussed in Packard’s cellular automaton model would lead to fixed points, and so would be in Wolfram’s class 2. Wolfram’s class 4 behavior involves crystal growth which is a mixture of order and randomness: localized structures are produced which on their own are fairly simple, but these structures move around and interact with each other in very complicated ways.

Wolfram describes the crystal growth by considering two states, in which one state represents the region of solid and other state represents region of liquid or gas. The most complex snow crystals are formed when a developing crystal experiences different conditions as it passes through the atmosphere, each favoring a different type of crystal growth.  In order to simulate complex crystal growth, we could consider more than two states (for ex. three states), where each state could represent a different condition of crystal growth. Then, if we apply rules based on these states on random initial conditions, we may get more complex, class four behavior.

V       Summary 

Crystals have been known since the sixteenth century. There are many different kinds of crystals seen in nature. It is very fascinating to see the different intricate and complex forms that one sees during crystal growth. In this paper, I have described the different types of crystals, their formation, structure and patterns generated.  One of the most well known examples of crystal growth is the snowflake growth. Wolfram [2] has described cellular automata models to generate the real snowflake patterns. One could also use totalistic rules to generate the different patterns.  This paper shows some of the snowflake patterns generated using CA model with totalistic rules. Conway’s game of life, which was originally modeled on a square grid, can also be modeled on a hexagonal grid by considering the sum of 12 neighbors. This report discusses the hex life rule.

This paper also reports on the work done by Packard [1], Brown and Bruce [8]. Finally it concludes by describing the possibility of class 4 behavior in crystal growth. 

VI      References 

[1]        Packard, N. “Lattice Models for Solidification and Aggregation,” Theory and Applications of Cellular Automata, (1986), pp. 305. 

[2]        Stephen Wolfram. “A New Kind Of Science”. 

[3]        http://www.selah.wednet.edu/SOAR/SciProj2000/KaitlynS.html

[4]        Dendrites. http://www.mpipks-dresden.mpg.de/~emmerich/forschung/whatden.html

[5]        Bismuth Crystals. http://www.crystalgrowing.com/bismuth/bismuth1.htm

[6]        Quasicrystals. http://glinda.lrsm.upenn.edu/~weeks/icon.html

[7]        Gandin, A., and Rappaz, M., “A 3D Cellular Automaton Algorithm for the prediction of dendritic grain growth,” Acta Metallurica Inc (1997), pp.2187-2195

[8]        Brown, S., and Bruce, N., “A 3D CA model of ‘Free’ Dendritic growth” Scripts Metallurgica et Materialia (1995), pp. 241-246.

[9]        Snow Crystals. http://www.its.caltech.edu/~atomic/snowcrystals/dendrites/dendrite.htm

[10]      Condensed Matter Physics. http://www.cmp.caltech.edu/~lifshitz/quasicrystals.html

[11]       Ballinger, D., (1999) Hexlife. http://www.well.com/~dgb/hexlife.html.

 

Presentation Slides