import java.applet.*;
import java.awt.*;
import java.io.*;
import java.net.*;
import java.util.*;


///////////////////////////////////////////////////////
//  Travis Furrer
//  6.837 Project 5
//  December 4, 1998
///////////////////////////////////////////////////////
//   An instructional Ray-Tracing Renderer written
//  for MIT 6.837  Fall '98 by Leonard McMillan.
//
//   A fairly primitive Ray-Tracing program written
//   on a Sunday afternoon before Monday's class.
//   Everything is contained in a single file. The
//   structure should be fairly easy to extend, with
//   new primitives, features and other such stuff.
//
//   I tend to write things bottom up (old K&R C
//   habits die slowly). If you want the big picture
//   scroll to the applet code at the end and work
//   your way back here.
///////////////////////////////////////////////////////

// A simple vector class
class Vector3D {
    public float x, y, z;

    // constructors
    public Vector3D( ) {
    }

    public Vector3D(float x, float y, float z) {
        this.x = x; this.y = y; this.z = z;
    }

    public Vector3D(Vector3D v) {
        x = v.x;
        y = v.y;
        z = v.z;
    }

    // methods
    public final float dot(Vector3D B) {
        return (x*B.x + y*B.y + z*B.z);
    }

    public final float dot(float Bx, float By, float Bz) {
        return (x*Bx + y*By + z*Bz);
    }

    public static final float dot(Vector3D A, Vector3D B) {
        return (A.x*B.x + A.y*B.y + A.z*B.z);
    }

    public final Vector3D cross(Vector3D B) {
        return new Vector3D(y*B.z - z*B.y,
			    z*B.x - x*B.z,
			    x*B.y - y*B.x);
    }

    public final Vector3D cross(float Bx, float By, float Bz) {
        return new Vector3D(y*Bz - z*By,
			    z*Bx - x*Bz,
			    x*By - y*Bx);
    }

    public final static Vector3D cross(Vector3D A, Vector3D B) {
        return new Vector3D(A.y*B.z - A.z*B.y,
			    A.z*B.x - A.x*B.z,
			    A.x*B.y - A.y*B.x);
    }

    public final float length( ) {
        return (float) Math.sqrt(x*x + y*y + z*z);
    }

    public final static float length(Vector3D A) {
        return (float) Math.sqrt(A.x*A.x + A.y*A.y + A.z*A.z);
    }

    public final void normalize( ) {
        float t = x*x + y*y + z*z;
        if (t != 0 && t != 1) t = (float) (1 / Math.sqrt(t));
        x *= t;
        y *= t;
        z *= t;
    }

    public final static Vector3D normalize(Vector3D A) {
        float t = A.x*A.x + A.y*A.y + A.z*A.z;
        if (t != 0 && t != 1) t = (float)(1 / Math.sqrt(t));
        return new Vector3D(A.x*t, A.y*t, A.z*t);
    }

    public String toString() {
        return new String("["+x+", "+y+", "+z+"]");
    }
}


class Ray {
    public static final float MAX_T = Float.MAX_VALUE;
    Vector3D origin;
    Vector3D direction;
    float t;
    Renderable object;

    public Ray(Vector3D eye, Vector3D dir) {
        origin = new Vector3D(eye);
        direction = Vector3D.normalize(dir);
    }

    public boolean trace(Vector objects) {
        Enumeration objList = objects.elements();
        t = MAX_T;
        object = null;
        while (objList.hasMoreElements()) {
            Renderable object = (Renderable) objList.nextElement();
            object.intersect(this);
        }
        return (object != null);
    }

    // The following method is not strictly needed, and most likely
    // adds unnecessary overhead, but I prefered the syntax
    //
    //            ray.Shade(...)
    // to
    //            ray.object.Shade(ray, ...)
    //
    public final Color Shade(Vector lights, Vector objects, Color bgnd) {
        return object.Shade(this, lights, objects, bgnd);
    }

    public String toString() {
        return ("ray origin = "+origin+"  direction = "+direction+"  t = "+t);
    }
}

// All the public variables here are ugly, but I
// wanted Lights and Surfaces to be "friends"
class Light {
    public static final int AMBIENT = 0;
    public static final int DIRECTIONAL = 1;
    public static final int POINT = 2;

