PEX ERROR: src/db/db/dbPLCTriangulation.cc,480,next_edge == 0

[jinxtopcs]

Hi Matthias @klayoutmatthias,

I found another issue with v0.30.12 triangulation which does not happen in v0.30.9.
I hope you can reproduce the error using limited information below.
Thanks in advance.

from typing import *
import klayout.db as kdb
import klayout.pex as klp


tech1 = klp.RExtractorTech()
tech2 = klp.RExtractorTech()

m1 = 10
m2 = 20
v1 = 15

for l in (m1, m2):
    m = klp.RExtractorTechConductor()
    m.layer = l
    m.resistance = 1
    m.algorithm = klp.Algorithm.SquareCounting
    tech1.add_conductor(m)
    m.algorithm = klp.Algorithm.Tesselation
    m.triangulation_max_area = 0
    m.triangulation_min_b = 0.9
    tech2.add_conductor(m)

v = klp.RExtractorTechVia()
v.cut_layer = v1
v.bottom_conductor = m1
v.top_conductor = m2
v.resistance = 1
tech1.add_via(v)
tech2.add_via(v)

points = """-2002.95900	-13656.95000
-2002.95900	-13655.14950
-2207.79100	-13655.14950
-2207.79100	-13656.14950
-3127.59850	-13656.14950
-3127.59850	-13654.14950
-2209.79100	-13654.14950
-2209.79100	-13653.14950
-2000.95900	-13653.14950
-2000.95900	-13654.95000
-1099.08400	-13654.95000
-1099.08400	-13653.14900
-950.95900	-13653.14900
-950.95900	-13654.94950
-697.23850	-13654.94950
-697.23850	-13656.94950
-952.95900	-13656.94950
-952.95900	-13655.14900
-1097.08400	-13655.14900
-1097.08400	-13656.95000"""

points = points.split("\n")
points_kdb = []
for p in points:
    x, y = p.split()
    points_kdb.append(kdb.Point(round(float(x)/0.0005), round(float(y)/0.0005)))
    
polygon = kdb.Polygon(points_kdb)
region = kdb.Region([polygon])
geo: Dict[int, kdb.Region] = {m1: region}

x1, y1 = -697.23850, -13654.94950
x2, y2 = -3127.59850, -13656.14950
port_a = kdb.Point(round(x1/0.0005),round(y1/0.0005))
port_b = kdb.Point(round(x2/0.0005),round(y2/0.0005))


vertex_ports: Dict[int, List[kdb.Point]] = { m1: [port_a, port_b] } # Use for point-based terminals
polygon_ports: Dict[int, List[kdb.Polygon]] = {}
rexer = klp.RNetExtractor(dbu=0.0005)
try:
    network = rexer.extract(tech1, geo, vertex_ports, polygon_ports)
    print(f"PEX SquareCounting PASS: {network.to_s(with_coords=True)}\n")
except Exception as e:
    print(f"PEX SquareCounting ERROR: {e}\n")

try:
    network = rexer.extract(tech2, geo, vertex_ports, polygon_ports)
    print(f"PEX Tesselation PASS: {network.to_s(with_coords=True)}\n")
except Exception as e:
    print(f"PEX Tesselation ERROR: {e}\n")


try:
    m1_delaunay = region.delaunay(max_area=0, min_b=0)
    print(f"REGION min_b=0 PASS\n")
except Exception as e:
    print(f"REGION min_b=0 ERROR: {e}\n")

try:
    m1_delaunay = region.delaunay(max_area=0, min_b=0.9)
    print(f"REGION min_b=0.9 PASS\n")
except Exception as e:
    print(f"REGION min_b=0.9 ERROR: {e}\n")

Which produces below results in v0.30.12

ERROR: src/db/db/dbPLCTriangulation.cc,480,next_edge == 0
PEX SquareCounting ERROR: Internal error: src/db/db/dbPLCTriangulation.cc:480 next_edge == 0 was not true in RNetExtractor.extract

