• Skip to main content
  • Skip to search
  • Skip to footer
Cadence Home
  • This search text may be transcribed, used, stored, or accessed by our third-party service providers per our Cookie Policy and Privacy Policy.

  1. Community Forums
  2. Custom IC SKILL
  3. abeLayerTouch result question

Stats

  • Locked Locked
  • Replies 4
  • Subscribers 144
  • Views 9380
  • Members are here 0
This discussion has been locked.
You can no longer post new replies to this discussion. If you have a question you can start a new discussion

abeLayerTouch result question

BorisD
BorisD over 3 years ago

Greetings,

 I have a script which takes as input a string expression like this "PC touch CA touch M1 touch (...)"  etc. This expression can have arbitrary length and represents connectivity information. I created a parser based on Advanced Boolean Engine (abe) routines to check if the expression evals to t/nil. For 'touch' operation I use abeLayerTouch which works perfectly fine:

abeLayerTouch( abeLayer1 abeLayer2 abeResult )

The issue I have is that the resulting abeResult contains only the tiles from abeLayer1 that touch abeLayer2. But for my purpose, I need to continue checking using the entire islands from abeLayer1 that touch segments from abeLayer2. 

QUESTIONS:

  1. Is there a way for abeLayerTouch to return the entire island (aka polygon) instead of just the partitioned tile ?
  2. If not, any suggestions for alternative way to get what I want? I was trying to come up with a solution entirely within ABE realm, because of how quick it is. However, I finally resorted to loops and geometry.
  3. Are the islands in geoLayer OR abeIslandIterator sorted by default for number of points?
  4. For checking if a concave polygon is touching a rectangle, I couldn't find anything better than dbPointArrAnd, any ideas here? It felt really slow since for some reason it requires cellView and moreoever, I don't need it to return the overlapping area, I need boolean answer. So I wrote a 2 step algorithm, which profiled and turn out to better:
    1. Check if the sum of radiuses (r1 + r1) of smallest enclosing circle around two polygons is less then the distance between the circle center points L. If L>r1+r2 then polygons don't touch and stop here.
    2. Else check if at least one line N of polygonA is crossing|abutting line K of polygonB. If yes - polygons are abutting or straddle stop here.
      NOTE: This algorithm does not detect when polygonB is entirely inside polygonA without any abutting or crossing lines. However, this is not possible for my scenario with the abeLayerTouch.

 I ended up writing my own abeLayerConnect proc that performs what I need, but it can get slow with large number of polygons/islands and/with many points. I basically perform a standard abeLayerTouch, then for each tile from abeResult I check if it belongs to any islands from abeLayer1, if yes - I put them into a new abeLayer using abeLayerOrPtArray and continue with my expression using this new layer.

abeLayerTouch(abeLayer1 abeLayer2 abeResult)
;# Create array filled with tiles (threat tile as polygon for consistency)
ii=abeIslandIterator(abeResult)
tilesCount = ii->count
declare(aTiles[tilesCount])
for(i 0 tilesCount-1 aTiles[i] = ii->next)
;# Create array filled with polygons/islands
ii=abeIslandIterator(abeLayer1)
polysCount = ii->count
declare(aPolys[polysCount])
for(i 0 polysCount-1 aPolys[i] = ii->next)
;# Iterate over each polygon and check if a tile is touching.
;# If yes - add the polygon points to a new cumulutive abeLayer using abeLayerOrPtArray and 'remove' it from array. Remove the tile as well
;# because one tile can be part of exactly 1 polygon/island. Stop the loop and retry with new reduced number of polygons and tiles.
;# If no - just remove it from array -> none of the tiles were part from this particular polygon.
abePolys = abeNewLayer()
while(!zerop(tilesCount) || !zerop(polysCount)
  prog( (polygon tile)
    for( i 0 length(aPolys)-1
      polygon = aPolys[i]
      when(!eq(polygon 'unbound)
        for(k 0 length(aTiles)-1
          tile  = aTiles[k]
          when(!eq(tile 'unbound) && dbPointArrAnd(cv list(polygon) list(tile)) ; OR my custom made function which is actually faster
           abeLayerOrPtArray(polygon abePolys)
            aPolys[i] = 'unbound
            aTiles[k] = 'unbound
            tilesCount-=1
            polysCount-=1
            return(t)
          ); when
        ); for k
      ); when
      aPolys[i] = 'unbound
      polysCount-=1
    ); for i
  ); prog
); while
abePolys

Any tips and/or ideas are appreciated. Thank you!
  • Cancel
Parents
  • AurelBuche
    AurelBuche over 3 years ago

    Hi,

    Here is my solution for 1) and 2)

    It might be faster than yours and is one step closer to the ABE only realm

    (defun abe_layer_connect (abe_l0 abe_l1 abe_out)
        "Add ABE_L0 islands that touch (completely overlap, partially overlap or abut) ABE_L1 to ABE_OUT"
        (let ((abe_touch  (abeNewLayer))
              (abe_island (abeNewLayer))
              (abe_tmp    (abeNewLayer))
              )
        ;; First we compile the touching shapes using the default ABE function
    ;; Then we browse abe_l0 islands and keep the ones overlapping pre-compiled touching shapes
        (abeLayerTouch abe_l0 abe_l1 abe_touch)
        (let ((iter (abeIslandIterator abe_l0)))
          (while (setq island iter->next)
            (abeClearLayer abe_island)
            (abeClearLayer abe_tmp)
            (abeLayerOrPtArray island abe_island)
            (abeLayerAnd abe_island abe_touch abe_tmp)
            (unless (zerop abe_tmp->numTiles) (abeLayerOrPtArray island abe_out))
            ))
        ;; Delete useless layers and return the desired one
        (abeRemoveLayer abe_touch)
        (abeRemoveLayer abe_island)
        (abeRemoveLayer abe_tmp)
        abe_out))


    Hope this helps

    Cheers

    Aurélien

    • Cancel
    • Vote Up +1 Vote Down
    • Cancel
