/*
 * ビジュアル情報処理論
 *    3(1) ３次Bezier曲面を作成し,４角形に分割した後隠面消去をする。
 *  Programmed by Yoshizumi TANAKA. 1998/8
 *
 * *Button*
 *       Division … 分割数を２倍にします。
 *     Initialize … 初期状態（2＊2分割）に戻します。
 *
 * *Mouse*
 *  (1) 空白をつかんでドラッグすると回転します。
 *  (2) ドラッグをやめると隠面消去を始めます。
 */


import java.applet.*;
import java.awt.*;

public class HiddenSurfaceRemoval extends Applet {
    final int M = 8;

    Dimension appsize;
    int mouseX, mouseY;
    int status = 0;
    Button b1, b2;
    Obj obj[] = new Obj[M];
    Zbuffer zb;
    double Data[][][][] =
        {{{{0.000, 0.000, 1.000}, {0.552, 0.000, 1.000}, {1.000, 0.000, 0.552}, {1.000, 0.000, 0.000},},
	  {{0.000, 0.000, 1.000}, {0.552, 0.305, 1.000}, {1.000, 0.552, 0.552}, {1.000, 0.552, 0.000},},
	  {{0.000, 0.000, 1.000}, {0.305, 0.552, 1.000}, {0.552, 1.000, 0.552}, {0.552, 1.000, 0.000},},
	  {{0.000, 0.000, 1.000}, {0.000, 0.552, 1.000}, {0.000, 1.000, 0.552}, {0.000, 1.000, 0.000},},},
	 {{{-0.000, 0.000, 1.000}, {-0.000, 0.552, 1.000}, {-0.000, 1.000, 0.552}, {-0.000, 1.000, 0.000},},
	  {{-0.000, 0.000, 1.000}, {-0.305, 0.552, 1.000}, {-0.552, 1.000, 0.552}, {-0.552, 1.000, 0.000},},
	  {{-0.000, 0.000, 1.000}, {-0.552, 0.305, 1.000}, {-1.000, 0.552, 0.552}, {-1.000, 0.552, 0.000},},
	  {{-0.000, 0.000, 1.000}, {-0.552, 0.000, 1.000}, {-1.000, 0.000, 0.552}, {-1.000, 0.000, 0.000},},},
	 {{{-0.000, -0.000, 1.000}, {-0.552, -0.000, 1.000}, {-1.000, -0.000, 0.552}, {-1.000, -0.000, 0.000},},
	  {{-0.000, -0.000, 1.000}, {-0.552, -0.305, 1.000}, {-1.000, -0.552, 0.552}, {-1.000, -0.552, 0.000},},
	  {{-0.000, -0.000, 1.000}, {-0.305, -0.552, 1.000}, {-0.552, -1.000, 0.552}, {-0.552, -1.000, 0.000},},
	  {{-0.000, -0.000, 1.000}, {-0.000, -0.552, 1.000}, {-0.000, -1.000, 0.552}, {-0.000, -1.000, 0.000},},},
	 {{{0.000, -0.000, 1.000}, {0.000, -0.552, 1.000}, {0.000, -1.000, 0.552}, {0.000, -1.000, 0.000},},
	  {{0.000, -0.000, 1.000}, {0.305, -0.552, 1.000}, {0.552, -1.000, 0.552}, {0.552, -1.000, 0.000},},
	  {{0.000, -0.000, 1.000}, {0.552, -0.305, 1.000}, {1.000, -0.552, 0.552}, {1.000, -0.552, 0.000},},
	  {{0.000, -0.000, 1.000}, {0.552, -0.000, 1.000}, {1.000, -0.000, 0.552}, {1.000, -0.000, 0.000},},},
	 {{{0.000, 0.000, -1.000}, {0.000, 0.552, -1.000}, {0.000, 1.000, -0.552}, {0.000, 1.000, -0.000},},
	  {{0.000, 0.000, -1.000}, {0.305, 0.552, -1.000}, {0.552, 1.000, -0.552}, {0.552, 1.000, -0.000},},
	  {{0.000, 0.000, -1.000}, {0.552, 0.305, -1.000}, {1.000, 0.552, -0.552}, {1.000, 0.552, -0.000},},
	  {{0.000, 0.000, -1.000}, {0.552, 0.000, -1.000}, {1.000, 0.000, -0.552}, {1.000, 0.000, -0.000},},},
	 {{{-0.000, 0.000, -1.000}, {-0.552, 0.000, -1.000}, {-1.000, 0.000, -0.552}, {-1.000, 0.000, -0.000},},
	  {{-0.000, 0.000, -1.000}, {-0.552, 0.305, -1.000}, {-1.000, 0.552, -0.552}, {-1.000, 0.552, -0.000},},
	  {{-0.000, 0.000, -1.000}, {-0.305, 0.552, -1.000}, {-0.552, 1.000, -0.552}, {-0.552, 1.000, -0.000},},
	  {{-0.000, 0.000, -1.000}, {-0.000, 0.552, -1.000}, {-0.000, 1.000, -0.552}, {-0.000, 1.000, -0.000},},},
	 {{{-0.000, -0.000, -1.000}, {-0.000, -0.552, -1.000}, {-0.000, -1.000, -0.552}, {-0.000, -1.000, -0.000},},
	  {{-0.000, -0.000, -1.000}, {-0.305, -0.552, -1.000}, {-0.552, -1.000, -0.552}, {-0.552, -1.000, -0.000},},
	  {{-0.000, -0.000, -1.000}, {-0.552, -0.305, -1.000}, {-1.000, -0.552, -0.552}, {-1.000, -0.552, -0.000},},
	  {{-0.000, -0.000, -1.000}, {-0.552, -0.000, -1.000}, {-1.000, -0.000, -0.552}, {-1.000, -0.000, -0.000},},},
	 {{{0.000, -0.000, -1.000}, {0.552, -0.000, -1.000}, {1.000, -0.000, -0.552}, {1.000, -0.000, -0.000},},
	  {{0.000, -0.000, -1.000}, {0.552, -0.305, -1.000}, {1.000, -0.552, -0.552}, {1.000, -0.552, -0.000},},
	  {{0.000, -0.000, -1.000}, {0.305, -0.552, -1.000}, {0.552, -1.000, -0.552}, {0.552, -1.000, -0.000},},
	  {{0.000, -0.000, -1.000}, {0.000, -0.552, -1.000}, {0.000, -1.000, -0.552}, {0.000, -1.000, -0.000},},},};

