################################################################
#
# Name:          Shellify
# Version:       1.5 (2013 17 12)
# 
# Description:   1) Extracts the shell of a near solid. Removes internal geometry and external flaps. 
#                   Corrects orientation of faces. No geometry is added.
#                2) Intersects arbitraly many groups and merges the result into one group.
# 
# Author:        Anders Lyhagen 
#
# Usage:         Menu Shellify under Plugins
#                
#                1) (Shellify) If exactly one group is selected, the group is shellyfied
#                2) (Shellify) If many groups are selected, the groups are first intersected and the
#                   result is shellified
#                3) (Cut) Intersects arbitraly many groups and merges the result into one group. 
#
# History:       1.0 - First version
#                1.1 - The script is undoable in one step
#                1.2 - smooth etc preserved. Minor bugs fixed. Performance improved. Orignal group
#                      is now unaffected.
#                1.3 - original group replaced
#                1.4 - improved startface picking
#                1.5 - Cut added
# Issues:                              
#                - if start_face is a flap -> unpredictable results
#
################################################################

require 'sketchup'

module CAUL_Cut

  #return scale for max_diagonal = 25m or 1 if the max group is already bigger than 25m
  def self.getScale(gs)
    max = -1
    gs.each { |g| max = g.bounds.diagonal if g.bounds.diagonal > max }
    return max < 1000 ? 1000 / max : 1
  end
  
  def self.scaleGroups(gs, s)
    tr = Geom::Transformation.scaling([0,0,0], s, s, s)
    gs.each { |g| g.transform! tr }
  end
  
  def self.scaleGroup(g0, s)
    g0.transform! Geom::Transformation.scaling([0,0,0], s, s, s) if g0 != nil
  end
  
  def self.mergeGroups(ent, g0, g1)
    ng = ent.add_group
    ng.entities.add_instance(g0.entities.parent, g0.transformation)
    ng.entities.add_instance(g1.entities.parent, g1.transformation)
    g0.erase!
    g1.erase!
    nt1 = ng.entities[0]
    nt2 = ng.entities[1]
    nt1.explode
    nt2.explode
    return ng 
  end
  
  #delete edges with no faces attached
  def self.deleteStrayEdges(group)
    es = group.entities.grep(Sketchup::Edge)
    es.each {|e| e.erase! if !e.deleted? && e.faces.length == 0}
  end
  
  #return an array with [face, vertex] pairs where the vertex is present twice in the face loop
  def self.getDoubleVertexFaces(group)
    fs = group.entities.grep(Sketchup::Face)
    v_hash = Hash.new
    p_arr = []
  
    fs.each { |f| 
      v_hash.clear
      f.outer_loop.vertices.each { |v|
        if v_hash.has_key?(v)
          p_arr.push([f, v])
          break
        end
       
        v_hash[v] = nil
      }
    }
    return p_arr
  end

  #split the face at the vertex
  def self.splitFace(face, vertex)

    es = face.outer_loop.edges
    ind = 0
    es.each { |e| 
      break if (e.vertices[0] == vertex && e.reversed_in?(face)) ||
               (e.vertices[1] == vertex && !e.reversed_in?(face))
      ind += 1
    }
    face.erase!
    es[ind].find_faces
    es[(ind + 1) % es.length].find_faces
  end
  
  #Split all faces that have a vertex appearing twice in the face loop
  def self.splitFaces(group)
    p_arr = getDoubleVertexFaces(group)
    p_arr.each{ |a| splitFace(a[0], a[1]) }
  end
  
  #add all edges in g0 to g1. This resolves intersections with
  #coplanar faces that aren't dealt with very well by intersect_with.
  def self.addEdges(ent, g0, g1)
    e_group = ent.add_group
    es = g0.entities.grep(Sketchup::Edge)
    es.each { |e| e_group.entities.add_line(e.vertices[1].position, e.vertices[0].position) }
    e_group.transform!(g0.transformation)
    ng = mergeGroups(ent, g1 , e_group)
    deleteStrayEdges(ng)
    return ng
  end
  
  def self.intersect(ent, g0, g1)
     eg = ent.add_group
     g0.entities.intersect_with false, g0.transformation, eg , g1.transformation , true, g1
     return eg
  end
  
  def self.cutGroupPair(ent, g0, g1)
    
    g11 = addEdges(ent, g0, g1)
    g00 = g0 #...rename in case we want to duplicate the step above with (ent, g11, g0)
    ge = intersect(ent, g00, g11)
    
    #add the intersection edges to both groups
    ge.entities.each { |e| g11.entities.add_line(e.vertices[1].position, e.vertices[0].position) }
    ents = [] #transform the cut edges....
    ge.entities.each { |e| ents.push(e) }
    ge.entities.transform_entities(g00.transformation.inverse, ents)
    ents.each { |e| g00.entities.add_line(e.vertices[1].position, e.vertices[0].position) } 
    ge.erase!
    
    splitFaces(g00)
    splitFaces(g11)
    
    #collect a face hash for group 1
    g11_hash = Hash.new()
    g11.entities.each{ |f| g11_hash[f] = nil if f.is_a?(Sketchup::Face) }
    
    return mergeGroups(ent, g11, g00), g11_hash
  end

  def self.cutGroups(ent, gs)
    return nil, nil if gs.length < 2
    
    scale = getScale(gs)
    scaleGroups(gs, scale)
  
    ng = gs[0]
    for i in 1..gs.length - 1
        ng, g1_face_hash = cutGroupPair(ent, gs[i], ng)
    end
    
    scaleGroup(ng, 1 / scale)
    
    return ng, g1_face_hash
  end

