Internal error in Region::delaunay()

[martinjankoehler]

@klayoutmatthias
I noticed this while debugging the devel branch, but can also reproduce it with PyPi's klayout-0.29.11-cp312-cp312-macosx_11_0_arm64.whl

Steps to reproduce

import klayout.db as kdb
r = kdb.Region(kdb.Polygon([kdb.Point(-8000, -8075), kdb.Point(-8000, 8075), kdb.Point(18000, 8075), kdb.Point(18000, -8075)]))
r.delaunay(50, 0.5)

which yields the error

ERROR: src/db/db/dbTriangle.cc,450,fabs (s) > db::epsilon
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: Internal error: src/db/db/dbTriangle.cc:450 fabs (s) > db::epsilon was not true in Region.delaunay

[klayoutmatthias]

Hi @martinjankoehler,

this usually happens if the triangulation becomes too complex and there is no solution that satisfies the criteria.

Basically, the max area is given in square database units. If the DBU is 1nm, then 50 corresponds to 50nm² which is mighty small given the polygon dimension which is more like 100µm².

Is that actually intended?

Matthias

[martinjankoehler]

Hm, it's not really necessary for my use case, it just happened because the larger "substrate plane" Region got accidentally triangulated, with the default delaunay parameters in place.

I had just thought the function should

• either always give a solution,
• or at least throw a user-targeted exception message (instead of an internal error), as it's the user's error to have such bad scaling

But I should add separate delaunay arguments anyway for resistance use case
(in addition to the parameters for the FasterCap geometry use case).

[klayoutmatthias]

Hi Martin,

we're right of course.

I have not debugged the problem in detail, but I think, you enter numerical issues when the triangles become too small. Problem is that triangle corners are on integer coordinates (multiples of database units). The triangulation algorithm is based on splitting of triangles. Maybe in some cases, this renders invalid (degenerated or inverted) triangles due to rounding.

It is probably possible to capture these cases, but I think in the end the algorithm itself also becomes unstable when there is not enough accuracy reserve. In the worst case, it may not terminate.

I your case, the limit is somewhere around amax = 10500, which renders like 60k triangles. Looks like that is a practical number as a rule of thumb, and defines a kind of accuracy reserve that is needed for stability of the algorithm.

Matthias

[klayoutmatthias]

I think I found some solution for the issue - see the branch under "Development".

The specific example works now, but takes several minutes with a peak memory allocation of about 6G and produces 13M triangles.

Interestingly the triangulation has domains with local order

in other places it looks more Penrose-style

Matthias