Memory allocation error and solutions

Comments

• Matthias

  March 2014 edited November -1

  Hi David,

  that appears to be some extreme case - maybe the formation of the complex hole inside the polygon is requiring more memory than expected.

  In general, a lot of memory is consumed by the point array which is built before the polygon is made of that. You can try to release that memory by releasing the memory and forcing a garbage collect, but that appears not to have an effect on the process size. Maybe memory fragmentation is happening here.

  64bit should be one solution, but you need to make sure you run the 64bit executable. 64bit can run 32bit executables as well in WoW mode, but they will be subject to the same memory restrictions. There is a hardware limit of course too, so if you want to go even further, you should look for a more general solution.

  Looking at the output of your script I see a regular structure. That suggests, you could simplify the problem by producing slices (one slice per tooth) and putting them together later. That surely is more efficient than operations on big polygons.

  Matthias
• david234589

  March 2014 edited November -1

  Thanks Matthias.

  Yes I admit I am pushing your excellent program to the limits, and I'm surprised it even makes it this far, because that is a heavy requirement!

  Definitely running 64 bit. I uninstalled 32-bit.

  Yes it's true that in this script I have a regular structure but this was only a short example to illustrate the question -- my actual script has very complicated shapes and difficult or impossible to split up in such a way. Here I am mostly trying to understand the limits so I can work around them.

  I will mention that anything the script tries to do, before getting to the EdgeProcessor part, even with all those points in memory, still runs really quickly. It is only when it hits the EdgeProcessor line that it struggles if the input and/or output polygons have too many points.

  If there were a way to split both inner and outer polygons - say, split them with vertical lines along the x = 10 um, 20 um, 30 um,... and get an array of polygons. Then operate on the x = 0..10 um polygons, then on the 10..20 um polygons, then on the 20..30 um polygons, etc.... That could be a nice solution. However I fail to find a way to split the a polygon along, say, x = 10um line and return a handle to the two resultant polygons. On L-Edit they have a function for this (splitting along a vertical or horizontal line) so I mention that only because I am familiar with it, but there may be better approaches. Any simple way to do that in Ruby code? If not maybe I just need to buy and install a ton of memory.
