2.1 CAD

The conversion of the input structure, e.g. a CAD model, to obtain a meshable structure description can be a non-trivial process. It calls for a transformation of the input data to provide the mesher with more and/or different geometrical information. It will be easier to apply a solid model oriented mesher to a solid input model rather than to a boundary representation model (BREP model). On the other hand a mesh generator may require a consistent triangular boundary description which can be extracted from a BREP model in a straightforward manner. A solid model may not contain the necessary information on the boundary without calculating the intersection of the solids. The type and availability of geometrical information on the input model becomes a key issue to automate the meshing process. In the early beginnings of finite element analysis engineers had to create meshes manually exploiting their knowledge and understanding of the model's geometry [194]. Since then, more general algorithms have been introduced and activities have been geared more and more towards automation [105,169,25,19,191,56,187,151]. Often commercial CAD systems offer a large number of different algorithms which the user must utilize by finding a good selection, a good sequence, and good parameters to create and adjust a mesh interactively. Today most mesh generators claim to work automatically and to ``understand'' the geometry without human interaction. To some extent human interaction means additional geometrical information. A fully automatic mesh generator which requires very detailed input data may be less sophisticated than one that requires only a minimum of information. Two extremes can be distinguished, which both have their application:

• Exploiting as much geometrical information as possible (parts, layers ...). Possibly utilizing the same data structures as for example the CAD editor with which the model was created.
• Accepting a minimum of information like e.g. a flat data hierarchy consisting of a single list of polygons only.

Impressive looking meshes of, for example, an engine with many complicated mechanical parts, cylinders, and valves, are often easily generated because the information on each cylinder and part itself is provided. Structured grids are built for all simple parts and merged to form the entire mesh. If a single, combined surface of all parts is the only input data, the meshing process becomes unproportionally more complicated. This case has to be dealt with when the CAD model is not manually constructed using an editor, but rather derived from a simulation where the topography itself has been subject to the analysis. Such topography simulation is a common task in semiconductor process simulation.

On the other hand human interaction may provide engineering judgement. Not all geometrical tasks interfacing the design and the analysis phase are readily to be automated. A better understanding of the important balance between automation and control may save considerable computation time. Is it really necessary to mesh an entire model with all features? Or could some of the data be omitted to simplify the meshing process while still providing the desired simulation results? The input model can contain a wide variety of inconsistencies harmless for visualization purposes but crucial for any meshing algorithm. The order of the vertices in a polygon definition might not be correct or gaps in the boundary and overlapping elements might exist. In such cases one depends on powerful interactive tools to repair the problem areas [23]. A technique which is application dependent and requires the judgement of the engineer is the dimensional reduction [38] of the input model by means of the medial axis [169,3]. The medial axis or medial object is a method to detect and ``understand'' features of the geometry (Fig. 2.1). Utilizing the knowledge of these features one can perform various preprocessing steps like decomposing a complex structure into several simple ones or removing too much detail in a model (de-featuring). Such a qualitative data reduction results in a simplified model which may suffice for e.g. a stress analysis in computational mechanics. Unfortunately, the computation of the medials is very costly, because it requires the Delaunay Triangulation of a highly refined boundary.

Figure 2.1: Medial axis and medial object, M. Price et al. [124].

Figure 2.2: Thin layers in two and three dimensions with the local feature size (radius of the circles/spheres) at example locations (stars).

A definition of the common term local feature size will prove useful to theoretically formulate and grasp complex geometrical constellations.

Definition 2.1 (local feature size)   For any given location $x$ the radius of the smallest ball (volume defined by a sphere) with center $x$ that intersects two non-incident points, edges, or facets is called the local feature size $\mathcal{L}(x)$. In two dimensions the smallest ball is a smallest disk (area defined by a circle). Note that two different points can never be incident.

The continous function $\mathcal{L}(x)$ which is defined on the entire domain satisfies the inequality $\vert\mathcal{L}(x_{1})-\mathcal{L}(x_{2})\vert \leq \Vert\vec{x_{1}x_{2}}\Vert$ as proven in [135]. Intuitively $\mathcal{L}(x)$ should reflect small features of the input geometry but it should not reach arbitrarily small values for sensible inputs. In three dimensions it can therefore be advisable to slightly adjust the definition by combining incidence with visibility as described in detail in [162].