    public int lightType;
    public Vector3D lvec;           // the position of a point light or
                                    // the direction to a directional light
    public float ir, ig, ib;        // intensity of the light source

    public Light(int type, Vector3D v, float r, float g, float b) {
        lightType = type;
        ir = r;
        ig = g;
        ib = b;
        if (type != AMBIENT) {
            lvec = v;
            if (type == DIRECTIONAL) {
                lvec.normalize();
            }
        }
    }
}


class Surface {
    public float ir, ig, ib;        // surface's intrinsic color
    public float ka, kd, ks, ns;    // constants for phong model
    public float kt, kr, nt;
    private static final float TINY = 0.001f;
    private static final float I255 = 0.00392156f;  // 1/255

    public Surface(float rval, float gval, float bval,
		   float a, float d, float s, float n,
		   float r, float t, float index) {
        ir = rval; ig = gval; ib = bval;
        ka = a; kd = d; ks = s; ns = n;
        kr = r*I255; kt = t; nt = index;
    }

    public Color Shade(Vector3D p, Vector3D n, Vector3D v,
		       Vector lights, Vector objects, Color bgnd) {
        Enumeration lightSources = lights.elements();

        float r = 0;
        float g = 0;
        float b = 0;

	float t = 0;
	boolean inside;
	if ((kr > 0) || (kt > 0)) {
	    t = v.dot(n);
	}
	inside = (t < 0);

	//I'm not sure if this is the right thing to do, but it seems
	//to me that we shouldn't do any of this if the ray is coming
	//from inside.
	while (lightSources.hasMoreElements() && !inside) {
	//while (lightSources.hasMoreElements()) {
	    Light light = (Light) lightSources.nextElement();
	    if (light.lightType == Light.AMBIENT) {
		r += ka*ir*light.ir;
		g += ka*ig*light.ig;
		b += ka*ib*light.ib;
	    } else {
		Vector3D l;
		if (light.lightType == Light.POINT) {
		    l = new Vector3D(light.lvec.x - p.x,
				     light.lvec.y - p.y,
				     light.lvec.z - p.z);
		    l.normalize();
		} else {
		    l = new Vector3D(-light.lvec.x,
				     -light.lvec.y,
				     -light.lvec.z);
		}
		
		// Check if the surface point is in shadow
		Vector3D poffset = new Vector3D(p.x + TINY*l.x,
						p.y + TINY*l.y,
						p.z + TINY*l.z);
		Ray shadowRay = new Ray(poffset, l);
		if (shadowRay.trace(objects))
		    break;
		
		float lambert = Vector3D.dot(n,l);
		if (lambert > 0) {
		    if (kd > 0) {
			float diffuse = kd*lambert;
			r += diffuse*ir*light.ir;
			g += diffuse*ig*light.ig;
			b += diffuse*ib*light.ib;
		    }
		    if (ks > 0) {
			lambert *= 2;
			float spec = v.dot(lambert*n.x - l.x,
					   lambert*n.y - l.y,
					   lambert*n.z - l.z);
			if (spec > 0) {
			    spec = ks*((float) Math.pow((double) spec,
							(double) ns));
			    r += spec*light.ir;
			    g += spec*light.ig;
			    b += spec*light.ib;
			}
		    }
		}
	    }
	}

        // Compute illumination due to reflection (only if ray is
        // coming from outside)
        if ((kr > 0) && !inside) {
	    float myt = t*2;
	    Vector3D reflect = new Vector3D(myt*n.x - v.x,
					    myt*n.y - v.y,
					    myt*n.z - v.z);
	    Vector3D poffset = new Vector3D(p.x + TINY*reflect.x,
					    p.y + TINY*reflect.y,
					    p.z + TINY*reflect.z);
	    Ray reflectedRay = new Ray(poffset, reflect);
	    if (reflectedRay.trace(objects)) {
		Color rcolor = reflectedRay.Shade(lights, objects, bgnd);
		r += kr*rcolor.getRed();
		g += kr*rcolor.getGreen();
		b += kr*rcolor.getBlue();
	    } else {
		r += kr*bgnd.getRed();
		g += kr*bgnd.getGreen();
		b += kr*bgnd.getBlue();
	    }
        }

        // Compute illumination due to refraction
        if (kt > 0) {
	    float ntratio = 1;
	    //if ray is striking surface from inside object
	    if (inside) {
		ntratio = nt;
	    } else {
		ntratio = 1/nt;
	    }

	    //Note that t = cos(theta_i)
	    float term = ((float)Math.sqrt(1-ntratio*ntratio*(1-t*t))) -
		         ntratio*t;
	    Vector3D transmit = new Vector3D(-term*n.x-ntratio*v.x,
					     -term*n.y-ntratio*v.y,
					     -term*n.z-ntratio*v.z);
	    
  	    Vector3D poffset = new Vector3D(p.x + TINY*transmit.x,
  					    p.y + TINY*transmit.y,
  					    p.z + TINY*transmit.z);
  	    Ray transmittedRay = new Ray(poffset, transmit);
  	    if (transmittedRay.trace(objects)) {
  		Color rcolor = transmittedRay.Shade(lights, objects, bgnd);
  		r += kt*rcolor.getRed();
  		g += kt*rcolor.getGreen();
  		b += kt*rcolor.getBlue();
  	    } else {
		//This case is wierd and ideally never really happens.
  		r += kt*bgnd.getRed();
  		g += kt*bgnd.getGreen();
  		b += kt*bgnd.getBlue();
  	    }
        }

        r = (r > 1f) ? 1f : r;
        g = (g > 1f) ? 1f : g;
        b = (b > 1f) ? 1f : b;
        return new Color(r, g, b);
    }
}


