Test Report: LayoutView::create_measure_ruler( const DPoint point, int ac = ... )

[Kazzz-S]

This is a test report on the new feature LayoutView::create_measure_ruler().

The attached ZIP file T-341.zip contains the three major files listed in the table below.

Srl. No.	File Name	Contents
1	AutoMeasure-01-Points.oas	Test design in OASIS with 1871 seed points as boxes in L:D=5002:10
2	AutoMeasure-01-Points.lys	Session file to reproduce the generated rulers
3	DBFlags-AutoMeasure-01-Points.lyrdb	Shape DB file to visit each ruler

Notes:
(1) box centers are located on 5mm x 5mm Manhattan grids by a different tool.

A. How my PYA works (outline)

1. Open the OASIS
2. Collect the box shapes in L:D=5002:10 and make a list of center points ==> [seeds]
3. Hide the layer L:D=5002:1
4. For each seed in [seeds], call LayoutView::create_measure_ruler(seed)

B. Performance

• KLayout = 0.25.9 with LayoutView::create_measure_ruler() enabled
• System = MacOS 10.10.5 Yosemite; Core-i7, 2.9 GHz; 16 GB memory
• Implementation = PYA (Python 3.7.4 / Anaconda3)
• User time = 17.8 sec; fast enough for my application :-)

C. Observations

I have visited ALL the 1871 rulers with the help of "Shapes To Markers" tool (4-hour job!).
Out of those 1871 rulers, 110 are not as expected, which can be categorized into four types.
More details are given in the table below.

Type	Frequency	Flag in the Shape DB	Mode "in other words"
1	89	Red	p1(MyOutside) ---> p2(NeighborOutside) "not-width-but-space"
2	17	Green	p1(MyInside) ---> p2(NeighborOutside) "penetrating myself"
3	3	Blue	p1(MyOutside) ---> p2(2ndNeighborOutside) "leaping the neighbor"
4	1	Yellow	p1(MyInside) ---> p2(MyInside) "going in a wrong direction"

2019/09/03: Added a bookmark file for the 110 sites mentioned above. BM-110seeds-RGBY-flags.zip

For each type, a typical image is attached below.

(Type-1)

(Type-2)

(Type-3)

(Type-4)

D. Workaround and discussions

For those problematic seeds, I have noticed that if I move such a seed box nearby and rerun the PYA I can get an expected result in some cases. This is the reason behind the Feature Request (#342).
I believe this feature is useful not only for analyzing these issues but also for adjusting the seed points interactively. Because the initial locations of seed boxes are artificially determined to generate "many sampling points" in one shot and therefore some locations are not suitable, where manual position adjustment is required.

[End]

Thanks.
Kazzz

[Kazzz-S]

Hi @klayoutmatthias,

A simple test report is up.
Please get back to me if you need any clarification.

With warm regards,
Kazzz

[klayoutmatthias]

Hi Kazzz,

thanks a lot for these examples and testcases.

I need to say that the measurement feature has mainly been developed for manhattan geometries. The basic working principle is this:

• From the seed point, look for the nearest edge facing towards the seed
• create a measurement line perpendicular to this edge and passing through the seed
• determine the closest cut point of this line with any other edge

I guess the main issue is caused by the definition of "facing towards the starting point". A failure here might explain some of your observations.

I think that a modification of the algorithm is possible, although it will rather be a rewrite. I just wonder what's a good definition of distance

Best regards,

Matthias

[klayoutmatthias]

Hi Kazzz,

thanks again this great testcase.

I managed to enhance the implementation somewhat and don't find any more of the "rogue" rulers. Please see the tip of the issue-342 branch.

Still, when the measurement point is close to the pinch step, it will pick a vertex from this step and run a measurement against this. Like here:

I'm afraid this is mainly due to the restricted measurement algorithm. When the point is inside a parallel region, the rulers are nicely set:

Best regards,

Matthias

[Kazzz-S]

Hi Matthias,

Thank you very much for your prompt reply, again.

Hi Kazzz,

thanks a lot for these examples and testcases.

I need to say that the measurement feature has mainly been developed for manhattan geometries.

Yes, I understand this well :-) However, KLayout is so useful for non-manhattan geometry applications, too. In my application, it is rate to see a manhattan geometry. ;-(
So, this test case is a "stress test case" for KLayout.

The basic working principle is this:

• From the seed point, look for the nearest edge facing towards the seed
• create a measurement line perpendicular to this edge and passing through the seed
• determine the closest cut point of this line with any other edge

I could somehow read out these steps from the source code.
Earlier I tried to develop a similar algorithm for a large complicated any-angle shape but found it's not easy. So your achievement is a good teacher!

I guess the main issue is caused by the definition of "facing towards the starting point". A failure here might explain some of your observations.

I think that a modification of the algorithm is possible, although it will rather be a rewrite. I just wonder what's a good definition of distance

Best regards,

Matthias

I'll try "issue-342 branch".

Thanks again!
Kazzz

[klayoutmatthias]

Hey, I discovered some flower :-)

