#################################
### COPYRIGHT: Anders Lyhagen ###
#################################

module CAUL_FAQS
module Cut

  @EPSILON = 0.0001
  @E_VE_POS = Geom::Vector3d.new(@EPSILON, @EPSILON, @EPSILON)
  @E_VE_NEG = Geom::Vector3d.new(-@EPSILON, -@EPSILON, -@EPSILON)
  @id_count
  @X_DIV = @Y_DIV = @Z_DIV = 13
  @TARGET_SCALE = 24000
  @VERBOSE = false
  
  ##############################
  ####### PRE PROCESS ##########
  ##############################
  
  #triangulate non planar faces. Some faces may have trangressed the tolerance for 
  #flatness due to scaling. (this is a common source of problems in intersect)  
  def self.preProcess(g)
    s = Time.now
    fs = g.entities.grep(Sketchup::Face)
    tr = g.transformation
    tris = []
    
    fs.each { |f|  
      ps = f.outer_loop.vertices.map { |v| v.position.transform tr  }
      pl = Geom::fit_plane_to_points ps
      tris << f unless ps.all? { |p| p.on_plane? pl }
    }
    
    eh = {}
    tris.each { |f|
      mesh = f.mesh
      mf = f.material
      mb = f.back_material
      f.erase!
      
      mesh.polygons.each { |pol|
        f2 = g.entities.add_face mesh.point_at(pol[0].abs), mesh.point_at(pol[1].abs), mesh.point_at(pol[2].abs) 
      }   
    }
    if @VERBOSE
      puts formatString('Pre Process:', 20) + (Time.now - s).to_s + ' s'
      puts ' #flat fails: '+tris.length.to_s+'/'+fs.length.to_s
    end
  end
  
  ##############################
  ##### EXTRACT FACE PAIRS #####
  ##############################
    
  #Extract faces from g0 and g1 in the bounding box intersection between the groups
  def self.getBBFaces(g0, g0_bb, g1, g1_bb)
    s = Time.now
    bb_inter = g0_bb.intersect(g1_bb)
    bb_min = bb_inter.min.offset(@E_VE_NEG)
    bb_max = bb_inter.max.offset(@E_VE_POS)
    g0bb = getBBArray(g0)
    g1bb = getBBArray(g1)   
    g0bb_int = g0bb.select { |b| bbIntersect?(bb_min, bb_max, b[0], b[1]) }
    g1bb_int = g1bb.select { |b| bbIntersect?(bb_min, bb_max, b[0], b[1]) }    
    
    if @VERBOSE
      puts formatString('Extract BB:', 20) + (Time.now - s).to_s+' s'
      puts '   #g0 faces: ' + g0bb.length.to_s
      puts '   #g1 faces: ' + g1bb.length.to_s
    end
    
    return bb_inter, g0bb_int, g1bb_int
  end
  
  def self.getBBArray(g)
    tr = g.transformation
    return g.entities.grep(Sketchup::Face).map { |f|
      bb = Geom::BoundingBox.new      
      bb.add(f.outer_loop.vertices.map { |v| v.position.transform tr })
      @id_count += 1
      [bb.min.offset(@E_VE_NEG), bb.max.offset(@E_VE_POS), f, @id_count] }
  end
   
  def self.bbIntersect?(a_min, a_max, b_min, b_max)
    return false if b_min.x > a_max.x || b_max.x < a_min.x
    return false if b_min.y > a_max.y || b_max.y < a_min.y
    return false if b_min.z > a_max.z || b_max.z < a_min.z
    return true
  end
  
  def self.extractFacePairs(bb, g0bb, g1bb)
    s = Time.now
    #compute the bounds for the space hash
    dx_inv = 1.0 / ((bb.max.x - bb.min.x) / @X_DIV)
    dy_inv = 1.0 / ((bb.max.y - bb.min.y) / @Y_DIV)
    dz_inv = 1.0 / ((bb.max.z - bb.min.z) / @Z_DIV)
    
    #create the space hash
    sh = []
    (0..@X_DIV - 1).each { |i| sh << []
      (0..@Y_DIV - 1).each { |j| sh[i] << []
        (0..@Z_DIV - 1).each { |k| sh[i][j] << []
    }}}
    
    #add g0bb to space hash
    g0bb.each { |a| 
      inds = getBounds(a, bb, dx_inv, dy_inv, dz_inv)
      (inds[0]..inds[1]).each { |i|  
        (inds[2]..inds[3]).each { |j| 
          (inds[4]..inds[5]).each { |k|
            sh[i][j][k] << a
    }}}}
    
    res_h = {}
    res_a = []
    
    #find face pairs whose bounding boxes intersect
    g1bb.each { |b|
      b_id = (b[3] << 32)
      inds = getBounds(b, bb, dx_inv, dy_inv, dz_inv)
      (inds[0]..inds[1]).each { |i|  
        (inds[2]..inds[3]).each { |j| 
          (inds[4]..inds[5]).each { |k|
            sh[i][j][k].each { |a| 
              next if res_h.has_key?(b_id + a[3])
              res_h[b_id + a[3]] = nil
              res_a << [a[2], b[2]] if bbIntersect?(a[0], a[1], b[0], b[1])
            }
      }}}
    }
    
    if @VERBOSE
      puts formatString('Extract Pairs:', 20)+(Time.now - s).to_s+' s'
      puts '   #Pairs: ' +res_a.length.to_s
    end
    
    return res_a
  end
  
  def self.getBounds(b, bb, dx_inv, dy_inv, dz_inv)
    return [ [((b[0].x - bb.min.x) * dx_inv).floor, 0].max,
             [((b[1].x - bb.min.x) * dx_inv).floor, @X_DIV - 1].min,
             [((b[0].y - bb.min.y) * dy_inv).floor, 0].max,
             [((b[1].y - bb.min.y) * dy_inv).floor, @Y_DIV - 1].min,
             [((b[0].z - bb.min.z) * dz_inv).floor, 0].max,
             [((b[1].z - bb.min.z) * dz_inv).floor, @Z_DIV - 1].min ]
  end
  
  def self.getFacePairs(gc, gc_bb, gg, gg_bb)
    bb, g0bb, g1bb = getBBFaces(gc, gc_bb, gg, gg_bb)
    return extractFacePairs(bb, g0bb, g1bb)
  end
  
  ###################
  ###### CUT ########
  ###################
  
  def self.intersectFacePairs(ent, g0tr, g1tr, fp, gg)
    t0 = Time.now
      
    #organize the face pairs - for a given face in g0 (f0), find all faces in g1 that are to
    #be cut by f0.
    gfh = {}
    fp.each { |pair|
      if gfh.has_key?(pair[0])
        gfh[pair[0]] << pair[1]
      else
        gfh[pair[0]] = [pair[1]]
      end
    }
    
    ng0 = ent.add_group
    ng1 = ent.add_group
    idt = Geom::Transformation.new 
    
    #The resulting cut edges are distributed over multiple groups which are exploded into the
    #main group (gg). Many small explosions is faster and produces better merge (for some unknown reason).
    res_gs = []
    (0..12).each { |i| res_gs << ent.add_group }
   
    t1 = Time.now
    i = 0
    gfh.each_key { |fg0|
      f0 = copyFaceToGroup(ng0, fg0, g0tr)

      gfh[fg0].each { |fg1|    
        f1 = copyFaceToGroup(ng1, fg1, g1tr)          
        es0 = ng0.entities.intersect_with(false, idt, res_gs[(i += 1) % res_gs.length], idt , true, ng1)
        
        #make a second reversed cut if deemed necessary (this takes care of coplanarity)
        #es0.length == 0 => possible touchcut i.e where a face edge cuts another face.
        if es0.length == 0 || coplanar?(f0, f1)
          ng1.entities.intersect_with(false, idt, res_gs[(i += 1) % res_gs.length], idt , true, ng0)
        end
        ng1.entities.clear!     
      }
      ng0.entities.clear!
    }
    t2 = Time.now
    #explode the resulting edges into gg
    res_gs.each { |res_g| add(gg, res_g) if res_g.entities.length > 0; res_g.erase! }
    t3 = Time.now
    ng0.erase!
    ng1.erase!
   
    if @VERBOSE
      puts formatString('Intersect:', 20) + (t3 - t0).to_s+' s'
      puts formatString('    Adm:',   20) + (t1 - t0).to_s+' s'
      puts formatString('    Cut:',   20) + (t2 - t1).to_s+' s'
      puts formatString('    Exp:',   20) + (t3 - t2).to_s+' s'
    end
  end
  
  def self.copyFaceToGroup(g, f, tr)
    f0 = g.entities.add_face(f.outer_loop.vertices.map { |v| v.position.transform tr })
    f.loops.each { |l|
      next if l.outer?
      f1 = g.entities.add_face(l.vertices.map { |v| v.position.transform tr })
      f1.erase! if f1 != nil
    }
    return f0
  end
 
  def self.coplanar?(f0, f1)
    return false if f0.normal.dot(f1.normal).abs < 0.999
    vs = (f0.vertices + f1.vertices)
    pl = Geom::fit_plane_to_points vs  
    return vs.all? { |v| v.position.on_plane? pl }
  end
  
  def self.add(g0, g1)
    ng = g0.entities.add_instance(g1.entities.parent, g1.transformation * g0.transformation.inverse)
    g1.entities.clear!
    ng.explode
  end

  ###################
  ###### DIV ########
  ###################
  
  #There's a bug in the api which prevents a group's BB to update
  #if its geoemtry is scaled within a start_operation/commit,
  #thus, if scale is used prior to cut, then scaled bb:s must be
  #provided explicitly.
  def self.cutBB(ent, cg, gg, cg_bb, gg_bb)
    @id_count = 0
    preProcess(gg)
    gg_bb = addDimension(gg_bb)
    fp = getFacePairs(cg, cg_bb, gg, gg_bb)
    intersectFacePairs(ent, cg.transformation, gg.transformation, fp, gg)
  end
  
  #This is the main method!!
  def self.cut(ent, cg, gg)
    @id_count = 0
    gg_bb = gg.bounds
    cg_bb = cg.bounds
    cutBB(ent, cg, gg, cg.bounds, gg.bounds)    
  end
 
  ###################
  ####### AUX #######
  ###################
  
  def self.addDimension(bb)
    bb2 = Geom::BoundingBox.new
    p0 = Geom::Point3d.new(bb.max.x + 1, bb.max.y + 1, bb.max.z + 1)
    p1 = Geom::Point3d.new(bb.min.x - 1, bb.min.y - 1, bb.min.z - 1)
    bb2.add(p0)
    bb2.add(p1)
    return bb2
  end
  
  #scale the geometry in g and create a new bounding box reflecting the new size.
  #Due to a bug in the api g's native bb does not update if the operation is
  #performed within a start/commit operation.
  def self.scale(g, s, pfix_w)
    bb = g.bounds
    bb_min = bb.min.transform(g.transformation.inverse)
    bb_max = bb.max.transform(g.transformation.inverse)
    
    pfix_g = pfix_w.transform(g.transformation.inverse)
    tr = Geom::Transformation.scaling(pfix_g, s, s, s)
    g_ents = g.entities.grep(Sketchup::Face) + g.entities.grep(Sketchup::Edge).select{|e| e.faces.length == 0}
    g.entities.transform_entities(tr, g_ents)
    
    bb_min.transform!(tr)
    bb_max.transform!(tr)
    nbb = Geom::BoundingBox.new
    nbb.add(bb_min.transform(g.transformation))
    nbb.add(bb_max.transform(g.transformation))
    return nbb
  end  

  def self.formatString(s, len) 
    sp = ''
    (0..(len - s.length - 1)).each { |i| sp += ' ' }
    return s + sp
  end

  
  ##################
  #### MAIN ########
  ##################
   
  def self.main
  
    mod = Sketchup.active_model
    ent = mod.entities
    sel = mod.selection
    
    mod.start_operation("Cut", true) 
    t0 = Time.now
    gs = sel.grep(Sketchup::Group)
    cg = gg = nil
    if (gs[0].bounds.max.y - gs[0].bounds.min.y).abs > (gs[1].bounds.max.y - gs[1].bounds.min.y).abs   
      cg = gs[0]
      gg = gs[1]
    else
      cg = gs[1]
      gg = gs[0]
    end
    
    preProcess(gg)
    cg.erase!
    mod.commit_operation
    t1 = Time.now
    
    puts 'TOTAL '+(t1- t0).to_s
  end
  
  #main
  
end
end
