Algorithm Overview

Jump to section:

• Merging polygons
• Parallelization
• Polygon simplification
• Biasing algorithms
• Grid Fracturing
• Vertex bias direction
• Biasing algorithms
• Filtering Conditions
• Interpolation
• Bias Delta Equation
• Debug Mode

Merging polygons

We first convert all the GdsBoundary elements into polygons. Note that those polygons might have unwanted fracture lines in them, as GDS files don't support polygons with holes:

Fracture lines are not desirable as they are basically virtual edges, which, when biased, will introduce actual gaps in the geometry.

We therefore need to merge the GdsBoundary elements as they are in the GDS into Polygons, possibly containing holes. Any touching polygons will be merged together into a bigger polygon and all undesirable fracture lines will disappear.

Parallelization

Most GDS layers that will be biased will contain many polygons to bias. The algorithm is parallelized over the available polygons in the layer.

This works, as we already merged all touching polygons together, so any bias that needs to be applied to a certain point will guaranteed be coming from an 'opposite' point on the same polygon.

Polygon simplification

To avoid having to bias too many vertices, each polygon is simplified using the Ramer-Douglas-Peucker algorithm.

Grid fracturing

We fracture a copy of the polygon on a grid. This fractured polygon will be used to find the paired edge which determines the distance to be biased. Fracturing the grid in advance allows us to only consider edges in the vicinity of the current point as 'opposites'. Note that it is still the original polygon that is biased! We're only using the fractured polygon to reduce the search space to find opposite edges.

In this step we're basically instantiating a grid which stores the centers of the grid cells and the edge crossing locations. We then use that information to fracture the polygon on a grid, as can be seen in the image below:

The goal will now be to iterate over each point in the original non-fractured polygon. By using the location of the point to bias we can select the grid-cell to which the current point belongs. Assuming that each grid cell is bigger than the minimum to-bias distance we'll know for sure that any opposite edge should be in the current grid cell or one of its neighbors.

Vertex bias direction

For each polygon we iterate over each vertex in its boundary (outer boundary and possible hole boundaries too). We're also keeping track of the neighboring vertices.

For each of those vertices, we will try to find the closest edge on the opposite side of the polygon. We'll recognize multiple cases that require a slightly different way of biasing, depending on which angle we're seeing around the current point.

Let's now have a look at the angle

$$\theta \in \left[ 0, 2\pi \right)$$

between the incoming edge and the outgoing edge at the current point to bias. We can split it up into 5 distinct angle regions:

1. θ < 90°: We're looking at a concave position in the polygon: the to-bias region is outside of a V-like shape. Such a point should probably not be biased as the bias direction would be too parallel with both the incoming and outgoing edge. Moreover, sharp angles should probably not be present in our GDS anyway. .

2. θ ≈ 90°: We're looking at a concave right angle in the polygon. The problem with such a point is that it effectively belongs to two perpendicular edges. The approach used here is to calculate the bias delta for the incoming edge and the bias delta for the outgoing edge and select the largest resulting bias delta.

   Info

   -r is the CLI flag to change the 'right angle tolerance', i.e. the amount of deviation from 90° to consider an angle still to be a right angle.

   

3. 90°<θ<270°: This is the most common case: we're looking at a (quasi) straight edge, where (at least locally) the incoming angle is approximately equal to the outgoing angle. We'll look for another edge with a certain viewing cone leaving from the point to bias.

   Info

   -v is the CLI flag to change the viewing angle

4. θ≈270°: This convex right angle case needs special care as it's a common termination in components like in MMIs. We can discern two cases: a U-like shape and a Z-like shape. We'll want to bias the U-like shape as it has two parallel edges, but Z-like shapes we'll need to leave alone:

   This is a U-like shape common in mmis: the two edges need to come closer together.

   This is a Z-like shape: the (circled in blue) point should (probably) not be biased as the next edge does not fold back.

5. 270°<θ<360°: This is again a sharp angle and should probably not be present in the GDS, hence we will not bias it .

   

Biasing algorithms

Since we're ignoring both concave and convex sharp-angle cases and since the θ≈90° relies on having two edge-biasing steps, we can basically discern two independent biasing algorithms:

1. Edge bias: used for 99% of all points to bias
2. Convex right angle bias: used in very specific cases (U-like terminations)

Let's go a bit deeper in both those algorithms...

1. Edge Bias

• For each point on the unfractured polygon, find the grid cell to which the point belongs in the fractured polygon together with all the neigboring cells.
• Get all edges from the polygons in the current grid cell and the 8 neighboring grid cells: those are the candidate 'receiver' edges.
• Iterate over all found edges.
• Find the closest point on the current edge being considered with respect to the current point being biased. Note that we considerably reduced the number of edges to check for by fracturing our polygon on a grid.
• Check the filtering conditions for the opposite point we found. If the opposite point passes all the filtering conditions it means that the opposite point we found is currently the best option to bias towards. We save the point.
• Once we went through all the possible opposite line segments. Use the distance between the vertex being biased and the best opposite point we found to calculate the bias delta.
• Move the point by the calculated bias delta amount in the direction of the opposite point.

2. Convex right angle Bias

When we're at a convex right angle we'll need to have a different approach as we might wwant to bias along the edge, which is impossible in the normal edge-bias algorithm as we limit ourselves to a certain viewing cone.

We therefore look at the next point on the line string, which by definition will be in the perpendicular direction compared to the edge made by the previous point and the current point. We look at what bias this point would give.

Then we do the opposite: we look at the previous point on the line string, which by definition will be in the perpendicular direction compared to the edge made by the next point and the current point. We look at what bias this point would give.

Then we select the point with the largest bias and bias in that direction.

Filtering Conditions

An 'opposite' point will be considered invalid when one of the following checks fails.

1. The distance to the 'opposite' point is zero: the 'opposite' point is the same point as the point being biased, hence invalid.
2. The distance to the opposite point is larger than the minimum distance we've found so far: the 'opposite' point is farther away and will result in less bias then what we've found so far, hence irrelevant.
3. The 'opposite' point is a point on one of the virtual edges of the grid we just created: virtual edges are not real and should not be considered, hence invalid.
4. The line from the current point to the opposite point is not in the viewing cone of the current point: invalid.
5. The line from the opposite point to the current point is not in the viewing angle of the opposite point: invalid.
6. The line from the current point to the opposite point crosses a polygon hole ore more generally leaves the current polygon being considered: invalid.

Interpolation

This is almost the complete story, but we forgot one thing: edge interpolation.

Sometimes we'll have very long straight edges which still need a different bias compared to where on the edge you are. Consider for example the following cellure:

With the currently described biasing algorithm only the currently present vertices will be biased:

However, the bottom edge should also be biased towards the removed half circle. To be able to do this we need to enable interpolation.

This looks more like it.

Bias Delta Equation

Each edge gets the following polynomial bias:

$$ \Delta = c_0 + c_1 x + c_2 x^2 + ... c_n x^n $$

The bias describes how the thickness of a polygon gets reduced, hence each biased vertex of a polygon gets moved in the direction of the opposite edge by half that amount.

Debug Mode

When running vbias in debug mode, we will keep track of debug elements. Debug elements are annotations which will be patched into the GDS Cell on save. This gives an insight in how a vertex was classified and biased. Have a look at the following y-splitter image:

What we're seeing here is black lines connecting the original point with its original 'opposite' pair edge. The cyan line heads signify how the original point was moved.

Further to the right of the gds, we can see angle annotations:

As we discussed here, sometimes the angle around a certain point determines how the point will be biased.