# GrainTracker

The Grain Tracker is a utility that may be used in phase-field simulations to reduce the number of order parameters needed to model a large polycrystal system. The GrainTracker utilizes the FeatureFloodCount object for indentifying and extracting individual grains from a solution field. Once the FeatureFloodCount object has identified all grains, the GrainTracker does two things:

• Match up grains from the current timestep with grains from the previous timestep.

• Remap grains that are "close" to coming into contact.

## Grain Tracking

The ability to track features over time is of interest for many simulation types. Here we present an algorithm for tracking arbitrary features on an unstructured mesh over time. The tracking stage is responsible for maintaining consistent and unique identification for an arbitrary number of moving and interacting features over time. The tracking stage is the only stage in the algorithm which requires stateful data between time steps. This is important from an implementation perspective as it can have an affect on the ability of a simulation to checkpoint, terminate, and successfully restart. Restart capabilities are useful for handling hardware faults or spreading out a long running simulation over several execution windows common in high performance computing environments.

During the first invocation of the feature tracking stage there is no previous feature data to compare against so no tracking is performed. Instead a set of IDs must be assigned to each identified feature. These IDs may be supplied externally if desired. In fact there are no restrictions on the IDs if supplied externally. The IDs need not be contiguous nor must they be unique. However, if separate features are assigned duplicate IDs and those features come into contact during a simulation, the data will be coalesced, which may or may not result in a correct simulation. If an external assignment is not desired, the feature tracking algorithm will assign a set of contiguous and unique IDs to each individual feature. This is accomplished by first sorting the identified features by the min element ID stored in each feature's data structure and assigning a number based on the sorted position. This strategy ensures a stable sorting insusceptible to different mesh partitionings.

On subsequent invocations, the feature information from the previous time step is compared against all of the features from the current time step and organized such that the best matches for all features is determined correctly. The comparison criterion is to globally minimize the centroid distances of all features simultaneously. The centroid is calculated by averaging the element centroids making up each feature. As we iterate over the new list of features, we select the feature in the previous list that is closest by centroid distance. This pairing is saved into a "best match" data structure while the remaining features are being processed.

It's possible for features to compete for the same "best match" feature on the previous time step. This indicates that a feature has been absorbed or has otherwise disappeared on the current step and that its corresponding feature from the previous step is incorrectly identifying an unrelated feature as the best match. This case is handled by marking the feature with the greater centroid distance mismatch as inactive.

When all pairs have been compared, all of the features in the best match data structure are marked ("matched") and the IDs from the previous time step are saved into the corresponding matches in the current time step. Unmatched features from both the new list and previous lists are then handled. The features in the previous list that are unmatched are marked as inactive. The unmatched features in the current list are "new", meaning that they haven't been previously identified. The former case occurs when there are exactly zero features in the current list, meaning any feature in the previous list will remain unmatched. The latter case can occur when a feature splits or when a new feature is created.

## Grain Remapping

Figure 1: Red feature bounding boxes intersecting (fast check).

Figure 2: Red feature halos intersecting (complete check).

Grain remapping is implemented using a recursive backtracking algorithm capable of performing several variable swaps to transform the improperly colored grain graph into a proper one. This backtracking algorithm runs only on the root process which is the only processor that contains the complete global grain graph. When a pair of grains are located that are in close proximity Figure 1 and Figure 2, one of them is arbitrarily chosen and designated as the "target" grain indicating that we seek to remap its defining variable values to a different solution variable. Depending on the number of neighbors a graph has and the variables representing each of those neighbors, it may or may not be possible to create a valid graph by remapping only the target grain. In this case a depth-limited, depth-first search is performed seeking a series of neighbor swaps to leave the graph in a valid state.

To begin, an array of lists of size is built and populated, where is the number of variables (colors) in use. For each variable the nearest grain represented by that variable (as determined by the bounding box distance) is located and its distance is stored in the list at the corresponding array position along with the grain ID itself. In cases where the nearest bounding boxes for a given variable overlap the target grain, we maintain a negative count representing the total number of overlaps and the ID of each grain which overlaps. Otherwise we store the closest bounding box edge to bounding box edge distance for the given variable. We don't bother to calculate or store any information for grains with matching variable indices, or for grains that live on a reserved order parameter since those variables are ineligible for remapping. If there are any empty order parameters (an order parameter representing zero grains), a distance of infinity () is entered into the corresponding position prioritizing those variables for remapping. This color distance'' array is then sorted in reverse order putting the grains furthest away near the front and leaving those with several overlaps near the back.

Figure 3: Distance check against "B" Features.

Figure 4: Distance check against "C" Features.

Figure 5: Distance check against "D" Features.

Table 1: Large Red Distances

VariableDistance
A
B-2.0
C-1.0
D-3.0