    public void init() {
	setBackground(Color.black);
	setForeground(Color.white);
	appsize = size();
	zb = new Zbuffer(appsize.width, appsize.height);
	
	add(b1 = new Button("Division"));
	add(b2 = new Button("Initialize"));

	for (int i = 0; i < M; i++) {
	    obj[i] = new Obj(Data[i]);
	    obj[i].Scale(100);
	    obj[i].setScreen(appsize.width/2, appsize.height/2);
	    obj[i].setViewPoint(500, 20, 30);
	    obj[i].setViewRefPoint(0, 0, 50);
	}
	resize(appsize);
    }
    public void paint(Graphics g) {
	if (status == 0) {
	    for (int i = 0; i < M; i++) {
		obj[i].calcRadian();
		obj[i].Drawing(g);
	    }
	} else {
	    zb.init();
	    for (int i = 0; i < M; i++) {
		obj[i].calcRadian();
		obj[i].Shading(zb);
	    }
	    zb.paint(g);
	    showStatus("theta="+obj[0].theta+", phi="+obj[0].phi);
	}
    }
    public boolean action(Event e, Object o) {
	if (e.target == b1) { // division
	    status = 0;
	    for (int i = 0; i < M; i++) {
		obj[i].division();
	    }
	    repaint();
	    return true;
	} else if (e.target == b2) { // initialize
	    status = 0;
	    for (int i = 0; i < M; i++) {
		obj[i].init(1);
		obj[i].division();
	    }
	    repaint();
	    return true;
	} else {
	    return false;
	}
    }
    public boolean mouseDown(Event e, int x, int y) {
	status = 0;
	mouseX = x;
	mouseY = y;
	return true;
    }
    public boolean mouseDrag(Event e, int x, int y) {
	for (int i = 0; i < M; i++) {
	    obj[i].theta -= x - mouseX;
	    obj[i].phi   += y - mouseY;
	}
	mouseX = x;
	mouseY = y;
	repaint();
	return true;
    }
    public boolean mouseUp(Event e, int x, int y) {
	status = 1;
	repaint();
	return true;
    }
} // end of class HiddenSurfaceRemoval

class Obj extends Canvas {
    final int n = 3;
    int N = 16;