// An object must implement a Renderable interface in order to
// be ray traced. Using this interface it is straight forward
// to add new objects
abstract interface Renderable {
    public abstract boolean intersect(Ray r);
    public abstract Color Shade(Ray r, Vector lights,
				Vector objects, Color bgnd);
    public String toString();
}

// An example "Renderable" object
class Sphere implements Renderable {
    Surface surface;
    Vector3D center;
    float radius;
    float radSqr;

    public Sphere(Surface s, Vector3D c, float r) {
        surface = s;
        center = c;
        radius = r;
        radSqr = r*r;
    }

    public boolean intersect(Ray ray) {
        float dx = center.x - ray.origin.x;
        float dy = center.y - ray.origin.y;
        float dz = center.z - ray.origin.z;
        float v = ray.direction.dot(dx, dy, dz);

        // Do the following quick check to see if there is even a chance
        // that an intersection here might be closer than a previous one
        if (v - radius > ray.t)
            return false;

        // Test if the ray actually intersects the sphere
        float t = radSqr + v*v - dx*dx - dy*dy - dz*dz;
        if (t < 0)
            return false;

        // Test if the intersection is in the positive
        // ray direction and it is the closest so far
        t = v - ((float) Math.sqrt(t));
        if ((t > ray.t) || (t < 0))
            return false;

        ray.t = t;
        ray.object = this;
        return true;
    }

    public Color Shade(Ray ray, Vector lights, Vector objects, Color bgnd) {
        // An object shader doesn't really do too much other than
        // supply a few critical bits of geometric information
        // for a surface shader. It must must compute:
        //
        //   1. the point of intersection (p)
        //   2. a unit-length surface normal (n)
        //   3. a unit-length vector towards the ray's origin (v)
        //
        float px = ray.origin.x + ray.t*ray.direction.x;
        float py = ray.origin.y + ray.t*ray.direction.y;
        float pz = ray.origin.z + ray.t*ray.direction.z;

        Vector3D p = new Vector3D(px, py, pz);
        Vector3D v = new Vector3D(-ray.direction.x,
				  -ray.direction.y,
				  -ray.direction.z);
        Vector3D n = new Vector3D(px - center.x,
				  py - center.y,
				  pz - center.z);
        n.normalize();

        // The illumination model is applied
        // by the surface's Shade() method
        return surface.Shade(p, n, v, lights, objects, bgnd);
    }

    public String toString() {
        return ("sphere "+center+" "+radius);
    }
}

//My own renderable object.
class Triangle implements Renderable {
    Surface surface;
    Vector3D a,b,c,ab,bc,ca;
    Vector3D normal;

