In the traditional approach to modeling grain growth with the phase field method, each grain is represented using an order parameter. This becomes a problem when modeling large numbers of grains, because the computational cost of using so many order parameters is prohibitively large. In addition, at a specific point during the simulation, most of the order parameters will have a zero value, with only a few ever having a non-zero value. 

The [GrainTracker UserObject]( makes it possible to model many grains with unique IDs, but only use a much smaller number of order parameters.

Algorithm Description
The grain tracker inherits from [FeatureFloodCount]( and uses its functionality as a basic part of its structure. Therefore, we first discuss FeatureFloodCount and then the GrainTracker

[FeatureFloodCount]( identifies features using a standard stack-based recursive flood fill routine.  Each processor visits its local active elements and calls the flood method for the current element.  If the flood routine encounters a variable value above a threshold value chosen to identify grains, it is marked with a unique number.  The flood routine then recursively visits all connected neighbors marking them with the same number if their variable values are also above the desired threshold. Each processor works on a separate section of the mesh making this stage of the algorithm perfectly parallel.

After the flood algorithm has produced a series of local maps, that information must be gathered and shared among all processors to produce a complete map. A data marshaling (also known as serialization) routine packs up the information into a single long vector for efficient parallel communication. These lists are then replicated on every processor through a global all-reduce communication. A global reduction is necessary as features can grow arbitrarily large and can take on arbitrary shapes. After the data has been replicated on all processors it is unmarshalled through a reverse process into local data structures for use by the remaining pieces of the algorithm.

Once the global maps are constructed, a sphere is constructed that bounds all elements composing each feature by finding the extreme coordinate values in each dimension.  An optional buffer zone can be augmented to each sphere to adjust the behavior of collision detection in the grain tracker algorithm.  These bounding spheres are calculated and stored for use by the grain tracking algorithm discussed below.

[image:242 align:right]
    Identification of interference between grains represented with the same order parameter

[image:243 align:right]
    Remapping of grain to new order parameter

The grain tracking algorithm has three main purposes, to track grain evolution across time steps to maintain their unique ID, detect contact between grains, and remap grains to new order parameters to avoid grain coalescence. At each time step, ```FeatureFloodCount``` constructs a list of grain numbers present on the processor, as well as a list of one or more bounding spheres for each grain and the order parameter number currently being used to represent it. However, there is no guarantee that the number assigned to a specific grain at any time step will match the number given at the previous time step. A specific grain number is tracked between time steps by inspecting and comparing the information collected by the flood algorithm. Since any two grains represented by the same order parameter are not allowed to intersect at any time in the simulation, a simple movement minimization algorithm can guarantee consistent tracking between consecutive time steps. Thus, each grain maintains a unique identifier for the duration of the simulation regardless of how the grain changes shape, or migrates through the domain due to any kind of applied driving force. Finally, a status indicator is used to determine whether or not a grain is active, where active is defined as a grain that is represented by at least one entity in the domain for the current time step. Grain identifiers belonging to grains that are completely absorbed or otherwise disappear during the simulation have their status indicators set to "inactive" and are never reused.

The actual tracking of a unique grain number from one time step to the next is conducted by iterating over the current list of unique grains searching for the new bounding sphere whose centroid is closest to the previous one. While on first inspection this may seem like a naive implementation, the combination of the order parameter number and closest centroid ensures a unique match. While nearby grains may compete for a single closest centroid on their own, they will always have different variable ids or they would have been remapped on the previous time step. If a grain disappears in the current time step, there will be two grains in the previous time step claiming ownership of a single bounding sphere in the new list, the grain that disappeared and the actual grain. In this case the furthest grain is marked as inactive. This avoids large jumps in minimum distances as grains migrate towards or away from a periodic edge in the simulation.  In those cases at least one existing bounding sphere will remain close across any two time steps.

After the tracking routine has completed, the grains are inspected to see if grains represented with the same order parameter are about to come in contact. This is accomplished by inspecting every pair of grains represented by the same variable to find if any of their representative bounding spheres intersect. When intersection occurs, the list of grains is checked to locate a suitable order parameter where one of the intersecting grains can be remapped.  The criterion for this selection is straightforward.  The distance is calculated between bounding sphere centroids for the grain that needs remapping and all grains represented by other order parameters. Then, a list of each order parameter's closest grain is compiled.  The order parameter whose closest grain is located furthest away from the current grain is selected for remapping. Unfortunately this implementation is not guaranteed to find a suitable remapping candidate as this amounts to a greedy coloring algorithm. Additional candidates are also attempted until any suitable candidate is found. Once a suitable candidate is found, the solution values defining the grain are simply moved from the old order parameter solution to the new new order parameter. Additionally the variable index for the current grain is updated in the unique grains list to reflect the change. If no suitable order parameter is found for remapping due to an insufficient number of order parameters, the current remapping operation is aborted and the simulation aborts.

GrainTracker Usage

[image:244 align:right]
    Example of the grain tracker, where a simulation is conducted with 18 order parameters and representing 100 grains. Run with example in the phase_field module ```grain_growth_2D_graintracker.i```

The GrainTracker is very modular in design and can be added or removed from any simulation. Additionally the grain re-mapper can be used to supply a number of scalar field variables for visualization of the grain structure or other uses.  It can display grains represented by a given variable or all grains simultaneously; it can display fields indicating which order parameters own which grains, grain centroids, or even bounding spheres.

GrainTracker is enabled for a given simulation by adding a GrainTracker block in either the Postprocessor block or the UserObject block, as shown below

    type = GrainTracker
    threshold = 0.2 #Threshold used for FeatureFloodCount
    convex_hull_buffer = 0.0 #Extra buffer size added around bounding spheres 
    use_single_map = false #Determine whether information is tracked per coupled variable or consolidated into one (default: true) 
    enable_var_coloring = true #Instruct the UO to populate the variable index map
    condense_map_info = true #Determines whether we condense all the values when in multimap mode (default: false);
    compute_op_maps = true #Indicates whether the data structures that hold the active order parameter information should be populated or not (default: false)
    execute_on = 'initial timestep_begin'
    flood_entity_type = elemental #Determines whether the flood algorithm runs on nodes or elements

In addition to creating the GrainTracker block, you must also create an initial condition that uses each order parameter to model multiple grains. This can be accomplished with [PolycrystalIC's](GrainGrowthModel) or with the [EBSDReader](EBSDReader).

GrainTracker is tested in  

It is demonstrated in the example problem