import math

class vector:
    """ This class has all functions related to 3d vectors!"""
    def __init__(self, i, j, k):
        self.i=i
        self.j=j
        self.k=k

    def dot(self, v):
        return self.i*v.i + self.j*v.j + self.k*v.k

    def cross(self, v):
        return vector(self.j*v.k-self.k*v.j,
                  self.k*v.i-self.i*v.k,
                  self.i*v.j-self.j*v.i )
    def norm(self):
        return math.sqrt(self.i*self.i+self.j*self.j+self.k*self.k)

    def normalize(self):
        norm = 1/self.norm()
        self.i=self.i*norm
        self.j=self.j*norm
        self.k=self.k*norm

    def sub(self, a):
        return vector(self.i-a.i, self.j-a.j, self.k-a.k)

    def smult(self, s):
        self.i*=s
        self.j*=s
        self.k*=s

    def invert(self):
        self.smult(-1)

    def printv(self):
        print self.i, self.j, self.k

class Light:
    def __init__(self, origin, intensity):
        self.origin=origin
        self.intensity=intensity

class Sphere:
    def __init__(self, origin, radius, color):
        self.origin=origin
        self.radius=radius
        self.color=color

    def find_normal(self, point):
        normal=point.sub(self.origin)
        normal.normalize()
        return normal

    def find_reflection(self, point, ray): #R = V - ( 2 * V [dot] N ) N
        normal=self.find_normal(point)
        normal.smult(ray.dir.dot(normal)*2)
        return Ray(point, ray.dir.sub(normal))


class Ray:
    def __init__(self, origin, direction):
        self.origin=origin
        self.dir=direction
        self.dir.normalize()

    def sphere_intersect(self, sphere):
        translRay=Ray(self.origin.sub(sphere.origin), self.dir) #translate ray, to have sphere at 0,0,0

        a=self.dir.dot(self.dir)

        b=2*translRay.origin.dot(translRay.dir)

        c=translRay.origin.dot(translRay.origin)-sphere.radius*sphere.radius

        discr=b*b-4*a*c #discriminate of quadratic equation

        if(discr<0): #no intersect
            return -1.

        discr=math.sqrt(discr)
        a*=2
        t0=(-b+discr)/a
        t1=(-b-discr)/a

        if(t1<t0):
            t0=t1

        return t0

    def sphere_intersect_point(self, t):
        v=vector((self.dir.i*t+self.origin.i),(self.dir.j*t+self.origin.j), (self.dir.k*t+self.origin.k))
        return v

    def find_near(self, objects):
        dist=-1
        for obj in objects:
            t=self.sphere_intersect(obj)
            if(t>0 and (t<dist or dist<0) ):
                dist=t
                closest=obj
        if(dist<0):
            closest=0

        return (closest, self.sphere_intersect_point(dist) )

    def find_light(self, objects, closest, point, lights):
        intensity=0
        for light in lights:
            ray = Ray(point, light.origin.sub(point))
            intersect=ray.find_near(objects)
            if(intersect[0] == 0): #not in shadow
                normal=closest.find_normal(intersect[1])
                proj=normal.dot(ray.dir)*closest.color*light.intensity
                if(proj>0):
                    intensity += proj

        return intensity



class Pixel:
    def __init__(self, ray):
        self.ray=ray
        self.color=0
        self.recursions=0

    def trace(self, objects, lights):
        near=self.ray.find_near(objects)
        if(near[0]!=0 and self.recursions<1):
            tmp=self.ray.find_light(objects, near[0], near[1], lights)
            #print(tmp, end=" ")
            self.color+=tmp
            self.ray=near[0].find_reflection(near[1], self.ray)
            self.recursions+=1
            self.trace(objects, lights)

    def traceS(self, objects, lights):
        near=self.ray.find_near(objects)
        if(near[0]!=0):
            self.color=near[0].color



class Camera:
    def __init__(self, ypix, zpix, pixstep, origin, frameOffy, frameOffz):
        self.zpix=zpix
        self.ypix=ypix
        self.step=pixstep
        self.origin=origin
        self.offsety=frameOffy
        self.offsetz=frameOffz

        self.frame = []
        for i in range(zpix):
            for j in range(ypix):
                rOrigin=vector(0, j*pixstep+frameOffy, i*pixstep+frameOffz)

                rDir=rOrigin.sub( origin )
                rDir.normalize()

                self.frame.append(Pixel(Ray(rOrigin, rDir)))

        #for i in self.frame:
        #   i.ray.dir.print()

    def trace(self, objects, lights):
        for pixel in self.frame:
            pixel.trace(objects, lights)
    def traceS(self, objects, lights):
        for pixel in self.frame:
            pixel.traceS(objects, lights)

    def printc(self):
        print "P2"
        print "# Generated by python raytracer, by number2"
        print self.ypix, self.zpix
        print 256
        for i in range(self.zpix):
            for j in range(self.ypix):
                if(self.frame[i*self.ypix+j].color>1):
                    self.frame[i*self.ypix+j].color=1
                print int(math.ceil(255*self.frame[i*self.ypix+j].color)),
            print ''




def main():
    sphere=Sphere(vector(-20., 4, 0), 10., 1)
    lights=[]
    lights.append(Light(vector(0,8,5), .9))
    lights.append(Light(vector(0,-15,100), .5))
    lights.append(Light(vector(0,0,-40), .3))

    objList=[]
    objList.append(sphere)
    objList.append(Sphere(vector(-30, -8, 0), 10, 1))
    objList.append(Sphere(vector(-10, -6, 10), 4, 1))
    objList.append(Sphere(vector(-10, 0, 12), 2, 1))


    cam=Camera(100, 1000, .008, vector(5, 0, 5), -5, 1)
    cam.trace(objList, lights)

    cam.printc()

main()