    public Triangle(Surface s, Vector3D a, Vector3D b, Vector3D c) {
        surface = s;
        this.a = a;
        this.b = b;
        this.c = c;
	//Calculate the normal, assuming triangle vertices were given
	//in clockwise order when viewed from the "outside."
	ab = new Vector3D(b.x-a.x,
			  b.y-a.y,
			  b.z-a.z);
	ca = new Vector3D(c.x-a.x,
			  c.y-a.y,
			  c.z-a.z);
	bc = new Vector3D(c.x-b.x,
			  c.y-b.y,
			  c.z-b.z);
	normal = Vector3D.cross(ca,ab);
	ca.x = -ca.x;
	ca.y = -ca.y;
	ca.z = -ca.z;
	normal.normalize();
    }

    public boolean intersect(Ray ray) {
	Vector3D toproj = new Vector3D(ray.origin.x - a.x,
				       ray.origin.y - a.y,
				       ray.origin.z - a.z);
	float orthlen = toproj.dot(normal);
	
	float testnum = ray.direction.dot(normal);
	//There is a more efficient way to determine whether two floats
	//have the same sign?
	if (((orthlen > 0) && (testnum > 0)) ||
	    ((orthlen < 0) && (testnum < 0)))
	    return false;

	//Cool vector calculation....
	float t = (float)Math.abs(orthlen / normal.dot(ray.direction));

        if (t > ray.t) 
            return false;

	//find point at t distance out on ray, see if it is inside the
	//triangle's "frustrum" by doing some funky cross and dot
	//products.
	Vector3D abplane = ab.cross(a.x-ray.origin.x,
				    a.y-ray.origin.y,
				    a.z-ray.origin.z);
	Vector3D bcplane = bc.cross(b.x-ray.origin.x,
				    b.y-ray.origin.y,
				    b.z-ray.origin.z);
	Vector3D caplane = ca.cross(c.x-ray.origin.x,
				    c.y-ray.origin.y,
				    c.z-ray.origin.z);
	if (orthlen < 0) {
	    abplane.x = -abplane.x;
	    abplane.y = -abplane.y;
	    abplane.z = -abplane.z;

	    bcplane.x = -bcplane.x;
	    bcplane.y = -bcplane.y;
	    bcplane.z = -bcplane.z;

	    caplane.x = -caplane.x;
	    caplane.y = -caplane.y;
	    caplane.z = -caplane.z;
	}

	Vector3D tpoint = new Vector3D(ray.origin);
	tpoint.x += t*ray.direction.x;
	tpoint.y += t*ray.direction.y;
	tpoint.z += t*ray.direction.z;

	Vector3D a2tp = new Vector3D(tpoint.x-a.x,
				     tpoint.y-a.y,
				     tpoint.z-a.z);
	Vector3D b2tp = new Vector3D(tpoint.x-b.x,
				     tpoint.y-b.y,
				     tpoint.z-b.z);
	Vector3D c2tp = new Vector3D(tpoint.x-c.x,
				     tpoint.y-c.y,
				     tpoint.z-c.z);

  	if ((abplane.dot(a2tp) <= 0) &&
  	    (bcplane.dot(b2tp) <= 0) &&
  	    (caplane.dot(c2tp) <= 0)) {
	    //if the test passes, do this
	    ray.t = t;
	    ray.object = this;
	    return true;
	}
	return false;
    }

    public Color Shade(Ray ray, Vector lights, Vector objects, Color bgnd) {
        // An object shader doesn't really do too much other than
        // supply a few critical bits of geometric information
        // for a surface shader. It must must compute:
        //
        //   1. the point of intersection (p)
        //   2. a unit-length surface normal (n)
        //   3. a unit-length vector towards the ray's origin (v)
        //

        Vector3D p = new Vector3D(ray.origin.x + ray.t*ray.direction.x,
				  ray.origin.y + ray.t*ray.direction.y,
				  ray.origin.z + ray.t*ray.direction.z);
        Vector3D v = new Vector3D(-ray.direction.x,
				  -ray.direction.y,
				  -ray.direction.z);

        // The illumination model is applied
        // by the surface's Shade() method
        return surface.Shade(p, normal, v, lights, objects, bgnd);
    }

    public String toString() {
        return ("triangle "+a+" "+b+" "+c);
    }
}


//    The following Applet demonstrates a simple ray tracer with a
//    mouse-based painting interface for the impatient and Mac owners
public class RayTrace extends Applet implements Runnable {
    final static int CHUNKSIZE = 100;
    Image screen;
    Graphics gc;
    Vector objectList;
    Vector lightList;
    Surface currentSurface;

