Geometry Decomposition

Automatic decomposition has been researched and tools have been developed which have met with some limited success [Lu,99 , Staten,05]. Automatic decomposition requires complex feature detection and sub-division algorithms. The decomposition problem is at least on the same order of difficulty as the auto-hex meshing problem. Fully automatic methods for quality hexahedral meshing have been under research and development for many years [Blacker,93 , Folwell,98 , Price,95]. However, a method that can reliably generate hexahedral meshes for arbitrary volumes, without user intervention and that will build meshes of an equivalent quality to mapping and sweeping techniques, has yet to be realized. Although fully automatic techniques continue to progress [Staten,06], the objective of the proposed environment is to reduce the amount of user intervention required while utilizing the tried and true mapping and sweeping techniques as its underlying meshing engine.

Instead of trying to solve the all-hex meshing problem automatically, the ITEM approach to this problem is to maintain user interaction. The ITEM algorithms determine possible decompositions and suggest these to the user. The user can then make the decision as to whether a particular cut is actually useful. This process helps guide new users by demonstrating the types of decompositions that may be useful. It also aids experienced users by reducing the amount of time required to set up decomposition commands.

Diagnostics: The current diagnostic for determining whether a volume is mappable or sweepable is based upon the autoscheme tool described in [White,00]. Given a volume, the autoscheme tool will determine if the topology will admit a mapping, sub-mapping or sweeping meshing scheme. For volumes where a scheme cannot be adequately determined, a set of decomposition solutions are generated and presented to the user.

Solutions: The current algorithm for determining possible cut locations is based on the algorithm outlined in [Lu,99] and is described here for clarity:

• Find all curves that form a dihedral angle less than an input value (currently 135)
• Build a graph of these curves to determine connectivity
• Find all curves that form closed loops
• For each closed loop:
• • Find the surfaces that bound the closed loop
  • Save the surface
  • Remove the curves in the closed loop from the processing list
• For each remaining curve:
• • Find the open loops that terminates at a boundary
  • For each open loop:
  • • Find the surfaces that bound the open loop
    • Save the surfaces
• For each saved surface:
• • Create an extension of the surface
  • Present the extended surface to the user as a possible decomposition location.

This relatively simple algorithm detects many cases that are useful in decomposing a volume. Future work will include determining symmetry, sweep, and cylindrical core decompositions. These additional decomposition options should increase the likelihood of properly decomposing a volume for hexahedral meshing.

Figure 1 shows an example scenario for using this tool. The simple model at the top is analyzed using the above algorithm. This results in several different solutions being offered to the user, three of which are illustrated here. As each of the options is selected, the extended cutting surface is displayed providing rapid feedback to the user as to the utility of the given option. Note that all solutions may not result in a volume that is closer to being successfully hex-meshed. Instead the system relies on some user understanding of the topology required for sweeping.

Each time a decomposition solution is selected and performed, additional volumes may be added, which will in turn be analyzed by the autoscheme diagnostic tool. This interactive process continues until the volume is successfully decomposed into a set of volumes which are recognized as either mappable or sweepable.

Figure 1. ITEM decomposition tool shows 3 of the several solutions generated that can be selected to decompose the model for hex meshing