wrong order of multi_clip

edited January 2017 in Python scripting

Hi,
I found the order of multi_clip output is not same as input boxes list.
Part of my python script is,

print 'first 5 bboxes'
clist = layout.multi_clip(top_id, bblist)
for cid, ii in zip(clist,range(len(clist))):
    cc = layout.cell(cid)
    print cid, cc.bbox().to_s(), bblist[ii].to_s()


print 'first 4 bboxes'
bblist = bblist[0:4]

clist = layout.multi_clip(top_id, bblist)
for cid, ii in zip(clist,range(len(clist))):
   cc = layout.cell(cid)
   print cid, cc.bbox().to_s(), bblist[ii].to_s()

The output is blow,

first 5 bboxes
6018 (-406876,-292272;-405292,-290587) (-464094,-61533;-462056,-59423)
6019 (-464053,-61112;-462056,-59848) (-463756,-46673;-461645,-44653)
6020 (-463756,-46673;-461645,-44653) (-427809,22824;-425706,24936)
6021 (-427422,9928;-425537,11618) (-427422,9506;-425345,11618)
6022 (-427358,23248;-426041,24512) (-406876,-292698;-404847,-290587)
first 4 bboxes
6023 (-464053,-61112;-462056,-59848) (-464094,-61533;-462056,-59423)
6024 (-463756,-46673;-461645,-44653) (-463756,-46673;-461645,-44653)
6025 (-427422,9928;-425537,11618) (-427809,22824;-425706,24936)
6026 (-427358,23248;-426041,24512) (-427422,9506;-425345,11618)

You could found when 4 bboxes used in multi_clip, the output order is same as bboxes.
All clipped cell is in input bbox.

However, when I use 5 bboxes, the order output is SHIFT.
Is it a bug? Or how could I get correct clipped cells matched with input bboxes?

Thanks,
Dion