[klayoutmatthias]

I might have an entirely different solution ... instead of using the rulers, one can try a geometry analysis of the environment of the markers.

Here is some script:

# some functions ...

def centroid(p)

  cx = 0
  cy = 0
  
  # centroid
  # see https://en.wikipedia.org/wiki/Second_moment_of_area
  
  p.each_edge do |e|
    
    # needs to swap points because our polygons 
    # are clockwise oriented
    x1 = e.p2.x.to_f
    y1 = e.p2.y.to_f
    x2 = e.p1.x.to_f
    y2 = e.p1.y.to_f
    
    d = (x1 * y2 - x2 * y1)
    cx += d * (x1 + x2)
    cy += d * (y1 + y2)
  
  end
  
  a = p.area
  cx /= 6 * a
  cy /= 6 * a

  [ cx, cy ]
  
end

def inertia_tensor(p)

  ixx = 0
  iyy = 0
  ixy = 0
  
  # see https://en.wikipedia.org/wiki/Second_moment_of_area
  
  p.each_edge do |e|
    
    # needs to swap points because our polygons 
    # are clockwise oriented
    x1 = e.p2.x.to_f
    y1 = e.p2.y.to_f
    x2 = e.p1.x.to_f
    y2 = e.p1.y.to_f
    
    d = (x1 * y2 - x2 * y1)
    iyy += d * (x1 * x1 + x1 * x2 + x2 * x2)
    ixx += d * (y1 * y1 + y1 * y2 + y2 * y2)
    ixy += d * (x1 * y2 + 2 * x1 * y1 + 2 * x2 * y2 + x2 * y1)
  
  end
  
  iyy /= 12
  ixx /= 12
  ixy /= 24

  [ ixx, iyy, ixy ]
  
end

def eigenvalues(it)

  ( ixx, iyy, ixy ) = it
 
  # see http://www.math.harvard.edu/archive/21b_fall_04/exhibits/2dmatrices/
  t = ixx + iyy
  d = ixx * iyy - ixy * ixy
  
  s = Math.sqrt(t * t / 4 - d)
  [ t / 2 + s, t / 2 - s ].sort

end


# ------------------------------------------------------------------------

view = RBA::LayoutView::current
ly = RBA::CellView::active.layout

pattern = (3001 .. 3004).to_a.collect do |l| 
  RBA::Region::new(ly.top_cell.begin_shapes_rec(ly.layer(l, 1)))
end
joined_pattern = pattern.inject(:+)

markers = RBA::Region::new(ly.top_cell.begin_shapes_rec(ly.layer(5002, 10)))

rad = (0.5 + 1500.0 / ly.dbu).to_i
pts = 200


# create circles around the markers (circles are not depending on the 
# pattern orientation)

circles = RBA::Region::new
markers.each do |m|
  p = m.bbox.center
  rv = RBA::Vector::new(rad, rad)
  circles.insert(RBA::Polygon::ellipse(RBA::Box::new(p - rv, p + rv), pts))
end