A case with all negative distances is illustrated in Table 1. In this example, the target grain is chosen as the large grain labeled , centered on the right side of the image. All of the other colors have at least one bounding box that overlaps the large grain: 2 for , 1 for , and 3 for . The empty list () is used for the variable represented by the target grain to ensure that the same variable is never considered as a possible remapping option.

Figure 6: Distance check against "A" Features.

Figure 7: Distance check against "B" Features.

Figure 8: Distance check against "D" Features.

Table 2: Small light blue distances

VariableDistance
A52.6
B4.2
C
D-1.0

We iterate over the array of distances looking for available variables suitable for remapping the target grain. If a positive value is encountered, the grain can be immediately remapped and the algorithm returns "success". If however a negative value is encountered, we must first perform a fine-level check on each of the corresponding grain halos to see if these grains actually overlap. If they do not, we can immediately remap the target grain and return "success". If we encounter a case where there is only a single truly overlapping grain (bounding boxes and halos intersect), the algorithm tentatively marks the target grain with the other grain's variable effectively simulating a remapping operation. It then recurses on the other neighboring grain making it the new target. If the algorithm is able to find a successful remap in the recursive call, the returned "success" value indicates to the caller that the tentative mark can be removed. The "success" value can then be propagated on up the call stack. If all items in the "color distance" array are exhausted without finding a successful swap or set of swaps, the algorithm returns "fail". If we are in a recursive call, the tentative mark is removed and the next value in the array is inspected. We find that limiting the depth-first search to a relatively small depth (2 or 3) works reasonably well to fail out of impossibly tightly colored graphs faster. This also helps avoid the huge runtime penalty and exponential growth rate possible with an unlimited backtracking algorithm. Note: Tentative markings are indicated by turning on the DIRTY status flag in the feature's data structure. The DIRTY status uses an independent bit so it can exist simultaneously with another status.

Figure 10: Remap to "A".

Figure 11: Remap to "C".

## 3D Halo Images

Figure 12: 6000 grains in 3D

Figure 13: grain structure after several simulation steps.

## Description and Syntax

Grain Tracker object for running reduced order parameter simulations without grain coalescence.

## Input Parameters

• variableArray of coupled variables

C++ Type:std::vector

Options:

Description:Array of coupled variables

### Required Parameters

• var_name_baseArray of coupled variables (base_name)

C++ Type:std::string

Options:

Description:Array of coupled variables (base_name)

• compute_halo_mapsFalseInstruct the Postprocessor to communicate proper halo information to all ranks

Default:False

C++ Type:bool

Options:

Description:Instruct the Postprocessor to communicate proper halo information to all ranks

• reserve_op0Indicates the number of reserved ops (variables that cannot be remapped to)

Default:0

C++ Type:unsigned short

Options:

Description:Indicates the number of reserved ops (variables that cannot be remapped to)

• tracking_step0The timestep for when we should start tracking grains

Default:0

C++ Type:int

Options:

Description:The timestep for when we should start tracking grains

• connecting_threshold0.09The threshold for which an existing feature may be extended (defaults to "threshold")

Default:0.09

C++ Type:double

Options:

Description:The threshold for which an existing feature may be extended (defaults to "threshold")

• use_less_than_threshold_comparisonTrueControls whether features are defined to be less than or greater than the threshold value.

Default:True

C++ Type:bool

Options:

Description:Controls whether features are defined to be less than or greater than the threshold value.

• error_on_grain_creationFalseTerminate with an error if a grain is created (does not include initial callback to start simulation)

Default:False

C++ Type:bool

Options:

Description:Terminate with an error if a grain is created (does not include initial callback to start simulation)

• op_numArray of coupled variables (num_name)

C++ Type:unsigned int

Options:

Description:Array of coupled variables (num_name)

• flood_entity_typeELEMENTALDetermines whether the flood algorithm runs on nodes or elements

Default:ELEMENTAL

C++ Type:MooseEnum

Options:NODAL ELEMENTAL

Description:Determines whether the flood algorithm runs on nodes or elements

• compute_var_to_feature_mapFalseInstruct the Postprocessor to compute the active vars to features map

Default:False

C++ Type:bool

Options:

Description:Instruct the Postprocessor to compute the active vars to features map

• polycrystal_ic_uoOptional: Polycrystal IC object

C++ Type:UserObjectName

Options:

Description:Optional: Polycrystal IC object

• threshold0.1The threshold value for which a new feature may be started

Default:0.1

C++ Type:double

Options:

Description:The threshold value for which a new feature may be started

• execute_onINITIAL TIMESTEP_ENDThe list of flag(s) indicating when this object should be executed, the available options include NONE, INITIAL, LINEAR, NONLINEAR, TIMESTEP_END, TIMESTEP_BEGIN, FINAL, CUSTOM.

