D I S S E R T A T I O N

Mesh Generation for Technology CAD
in Three Dimensions

ausgeführt zum Zwecke der Erlangung des akademischen Grades
eines Doktors der technischen Wissenschaften

eingereicht an der Technischen Universität Wien
Fakultät für Elektrotechnik
von

Peter Fleischmann

Goldschlagstraße 78/22
Wien XV.
Matrikelnummer 8725344
geboren am 1. Juni 1969 in Kabul

Wien, im Dezember 1999

• Abstract
• Kurzfassung
• Acknowledgement
• Contents
• 1. Introduction
  • 1.1 Outline of the Thesis
  • 1.2 Terminology
• 2. Challenge and Demands
  • 2.1 CAD
  • 2.2 Semiconductor Process and Device Simulation
  • 2.3 State of the Art
• 3. Mesh Generation
  • 3.1 Geometrical Mesh Quality
  • 3.2 Finite Volumes and Finite Elements
    • 3.2.1 Requirements for Finite Volume Meshes
    • 3.2.2 Requirements for Finite Element Meshes
    • 3.2.3 Simple, Distinctive Mesh Examples
  • 3.3 Control Space
  • 3.4 Local Adaptation
    • 3.4.1 Moving Boundaries
    • 3.4.2 Hierarchical Meshes
    • 3.4.3 Bisection and Projection
    • 3.4.4 Red-Green Refinement
    • 3.4.5 Full Freedom Point Insertion and Removal
    • 3.4.6 Mesh Smoothing
    • 3.4.7 Local Transformations
  • 3.5 Surface Mesh
    • 3.5.1 Surface Extraction From Cellular Data
    • 3.5.2 Surface Coarsening, Data Reduction
    • 3.5.3 Surface Smoothing
  • 3.6 Point Placement
• 4. Methodologies
  • 4.1 Structured Grid Generation
    • 4.1.1 Algebraic Method
    • 4.1.2 PDE Method
  • 4.2 Product Methods
    • 4.2.1 Layer-Based Method
  • 4.3 Cartesian and Octree Methods
  • 4.4 Advancing Front Methods
  • 4.5 Delaunay Methods
• 5. Delaunay Triangulation
  • 5.1 Tetrahedralization of a Point Set
  • 5.2 Definition and Delaunay Properties
  • 5.3 Algorithms for Constructing a Delaunay Triangulation
    • 5.3.1 Divide-and-Conquer
    • 5.3.2 Sweepline
    • 5.3.3 Incremental Construction
    • 5.3.4 Incremental Search
    • 5.3.5 Convex Hull
  • 5.4 Non-Uniqueness
  • 5.5 Boundary Integrity
    • 5.5.1 Constrained Delaunay Triangulation
    • 5.5.2 Conforming Delaunay Triangulation
  • 5.6 Steiner Points and Steiner Triangulation
  • 5.7 Delaunay Slivers
• 6. Architecture and Implementation
  • 6.1 Meshing Strategy and Overall Concept
  • 6.2 Initial Point Generation
  • 6.3 Surface Triangulation
  • 6.4 Volume Tetrahedralization
    • 6.4.1 Algorithm Overview
    • 6.4.2 Point Location
    • 6.4.3 Degenerate Point Sets
      • 6.4.3.1 Cospherical Point Sets
      • 6.4.3.2 Cocircular Point Sets
  • 6.5 Local Adaptation
• 7. Examples
  • 7.1 CAD
  • 7.2 Interconnects
  • 7.3 Chemical Vapor Deposition and Reaction Kinetics
  • 7.4 NMOS Transistor
  • 7.5 CMOS Inverter
• 8. Outlook
• Bibliography
• List of Figures
• Publications
• About this document ...