    Point pos[][] = new Point[n+1][n+1];
    Point cel[][] = new Point[N+1][N+1];
    Point prj[][] = new Point[N+1][N+1];

    int x_sc_mid, y_sc_mid;
    int scale;
    double R, theta, phi;
    double ct, cp, st, sp;
    Point ViewRef = new Point();
    
    Obj(double in[][][]) {
	for (int i = 0; i <= n; i++)
	    for (int j = 0; j <= n; j++)
		pos[i][j] = new Point(in[i][j][0], in[i][j][1], in[i][j][2]);
	for (int i = 0; i <= N; i++) {
	    for (int j = 0; j <= N; j++) {
		cel[i][j] = new Point();
		prj[i][j] = new Point();
	    }
	}
       	init(1);
       	division();
    }
    public void init(int i) {
	init();
	N = i;
    }
    public void init() {
	for (int i = 0; i <= N; i++)
	    for (int j = 0; j <= N; j++)
		cel[i][j].init();
    }
    public void Scale(int s) {
	scale = s;
	for (int i = 0; i <= n; i++) {
	    for (int j = 0; j <= n; j++) {
		pos[i][j].x *= scale;
		pos[i][j].y *= scale;
		pos[i][j].z *= scale;
	    }
	}
    }
    public void setViewRefPoint(double vrx, double vry, double vrz){
	ViewRef.set(vrx, vry, vrz);
    }
    public void setViewPoint(double r, double th, double ph) {
	final double RAD = Math.PI / 180.0;
	R = r;
	theta = th;
	phi = ph;
    }
    public void calcRadian() {
	final double RAD = Math.PI / 180.0;
	double th = theta * RAD;
	double ph =   phi * RAD;
	st = Math.sin(th);
	ct = Math.cos(th);
	sp = Math.sin(ph);
	cp = Math.cos(ph);
    }
    public void setScreen(int x, int y) {
	x_sc_mid = x;
	y_sc_mid = y;
    }
    public void division() {
	if (N < 16) {
	    init();
	    N *= 2;
	    for (int u = 0; u <= N; u++)
		for (int v = 0; v <= N; v++)
		    Burnstain(u, v);
	} 
    }
    void Burnstain(int u, int v) {
	Point w[][] = new Point[n+1][n+1];

	for (int i = 0; i <= n; i++)
	    for (int j = 0; j <= n; j++)
		w[i][j] = new Point(pos[i][j]);
	
	for (int i = 0; i <= n; i++)
	    for (int k = 1; k <= n; k++)
		for (int j = 0; j <= n-k; j++) {
		    w[i][j].x += (w[i][j+1].x -w[i][j].x) * v / N;
		    w[i][j].y += (w[i][j+1].y -w[i][j].y) * v / N;
		    w[i][j].z += (w[i][j+1].z -w[i][j].z) * v / N;
		}
	
	for (int k = 1; k <=n; k++)
	    for (int i = 0; i <= n-k; i++) {
		w[i][0].x += (w[i+1][0].x - w[i][0].x) * u / N;
		w[i][0].y += (w[i+1][0].y - w[i][0].y) * u / N;
		w[i][0].z += (w[i+1][0].z - w[i][0].z) * u / N;
	    }

	cel[u][v].set(w[0][0].x, w[0][0].y, w[0][0].z);
    }
    Point trans(Point p) {
	Point q;
	double tmp, d_rate;
	
	q = new Point(p.x-ViewRef.x, p.y-ViewRef.y, p.z-ViewRef.z);
	
	tmp =   q.x * ct + q.y * st;
	q.x = - q.x * st + q.y * ct;
	q.y = - tmp * sp + q.z * cp;
	q.z =   tmp * cp + q.z * sp;
	
	d_rate = R / (R - q.z);
	q.x =   q.x * d_rate + x_sc_mid;
	q.y = - q.y * d_rate + y_sc_mid;
	q.z =   R - q.z;
	
	return q;
    }
    public void Drawing(Graphics g) {
	for(int i = 0; i <= N; i++)
	    for(int j = 0; j <= N; j++)
		prj[i][j] = trans(cel[i][j]);
	
	for(int j = 0; j <= N; j++) {
	    for(int i = 0; i < N; i++)
		Line(g, i, j, i+1, j);
	    if (j < N)
		for(int i = 0; i <= N; i++)
		    Line(g, i, j, i, j+1);
	}
    }
    void Line(Graphics g, int i, int j, int k, int h) {
	g.drawLine((int) prj[i][j].x, (int) prj[i][j].y,
		   (int) prj[k][h].x, (int) prj[k][h].y);
    }
    public void Shading(Zbuffer zb) {
	for (int i = 0; i < N; i++) {
	    for (int j = 0; j < N; j++) {
		Vertex v = new Vertex(4);
		v.addP(prj[i][j], prj[i][j+1], prj[i+1][j+1], prj[i+1][j]);
		v.setBright(cel[i][j], cel[i][j+1], cel[i+1][j+1], zb.light);
		ySortTable yst = new ySortTable(v);
		yst.Shading(zb);
	    }
	}
    }
} // end of class Obj

