################################################################
#
# Name:          Shellify
# Version:       1.3
# Description:   Extracts the shell of a near solid. Removes internal geometry and external flaps. 
#                Corrects orientation of faces. No geometry is added. 
#
# Author:        CAUL
#
# Usage:         1) Select a group
#                2) Choose Shellify from the plugin menu
#
# 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 now replaced
#
# Issues:
#                - a vertex is present twice in some face loop -> the algo may break                               
#                - if start_face is a flap -> unpredictable results
#
################################################################


require 'sketchup'

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 face attached to this vertex with maximum |z| normal component
  # 3) reverse the 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_f = max_z.faces[0]
    max_z.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

  #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)  
    p  = edge.reversed_in?(face) ? [0, 1] : [1, 0]
    return (edge.vertices[p[0]].position - edge.vertices[p[1]].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 directions 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 all processed edges 
    shell_h = Hash.new #final shell

    #push start face
    front_q.push(start_face)
    front_h[start_face] = nil
  
    #stats
    loop_count_stat = 0

    while front_q.length > 0 do 
    
      face = front_q.pop
      shell_h[face] = nil
       
      face.loops.each { |loop|
        loop.edges.each { |e|
        
          loop_count_stat += 1
        
          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)
                
            #add to front_q unless it's already present
            unless front_h.has_key?(f1)  
              front_q.push(f1)
              front_h[f1] = nil
            end
          end#end if
        
        }#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 shell_h
    fs = group.entities.grep(Sketchup::Face)
    fs.each {|f| f.erase! unless shell_h.has_key?(f)}
    
    #delete 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
  
    mod = Sketchup.active_model
    ent = mod.entities
    sel = mod.selection
    
    replace_original = true
    
    if sel.length == 1 && sel.first.is_a?(Sketchup::Group)  
      
      mod.start_operation("shellify")      
      
      new_group = sel.first.copy
      new_group.move!(Geom::Transformation.new(sel.first.bounds.corner(1))) unless replace_original
      
      #extract shell from the outside (-> remove internal geometry)
      constructShell(new_group, true)
      
      #extract shell from the inside (-> remove external flaps)
      constructShell(new_group, false)
      
      sel.first.erase! if replace_original
      sel.add new_group
      
      mod.commit_operation
    end
  end
  
  unless file_loaded?( __FILE__ )
    menu = UI.menu( 'Plugins' )
    menu.add_item( 'Shellify' ) { self.shellify }
  end

  file_loaded( __FILE__ )
  
  shellify 
  
end