Default:INITIAL TIMESTEP_END

C++ Type:ExecFlagEnum

Options:NONE INITIAL LINEAR NONLINEAR TIMESTEP_END TIMESTEP_BEGIN FINAL CUSTOM

Description:The list of flag(s) indicating when this object should be executed, the available options include NONE, INITIAL, LINEAR, NONLINEAR, TIMESTEP_END, TIMESTEP_BEGIN, FINAL, CUSTOM.

• boundaryThe list of boundary IDs from the mesh where this boundary condition applies

C++ Type:std::vector

Options:

Description:The list of boundary IDs from the mesh where this boundary condition applies

• halo_level2The thickness of the halo surrounding each feature.

Default:2

C++ Type:unsigned short

Options:

Description:The thickness of the halo surrounding each feature.

• enable_var_coloringTrueInstruct the Postprocessor to populate the variable index map.

Default:True

C++ Type:bool

Options:

Description:Instruct the Postprocessor to populate the variable index map.

• reserve_op_threshold0.95Threshold for locating a new feature on the reserved op variable(s)

Default:0.95

C++ Type:double

Options:

Description:Threshold for locating a new feature on the reserved op variable(s)

• remap_grainsTrueIndicates whether remapping should be done or not (default: true)

Default:True

C++ Type:bool

Options:

Description:Indicates whether remapping should be done or not (default: true)

• verbosity_level1Level 0: Silent during normal operation, Level 1: Informational messages but no detailed grain structure printouts, Level 2: Verbose output including data structure dumps, Level 3: Debugging mode.

Default:1

C++ Type:short

Options:

Description:Level 0: Silent during normal operation, Level 1: Informational messages but no detailed grain structure printouts, Level 2: Verbose output including data structure dumps, Level 3: Debugging mode.

### Optional Parameters

• enableTrueSet the enabled status of the MooseObject.

Default:True

C++ Type:bool

Options:

Description:Set the enabled status of the MooseObject.

• use_displaced_meshFalseWhether or not this object should use the displaced mesh for computation. Note that in the case this is true but no displacements are provided in the Mesh block the undisplaced mesh will still be used.

Default:False

C++ Type:bool

Options:

Description:Whether or not this object should use the displaced mesh for computation. Note that in the case this is true but no displacements are provided in the Mesh block the undisplaced mesh will still be used.

• outputsVector of output names were you would like to restrict the output of variables(s) associated with this object

C++ Type:std::vector

Options:

Description:Vector of output names were you would like to restrict the output of variables(s) associated with this object

• use_single_mapFalseDetermine whether information is tracked per coupled variable or consolidated into one (default: true)

Default:False

C++ Type:bool

Options:

Description:Determine whether information is tracked per coupled variable or consolidated into one (default: true)

• tolerate_failureFalseAllow the grain tracker to continue when it fails to find suitable grains for remapping. This will allow the simulation to continue but it will also allow non-physical grain coalesnce. DO NOT USE for production results!

Default:False

C++ Type:bool

Options:

Description:Allow the grain tracker to continue when it fails to find suitable grains for remapping. This will allow the simulation to continue but it will also allow non-physical grain coalesnce. DO NOT USE for production results!

• control_tagsAdds user-defined labels for accessing object parameters via control logic.

C++ Type:std::vector

Options:

Description:Adds user-defined labels for accessing object parameters via control logic.

• allow_duplicate_execution_on_initialFalseIn the case where this UserObject is depended upon by an initial condition, allow it to be executed twice during the initial setup (once before the IC and again after mesh adaptivity (if applicable).

Default:False

C++ Type:bool

Options:

Description:In the case where this UserObject is depended upon by an initial condition, allow it to be executed twice during the initial setup (once before the IC and again after mesh adaptivity (if applicable).

• condense_map_infoTrueDetermines whether we condense all the node values when in multimap mode (default: false)

Default:True

C++ Type:bool

Options:

Description:Determines whether we condense all the node values when in multimap mode (default: false)

• use_global_numberingTrueDetermine whether or not global numbers are used to label features on multiple maps (default: true)

Default:True

C++ Type:bool

Options:

Description:Determine whether or not global numbers are used to label features on multiple maps (default: true)

• force_preauxFalseForces the GeneralUserObject to be executed in PREAUX

Default:False

C++ Type:bool

Options:

Description:Forces the GeneralUserObject to be executed in PREAUX

• max_remap_recursion_depth6The recursion depth allowed when searching for remapping candidates. Note: Setting this value high may result in very computationally expensive searches with little benefit. (Recommended level: 6)

Default:6

C++ Type:unsigned short

Options:

Description:The recursion depth allowed when searching for remapping candidates. Note: Setting this value high may result in very computationally expensive searches with little benefit. (Recommended level: 6)