Comments

  • edited January 2017

    Hi Dion,

    please try to use Markdown markup to properly format the code - for Python this is in particular important. You just have to add four blanks in front of the code lines.

    Regarding your problem: the order of the output cells is not guaranteed right now. There may be even less output cells if two clip boxes happen to be the same.

    I have not tried it, but if I read my code correctly, the clip function uses a STL map with a "pair<cell_index, clip_box>" key. The output is taken from those entries where cell_index == index of top cell of input, so the remaining sorting will be according to the box (using < and == relations). So maybe it's sufficient to sort the clip boxes before you pass them to the multi_clip function (with < and == - maybe even <=> is synthesized correctly) and to make sure there are no duplicates.

    Regards,

    Matthias

  • edited November -1
    Hi Matthias,
    You are right, clip function use STL map.
    However, there are two problems.
    1. the output results looks sorted the bbox of cut results, not the input bboxes.
    2. if input bboxes cut nothing, no result will output. Then the count of output is different from input.

    So even I sorted the input bboxes, these are still miss match cases.

    Thanks,
    Dion
  • edited January 2017

    Hi Matthias,

    I add patch to output clip results as order. when no data in clip bbox, it will return cell idx 0.
    Maybe you could add an option in next release.

    diff --git a/src/dbClip.cc b/src/dbClip.cc
    index 55ab499..3f8aaa5 100644
    --- a/src/dbClip.cc
    +++ b/src/dbClip.cc
    @@ -520,7 +520,8 @@ collect_clip_variants (const db::Layout &layout,
                            db::Layout &target_layout,
                            db::cell_index_type cell_index,
                            const db::Box &clip_box,
    -                       std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type> &variants)
    +                       std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type> &variants,
    +                       std::map <db::Box, db::Box> &b2b_map)
     {
       const db::Cell &cell = layout.cell (cell_index);
       db::box_convert <db::CellInst> bc (layout);
    @@ -530,11 +531,12 @@ collect_clip_variants (const db::Layout &layout,
    
         std::pair <std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type>::iterator, bool> vmp = variants.insert (std::make_pair (std::make_pair (cell_index, cell_box), 0));
         if (vmp.second) {
    +      b2b_map[cell_box] = clip_box;
    
           for (db::Cell::touching_iterator inst = cell.begin_touching (cell_box); ! inst.at_end (); ++inst) {
             for (db::CellInstArray::iterator a = inst->cell_inst ().begin_touching (cell_box, bc); ! a.at_end (); ++a) {
               db::Box inst_clip_box = db::Box::from_double (cell_box.transformed (inst->cell_inst ().complex_trans (*a).inverted ()));
    -          collect_clip_variants (layout, target_layout, inst->cell_index (), inst_clip_box, variants);
    +          collect_clip_variants (layout, target_layout, inst->cell_index (), inst_clip_box, variants, b2b_map);
             }
           }
    
    @@ -576,10 +578,13 @@ clip_layout (const Layout &layout,
    
       try {
    
    +    std::map <db::Box, db::cell_index_type> b2c_map;
    +    std::map <db::Box, db::Box> b2b_map;
    +
         //  create clip variants of cells
         std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type> variants;
         for (std::vector <db::Box>::const_iterator cbx = clip_boxes.begin (); cbx != clip_boxes.end (); ++cbx) {
    -      collect_clip_variants (layout, target_layout, cell_index, *cbx, variants);
    +      collect_clip_variants (layout, target_layout, cell_index, *cbx, variants, b2b_map);
         }
    
         make_clip_variants (layout, target_layout, variants);
    @@ -592,7 +597,21 @@ clip_layout (const Layout &layout,
         //  prepare the result vector ..
         for (std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type>::const_iterator var = variants.begin (); var != variants.end (); ++var) {
           if (var->first.first == cell_index) {
    -        result.push_back (var->second);
    +        b2c_map[b2b_map[var->first.second]] = var->second;
    +        //result.push_back (var->second);
    +      }
    +    }
    +
    +    for (std::vector <db::Box>::const_iterator cbx = clip_boxes.begin (); cbx != clip_boxes.end (); ++cbx) {
    +      if ( b2c_map.count(*cbx) ) {
    +        result.push_back (b2c_map[*cbx]);
    +      } else {
    +        result.push_back (0);
           }
         }
    

    Thanks,
    Dion

  • edited November -1

    Hi Dion,

    I'll do it slightly differently.

    You should confine your solution to the top level (set b2b_map for the first recursion only). Otherwise you may risk that cells below may overwrite your entries. Plus 0 is a valid cell index - so if you intend to mark "non-existing cells" you need to do it in a different way.

    Find my patch below (line numbers may not match the current release).

    Regards,

    Matthias

    Index: src/db/dbClip.cc
    ===================================================================
    --- src/db/dbClip.cc    (revision 3512)
    +++ src/db/dbClip.cc    (working copy)
    @@ -497,25 +497,32 @@
                            db::Layout &target_layout,
                            db::cell_index_type cell_index,
                            const db::Box &clip_box,
    -                       std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type> &variants)
    +                       std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type> &variants,
    +                       bool stable)
     {
       const db::Cell &cell = layout.cell (cell_index);
       db::box_convert <db::CellInst> bc (layout);
    
    -  db::Box cell_box = cell.bbox () & clip_box;
    -  if (! cell_box.empty ()) {
    +  db::Box cell_box;
    +  if (stable) {
    +    cell_box = clip_box;
    +  } else {
    +    cell_box = cell.bbox () & clip_box;
    +    if (cell_box.empty ()) {
    +      return;
    +    }
    +  }
    
    -    std::pair <std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type>::iterator, bool> vmp = variants.insert (std::make_pair (std::make_pair (cell_index, cell_box), 0));
    -    if (vmp.second) {
    +  std::pair <std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type>::iterator, bool> vmp = variants.insert (std::make_pair (std::make_pair (cell_index, cell_box), 0));
    +  if (vmp.second) {
    
    -      for (db::Cell::touching_iterator inst = cell.begin_touching (cell_box); ! inst.at_end (); ++inst) {
    -        for (db::CellInstArray::iterator a = inst->cell_inst ().begin_touching (cell_box, bc); ! a.at_end (); ++a) {
    -          db::Box inst_clip_box = db::Box (cell_box.transformed (inst->cell_inst ().complex_trans (*a).inverted ()));
    -          collect_clip_variants (layout, target_layout, inst->cell_index (), inst_clip_box, variants);
    -        }
    +    for (db::Cell::touching_iterator inst = cell.begin_touching (cell_box); ! inst.at_end (); ++inst) {
    +      for (db::CellInstArray::iterator a = inst->cell_inst ().begin_touching (cell_box, bc); ! a.at_end (); ++a) {
    +        db::Box inst_clip_box = db::Box (cell_box.transformed (inst->cell_inst ().complex_trans (*a).inverted ()));
    +        collect_clip_variants (layout, target_layout, inst->cell_index (), inst_clip_box, variants, false);
           }
    +    }
    
    -    }
       }
     }
    
    @@ -541,7 +548,8 @@
     clip_layout (const Layout &layout, 
                  Layout &target_layout, 
                  db::cell_index_type cell_index, 
    -             const std::vector <db::Box> &clip_boxes)
    +             const std::vector <db::Box> &clip_boxes,
    +             bool stable)
     {
       std::vector<db::cell_index_type> result;
    
    @@ -555,8 +563,9 @@
    
         //  create clip variants of cells
         std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type> variants;
    +
         for (std::vector <db::Box>::const_iterator cbx = clip_boxes.begin (); cbx != clip_boxes.end (); ++cbx) {
    -      collect_clip_variants (layout, target_layout, cell_index, *cbx, variants);
    +      collect_clip_variants (layout, target_layout, cell_index, *cbx, variants, stable);
         }
    
         make_clip_variants (layout, target_layout, variants);
    @@ -567,10 +576,23 @@
         }
    
         //  prepare the result vector ..
    -    for (std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type>::const_iterator var = variants.begin (); var != variants.end (); ++var) {
    -      if (var->first.first == cell_index) {
    +    if (! stable) {
    +
    +      for (std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type>::const_iterator var = variants.begin (); var != variants.end (); ++var) {
    +        if (var->first.first == cell_index) {
    +          result.push_back (var->second);
    +        }
    +      }
    +
    +    } else {
    +
    +      //  We have made sure before that there is a top-level entry for each clip box that was input
    +      for (std::vector <db::Box>::const_iterator cbx = clip_boxes.begin (); cbx != clip_boxes.end (); ++cbx) {
    +        std::map <std::pair <db::cell_index_type, db::Box>, db::cell_index_type>::const_iterator var = variants.find (std::make_pair (cell_index, *cbx));
    +        tl_assert (var != variants.end ());
             result.push_back (var->second);
           }
    +
         }
    
         //  release the under construction state
    Index: src/db/dbClip.h
    ===================================================================
    --- src/db/dbClip.h (revision 3512)
    +++ src/db/dbClip.h (working copy)
    @@ -60,9 +60,10 @@
      *  @param target_layout The target layout where to produce the clip cell
      *  @param cell_index Which cell to clip
      *  @param clip_boxes Which boxes to clip at
    + *  @param stable If true, the function will return corresponding clip cells for each clip box. The clip cells may be empty.
      *  @return A set of cells which contain the clips. If the layout and target layout is identical, these cells may be identical with original cells.
      */
    -KLAYOUT_DLL std::vector <db::cell_index_type> clip_layout (const Layout &layout, Layout &target_layout, db::cell_index_type cell_index, const std::vector <db::Box> &clip_boxes);
    +KLAYOUT_DLL std::vector <db::cell_index_type> clip_layout (const Layout &layout, Layout &target_layout, db::cell_index_type cell_index, const std::vector <db::Box> &clip_boxes, bool stable);
    
     } // namespace db
    
    Index: src/db/gsiDeclDbLayout.cc
    ===================================================================
    --- src/db/gsiDeclDbLayout.cc   (revision 3512)
    +++ src/db/gsiDeclDbLayout.cc   (working copy)
    @@ -308,7 +308,7 @@
     {
       std::vector <db::Box> boxes;
       boxes.push_back (box);
    -  std::vector <db::cell_index_type> cc = db::clip_layout(*l, *l, c, boxes);
    +  std::vector <db::cell_index_type> cc = db::clip_layout(*l, *l, c, boxes, true);
       tl_assert (! cc.empty ());
       return cc [0];
     }
    @@ -317,7 +317,7 @@
     {
       std::vector <db::Box> boxes;
       boxes.push_back (box);
    -  std::vector <db::cell_index_type> cc = db::clip_layout(*l, *t, c, boxes);
    +  std::vector <db::cell_index_type> cc = db::clip_layout(*l, *t, c, boxes, true);
       tl_assert (! cc.empty ());
       return cc [0];
     }
    @@ -324,12 +324,12 @@
    
     static std::vector<db::cell_index_type> multi_clip (db::Layout *l, db::cell_index_type c, const std::vector<db::Box> &boxes)
     {
    -  return db::clip_layout(*l, *l, c, boxes);
    +  return db::clip_layout(*l, *l, c, boxes, true);
     }
    
     static std::vector<db::cell_index_type> multi_clip_into (db::Layout *l, db::cell_index_type c, db::Layout *t, const std::vector<db::Box> &boxes)
     {
    -  return db::clip_layout(*l, *t, c, boxes);
    +  return db::clip_layout(*l, *t, c, boxes, true);
     }
    
     static unsigned int get_layer (db::Layout *l, const db::LayerProperties &lp)
    Index: src/lay/layClipDialog.cc
    ===================================================================
    --- src/lay/layClipDialog.cc    (revision 3512)
    +++ src/lay/layClipDialog.cc    (working copy)
    @@ -156,7 +156,7 @@
         std::sort (clip_boxes.begin (), clip_boxes.end ());
         clip_boxes.erase (std::unique (clip_boxes.begin (), clip_boxes.end ()), clip_boxes.end ());
    
    -    std::vector<db::cell_index_type> new_cells = db::clip_layout (cv->layout (), cv->layout (), cv.cell_index (), clip_boxes);
    +    std::vector<db::cell_index_type> new_cells = db::clip_layout (cv->layout (), cv->layout (), cv.cell_index (), clip_boxes, false);
    
         if (new_cells.size () > 1) {
    
  • edited November -1
    Hi Matthias,
    Thanks for you patch. It's much better than mine :)

    Thanks,
    Dion
  • edited November -1
    Hi Matthias,
    Is your above patch included in 0.24.10 release?
    Or there is no plan to add it to future release ?

    Thanks,
    Dion
  • edited November -1

    Hi Dion,

    sorry, but considering that a somewhat "more than trivial" change I did not include that into 0.24.10.

    I'm moving everything to GitHub now (https://github.com/klayoutmatthias/klayout). In the master, this patch is already included.

    Matthias

Sign In or Register to comment.