    Vector3D eye, lookat, up;
    Vector3D Du, Dv, Vp;
    float fov;

    Color background;

    int width, height;

    public void init( ) {
        // initialize the off-screen rendering buffer
        width = size().width;
        height = size().height;
        screen = createImage(width, height);
        gc = screen.getGraphics();
        gc.setColor(getBackground());
        gc.fillRect(0, 0, width, height);

        fov = 30;               // default horizonal field of view

        // Initialize various lists
        objectList = new Vector(CHUNKSIZE, CHUNKSIZE);
        lightList = new Vector(CHUNKSIZE, CHUNKSIZE);
        currentSurface = new Surface(0.8f, 0.2f, 0.9f,
				     0.2f, 0.4f, 0.4f,
				     10.0f, 0f, 0f, 1f);

        // Parse the scene file
        String filename = getParameter("datafile");
        showStatus("Parsing " + filename);
        InputStream is = null;
        try {
            is = new URL(getDocumentBase(), filename).openStream();
            ReadInput(is);
            is.close();
        } catch (IOException e) {
            showStatus("Error reading "+filename+
		       ": "+e.getMessage());
            System.err.println("Error reading "+filename+
			       ": "+e.getMessage());
            System.exit(-1);
        }

        // Initialize more defaults if they weren't specified
        if (eye == null) eye = new Vector3D(0, 0, 10);
        if (lookat == null) lookat = new Vector3D(0, 0, 0);
        if (up  == null) up = new Vector3D(0, 1, 0);
        if (background == null) background = new Color(0,0,0);

        // Compute viewing matrix that maps a
        // screen coordinate to a ray direction
        Vector3D look = new Vector3D(lookat.x - eye.x,
				     lookat.y - eye.y,
				     lookat.z - eye.z);
        Du = Vector3D.normalize(look.cross(up));
        Dv = Vector3D.normalize(look.cross(Du));
        float fl = (float)(width / (2*Math.tan((0.5*fov)*Math.PI/180)));
        Vp = Vector3D.normalize(look);
        Vp.x = Vp.x*fl - 0.5f*(width*Du.x + height*Dv.x);
        Vp.y = Vp.y*fl - 0.5f*(width*Du.y + height*Dv.y);
        Vp.z = Vp.z*fl - 0.5f*(width*Du.z + height*Dv.z);
    }


    double getNumber(StreamTokenizer st) throws IOException {
        if (st.nextToken() != StreamTokenizer.TT_NUMBER) {
            System.err.println("ERROR: number expected in line "+st.lineno());
            throw new IOException(st.toString());
        }
        return st.nval;
    }

