Abstract:
An exemplary embodiment providing one or more improvements includes software which is robust, efficient, and has a very fast run time for user directed grid enrichment and flow solution adaptive grid refinement. All user selectable options (e.g., the choice of functions, the choice of thresholds, etc.), other than a pre-marked cell list, can be entered on the command line. The ease of application is an asset for flow physics research and preliminary design CFD analysis where fast grid modification is often needed to deal with unanticipated development of flow details.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims priority from provisional application No. 60/943,635 filed Jun. 13, 2007. 
     
    
     ORGIN OF THE INVENTION 
       [0002]    The invention described herein was made by employees of the United States Government and may be manufactured and used by or for the Government for governmental purposes without payment of any royalties thereon or therefor. 
       BACKGROUND OF THE INVENTION 
       [0003]    1. Field of the Invention 
         [0004]    This disclosure relates to computer technology for implementing computational fluid dynamics analysis. 
         [0005]    2. Description of the Related Art 
         [0006]    Computational fluid dynamics (CFD) analysis is a complex technology involving strongly coupled non-linear partial differential equations which perform computations in a finite difference form supported by a discrete grid domain containing complex geometric shapes. 
         [0007]    CFD analysis is often applied to flows typical of aerospace systems. Such flows often are characterized by the Mach number, which may range from 0 to 25. Such flows often have high Reynolds numbers resulting in regions of laminar flow becoming turbulent flow. Boundary layers are created by flows along body and inlet surfaces. Internal flows may have adverse pressure gradients. Shock waves, accompanied by separation of the boundary layer, may be present at transonic, supersonic and hypersonic speeds. Real gas effects may become important at hypersonic Mach numbers. The geometry of the system may be complex and unsteady flow may be present. 
         [0008]    The efficacy of the CFD analysis depends on the manner of subdivision of the three-dimensional space. The numerical approximation of the Navier-Stokes equation contains errors that depend on the local density of tetrahedral subdivision and the local flow situation. Often times, deficiency of density distribution in the space is known only after the completion of a CFD analysis. Practitioners of the art have long desired to have an accurate, fast, and robust tool to modify the grid by h-refinement or some other means. However, modern computational mesh may contain more than 100 million cells. It is a monumental task for practitioners of the art to analyze both the solution and the mesh to decide where and how to perform mesh refinement efficiently within a reasonable amount of time and with a reasonable amount of effort. 
         [0009]    Another impediment to applying the h-refinement procedure for advanced CFD analysis is that the conventional method of refinement subdivides each targeted cell into eight parts. Should refinement be required again at the location of the original cell, two steps of division would result in 64 parts, an unwieldy number. To make matters worse, the rules for grid integrity would require the subdivision of neighboring cells into eight, four, or two parts at each step of h-refinement. 
         [0010]    The foregoing examples of the related art and limitations related therewith are intended to be illustrative and not exclusive. Other limitations of the related art will become apparent to those of skill in the art upon a reading of the specification and a study of the drawings. 
         [0011]    Embodiments of the present disclosure meet the long-felt need for an accurate, fast, and robust tool to modify the grid by h-refinement. 
       SUMMARY OF THE INVENTION 
       [0012]    In accordance with the present invention, a naturally occurring structure is recognized for the first time to facilitate cell subdivision into only two parts at each step. This naturally occurring structure has been termed herein a “pinwheel” and is comprised of a group of neighboring cells sharing only one common edge (as explained more fully below). At each h-refinement step, all cells in a pinwheel are partitioned each into two pas, with this partitioning occurring in preferred directions selected by the CFD practitioner. For example, the practitioner may choose directions with the highest local gradient of a flow quantity. Additionally, in accordance with the present invention, such subdivision of each pinwheel does not propagate to contiguous cells or pinwheels. This feature maintains grid integrity. Only the cells meeting desirable requirements of the CFD practitioner are divided, achieving the highest degree of functionality and having the economy of adding the least number of cells at each step. The pinwheel representation of the tetrahedral grid domain is complete and exhaustive because a pinwheel is associated with each edge, and edges are wherever a tetrahedral cell exists in the grid domain. 
         [0013]    Additionally, the present invention will permit the practitioner to break up the large cells multiple times by repeated applications of this adaptive process. 
         [0014]    Such embodiments of the present invention provide the benefit of robustness, economy of minimum cell addition, and very fast run time for user directed grid enrichment and flow solution adaptive grid refinement. 
         [0015]    The following embodiments and aspects thereof are described and illustrated in conjunction with systems, tool, and methods which are meant to be exemplary and illustrative, not limiting in scope. In various embodiments, one or more of the above-described problems have been reduced or eliminated, while other embodiments are directed to other improvements, as will be apparent to those of skill in the art upon a reading of the specification and a study of the drawings. 
         [0016]    The novel abilities and features of the embodiments of the present invention can also include placing the flow functions (e.g., flow quantity, pressure, velocity, turbulence, etc.) in the inventive code for instant access by the user, as well as allowing the user to select the function values or gradients to suit their particular applications without hindrance because the function set can contain all common CFD physical functions represented by the Navier-Stokes equation. 
         [0017]    In accordance with the present invention, innovative numerical filtering algorithms are used in embodiments of the code to relieve the practitioner of the art from the time-consuming chores of performing calculations of statistical distribution of the flow function and then setting the h-refinement threshold amongst millions of tetrahedral cells. The fast and compact algorithms that are critical to the success of the h-refinement process do not exist outside of the inventive embodiments. The present invention automatically determines the adaptation numerical threshold for the selected flow function(s). For example, the practitioner may simply request to divide a certain percentage of the eligible cells (e.g., the top five percent), and the inventive code will automatically determine the correct numerical threshold for adaptation (or division) for the chosen function(s). 
         [0018]    Embodiments of the present invention create a unique relational database for quickly identifying the edges and cells for division. The cell division process will not be efficient or robust without this unique relational database. This database recognizes a structure in the tetrahedral unstructured mesh, herein termed a “pinwheel.” 
         [0019]    In the edge selection process based on the functions selected by the practitioners of the art, only the pole-edge (as defined and explained below) will be divided if the functional value within a pinwheel exceeds the threshold for adaptation (and this pinwheel is chosen for division). As a result, all selected cells are divided into only two, not four or eight as in other known methods which do not recognize the pinwheel structure in the tetrahedrons unstructured mesh. 
         [0020]    Dividing a cell by only a factor of two has tremendous significance in practical applications of h-refinement. It allows the practitioners of the art to perform repeated adaptation without a huge increase in the final size of the computational grid, and the cells are divided only in regions where such division is warranted because the division does not propagate to the pinwheel&#39;s neighbors. 
         [0021]    In addition to the exemplary aspects and embodiments described above, further aspects and embodiments of the present invention will become apparent by reference to the drawings and by study of the following descriptions. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0022]      FIG. 1  is a flow chart of one embodiment showing the steps involved in generating the grid files for user applications. 
           [0023]      FIG. 2  is a diagrammatic depiction of a pinwheel containing seven tetrahedrons. 
           [0024]      FIG. 3  is a diagrammatic depiction of the division of an edge of a tetrahedron resulting in two new tetrahedrons. 
           [0025]      FIG. 4  is a flow chart showing the databases and tables included in step  16  in  FIG. 1 . 
           [0026]      FIG. 5  is a flow chart showing the steps included in steps  22  and  24  in  FIG. 1 . 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0027]    In embodiments of the present disclosure, the following terms have the indicated meanings. “Tetrahedral Cell” means a volume element in space bound by four vertices, six edges, and four triangular surfaces. “Tetrahedral Unstructured Grid” means a discretization of a three-dimensional volume of space in which the elementary units are tetrahedral cells. The organization of the tetrahedral cells in the grid follows a strict set of geometrical rules. “h-refinement” means a grid refinement by dividing existing cells into two, four, eight cells of the same geometric type, for example, tetrahedrons. “Pinwheel” means a feature in the tetrahedral mesh formed by all cells attached to a single edge (see  FIG. 2 ). “Pole-edge” means the common edge for all the cells in a pinwheel. 
         [0028]    Embodiments of the present invention have been written in standard Fortran-90 language. They can be complied and run on any Unix or Linux computer platform. Embodiments also can be adapted to run on a personal computer (PC) platform if desirable, or can be written in other languages, or for other platforms. Two versions of the code using different methodologies have been written to ensure reliable operation. 
         [0029]    The novel features of the present code can include a very large collection of user selectable options, a very fast execution time with run time almost linearly scalable to the number of cells in the grid by construction of a unique internal database, the utilization of the pinwheel structure for cell partition into only two parts and without propagation of cell division outside of the pinwheel, grid integrity requirements being automatically satisfied (i.e., the known rules of grid integrity); an easy to understand syntax with input on the command line; and automation of grid modification, after preliminary CFD solutions are obtained. 
         [0030]      FIG. 1  is a flow chart of one embodiment of the present invention showing the steps involved in generating the grid files for user applications. 
         [0031]    In step  10  the user begins by choosing one of the three main branches of the code for adding grid. That is to say, the user chooses to add grid either according to a given list of cells, or in prescribed spatial domains, or by adaptive addition of cells according to flow functions. The implementation of the third option, the adaptive addition of cells according to flow function, includes all the steps in  FIG. 1 . 
         [0032]    In step  12  the user indicated groups of files for grid geometry and solutions are transferred to computer memory. 
         [0033]    In step  14 , the original grid database integrity according to established rules for grid connectivity between points, edges, and cells are verified. 
         [0034]    In step  16 , innovative internal relational databases (e.g., tables) for accurate and fast execution of h-refinement according to user instructions are created. The creation, utilization, and the completeness of these internal relational databases are unique to the present invention (see  FIG. 4 , and its description below, for further details of these tables.). 
         [0035]    In step  18 , the user instructions are decoded and organized according to easy-to-use and easy-to-remember syntax. A to-do list is generated for performing the requested h-refinement. 
         [0036]    In step  20 , user requested flow variables from the five (expandable to seven or more, depending on physical composition of the fluid) primitive variables in the flow solution (however, other combinations can also be derived) are generated. Values of flow variables are associated with each cell, which are in turn transferable to edges and points in the grid. 
         [0037]    In step  22  flow variable and gradient statistics for the values of each function are calculated and set an adaptation threshold for all cells and edges. (see,  FIG. 5  and its description below, for additional details) 
         [0038]    In step  24  all the edges in the grid are examined and all edges which have functional values exceeding the threshold are marked. Within a small neighborhood of contiguous cells, the highest ranked marked edge is chosen as a “pole edge” around which a pin wheel is defined (and any other marked edges in the pinwheel are now “unmarked”). This is done repeatedly in the process until all qualified edges are exhausted (see,  FIG. 5  and its description below, for further details). 
         [0039]    In step  26  all cells with one marked edge (the pole edges) are marked for division. 
         [0040]    In step  28  each marked cell is divided by two. 
         [0041]    In step  30  a new database is created for the adapted grid and the database is checked for integrity according to the same rules as in step  14 . 
         [0042]    In step  32  the new grid is written into a set of files. 
         [0043]    In step  34  the user is provided a summary of the results, for example, the statistics of the process, a new grid, and a new solution file with data corresponding to the new grid. If desired, the user can perform repeated adaptation from step  12  to further divide cells using the new grid and the new solution. 
         [0044]    It should be noted that if in step  10  the user chooses to add grid either according to a given list of cells, or in prescribed spatial domains (rather than by adaptive addition of cells according to flow functions) then only steps  10 ,  12 ,  16 ,  30 ,  32  and  34  would apply. 
         [0045]      FIG. 2  is a diagrammatic depiction of a pinwheel containing seven tetrahedron cells. The tetrahedrons represented are described by the lettered points; ABCD, ABDE, ABEF,ABFG, ABGH, ABHK, and ABKC. Division of the edge AB by midpoint M results in the division of each tetrahedron into two tetrahedrons. 
         [0046]      FIG. 3  is a diagrammatic depiction of the division of an edge of a tetrahedron cell resulting in two new tetrahedron cells. Edge AB is divided into by mid-point M. The original tetrahedron ABCD is thereby divided into smaller tetrahedrons AMCD and MBCD. 
         [0047]      FIG. 4  is a flow chart showing the databases and tables included in step  16  in  FIG. 1 . These four tables are linearly scalable and form the core of the internal high-speed search engine. In the original grid file, point and cell identities are sequential numbers determined as parts of the original grid generation process. In the embodiments of this software, each edge is given a unique identity number. Three tables are created to represent a complete relational databases to link points to edges, edges to cells, cells to edges, and edges to points 
         [0048]    Box  162  entitled Cell-to-Points is a table of the original grid files. 
         [0049]    Box  164  entitled Point-Pairs-to-Edge is a database arranged in sequential order. Each cell has six edges, and each edge has two end points. Each edge has a higher and a lower end-point identification number. The sequential order arrangement uses the higher number first, and then the lower number. In a first pass of the edge identification process, the embodiments count the numbers of edges having the same higher point number, and assigns sufficient space to accommodate all such edges in the edge table. In a second pass, all edges with the same high identification number are placed as a group within the assigned space in order of appearance into the table, the table item number for each edge becomes the unique identification number of each edge. 
         [0050]    Box  166  entitled Edges-to-Cell is a table which allows quick search of pinwheels by the process of two steps. The first step creates a list of cell identification numbers in which all cell identifications related to a given edge are placed contiguously in the list. The second step creates a table of location keys and the number of attached cells for each edge. When the inventive code selects an edge and then needs to know all of the cells attached to it, the table can instantly provide the location of the cell group and provide all the cell identification numbers related to this edge. 
         [0051]    Box  168  entitled Cells-to-Edges identifies the six edges of each cell which allows quick processing. The cells-to-edges table is novel to the disclosed inventive process. This new table, arranged in the order of the cell identity numbers, provides the identities of the six edges of each cell. The cell-to-edges-table facilitates instant access whenever the grid adaptation process requires such information for a cell. The four tables (cells-to-point, point-pairs-to-edges, edges-to-cells, and cells-to-edges) utilized together is a novel feature for providing a complete roadmap for the present invention. 
         [0052]      FIG. 5  is a flow chart showing the substeps included in steps  22  and  24  in  FIG. 1 . Within step  22  the following substeps are performed: in substep  220 , the practioner chooses one or more desired function that he or she wishes to analyze, for example, pressure, velocity, turbulence, etc; in substep  222  hundreds of numerical bins are assigned to each function, between the maximum and minimum value of each function; in substep  224  the code calculates a function value for each edge and assigns each edge to the corresponding bin. The process proceeds by scanning through all the bins and counting the number of occurrences for the function value(s) belonging to each bin. A threshold is set to select, in accordance with specifications by the user of this software, a percentage of the total number of edges that bear significant function values (e.g., excluding constant values in regions representing by background flow properties, and other similar situations) In subset  226 , the inventive code determines the bins that contain edges that are above the threshold value and confers a rank on the edges, for example, between 1 through 16 according to how much the edge values have exceeded the threshold. 
         [0053]    Substeps  224  and  226  are repeated through all the functions selected by the users in each application of this software. When an edge is qualified for adaptation under more than one function, the higher ranking amongst all qualifying functions is given to this edge. 
         [0054]    Within step  24  the following substeps are performed: in substep  242  all edges selected for adaptation are marked in the grid; in subset  244 , from a small neighborhood of contiguous cells the highest ranked marked edge is chosen as a “pole edge” around which a pinwheel is defined. This is done repeatedly in the process until all qualified edges in the entire grid are exhausted. In substep  246  only one highest ranking edge (the “pole edge”) in each pinwheel is retained as marked for cell division, i.e., any other marked edge in a pinwheel is no longer “marked.” 
         [0055]    While a number of exemplary aspects and embodiments have been discussed above, those of skill in the art will recognize certain modifications, permutations, additions, and sub-combinations thereof. It is therefore intended that the following appended claims and claims hereafter introduced are interpreted to include all such modifications, permutations, additions, and sub-combinations as are within their true spirit and scope.