# cut out the pattern on the circles and select the parts with the markers

masked_pattern_at_sites = (joined_pattern & circles).select_interacting(markers)

# revisit the circles and replace them by ones centered at the centroid
# (now with a smaller radius for less averaging)

rad2 = (0.5 + 1000.0 / ly.dbu).to_i

circles.clear

masked_pattern_at_sites.each do |p|

  ( cx, cy ) = centroid(p)
  
  p = RBA::Point::new(cx, cy)
  rv = RBA::Vector::new(rad2, rad2)
  circles.insert(RBA::Polygon::ellipse(RBA::Box::new(p - rv, p + rv), pts))
  
end

# do the computation again

masked_pattern_at_sites = (joined_pattern & circles).select_interacting(markers)

# NOTE: one could basically repeat the centroid/create circular masks to achieve 
# convergence ...


# write this to the debug layer

debug_out = ly.top_cell.shapes(ly.layer(9999, 0))
debug_out.clear
debug_out.insert(masked_pattern_at_sites)

# now handle each circular-masked part of pattern
# 1.) determine centroid 
# 2.) utilize second inertia tensor to describe it's shape
#     in a first-order approximation
# 3.) eliminate rotation by computing the tensor's Eigenvalues
# 4.) compare vs. rectangle to obtain the effective width
# 5.) TODO: comparing vs. a rectangle means making a small 
#     error because our real shape is a "band" cut out from
#     a circle. There might be an analytical solution that
#     can be utilized.

masked_pattern_at_sites.each do |p|

  ( cx, cy ) = centroid(p)

  # move to center of mass
  p = p.moved(RBA::Vector::new(-cx, -cy))
  
  it = inertia_tensor(p)
  
  ev = eigenvalues(it)
  
  # compare to rectangle (TODO: see above)
  # Ixx = 1/12*(h**3)*w  Iyy = 1/12*(w**3)*h
  ( ixx, iyy ) = ev
  w = (12**2 * ixx**3 / iyy)**(1.0/8.0)
  h = (12**2 * iyy**3 / ixx)**(1.0/8.0)

  ant = RBA::Annotation::new
  ant.p1 = RBA::DPoint.new((cx - 0.5 * w) * ly.dbu, (cy - 0.5 * w) * ly.dbu)
  ant.p2 = RBA::DPoint.new((cx + 0.5 * w) * ly.dbu, (cy + 0.5 * w) * ly.dbu)
  ant.outline = 6 # Ellipse
  ant.fmt = ("%.1f" % (w * ly.dbu))
  ant.fmt_x = ""
  ant.fmt_y = ""
  
  view.insert_annotation(ant)
  
end

Accuracy can be improved (see TODO in the code). But this algorithm will provide some "averaging" over the line length and smooth out steps. It also provides some kind of "self-alignment" of the measurement sites.

If you don't like the measurement approach, you might still want to obtain the seed positions from the centroid positions.

The results don't look really bad to me though:

Enjoy,

Matthias

[Kazzz-S]

Hi Matthias,

Thank you so much for suggesting an alternative solution with a fully functioning RBA!
I could reproduce the same "flower."
Yes, this is an idea! And even faster than the ruler creation.

I need some more time to digest the suggested RBA fully, however, I'll try to develop
my tool based on this approach, too.

Thank you once again!
Kazzz

[Kazzz-S]

Hi Matthias,

Hi Kazzz,

thanks again this great testcase.

I managed to enhance the implementation somewhat and don't find any more of the "rogue" rulers. Please see the tip of the issue-342 branch.

I've also confirmed that "issue-342 branch" has fixed the 110 cases!
Thank you very much for the quick fix, which is a really great help for me.

Still, when the measurement point is close to the pinch step, it will pick a vertex from this step and run a measurement against this. Like here:

By operating the enhanced GUI (#342), I could comfortably manage this case!

I'm afraid this is mainly due to the restricted measurement algorithm. When the point is inside a parallel region, the rulers are nicely set:

Best regards,

Matthias

Thanks a lot and with best regards,
Kazzz