14-11-2012, 04:48 PM
Adaptive Polygon Simplification Basing on Delaunay Triangulation and its Application in High Speed PCBs and IC Packages Simulation
Adaptive Polygon Simplificatio.pdf (Size: 232.41 KB / Downloads: 15)
ABSTRACT
As modern high speed Package Circuit Boards (PCBs) and Integrated Circuit (IC) packages become more and more complicated,
the electromagnetic simulation inside the PCBs and IC packages becomes more and more difficult. The most challenge work is that
complicated multiple layer shapes inside PCBs and IC packages need very huge amount of high quality meshes for electromagnetic
simulation, which lead to huge memory requirement for solving the linear matrix. For most personal computers, that requirement
usually lead to out of memory in matrix solution. To overcome this problem without losing the simulation precision, this article
presents an algorithm to simplify complex 2-D polygons based on Delaunay triangulation. By checking the smallest angles of triangles
which contain an edge of the polygons, the algorithm simplifies polygons adaptively and updates the simplified polygons’ Delaunay
triangulation. Different from other simplifications which try to decrease the count of vertices, this algorithm tries to delete redundant
short edges, leading to greatly reduced mesh points during the process of generating the constrained and quality Delaunay
triangulation. The algorithm presented here has been applied for mesh generation for finite-element analysis of complicated PCBs and
IC packages. Test results show that the proposed algorithm can reduce more than 75% in total nodes in comparison with the approach
without simplification, resulting in significant reduction of computer resources in numerical computation.
INTRODUCTION
he finite element method (FEM) has been widely adopted
in the electromagnetic simulation of high speed Printed
Circuit Boards (PCBs) and Integrated Circuit (IC) packages,
where the 2-D structure of every layer (often described by
polygons) is discretized through constrained Delaunay
triangulation for FEM modeling. However, as modern high
speed PCBs and IC packages have more and more layout
layers and the shapes of every layer are more and more
complicated, the electromagnetic simulation inside the PCBs
and IC packages becomes more and more difficult since very
huge amount of high quality meshes are needed, which lead to
huge memory requirement for solving FEM linear matrix. On
the other hand, due to the extreme complexity of shape
structures, the original layout data of every layer may contain
a huge number of redundant short edges that will lead to
excessive number of FEM nodes when generating high quality
triangle meshes. A proper polygon simplification process that
removes those redundant edges is therefore highly desired to
reduce the consequent FEM computational resources. The
purpose of polygon simplification is to remove as many
redundant edges of polygons as possible while the changes of
shapes and the field distribution are very small.
CURRENT DISTRIBUTION SIMULATION OF PCBS AND IC
PACKAGES
One of most important factors to decide the layout design of
PCBs and IC packages is the current distribution of every
layer. Designers often hope the current distribution in layers to
be a reasonable range. Another key feature that designers are
interested is the IR drop between the voltage source and ports
in PCBs and IC packages, which can be used to design the
power supply system of PCBs and IC packages to ensure that
all components have enough voltage margins to work
correctly.
When a steady current flows in metal layout (the metal
layers of the PCBs and IC packages), the electrical potential in
the non-source region satisfies Laplace’s equation for the
scalar electrical potential[3]:
POLYGON SIMPLIFICATION APPROACH
The purpose of polygon simplification is to delete as many
redundant edges of polygons as possible without losing the
precision of shapes. In Delaunay triangulation, an edge of
polygon is called a lost edge if there is no triangle associated
with the polygon edge. On the contrary, the edge will be
called an associated edge if it is an edge of some triangle of
current Delaunay triangulation. The simplification approach in
this paper supposes that only the associated edges in Delaunay
triangulation could be deleted for simplification.
In this paper, a new polygon simplification approach was
presented based on the Delaunay triangulation results. Unlike
the previously proposed algorithms, the approach focuses on
removing edge-associated extremely low quality triangles
from the initial Delaunay triangulation. This new approach
simplifies the polygon dynamically as the Delaunay
triangulation updates, and is able to remove extremely short
edges and avoid the polygon overlapping.
APPLICATION
The polygon simplification method is successfully applied
to analyze the IR drop of complicated PCBs and IC packages
by finite element (FEM) method [3]. Results show that without
polygon simplification, some of the PCBs and IC packages
models can’t be analyzed in 32 bit machines because of out of
memory when solution. Even though recently the computers
are more and more powerful and 64 bit machines are very
common, the FEM matrices solution time will increase greatly
if the polygons are not simplified before mesh refinement.
Fig. 6(a) shows a real PCB layer with very complicated
metal shapes. Fig. 6(b) shows the refined Delaunay mesh with
polygon simplified. In the simulation, a port with a pair of
nodes is defined to calculate the resistance between the pair of
nodes, which can show the IR drop between the pair of nodes
defined by the port.
CONCLUSION
In this article, an adaptive polygon simplification based on
Delaunay triangulation was presented, which can
automatically recognize polygons’ geometric size and shapes
as well as getting an efficient simplification without losing the
simulation precision. In addition, this method can also avoid
polygons overlapping during polygon simplification. Tested
by some PCBs and IC packages models, this simplification is
especially suitable for mesh generation of large and
complicated PCBs and IC packages. It is tested that after
applied this new approach, the total FEM nodes decreased for
more than 75% for most of the PCBs and IC packages models
while their simulation results are nearly unchanged.