Interval Assignment for Volumes with Holes

2nd Symposium on Trends in Unstructured Mesh Generation, University of Colorado, Boulder, August 1999

MESHING
RESEARCH
CORNER

Jason Shepherd and Steven Benzley
Civil and Environmental Engineering Department, Brigham Young University, Provo, UT 89604
shepjas@et.byu.edu

Scott Mitchell
Parallel Computing Sciences Department, Sandia National Laboratories, Albuquerque, NM 87185

Abstract
Surface meshing algorithms require certain relationships between the number of mesh edges (intervals) on the curves bounding a surface. For example, mapping requires that the number of intervals on opposite sets of curves be equal. Assigning the number of intervals to all of the curves in the model such that all relationships are satisfied is called interval assignment. Volume meshing algorithms also require certain relationships between numbers of intervals that are not always captured by the surface meshing requirements. For example, sweeping a cylindrical shell requires that the numbers of intervals between the top and bottom annuluses are the same for the inner and outer cylinder walls.

This paper presents a new technique for automatically identifying volume constraints. Volume constraints are grouped with surface constraints and are solved simultaneously. This technique reduces the amount of user time required to mesh models composed of sweepable volumes with holes; previously a user often had to manually identify constraints and set intervals before these volumes would successfully mesh.

A sweepable volume has source, target, and linking surfaces. Each maximal edge-connected set of linking surfaces defines a blind-hole, a through-hole, or the outer shell of the volume. Note the outer shell is topologically equivalent to a through-hole. Within a linking set, nothing special needs to be done for the volume because the numbers of intervals between source and target surfaces are already favorably constrained by the surface mapping constraints. However, between two linking sets the numbers of intervals need to be explicitly constrained for the volume.

The algorithm described in this paper uses graph algorithms to identify linking sets, and determine if they correspond to through-holes or blind-holes. For blind-holes, the algorithm generates constraints that prevent the hole from being too deep in interval parameter space and penetrating opposite target surfaces. Each source/target surface has a variable representing its level in the sweep. For each linking set, the adjoining source and target surfaces are partially ordered by the structure of the linking set. Representative chains of curves capture this partial ordering; the level of a surface at the end of a chain must be equal to the level of the surface at the beginning of the chain plus the number of intervals assigned to the chain. We find a small set of representative paths for each linking set; all source/targets pairs do not generate a path. The representative paths for all linking sets are gathered and distilled by Gaussian elimination into a small set of constraints.

Interval assignment has other considerations besides meshing scheme constraints: a user sets the number of intervals on individual curves, and designates them as hard-set (cannot be modified) or soft-set (merely a goal). Note that in some cases there is no interval assignment solution. The interval assignment constraints and goals are solved by a series of (integer) linear programs. The resulting numbers of intervals are assigned to each curve in the model, and subsequently meshing the surfaces and volumes will not change these numbers.