    void ReadInput(InputStream is) throws IOException {
	StreamTokenizer st = new StreamTokenizer(is);
    	st.commentChar('#');
    scan: while (true) {
	switch (st.nextToken()) {
	default:
	    break scan;
	case StreamTokenizer.TT_WORD:
	    if (st.sval.equals("sphere")) {
		Vector3D v = new Vector3D((float) getNumber(st),
					  (float) getNumber(st),
					  (float) getNumber(st));
		float r = (float) getNumber(st);
		objectList.addElement(new Sphere(currentSurface,
						 v, r));
	    } else if (st.sval.equals("triangle")) {
		Vector3D a = new Vector3D((float) getNumber(st),
					  (float) getNumber(st),
					  (float) getNumber(st));
		Vector3D b = new Vector3D((float) getNumber(st),
					  (float) getNumber(st),
					  (float) getNumber(st));
		Vector3D c = new Vector3D((float) getNumber(st),
					  (float) getNumber(st),
					  (float) getNumber(st));
		objectList.addElement(new Triangle(currentSurface,
						   a, b, c));
	    } else if (st.sval.equals("eye")) {
		eye = new Vector3D((float) getNumber(st),
				   (float) getNumber(st),
				   (float) getNumber(st));
	    } else if (st.sval.equals("lookat")) {
		lookat = new Vector3D((float) getNumber(st),
				      (float) getNumber(st),
				      (float) getNumber(st));
	    } else if (st.sval.equals("up")) {
		up = new Vector3D((float) getNumber(st),
				  (float) getNumber(st),
				  (float) getNumber(st));
	    } else if (st.sval.equals("fov")) {
		fov = (float) getNumber(st);
	    } else if (st.sval.equals("background")) {
		background =
		    new Color((float) getNumber(st),
			      (float) getNumber(st),
			      (float) getNumber(st));
	    } else if (st.sval.equals("light")) {
		float r = (float) getNumber(st);
		float g = (float) getNumber(st);
		float b = (float) getNumber(st);
		if (st.nextToken() !=
		    StreamTokenizer.TT_WORD) {
		    throw new IOException(st.toString());
		}
		if (st.sval.equals("ambient")) {
		    lightList.addElement(new Light(Light.AMBIENT,
						   null, r, g, b));
		} else if (st.sval.equals("directional")) {
		    Vector3D v =new Vector3D((float)getNumber(st),
					     (float)getNumber(st),
					     (float)getNumber(st));
		    lightList.addElement(new Light(Light.DIRECTIONAL,
						   v, r, g, b));
		} else if (st.sval.equals("point")) {
		    Vector3D v = new Vector3D((float) getNumber(st),
					      (float) getNumber(st),
					      (float) getNumber(st));
		    lightList.addElement(new Light(Light.POINT, v, r, g, b));
		} else {
		    System.err.println("ERROR: in line "+st.lineno()+
				       " at "+st.sval);
		    throw new IOException(st.toString());
		}
	    } else
		if (st.sval.equals("surface")) {
		    float r = (float) getNumber(st);
		    float g = (float) getNumber(st);
		    float b = (float) getNumber(st);
		    float ka = (float) getNumber(st);
		    float kd = (float) getNumber(st);
		    float ks = (float) getNumber(st);
		    float ns = (float) getNumber(st);
		    float kr = (float) getNumber(st);
		    float kt = (float) getNumber(st);
		    float index = (float) getNumber(st);
		    currentSurface = new Surface(r, g, b,
						 ka, kd, ks,
						 ns, kr, kt, index);
		}
	    break;
	}
    }
        is.close();
	if (st.ttype != StreamTokenizer.TT_EOF)
	    throw new IOException(st.toString());
    }
    
    boolean finished = false;
    
    public void paint(Graphics g) {
        if (finished)
            g.drawImage(screen, 0, 0, this);
	//g.setColor(Color.green);
	//g.drawRect(2,2,195,195);
    }

    // this override avoids the unnecessary clear on each paint()
    public void update(Graphics g) {
        paint(g);
    }


    Thread raytracer;

    public void start() {
        if (raytracer == null) {
            raytracer = new Thread(this);
            raytracer.start();
        } else {
            raytracer.resume();
        }
    }

    public void stop() {
        if (raytracer != null) {
            raytracer.suspend();
        }
    }

    private void renderPixel(int i, int j) {
        Vector3D dir = new Vector3D(
				    i*Du.x + j*Dv.x + Vp.x,
				    i*Du.y + j*Dv.y + Vp.y,
				    i*Du.z + j*Dv.z + Vp.z);
        Ray ray = new Ray(eye, dir);
        if (ray.trace(objectList)) {
            gc.setColor(ray.Shade(lightList, objectList, background));
        } else {
            gc.setColor(background);
        }
        gc.drawLine(i, j, i, j);        // oh well, it works.
    }

    public void run() {
        Graphics g = getGraphics();
        long time = System.currentTimeMillis();
        for (int j = 0; j < height; j++) {
            showStatus("Scanline "+j);
            for (int i = 0; i < width; i++) {
                renderPixel(i, j);
            }
            g.drawImage(screen, 0, 0, this);        //doing this less often
	                                            //speeds things up a bit
        }
        g.drawImage(screen, 0, 0, this);
        time = System.currentTimeMillis() - time;
        showStatus("Rendered in "+(time/60000)+":"+((time%60000)*0.001));
        finished = true;
    }


//      public boolean mouseDown(Event e, int x, int y) {
//          renderPixel(x, y);
//          repaint();
//          return true;
//      }

//      public boolean mouseDrag(Event e, int x, int y) {
//          renderPixel(x, y);
//          repaint();
//          return true;
//      }

//      public boolean mouseUp(Event e, int x, int y) {
//          renderPixel(x, y);
//          repaint();
//          return true;
//      }
}