ERROR: src/db/db/dbPLCTriangulation.cc,480,next_edge == 0
PEX Tesselation ERROR: Internal error: src/db/db/dbPLCTriangulation.cc:480 next_edge == 0 was not true in RNetExtractor.extract

ERROR: src/db/db/dbPLCTriangulation.cc,480,next_edge == 0
REGION min_b=0 ERROR: Internal error: src/db/db/dbPLCTriangulation.cc:480 next_edge == 0 was not true in Region.delaunay

ERROR: src/db/db/dbPLCTriangulation.cc,480,next_edge == 0
REGION min_b=0.9 ERROR: Internal error: src/db/db/dbPLCTriangulation.cc:480 next_edge == 0 was not true in Region.delaunay

and below results in v0.30.9

PEX SquareCounting PASS: R V0.10(-697.2385,-13654.9495;-697.2385,-13654.9495) V1.10(-3127.5985,-13656.1495;-3127.5985,-13656.1495) 1215.41

PEX Tesselation PASS: R V0.10(-697.2385,-13654.9495;-697.2385,-13654.9495) V1.10(-3127.5985,-13656.1495;-3127.5985,-13656.1495) 1213.22

REGION min_b=0 PASS

REGION min_b=0.9 PASS

[klayoutmatthias]

Sadly, you are right :(

I'll take a look.

Here is my simplified version of the reproducer:

import klayout.db as kdb

points = [
  ( -2002.95900, -13656.95000 ),
  ( -2002.95900, -13655.14950 ),
  ( -2207.79100, -13655.14950 ),
  ( -2207.79100, -13656.14950 ),
  ( -3127.59850, -13656.14950 ),
  ( -3127.59850, -13654.14950 ),
  ( -2209.79100, -13654.14950 ),
  ( -2209.79100, -13653.14950 ),
  ( -2000.95900, -13653.14950 ),
  ( -2000.95900, -13654.95000 ),
  ( -1099.08400, -13654.95000 ),
  ( -1099.08400, -13653.14900 ),
  ( -950.95900, -13653.14900 ),
  ( -950.95900, -13654.94950 ),
  ( -697.23850, -13654.94950 ),
  ( -697.23850, -13656.94950 ),
  ( -952.95900, -13656.94950 ),
  ( -952.95900, -13655.14900 ),
  ( -1097.08400, -13655.14900 ),
  ( -1097.08400, -13656.95000 )
]

polygon = kdb.CplxTrans(0.0005).inverted() * kdb.DPolygon(points)
polygon.move(kdb.Point() - polygon.bbox().p1)
print(str(polygon))

res = polygon.delaunay(0, 0)
print(str(res))

Matthias

[klayoutmatthias]

I found and fixed the issue. It was not a new problem, but got triggered by the different execution path introduced with the last fixes.

Thanks for reporting the problem.

Two notes:

1. With these geometries the tesselation extractor does not make much sense - that is the domain of the square counting extractor
2. Even with a moderate b_min value of 0.9, these geometries are triangulated by a large number of triangles (~7k) and the triangulation takes forever. Again, this is not a good geometry for refined Delaunay triangulation. With b_min of 0 the triangulation is fast, but the triangle quality is poor.

Matthias

[jinxtopcs]

Hi @klayoutmatthias,
Thank you for quickly debugging & fixing the issue !

Yes, I agree with your 1st note.
Currently, I setup the extractor based on the layer type, i.e. orthogonal layer (squarecounting extractor) and any-angle layer (tesselation extractor).
This issue indeed happens on the orthogonal layer.

But after looking at your 2nd note, it looks like I must make a trade-off between quality (refined Delaunay) and speed (standard Delaunay) when working on a long-thin line in the any-angle layer (tesselation extractor). Please correct me if I am wrong.

I think I will implement standard Delaunay (b_min 0) in the any-angle layer when refined Delaunay fails or takes too long to triangulate.

Again, appreciate your support & knowledge !