class Zbuffer {
    int x, y, x_min, x_max, y_min, y_max;
    Vector light;
    double depth[][];
    DotColor RGB[][];

    Zbuffer(int init_x, int init_y) {
	x_max = y_max = 0;
	x = x_min = init_x;
	y = y_min = init_y;
	light = new Vector(100, 100, 100);
	light.formalize();
	depth = new double[x][y];
	RGB = new DotColor[x][y];
	for (int i = 0; i < x; i++) {
	    for (int j = 0; j < y; j++) {
		depth[i][j] = 1.0e30;
		RGB[i][j] = new DotColor();
	    }
	}
    }
    void init() {
	x_min = x;
	y_min = y;
	x_max = 0;
	y_max = 0;
	for (int i = 0; i < x; i++) {
	    for (int j = 0; j < y; j++) {
		depth[i][j] = 1.0e30;
		RGB[i][j].set();
	    }
	}
    }
    public void paint(Graphics g) {
	for (int i = x_min; i < x_max; i++) {
	    for (int j = y_min; j < y_max; j++) {
		RGB[i][j].setColor(g);
		g.drawLine(i, j, i, j);
	    }
	}
    }
}

class Point {
    double x, y, z;
    Point() {}
    Point(double init_x, double init_y, double init_z) {
	set(init_x, init_y, init_z);
    }
    Point(Point p) {
	set(p.x, p.y, p.z);
    }
    void init() {
	set(0, 0, 0);
    }
    void set(double in_x, double in_y, double in_z) {
	x = in_x;
	y = in_y;
	z = in_z;
    }
} // end of class Point

class ySortTable {
    int y_min[], y_max[];
    double x_min[], z_min[], m_inv[], n_inv[];
    double bright;
    int n = 0;
    
