next up previous contents
Next: D. From Boltzmann Distribution Up: Dissertation Rainer Minixhofer Previous: B.4 Electron Beam Exposure


C. General Algorithm for Polygon-Biasing

The situation for biasing a polygon is sketched in Figure C.1. A polygon is defined as a sequence of points which are given in a counterclockwise order by oriented segments (vectors). A general algorithm to calculate a new ``shrinked'' or ``grown'' polygon based on shifting its segments parallel by a certain amount (the bias) has to be applied. This shift is equivalent to the movement of the points of the polygon by a normal vector $ \vec{e}_n$ calculated from the normal vectors of the two segments $ g_{12}$ and $ g_{23}$ times the bias.
This algorithm is only valid for convex polygons. For concave polygons (polygons where at least one point has an internal angle $ >180^\circ$) this algorithm may fail because of point collisions or generation of loops. However, for small bias and suitable geometries the following simple algorithm is applicable.

Figure C.1: Geometrical situation when biasing a polygon with a given distance
\begin{figure}\begin{center}
\par
\input{figures/polygon_biasing.pstex_t}
\par\end{center}\end{figure}

The line segment $ \vec{g}$ can be described by the general parametric line equation:

$\displaystyle A x+B y+C = 0$ (C.1)

Furthermore, the normal vector $ \vec{e}_n$ is given by

$\displaystyle \vec{e}_n = A \vec{x}_n + B \vec{y}_n$ (C.2)

and thus the second equation

$\displaystyle A^2 + B^2 = 1$ (C.3)

must be fulfilled too. Substituting the start and end coordinates of the vector $ \vec{g}_{12}$, $ P_1=(x_1,y_1)$ and $ P_2=(x_2,y_2)$ into (C.1) and (C.3) gives three equations which have to be solved to get the parameters $ A,B$ of the line segment.

$\displaystyle C + A x_1 + B y_1 = 0$ (C.4)
$\displaystyle C + A x_2 + B y_2 = 0$ (C.5)
$\displaystyle A^2 + B^2 = 1$ (C.6)

with the solutions

$\displaystyle A = \pm \frac{\vert x_1-x_2\vert (y_2-y_1)}{(x_1-x_2)\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}$ (C.7)
$\displaystyle B = \pm \frac{\vert x_1-x_2\vert}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}$ (C.8)

Per definition the normal vector $ \vec{e}_n$ is positive if the line segment $ \vec{g}$ is rotated $ 90^\circ$ counterclockwise into the normal vector. This means

$\displaystyle \frac{\vec{g} \times \vec{e}_n}{\vert\vec{g}\vert} > 0 \Rightarro...
...end{array} \right) > \left( \begin{array}{c} 0  0  0  \end{array} \right)$ (C.9)

which yields the criteria

$\displaystyle B \frac{x_2 - x_1}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}} - A \frac{y_2 - y_1}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}} > 0$ (C.10)

The relation (C.11) is only fulfilled with the solution

$\displaystyle A = -\frac{y_2-y_1}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}$ (C.11)
$\displaystyle B = \frac{x_2-x_1}{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}$ (C.12)

of the (C.8),(C.9). To determine the vector by which each point is shifted during biasing (by the distance d), the two line segments $ \vec{g}_{12}$ and $ \vec{g}_{23}$ attached to the point are moved parallel and thus form the new intersection point $ P'_2$. The normal vectors remain the same, but the parameters $ C$ of the general line equations change accordingly to the parallel shift. The initial intersection point $ P_2=(x_2,y_2)$ is moved by the vector $ \Delta\vec{x}_2$ to the point $ P'_2=(x'_2,y'_2)$ (see Figure C.1). The parameters $ C_{12},C_{23}$ of the shifted line equations are calculated from their respective line equations and the unchanged line parameters $ A_{12},A_{23},B_{12},B_{23}$.

$\displaystyle C_{12}=-(A_{12} x +B_{12} y + A^2_{12} d + B^2_{12})$ (C.13)
$\displaystyle C_{23}=-(A_{23} x +B_{23} y + A^2_{23} d + B^2_{23})$ (C.14)

The new intersection point $ P'_2=(x'_2,y'_2)$ must satisfy both line equations and thus by solving the equations the new intersection point coordinates yield

$\displaystyle x'_2=\frac{\left( A_{23}^2 B_{12} - \left( A_{12}^2 + B_{12} \lef...
... - B_{23} \right) \right) B_{23} \right) d} {A_{23}B_{12} - A_{12}B_{23}} + x_2$ (C.15)
$\displaystyle y'_2=\frac{\left( {A_{12}}^2A_{23} + A_{23} {B_{12}}^2 - A_{12}\...
..._{23}}^2 + {B_{23}}^2 \right) \right) d} {A_{23} B_{12} - A_{12} B_{23}} + y_2$ (C.16)

Substituting (C.12),(C.13) in (C.17),(C.18) and using the substitutions $ g_{12}=\vert\vec{g}_{12}\vert$, $ g_{23}=\vert\vec{g}_{23}\vert$, $ \Delta
x_{21}=x_2-x_1$, $ \Delta x_{32}=x_3-x_2$, $ \Delta y_{21}=y_2-y_1$ and $ \Delta y_{32}=y_3-y_2$ gives finally

$\displaystyle x'_2=\frac{d\left( -g_{23} \Delta x_{21} + g_{12} \Delta x_{32} \right) } {-x_3 \Delta y_{21} - x_1 \Delta y_{32} + x_2 \Delta y_{31} } + x_2$ (C.17)
$\displaystyle y'_2=\frac{d\left( -g_{23} \Delta y_{21} + g_{12} \Delta y_{32} \right) } {-x_3 \Delta y_{21} - x_1 \Delta y_{32} + x_2 \Delta y_{31} } + y_2$ (C.18)


next up previous contents
Next: D. From Boltzmann Distribution Up: Dissertation Rainer Minixhofer Previous: B.4 Electron Beam Exposure

R. Minixhofer: Integrating Technology Simulation into the Semiconductor Manufacturing Environment