float4 readCubeMap(samplerCUBE cm, float3 coord)		
{
	float4 color = texCUBElod( cm, float4(coord.xy, - coord.z,0) );
	return color;
}

float readDistanceCubeMap(samplerCUBE dcm, float3 coord)		
{
	float dist = texCUBElod(dcm, float4(coord.xy, - coord.z,0)).a;
	return dist;
}

#define MAX_LIN_ITERATIONCOUNT 50  //80
#define MIN_LIN_ITERATIONCOUNT 30  //60
#define SECANT_ITERATIONCOUNT 1
#define MAX_RAY_DEPTH 4

//#define METHOD1

void linearSearch(  float3 x, float3 R, float3 N, samplerCUBE mp,
					float2 minMax,					
                    out float3 p,
                    out float dl,
                    out float dp,
                    out float llp,
                    out float ppp)
{
 float3 Ra = abs(R), xa = abs(x);
 float xm =  max(max(xa.x,xa.y),xa.z);
 float Rm = max(max(Ra.x,Ra.y),Ra.z);
 float a = xm / Rm;
 
 int shootL = 0, shootP = 0;          
 bool found = false; 
 
 float min = minMax.x;
 float maximum = minMax.y;
 
 float minD = 0;
 float maxD = 0;
 {
  	float a = dot(R,R);
	float b = 2 * dot(R, x);
	float c = dot(x,x) - min * min; 
	float c2 = dot(x,x) - maximum * maximum; 
	
	float dis = b*b - 4*a*c;
	float dis2 = b*b - 4*a*c2;
	
	float t1 = (-b + sqrt(dis))/ 2.0 * a;
	float t2 = (-b - sqrt(dis))/ 2.0 * a;
    float t3 = (-b + sqrt(dis2))/ 2.0 * a;
	float t4 = (-b - sqrt(dis2))/ 2.0 * a;
	
	int numvalids = 0;
	if(t1 > 0)
	{
	 numvalids++;
	 if(t1 > maxD)maxD = t1;
	 if(t1 < minD || minD == 0)minD = t1;
	}
	if(t2 > 0)
	{
	 numvalids++;
	 if(t2 > maxD)maxD = t2;
	 if(t2 < minD || minD == 0)minD = t2;
	}
	if(t3 > 0)
	{
	 numvalids++;
	 if(t3 > maxD)maxD = t3;
	 if(t3 < minD || minD == 0)minD = t3;
	}
	if(t4 > 0)
	{
	 numvalids++;
	 if(t4 > maxD)maxD = t4;
	 if(t4 < minD || minD == 0)minD = t4;
	}
	
	if(numvalids % 2 == 1)
	 minD = 0.01;
	if(numvalids == 0)
	 minD = maxD + 1.0;	
 }
 
#ifdef METHOD1
 int iterationNeeded = MAX_LIN_ITERATIONCOUNT;// + (dot(normalize(x), R) + 1.0) / 2.0 * (MAX_LIN_ITERATIONCOUNT - MIN_LIN_ITERATIONCOUNT);
 float pa;
 float dD = (maxD - minD) / (float) iterationNeeded ;
 dp = minD; 
 
 //Linear iteration
 while(dp <= maxD && !found)
 {
	 
#else
 float dt =  length(x / xm - R / Rm) * MAX_LIN_ITERATIONCOUNT;
 dt = max(dt, MIN_LIN_ITERATIONCOUNT);
 dt = 1.0 / dt;
 
 float minT = max(minD / (a + minD) - dt, dt);
 float maxT = maxD / (a + maxD) + dt;
 
 float t = minT;//dt;
 float pa;
 
 while(t <= maxT && !found)
 {
	 dp = a * t / (1 - t);
#endif

   p = x + R * dp;
   pa = readDistanceCubeMap(mp, p);
      
   if(pa > 0)
   {
    ppp = length(p) / pa;
    if(ppp < 1)
      shootP = -1;
    else 
      shootP = 1;      
    if(shootL * shootP == -1)
      found = true;
    else
    {
      shootL = shootP;
      dl = dp;
      llp = ppp;
    }
   }
   else
     shootL = 0;
 
 #ifdef METHOD1     
   dp += dD; 
 #else 
   t += dt;
 #endif
 }

 if(!found)
  p = float3(0,0,0);
}


void secantSearch(float3 x, float3 R, samplerCUBE mp, 
	               float dl,
	               float dp,
	               float llp,
	               float ppp,
	               out float3 p)
{
  for(int i= 0; i < SECANT_ITERATIONCOUNT; i++)
  {
   float dnew;
   dnew = dl + (dp - dl) * (1 - llp) / (ppp - llp);
   p = x + R * dnew;
   half pppnew = length(p) / readDistanceCubeMap(mp, p);
   if(pppnew < 1)
   {
    llp = pppnew;
    dl = dnew;
   }
   else
   {
    ppp = pppnew;
    dp = dnew;
   }
  }
}


float3 Hit(float3 x, float3 R, float3 N, 
           samplerCUBE mp1,
           samplerCUBE mp2,
           samplerCUBE mp3Color,
           samplerCUBE mp3Dist,
           float2 minMax,
           float2 minMax1,
		   float2 minMax2,		   
           out float4 Il, out float3 Nl)
{
 float dl1 = 0, dp1, llp1, ppp1;
 float3 p1;
 linearSearch(x, R, N, mp1, minMax1, p1, dl1, dp1, llp1, ppp1);
 float dl2 = 0, dp2, llp2, ppp2;
 float3 p2;
 linearSearch(x, R, N, mp2, minMax2, p2, dl2, dp2, llp2, ppp2);
 
 bool valid1 = dot(p1,p1) != 0;
 bool valid2 = dot(p2,p2) != 0;
		
 float dl, dp, llp, ppp;
 float3 p;
 
 if(!valid1 && ! valid2)
 {
    linearSearch(x, R, N, mp3Dist, minMax, p, dl, dp, llp, ppp);
    if(dot(p,p) != 0)
    {
     Il.a = 1;    
     secantSearch(x, R, mp3Dist, dl, dp, llp, ppp, p);
     Il.rgb =  Nl.rgb = readCubeMap(mp3Color, p).rgb;  
    }
    else
     Il = float4(0,0,0,0);
 }
 else
 {
    if( !valid2 || (valid1 && dp1 < dp2))
    {
     secantSearch(x, R, mp1, dl1, dp1, llp1, ppp1, p1);
     Il.rgb =  Nl.rgb = readCubeMap(mp1, p1).rgb;
     p = p1;
    }
    else
    {
     secantSearch(x, R, mp2, dl2, dp2, llp2, ppp2, p2);
     Il.rgb =  Nl.rgb = readCubeMap(mp2, p2).rgb;
     p = p2;
    }    
 } 
 return p;
}

struct Shaded_OUT
{
 float4 vPos : POSITION;
 float4 wNormal : TEXCOORD0;
 float4 wPos    : TEXCOORD1; 
};


float4 MultipleReflectionPS(Shaded_OUT IN,
							uniform samplerCUBE CubeMap : register(s0),
							uniform samplerCUBE DistanceMap : register(s1),
							uniform samplerCUBE NormDistMap1 : register(s2),
							uniform samplerCUBE NormDistMap2 : register(s3),
							uniform float3 cameraPos,
							uniform float3 lastCenter,
							uniform float4 min,
							uniform float4 min1,
							uniform float4 min2,
							uniform float4 Max,
							uniform float4 max1,
							uniform float4 max2) : COLOR0
{
	float2 miniMaxi1;
    miniMaxi1.x = min.a;
    miniMaxi1.y = Max.a;
   
    float2 miniMaxi2;
    miniMaxi2.x = min1.a;
    miniMaxi2.y = max1.a;
   
    float2 miniMaxi3;
    miniMaxi3.x = min2.a;
    miniMaxi3.y = max2.a;
	 		
	 float3 N = normalize(IN.wNormal.xyz);
	 float3 x = IN.wPos.xyz - lastCenter;
	 float3 V  = (IN.wPos.xyz - cameraPos);
		 
	 float4 I = float4(0,0,0,0);
	 V = normalize(V);
	 float3 l;
	 int depth = 0;
	
	 while(depth < MAX_RAY_DEPTH)
	 {
	   float3 R;  
	   R = normalize(reflect( V, N));	  
	  	
	   float3 Nl;
	   float4 Il;
	   l = Hit(x, R, N, NormDistMap1, NormDistMap2, CubeMap, DistanceMap, miniMaxi1, miniMaxi2, miniMaxi3, Il, Nl);
	   if(Il.a == 0)
	   {
		   depth += 1;		 
	   }
	   else
	   {
		   I = Il;
		   depth = MAX_RAY_DEPTH;
	   }
	   x = l;	   
	   N = Nl;
	   V = R;   	   
	}
	if(I.a == 0)
	  I = readCubeMap(CubeMap, l);
	
	return I;
}

float4 MultipleRefractionPS(Shaded_OUT IN,
							uniform samplerCUBE CubeMap : register(s0),
							uniform samplerCUBE DistanceMap : register(s1),
							uniform samplerCUBE NormDistMap1 : register(s2),
							uniform samplerCUBE NormDistMap2 : register(s3),
							uniform float3 cameraPos,
							uniform float3 lastCenter,
							uniform float refIndex,
							uniform float sFresnel, //0.04 
							uniform float4 min,
							uniform float4 min1,
							uniform float4 min2,
							uniform float4 Max,
							uniform float4 max1,
							uniform float4 max2) : COLOR0
{
	float2 miniMaxi1;
    miniMaxi1.x = min.a;
    miniMaxi1.y = Max.a;
   
    float2 miniMaxi2;
    miniMaxi2.x = min1.a;
    miniMaxi2.y = max1.a;
   
    float2 miniMaxi3;
    miniMaxi3.x = min2.a;
    miniMaxi3.y = max2.a;

	float4 I = float4(0,0,0,0);
			
	 float3 N = normalize(IN.wNormal.xyz);
	 float3 x = IN.wPos.xyz - lastCenter;
	 float3 V  = (IN.wPos.xyz - cameraPos);
	  V = normalize(V);
	 
	 float F;
	 int depth = 0;
	F = sFresnel + pow(1 - dot(N, -V), 5) * (1 - sFresnel);	 
	
	while(depth < MAX_RAY_DEPTH)
	{
	  float3 R;  
	  	 
	  float ri = refIndex;	 
	  if(dot(V,N) > 0)
	  {
		ri = 1.0 / ri;
		N = -N;	    
	  }
	  R = refract( V, N, ri);
	  if(dot(R,R) == 0) R = reflect( V, N);
	  					
	  float3 Nl;
	  float4 Il;
	  float3 l = Hit(x, R, N, NormDistMap1, NormDistMap2, CubeMap, DistanceMap, miniMaxi1, miniMaxi2, miniMaxi3, Il, Nl);
	  if(Il.a == 0)
	  {
		  //I = readCubeMap(CubeMap, l);
		   depth += 1;		 
	  }
	  else
	  {
		   I = Il;
		   depth = MAX_RAY_DEPTH;
	  }
	  x = l;	   
	  N = normalize(Nl);
	  V = R;	   	   
	}  
	    
	I *= (1.0 - F);	
    
	return I;
}

float4 MultipleRefractionPhotonMap_PS(Shaded_OUT IN,
									uniform samplerCUBE DistanceMap : register(s0),
									uniform samplerCUBE NormDistMap1 : register(s1),
									uniform samplerCUBE NormDistMap2 : register(s2),
									uniform float3 cameraPos,
									uniform float3 lastCenter,
									uniform float refIndex,
									uniform float4 min,
									uniform float4 min1,
									uniform float4 min2,
									uniform float4 max,
									uniform float4 max1,
									uniform float4 max2) : COLOR0
{
	float2 miniMaxi1;
    miniMaxi1.x = min.a;
    miniMaxi1.y = max.a;
   
    float2 miniMaxi2;
    miniMaxi2.x = min1.a;
    miniMaxi2.y = max1.a;
   
    float2 miniMaxi3;
    miniMaxi3.x = min2.a;
    miniMaxi3.y = max2.a;

	float4 I = float4(0,0,0,0);
		 
	float3 N = normalize(IN.wNormal.xyz);
	float3 V  = (IN.wPos.xyz - cameraPos);
	float3 x = IN.wPos.xyz - lastCenter;
	V = normalize(V);
	float3 l;
	int depth = 0;
	
	while(depth < MAX_RAY_DEPTH)
	{
	  float3 R;  
	  
	  float ri = refIndex;
	 
	  if(dot(V,N) > 0)
	  {
		ri = 1.0 / ri;
		N = -N;	    
	  }
	  R = refract( V, N, ri);
	  if(dot(R,R) == 0) R = reflect( V, N); 
					
	  float3 Nl;
	  float4 Il;
	  l = Hit(x, R, N, NormDistMap1, NormDistMap2, DistanceMap, DistanceMap, miniMaxi1, miniMaxi2, miniMaxi3, Il, Nl);
	  if(Il.a == 0)
	  {
		   depth += 1;		 
	  }
	  else
	  {
		   I = Il;
		   depth = MAX_RAY_DEPTH;
	  }
	  x = l;	   
	  N = normalize(Nl);
	  V = R;	   	   
	}
	
	return float4(l,1);
}