    ySortTable(Vertex v) {
        x_min = new double[v.n];
        y_min = new int[v.n];
        y_max = new int[v.n];
	z_min = new double[v.n];
        m_inv = new double[v.n];
        n_inv = new double[v.n];
	bright = v.bright;
        
        for (int i = 0,j = 1; i < v.n; i++,j++) {
            if (j == v.n) j = 0;
            if (v.p[i].y == v.p[j].y) continue;
            if (v.p[i].y < v.p[j].y) {
                x_min[n] = v.p[i].x;
                y_min[n] = (int)v.p[i].y;
                y_max[n] = (int)v.p[j].y;
		z_min[n] = v.p[i].z;
            } else {
                x_min[n] = v.p[j].x;
                y_min[n] = (int)v.p[j].y;
                y_max[n] = (int)v.p[i].y;
		z_min[n] = v.p[j].z;
            }
            m_inv[n] = (v.p[i].x-v.p[j].x) / (v.p[i].y-v.p[j].y);
            n_inv[n] = (v.p[i].z-v.p[j].z) / (v.p[i].y-v.p[j].y);
            n++;
            }
        ySort();
    }
    void ySort() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (y_min[j] > y_min[j+1]) {
                    swap(j, j+1);
		}
	    }
	}
    }
    void swap(int i, int j) {
        int tmp1;
        double tmp2;
        
        tmp2 = x_min[i];
        x_min[i] = x_min[j];
        x_min[j] = tmp2;

	tmp1 = y_min[i];
        y_min[i] = y_min[j];
        y_min[j] = tmp1;
        
        tmp1 = y_max[i];
        y_max[i] = y_max[j];
        y_max[j] = tmp1;

        tmp2 = z_min[i];
        z_min[i] = z_min[j];
        z_min[j] = tmp2;
	
        tmp2 = m_inv[i];
        m_inv[i] = m_inv[j];
        m_inv[j] = tmp2;

        tmp2 = n_inv[i];
        n_inv[i] = n_inv[j];
        n_inv[j] = tmp2;
    }
    public void Shading(Zbuffer zb) {
	double  x[] = new double[n];
	double ix[] = new double[n];
	double  z[] = new double[n];
	double iz[] = new double[n];
	
	for (int i = 0; i < n; i++) {
	    x[i] = x_min[i];
	    z[i] = z_min[i];
	}
	    
	for(int line = y_min[0]; ; line++) {
	    int nx = 0;
	    for(int i = 0; i < n; i++)
		if (line >= y_min[i] && line < y_max[i]) {
		    xInsert(ix, x[i], iz, z[i], nx);
		    nx++;
		    x[i] += m_inv[i];
		    z[i] += n_inv[i];
		}
	    if (nx == 0) break;
	    for(int i = 0; i < nx; i += 2) {
		int left = (int)ix[i];
		int right = (int)ix[i+1];
		double this_z = iz[i];
		double l_inv;
		if (left == right) {
		    l_inv = 0;
		} else {
		    l_inv = (iz[i+1]-iz[i])/(ix[i+1]-ix[i]);
		}
		for (int j = left; j <= right; j++) {
		    if (this_z < zb.depth[j][line]) {
			zb.depth[j][line] = this_z;
			zb.RGB[j][line].set(255*bright, 0, 0);
		    }
		    if (zb.x_min > left) zb.x_min = left;
		    if (zb.x_max < right) zb.x_max = right;
		    if (left == right) break;
		    this_z += l_inv;
		}
	    }
	    if (zb.y_min > y_min[0]) zb.y_min = y_min[0];
	    if (zb.y_max < line) zb.y_max = line;
	}
    }
    void xInsert(double x[], double x_n, double z[], double z_n, int nx) {
        int i;
        
        for(i = 0; i < nx; i++) {
            if (x[i] > x_n) {
                for (int j = nx-1; j >= i; j--) {
                    x[j+1] = x[j];
		    z[j+1] = z[j];
	        }
                break;
            }
        }
        x[i] = x_n;
	z[i] = z_n;
    }
}// end of class ySortTable


class Vector {
    double x, y, z;
    Vector() {}
    Vector(double init_x, double init_y, double init_z) {
	x = init_x;
	y = init_y;
	z = init_z;
    }
    Vector sa(Point A, Point B) {
	Vector C = new Vector();
	C.x = A.x - B.x;
	C.y = A.y - B.y;
	C.z = A.z - B.z;
	return C;
    }
    double naiseki(Vector A, Vector B) {
	return A.x*B.x + A.y*B.y + A.z*B.z;
    }
    void gaiseki(Vector A, Vector B) {
	x = A.y*B.z - A.z*B.y;
	y = A.z*B.x - A.x*B.z;
	z = A.x*B.y - A.y*B.x;
    }
    void formalize() {
	double n = 1 / Math.sqrt(x*x + y*y + z*z);
	x *= n;
	y *= n;
	z *= n;
    }
} // end of class Vector

class Vertex {
    int n;
    double bright;
    Point p[];
    Vector A = new Vector();
    
    Vertex(int init_n) {
	n = init_n;
	p = new Point[n];
    }
    void addP(Point p0, Point p1, Point p2, Point p3) {
	p[0] = p0;
	p[1] = p1;
	p[2] = p2;
	p[3] = p3;
    }
    void setBright(Point p0, Point p1, Point p2, Vector light) {
	A.gaiseki(A.sa(p1, p0), A.sa(p2, p0));
	A.formalize();
	bright = A.naiseki(A, light);
    }
} // end of class Vertex

class DotColor {
    int r, g, b;
    DotColor() {
	set();
    }
    void set() {
	r = g = b = 0;
    }
    void set(double init_r, double init_g, double init_b) {
	r = (int)init_r;
	g = (int)init_g;
	b = (int)init_b;
    }
    void setColor(Graphics G) {
	int ir, ig, ib;
	ir = standardize_one(r);
	ig = standardize_one(g);
	ib = standardize_one(b);
	G.setColor(new Color(ir, ig, ib));
    }
    int standardize_one(double col) {
        if (col >= 255) return 255;
        if (col <= 0) return 0;
        return (int)col;
    }
}