Patent ID: 8584060

Claim:
A method comprising: a first step of providing design shapes for a design level, said design shapes including first-type edges and second-type edges having different directions; a second step of identifying inner vertices of said design shapes; a third step of pairing a subset of said inner vertices having common coordinate values; a fourth step of determining if any unmatched inner vertex is present after all inner vertices that can be paired based on common coordinate values are paired, and if present, assigning a virtual vertex for each unmatched inner vertex; a fifth step of identifying each outer vertex as a first-type vertex or a second-type vertex based on presence or absence of a shared edge with said inner vertices and said at least one assigned virtual vertex, and based on whether said shared edge is a first-type edge or a second-type edge; a sixth step of generating first mask level shapes for a first mask level, wherein said first mask level shapes touch said first-type vertices; a seventh step of generating second mask level shapes for a second mask level, wherein said second mask level shapes touch said second-type vertices; and an eighth step of generating cut mask level shapes, wherein said cut mask level shapes touch each first-type edges that are not over said second mask level shapes and touch each second-type edges that are not over said first mask level shapes, wherein at least one step among said second, third, fourth, fifth, sixth, seventh, and eighth steps is performed employing an apparatus comprising one or more processors in communication with a memory and configured to perform said at least one step.