Reply
  • AurelBuche
    AurelBuche over 3 years ago

    Hi,

    Here is my solution for 1) and 2)

    It might be faster than yours and is one step closer to the ABE only realm

    (defun abe_layer_connect (abe_l0 abe_l1 abe_out)
        "Add ABE_L0 islands that touch (completely overlap, partially overlap or abut) ABE_L1 to ABE_OUT"
        (let ((abe_touch  (abeNewLayer))
              (abe_island (abeNewLayer))
              (abe_tmp    (abeNewLayer))
              )
        ;; First we compile the touching shapes using the default ABE function
    ;; Then we browse abe_l0 islands and keep the ones overlapping pre-compiled touching shapes
        (abeLayerTouch abe_l0 abe_l1 abe_touch)
        (let ((iter (abeIslandIterator abe_l0)))
          (while (setq island iter->next)
            (abeClearLayer abe_island)
            (abeClearLayer abe_tmp)
            (abeLayerOrPtArray island abe_island)
            (abeLayerAnd abe_island abe_touch abe_tmp)
            (unless (zerop abe_tmp->numTiles) (abeLayerOrPtArray island abe_out))
            ))
        ;; Delete useless layers and return the desired one
        (abeRemoveLayer abe_touch)
        (abeRemoveLayer abe_island)
        (abeRemoveLayer abe_tmp)
        abe_out))


    Hope this helps

    Cheers

    Aurélien

    • Cancel
    • Vote Up +1 Vote Down
    • Cancel
Children
  • sebcliq
    sebcliq over 3 years ago in reply to AurelBuche

    3. Are the islands in geoLayer OR abeIslandIterator sorted by default for number of points?

    To the best of my knowledge, the island iterator does not do any kind of sorting - it is designed to deal with millions of shapes as fast as possible, and any kind of sorting would basically kill performance.

    For question 4, I would maybe use geometrical algorithm based on dot product to check if a point belong to a segment or not. Then there is classical algorithm to determine whether a point is inside a polygon or not, based on the sign value of the sum of angles from point to all adjacent pairs on point in polygon [it does not work if point is exactly on boundary, so I complement it with first part of answer]

    Then as a general comment, it is generally more efficient in SKILL[++] to write a "specific language: based on list than based on strings, because list parsing is immediate in SKILL.

    Instead of

    "PC touch CA touch M1 touch (...)"

    I generally  prefer to write

    (touch PC CA M1 ... (and ... (or ... ) )

    Which is must easier to parse [use lineread !]

    And then for example create a SKILL++ object from the layers (PC, CA...) and method to assemble your objects [which in the end point to geoLayer of course]

    This is actually what we did in our company (write a SKILL++ class system on top of ABE, then write a "boolean language parser" - we encapsulate and "augment" all ABE functions into methods working on our objects.

    I cannot share the code here for obvious legal reasons, but this may be a way you want to pursue - at least, I can tell you this is working very fine for us, and people seem happy with this SKILL++ layer on top of ABE (I guess Aurelien can confirm ;-) )

    Sebastien

    • Cancel
    • Vote Up +2 Vote Down
    • Cancel

Community Guidelines

The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.

© 2025 Cadence Design Systems, Inc. All Rights Reserved.

  • Terms of Use
  • Privacy
  • Cookie Policy
  • US Trademarks
  • Do Not Sell or Share My Personal Information