• david234589

  March 2014 edited March 2014

  Never mind. Figured it out.

  I coded up the following "slicer" (1D tiling function) pasted below. Not the prettiest code but it works. There are a few limitations of the code though these can be fixed. First, it has problems if the slice locations v fall outside of the original polygon. Second, there are a few strange cases where it may not work. At any rate, this is good enough for me.

  Here is some example code which calls the .rb file pasted later:

  # Draw a polygon (make sure it is larger than the v positions below), select it, then run this script to slice it up and draw the slices
  
  layout_view = RBA::Application.instance.main_window.current_view  
  layout = layout_view.active_cellview.layout
  out_cell = layout_view.active_cellview.cell
  out_layer = layout.layer(1,0)
  dbu = layout.dbu
  poly = RBA::Polygon.new(RBA::Box.new(0/dbu,0/dbu,10/dbu,10/dbu))
  #out_cell.shapes(layout.layer(2,0)).insert(poly)
  filepath = 'C:/filepath/'
  filename = 'split vertically.rb'
  file = File.expand_path(filename, filepath)
  load file
  
  v = [1,2,10,11]
  direction = 'vertical'
  
  if layout_view == nil
    raise "No view selected"
  end
  
  layout_view.transaction("Split")
  begin
    layout_view.each_object_selected { |obj|
      if obj.shape.is_polygon?
        split_poly_arr, orig_poly = Split.split(v,obj.shape,direction)
        split_poly_arr.each { |p| out_cell.shapes(out_layer).insert(p) }
      else
        RBA::MessageBox::warning("Warning", "Found something other than a polygon. Ignoring.", RBA::MessageBox::Ok)
      end
    }
  ensure
    layout_view.commit
  end
  

  And here is the .rb file itself:

  class Split
  
    # Splits a polygon along vertical or horizontal lines at positions v, and returns the array of polygons produced.
  
  =begin # EXAMPLE USAGE.
    layout_view = RBA::Application.instance.main_window.current_view  
    layout = layout_view.active_cellview.layout
    out_cell = layout_view.active_cellview.cell
    out_layer = layout.layer(1,0)
    dbu = layout.dbu
    poly = RBA::Polygon.new(RBA::Box.new(0/dbu,0/dbu,10/dbu,10/dbu))
    #out_cell.shapes(layout.layer(2,0)).insert(poly)
    filepath = 'C:/Users/dnhutchi/KLayout/macros/Sandbox'
    filename = 'split vertically.rb'
    file = File.expand_path(filename, filepath)
    load file
  
    v = [1,2,10,11]
    direction = 'vertical'
  
    if layout_view == nil
      raise "No view selected"
    end
  
    layout_view.transaction("Split")
    begin
      layout_view.each_object_selected { |obj|
        if obj.shape.is_polygon?
          split_poly_arr, orig_poly = Split.split(v,obj.shape,direction)
          split_poly_arr.each { |p| out_cell.shapes(out_layer).insert(p) }
        else
          RBA::MessageBox::warning("Warning", "Found something other than a polygon. Ignoring.", RBA::MessageBox::Ok)
        end
      }
    ensure
      layout_view.commit
    end
  =end 
  
    def self.split(val, shape, horiz_or_vert, cellview = RBA::CellView::active)
  
      layout = cellview.layout
      out_cell = cellview.cell
      dbu = layout.dbu
  
      val.class == Fixnum ? (val_arr = [val]) : (val_arr = val)
      val_arr.map! { |v| v.to_f / dbu } # Convert to database units
  
      split_me = shape    # Keeps track of which shape we are splitting
      split_poly_arr = [] # The output array of post-split polygons
  
      poly1  = nil
      poly2  = nil
      first  = nil
      second = nil
      p "val_arr = #{val_arr}"
      val_arr.each { |v|
  
        # Get the points of the shape we will split
        pts = []
        split_me.each_point_hull { |pt| pts.push(pt) }
  
        # Repeat the 1st element again at the end of the array so that each_cons works correctly
        pts.push(pts[0]) 
  
        pts1 = []
        pts2 = []
        pts.each_cons(2) { |pn|
          p = RBA::Point.new(pn[0].x, pn[0].y)
          n = RBA::Point.new(pn[1].x, pn[1].y)
  
          p p.x.class
          p v.class
          p "Classes above"
  
          # See if the x coords of p and n straddle the v position or not
          if    horiz_or_vert == 'vertical' && (p.x <= v && n.x > v)
            new_pt = RBA::Point.new(v, (n.y-p.y).fdiv(n.x-p.x) * (v-p.x) + p.y) if horiz_or_vert == 'vertical'
            pts1.push(p)
            pts1.push(new_pt)
            pts2.push(new_pt)
          elsif horiz_or_vert == 'horizontal' && (p.y <= v && n.y > v)
            new_pt = RBA::Point.new((n.x-p.x).fdiv(n.y-p.y) * (v-p.y) + p.x, v) if horiz_or_vert == 'horizontal'
            pts1.push(p)
            pts1.push(new_pt)
            pts2.push(new_pt)
          elsif horiz_or_vert == 'vertical' && (p.x > v && n.x <= v)
            new_pt = RBA::Point.new(v, (n.y-p.y).fdiv(n.x-p.x) * (v-p.x) + p.y) if horiz_or_vert == 'vertical'
            pts2.push(p)
            pts2.push(new_pt)
            pts1.push(new_pt)
          elsif horiz_or_vert == 'horizontal' && (p.y > v && n.y <= v)
            new_pt = RBA::Point.new((n.x-p.x).fdiv(n.y-p.y) * (v-p.y) + p.x, v) if horiz_or_vert == 'horizontal'
            pts2.push(p)
            pts2.push(new_pt)
            pts1.push(new_pt)
          elsif horiz_or_vert == 'vertical' && (p.x <= v && n.x <= v)
            pts1.push(p)  
          elsif horiz_or_vert == 'horizontal' && (p.y <= v && n.y <= v)
            pts1.push(p)
          elsif horiz_or_vert == 'vertical' && (p.x > v && n.x > v)
            pts2.push(p)
          elsif horiz_or_vert == 'horizontal' && (p.y > v && n.y > v)
            pts2.push(p)
          else
            RBA::MessageBox::warning("Warning", "This shouldn't happen. Check the code..", RBA::MessageBox::Ok)
          end 
        }
        pts1.map! {|p| x = p.x.fdiv dbu; y = p.y.fdiv dbu; p = RBA::Point.new(x*dbu,y*dbu)}
        pts2.map! {|p| x = p.x.fdiv dbu; y = p.y.fdiv dbu; p = RBA::Point.new(x*dbu,y*dbu)}
  
        poly1 = RBA::Polygon.new(pts1)
        poly2 = RBA::Polygon.new(pts2)
  
        # See which one is on the left (or below) and which poly is on the right (or above) of the split line
        first, second = self.first_second(poly1,poly2,v,horiz_or_vert) 
  
        # Save the first polygon and prepare to split the second polygon
        split_poly_arr.push(first)
        split_me = second
      }
      split_poly_arr.push(second) # Add that final sub-polygon onto the array
      [split_poly_arr,shape]
    end
  
    # This method takes in two polygons and a split line at v, and figures out which one is on the left (or below) and which one is on the right (or above) of the split line
    def self.first_second(poly1,poly2,v,horiz_or_vert)
      dbu = RBA::Application.instance.main_window.current_view.active_cellview.layout.dbu
      # Get the points of the original shape
      pts1 = []
      pts2 = []
      poly1.each_point_hull { |pt| pts1.push(pt) }
      poly2.each_point_hull { |pt| pts2.push(pt) }
  
      pts1_is_first = false # "first" meaning either left or below. "second" would mean either right or above.
      pts2_is_first = false
  
      case horiz_or_vert
      when 'vertical'
  
        i = 0; while self.float_cmp(pts1[i].x.to_f*dbu,v) == 0 do; i += 1; end # Choose a point that is not on the cut line v # TODO: FIX THIS SO I'M NOT USING == TO COMPARE FLOATS!
        pts1_is_first = true if pts1[i].x < v
  
        i = 0; while self.float_cmp(pts2[i].x.to_f*dbu,v) == 0 do; i += 1; end
        pts2_is_first = true if pts2[i].x < v
  
      when 'horizontal' # Has not been tested yet
  
        i = 0; while self.float_cmp(pts1[i].y.to_f*dbu,v) == 0 do; i += 1; end # Choose a point that is not on the cut line v
        pts1_is_first = true if pts1[i].y < v
  
        i = 0; while self.float_cmp(pts2[i].y.to_f*dbu,v) == 0 do; i += 1; end
        pts2_is_first = true if pts2[i].y < v
  
      end
  
      if    pts1_is_first && !pts2_is_first
        first  = poly1
        second = poly2
      elsif !pts1_is_first && pts2_is_first
        first  = poly2
        second = poly1
      else
        RBA::MessageBox::warning("Warning", "This should not happen. Check the code for errors.", RBA::MessageBox::Ok)
      end
  
      [first, second]
    end
  
    def self.which_one(two_polygons,v,horiz_or_vert)
      the_shape_to_split = nil
  
      if two_polygons.length == 1
        the_shape_to_split = two_polygons[0]
      else
  
        dbu = RBA::Application.instance.main_window.current_view.active_cellview.layout.dbu
  
        # Figures out which of the two polygons should be cut by a vertical or horizontal line at v
        two_polygons.each { |poly|
  
          case horiz_or_vert
          when 'vertical'
            # Get the points of the original shape
            pts = []; poly.each_point_hull { |pt| pts.push(pt) }
  
            pts.each_cons(2) { |pn|
              p = pn[0]*dbu
              n = pn[1]*dbu
  
              # See if the x coords of p and n straddle the v position or not
              straddle = false
              straddle = true if (p.x < v && n.x > v) || (p.x > v && n.x < v)
              the_shape_to_split = poly if straddle
            }
  
          when 'horizontal' # I have not tested this case
            # Get the points of the original shape
            pts = []; poly.each_point_hull { |pt| pts.push(pt) }
  
            pts.each_cons(2) { |pn|
              p = pn[0]*dbu
              n = pn[1]*dbu
  
              # See if the x coords of p and n straddle the v position or not
              straddle = false
              straddle = true if (p.y < v && n.y > v) || (p.y > v && n.y < v)
              the_shape_to_split = poly if straddle
            }
          end
        }
      end
  
      the_shape_to_split # If this returns nil, then your split line does not intersect either polygon
    end
  
    def self.float_cmp(f1,f2,precision = 0.0001)
      # Acts like <=> for floats
      if (f1 - f2).abs < precision
        ret = 0
      elsif f1 < f2
        ret = -1
      elsif f1 > f2
        ret = 1
      else
        p 'error'
      end
      ret
    end
  
  end
  
• Matthias

  April 2014 edited November -1

  Hi David,

  thank you for that example. I have not figured out yet what causes the memory issue. Basically a 64bit machine should be able to address much more memory, but first, a 64bit binary also requires more (because pointers will be 8 byte instead of 4 for example) and second, there is always a limitation, at least at physical memory + swap.

  I somewhat think the problem is related to the big hole. When you use smaller boxes (i.e. horizontal slices) as the background for the subtraction and repeat the step with every slice it may work - but I have not tried that yet.

  Your latest code uses some interesting Ruby techniques and frankly I have not figured out how it works on first glance - but I'll study it :-)

  Thanks,

  Matthias