end

module CAUL_Shellify

  #Pick a start face on the shell:
  # 1) Pick the vertex with max z component (ignore edges with no faces attached)
  # 2) pick the edge attached least aligned with the z axis
  # 3) pick the face attached to this edge with maximum |z| normal component
  # 4) reverse face if necessary
  def self.getStartFace(group, outside)
    vs = group.entities.grep(Sketchup::Edge).map{|e| e.vertices}.flatten!.uniq!.find_all{|v| v.faces.length > 0}
    
    max_z = vs[0]
    vs.each { |v| max_z = v if v.position.z > max_z.position.z }
    
    max_e = max_z.edges[0]
    max_z.edges.each { |e| max_e = e if getNormZComp(e) < getNormZComp(max_e) }

    max_f = max_e.faces[0]
    max_e.faces.each { |f| max_f = f if f.normal.z.abs > max_f.normal.z.abs }
    
    return outside ? (max_f.normal.z < 0 ? max_f.reverse! : max_f) :
                     (max_f.normal.z > 0 ? max_f.reverse! : max_f)
  end
  
  def self.getNormZComp(edge)
    return (edge.vertices[0].position - edge.vertices[1].position).normalize!.z.abs
  end
  
  #the edges is known to have two faces, return the face that is not the parameter
  def self.getTheOtherFace(edge, face)
    return edge.faces[0] == face ? edge.faces[1] : edge.faces[0]  
  end

  #construct a vector along the edge in the face's loop direction
  def self.getEdgeVector(edge, face)  
    return edge.reversed_in?(face) ? (edge.vertices[0].position - edge.vertices[1].position) :
                                     (edge.vertices[1].position - edge.vertices[0].position) 
  end

  #given an edge with multiple faces (>2) and a face belonging to the 
  #shell (and the edge), pick the other face belonging to the shell.
  #This is done by compairing angles (while being aware of directions).
  def self.getShellFace(edge, face)
    
    c_e = getEdgeVector(edge, face) 
    c_n = face.normal 
    c_p = c_e.cross(c_n).reverse
    c_dir = edge.reversed_in?(face)
      
    #min assignments
    min_a = Math::PI * 2
    shell_face = nil
  
    #Deal with a special case where the edge crosses the face from the 
    #boundary to an internal hole. The face then becomes attached 
    #twice to the edge which makes the face loop direction ambiguous. 
    #..if this happens nil is returned. (the algo produces strange results here)
    self_count = 0
  
    edge.faces.each { |f|
        
      unless f == face
       
        t_n = edge.reversed_in?(f) == c_dir ? f.normal.reverse : f.normal                                               
        t_p = c_e.cross(t_n)
        a = t_p.dot(c_n) < 0 ? (Math::PI * 2) - c_p.angle_between(t_p) :
                                                c_p.angle_between(t_p)                                            
        if a < min_a
          min_a = a
          shell_face = f
        end
      else
        self_count += 1
        break if self_count > 1
      end
    }
   
    return self_count > 1 ? nil : c_dir == edge.reversed_in?(shell_face) ? shell_face.reverse! : shell_face
  end

  def self.getShell(start_face)

    front_q = Array.new #shell faces with untested neighbour faces
    front_h = Hash.new  #hash with processed faces
    edge_h = Hash.new   #Hash with processed edges 
    shell_h = Hash.new  #final shell

    #push start face
    front_q.push(start_face)
    front_h[start_face] = nil
  
    while front_q.length > 0 do 
    
      face = front_q.pop
      shell_h[face] = nil
       
      face.loops.each { |loop|
        loop.edges.each { |e|
        
          if !edge_h.has_key?(e) && e.faces.length > 1 
            
            edge_h[e] = nil #add the edge to the hash
            
            f1 = e.faces.length == 2 ? getTheOtherFace(e, face) :
                                       getShellFace(e, face) 
          
            next if f1 == nil #special case, see getShellFace
          
            f1.reverse! if e.reversed_in?(face) == e.reversed_in?(f1)
            
            unless front_h.has_key?(f1)  
              front_q.push(f1)
              front_h[f1] = nil
            end
          end
        
        }#end single loop
      }#end loops
    end#end outer while
  
    return shell_h
  end

  def self.mergeCoPlanarFaces(group)
  
    #filter out potential coplanar faces
    edges = group.entities.grep(Sketchup::Edge).select{|e| e.faces.length == 2 && 
                                e.faces[0].normal.dot(e.faces[1].normal) > 0.99990}
  
    edges.each { |e|
      #the number of faces may change as we erase edges
      if !e.deleted? && e.faces.length < 2
        e.erase!
      elsif !e.deleted?  
        vs = e.faces[0].vertices + e.faces[1].vertices
        p = Geom::fit_plane_to_points vs
        cop = vs.all? { |v| v.position.on_plane? p }
        e.erase! if cop
      end
    }
  end
  
  def self.reduceShellInGroup(shell_h, group)
    #delete faces not selected for inclusion in shell_h
    fs = group.entities.grep(Sketchup::Face)
    fs.each {|f| f.erase! unless shell_h.has_key?(f)}
    
    #delete remaining stray edges
    es = group.entities.grep(Sketchup::Edge)
    es.each {|e| e.erase! if !e.deleted? && e.faces.length == 0}
  end

  def self.reverseAll(group)
    group.entities.grep(Sketchup::Face).each {|f| f.reverse! }
  end
 
  def self.constructShell(group, outside)
    start_face = getStartFace(group, outside)
    shell_h = getShell(start_face)
    reduceShellInGroup(shell_h, group)
    mergeCoPlanarFaces(group)
    reverseAll(group) unless outside
  end
  
  def self.shellify(group)
    #extract shell from the outside (-> remove internal geometry)
    constructShell(group, true)
     
    #extract shell from the inside (-> remove external geometry)
    constructShell(group, false)
  end
end


module CAUL_ShellifyMain

  def self.shellifyMain(mode)
  
    mod = Sketchup.active_model
    ent = mod.entities
    sel = mod.selection
    
    gs = sel.grep(Sketchup::Group)
    
    return nil if gs.length == 0
    
    mod.start_operation("shellify") 
    if mode == 0 #shellify
      if gs.length == 1
        CAUL_Shellify::shellify(gs[0])
      else
        ng, h = CAUL_Cut::cutGroups(ent, gs)
        CAUL_Shellify::shellify(ng)
        sel.add ng
      end
    elsif mode == 1 #cut
      if gs.length > 1
        ng, h = CAUL_Cut::cutGroups(ent, gs)
        sel.add ng
      end
    end
    mod.commit_operation  
  end
  
  unless file_loaded?( __FILE__ )
    menu = UI.menu( 'Plugins' )
    sub = menu.add_submenu('Shellify')
    sub.add_item( 'Shellify' ) { self.shellifyMain 0}
    sub.add_item( 'Cut' ) { self.shellifyMain 1}
  end

  file_loaded( __FILE__ )
  
  shellifyMain 0
 
end