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

module CAUL_FAQS

  #Given a ray, return the intersection point and face.
  class FaceHash
    
    #fh is a hash table with faces as key and grid position as
    #data.
    def initialize(fh)

      @fh = fh
      @bb = computeBB(fh)
      @bb_max = @bb.max.clone
      @bb_min = @bb.min.clone
      
      @EPSILON = 0.001
      @E_VE_POS = Geom::Vector3d.new(@EPSILON, @EPSILON, @EPSILON)
      @E_VE_NEG = Geom::Vector3d.new(-@EPSILON, -@EPSILON, -@EPSILON)
      @bb_max.offset!(@E_VE_POS)
      @bb_min.offset!(@E_VE_NEG)
      
      @DIVS = 20
      @X_DIV = (@bb_max.x - @bb_min.x) > @EPSILON ? @DIVS : 1  
      @Y_DIV = (@bb_max.y - @bb_min.y) > @EPSILON ? @DIVS : 1
      @Z_DIV = (@bb_max.z - @bb_min.z) > @EPSILON ? @DIVS : 1
      
      @dx_inv = @X_DIV > 1 ? 1.0 / ((@bb_max.x - @bb_min.x) / @X_DIV) : 1.0 
      @dy_inv = @Y_DIV > 1 ? 1.0 / ((@bb_max.y - @bb_min.y) / @Y_DIV) : 1.0
      @dz_inv = @Z_DIV > 1 ? 1.0 / ((@bb_max.z - @bb_min.z) / @Z_DIV) : 1.0
          
      #create the 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 faces to hash
      @fh.each_key { |f| 
        inds = getBounds(f.bounds.min, f.bounds.max)
        (inds[0]..inds[1]).each { |i|  
          (inds[2]..inds[3]).each { |j| 
            (inds[4]..inds[5]).each { |k|
              @sh[i][j][k] << f 
        }}}}
        
        #construct some temps...
        @ray_p0 = Geom::Point3d.new
        @ray_p1 = Geom::Point3d.new
        @ray_bb_min = Geom::Point3d.new
        @ray_bb_max = Geom::Point3d.new
      end
       
      def computeBB(fh)
        bb = Geom::BoundingBox.new()
        fh.each_key { |f|
          f.outer_loop.vertices.each { |v|
            bb.add(v.position)
        }}
        return bb
      end
       
      def getBounds(in_bb_min, in_bb_max)
        return [ [((in_bb_min.x - @bb_min.x) * @dx_inv).floor, 0].max,
                 [((in_bb_max.x - @bb_min.x) * @dx_inv).floor, @X_DIV - 1].min,
                 [((in_bb_min.y - @bb_min.y) * @dy_inv).floor, 0].max,
                 [((in_bb_max.y - @bb_min.y) * @dy_inv).floor, @Y_DIV - 1].min,
                 [((in_bb_min.z - @bb_min.z) * @dz_inv).floor, 0].max,
                 [((in_bb_max.z - @bb_min.z) * @dz_inv).floor, @Z_DIV - 1].min ]
      end
      
      def getFaces(in_bb_min, in_bb_max)
        res = {}
        inds = getBounds(in_bb_min, in_bb_max)
        (inds[0]..inds[1]).each { |i|  
          (inds[2]..inds[3]).each { |j| 
            (inds[4]..inds[5]).each { |k|
              @sh[i][j][k].each { |f| 
                res[f] = nil  
        }}}}
        return res
      end
      
      #given a ray [point, vector], return the ray's two intersection points on the
      #main bounding box. The purpose is to minimize the ray's bb; this in turn will
      #minimize potential intersecting faces in the space hash (which works on bb:s)
      def cutRay(ray)
        tmin = -Float::MAX
        tmax =  Float::MAX
        
        if ray[1].x != 0
          x_inv = 1.0 / ray[1].x
          tx1 = (@bb_min.x - ray[0].x) * x_inv 
          tx2 = (@bb_max.x - ray[0].x) * x_inv
          tmin = tx1 < tx2 ? (tx1 > tmin ? tx1 : tmin) : (tx2 > tmin ? tx2 : tmin)   
          tmax = tx1 > tx2 ? (tx1 < tmax ? tx1 : tmax) : (tx2 < tmax ? tx2 : tmax)
        end
        
        if ray[1].y != 0
          y_inv = 1.0 / ray[1].y
          ty1 = (@bb_min.y - ray[0].y) * y_inv 
          ty2 = (@bb_max.y - ray[0].y) * y_inv
          tmin = ty1 < ty2 ? (ty1 > tmin ? ty1 : tmin) : (ty2 > tmin ? ty2 : tmin)   
          tmax = ty1 > ty2 ? (ty1 < tmax ? ty1 : tmax) : (ty2 < tmax ? ty2 : tmax)
        end
        
        if ray[1].z != 0
          z_inv = 1.0 / ray[1].z
          tz1 = (@bb_min.z - ray[0].z) * z_inv 
          tz2 = (@bb_max.z - ray[0].z) * z_inv
          tmin = tz1 < tz2 ? (tz1 > tmin ? tz1 : tmin) : (tz2 > tmin ? tz2 : tmin)   
          tmax = tz1 > tz2 ? (tz1 < tmax ? tz1 : tmax) : (tz2 < tmax ? tz2 : tmax)
        end
        
        return nil, nil if tmin > tmax
        @ray_p0.set!(ray[0].x + ray[1].x * tmin, ray[0].y + ray[1].y * tmin, ray[0].z + ray[1].z * tmin)
        @ray_p1.set!(ray[0].x + ray[1].x * tmax, ray[0].y + ray[1].y * tmax, ray[0].z + ray[1].z * tmax) 
        return @ray_p0, @ray_p1
      end
      
      def getPoint(ray)
      
        #minimize the ray as much as possible
        p0, p1 = cutRay(ray)
        return nil if p0 == nil
        
        #computeRayDivision(p0, p1)
     
        #compute ray's bb
        @ray_bb_min.x = p0.x < p1.x ? p0.x : p1.x 
        @ray_bb_min.y = p0.y < p1.y ? p0.y : p1.y
        @ray_bb_min.z = p0.z < p1.z ? p0.z : p1.z
        @ray_bb_max.x = p0.x > p1.x ? p0.x : p1.x
        @ray_bb_max.y = p0.y > p1.y ? p0.y : p1.y
        @ray_bb_max.z = p0.z > p1.z ? p0.z : p1.z
        
        #Add some slack to bb
        @ray_bb_max.offset!(@E_VE_POS)
        @ray_bb_min.offset!(@E_VE_NEG)

        #extract potential intersections
        fs = getFaces(@ray_bb_min, @ray_bb_max)
       
        #find all intersection points (usually only one..)
        ps_ints = []
        fs_ints = []
        fs.each_key { |f| 
          p_int = Geom::intersect_line_plane(ray, [f.vertices[0].position, f.normal]) 
          cl = f.classify_point(p_int)
          unless f.classify_point(p_int) == Sketchup::Face::PointOutside
            ps_ints << p_int
            fs_ints << f
          end
        }
        
        return nil, nil, nil, nil if ps_ints.length == 0
        
        #pick the closest intersection point (normally we have only one intersection)
        min_ind = 0
        min_dist = Float::MAX
        #pick the closest intersection point
        (1..ps_ints.length - 1).each { |i|
          d = ray[0].distance(ps_ints[i])
          if d < min_dist
            min_ind = i
            min_dist = d
          end
        }
        
        f = fs_ints[min_ind]
        a = @fh[f]
        u_ind = a[0]
        v_ind = a[1]
        return ps_ints[min_ind], f, u_ind, v_ind
      end
      
  end
end
