Nir Yefet 1998  project summary:
 [ Nir's homepage ] [Computational Physics] [Comphy's projects]  [The Project Software]  PAGE INDEXIntroductionPercolationCritical pointHoshen-Kopelman methodSoftwareViewsLinksBottom of the page

3D Visualization of percolation clusters

N. Yefet, as a project handed to Dr. J. Adler
Technion - The Israeli Institute of Technology

Many phenomena in physics, chemistry, and biology can be modeled by spatial random processes.

## Introduction

In this project the problem of PERCOLATION is investigated .
In order to introduce the concept of percolation in 3D we consider an example from simple electricity.
Consider a large box, balls and a kid. Some balls are conductors and some are not. The box's lower face is connected to an electrical contact. The kid had came and started to throw the balls into the box. (As we know, A kid doesn't recognize the difference among the balls). This kid is(was) not a lazy one. He filled the box. Surprisingly, he chose to touch the ball on top of the box. Is this kid still alive???
Most of the time we use the percolation model for which analytical results are not available as in our example. Percolation can be easily studied using more computer power than is available. In this project I emphasis the need to use computers carefully, rather than as sledge hammers.                                TOP

## Percolation

Considering our simple physics problem into a specific mathematical model: site percolation on a box lattice. This uses an L x L x L box matrix of 1s and 0s, called the site matrix. Each site is a ball. A 1 represents an `occupied` site (a conductor ball)  and a 0 an `empty` site (a plastic ball). The sites are occupied randomly with some site occupation probability, p.
A cluster is a set of occupied sites all of which are connected to an occupied site by neighboring occupied sites. (Neighbors are only in the x- , y- and z-directions, not along diagonals), i.e. an occupied site belongs to a cluster if a member of the cluster is either above, below, left or right of it. A spanning cluster has an element in both the top and bottom surfaces of the site matrix. There is a certain probability p to have a site be occupied.
As p increases, the probability that there is a cluster from one side of the system to the opposite side increases. As the size of the square lattice increases, there is a narrower range of p values for which we go from no "spanning cluster" to the existence of a spanning cluster. This is an example of a phase transition and many of the ideas that apply to this simple model are also important for critical phenomena that are studied in condensed matter physics and quantum field theory.

 A 2D Site Percolation [1] 3D Box filled with some clusters
TOP

The Critical Point

Investigations lead the result of  how the probability of a site matrix having a spanning cluster depends on the site occupation probability p. Site percolation is an example of a critical phenomenon. There is a special value of p, called the critical site occupation probability pc, such that for p < pc spanning clusters never occur. While for p pc they always occur. The case p=pc is called a critical point.                                          TOP

Hoshen-Kopelman Algorithm

Hoshen-Kopelman algorithm describes the idea behind the percolation check. The algorithm is based in labeling each occupied site in the crystal.

The algorithm can best be described by an example. Consider a crystal with the following configuration.
 x-y-0 x-y-1 x-y-2 x-y-3 5 4 6 4 11 4 4 4 4 16 4 9 10 13 10 15 1 3 2 8 12 8 4 1 1 2 1 7 2 1 2 14
Each place in the matrix is a site in the crystal. It's a 3D matrix for simulation of a 3D crystal.
Assigning cluster labels to sites beginning at lower left corner (0,0,0) and continues in the x-direction from left to right.
Each occupied site, located at (x,y,z) looks at its neighbors sites with lowers coordinates (x,y,z-1), (x,y-1,z),(x-1,y,z). Else neighbors are unoccupied it gets the next available cluster label {i.e. (3,0,0) is assigned 2} ELSE the site is assigned its label.
One can see that there might be different labels for the same cluster as seen at sites (2,1,0) labeled 3 & site (3,1,0) labeled 2.
Let's see how did they get their labels?
Site (2,1,0) is assigned 3  because its neighbors are unoccupied {NOTE that sites (3,1,0) hasn't get a label yet}
Site (3,1,0) is assigned label 2 because it has an occupied neighbor at (3,1,1) labeled 2.
Noticing the linkage between the clusters and the improper labels we set np(3)=2 which means that from now, we cancel the use of label 3 and use label 2 instead of it.
Using this method we assign the following proper labels (3,1,1) np(3)=2; (1,3,1) np(5)=4; (3,0,1) np(7)=2; (0,3,1) np(9)=4;
There are bit more complicated situations. At site (3,2,2) np(12)=np(13)=10; than np(11)=4. At site (2,3,2) we set np(13)=4 and update np(12)=np(10)=4. The update of  label-13's neighbors is done in the first step of the labeling loop in the algorithm using the original Hoshen-Kopelman algorithm. In few words, Each site with occupied neighbors is assigned the minimum proper label. at the end we have the following set of np's:
np(1)=0; np(2)=0; np(3)=2; np(4)=0; np(5)=4; np(6)=0; np(7)=2; np(8)=0; np(9)=np(10)=np(11)=np(12)=np(13)=4; np(14)=8; np(15)=0; np(16)=0;

Assigning the proper labels to the sites we get the sites labels as followed.
 x-y-0 x-y-1 x-y-2 x-y-3 4 4 6 4 4 4 4 4 4 16 4 4 4 4 4 15 1 2 2 8 4 14 4 1 1 2 1 2 2 1 2 14
Now, It's simple to check if there is a percolation or not. If there is the same label at two surfaces (lines in 2D) it means that there are sites linked between the points there is percolation.
In our example, One can see that there is a percolation between surfaces (x,y,0) and (x,y,3). the cluster is labeled 4.
The same cluster (#4) is also a percolation cluster between surface (0,y,z) and (3,y,z). There is no percolation in the y-direction.                                                                                                                                     TOP

The Project Software

To use this project software, you should have the following programs on your computer/workspace :
1) C compiler 2) Open GL/Mesa.
NOTE: All the files should be located in same directory.
UNIX users may use  main  as their compile file (note: chmod +x main).
Other should do the simple following steps:
1) Compile "perc.c" (The executable file should be named "perc.ex") : cc perc.c -o perc.ex
2) Compile "crystal.c" as an OpenGL file. (The executable file should be named "crystal.ex") gcc crystal.c -o crystal.ex -L/usr/local/Mesa-1.2.8/lib -lMesaGLU -lMesaaux -lMesatk -lMesaGL -lXext -lX11 -lm -L/usr/X11R6/lib Now, it's cleary you have to run perc.ex and than crystal.ex                                 TOP

Views

To view several still pictures from different angles click 1 2 3 4 5                                                      TOP

References

Books:  Percolation Theory

Websites: